Static Analysis

GO HOMEEDIT some of these notes are prompted by this scope


every inner level can access its outer levels - widely accepted to be the correct scoping de cision


functions access the latest definition of a local variable - not deducible at compile time l evel. This means that for some f wth the body x = 3, call g, g has x = 3 in scope

intro functional languages: rabbit (first scheme compiler), sussman/steele lambda papers, FP languages su ch as Hope, Miranda and Scheme. franz lisp? Bliss language - c-level language from CMU? pdp-10 hack: remove cons cell from freelist, updated freelist, and branching if the freelist was exhauste d to the gc in a single instruction! premature optimization is bad, no matter what. do not take shortcuts to simplify what is an already well- designed system! One key tip-off phrase is always something of the form, "We'll throw out all the old cru ft, start over fresh, and just Do Things Right." fixnum :: a 'fixed number', or native machine word building a compiler 'self-hosted', or incrementally -- hosting one in another. how is it done? maclisp on -10 has mark and sweep run on the register set - "bibop" scheme with all objects boxed, and se gregated by type into pages of memory stop and copy garbage collector: Cheney garbage collection algorithm - does bfs of heap to find everythin g. t used Clark algorithm: dfs traversal, uses heap to provide a search stack can implement mark and sweep with same costs as stop and copy! norman ramsey 'good' schemes use a range of implementations for lambas. depending on what we know about them at compile time. some turn into nothing, some are control flow, some are stack frames, some cause heap allocation. must understand how compiler handles everything, and scheme is built on this lambda structure lexemes :: construction of lexical meaning underlying words related through inflection. the lemma is one forn of the lexeme standard procedure :: standardized code for a procedure? TODO compiler implementation as a tree of objects that could link back to their parents? whoah cool stuff -- interesting? these things are relatively communicative but i am not sure what they mean DFA :: data-flow analysis - ? loop-invariant hoisting :: - ? global register allocation :: - ? global common subexpression elimination :: - ? find two things that are alpha-equivalent then make them a single expression copy propagation :: - ? induction-variable elimination :: - ? learn how to do more things with computer graphics! this area sounds super interesting but i do not know much about it. paper for orbit -- optimizing compiler for scheme -- forgot this history thing -- useful compiler jargon -- TODO compose my own dictionary! assemblers :: norman adams. graph structure? linear text scheme? serializing graph to minimize the span f rom jmps to the things they jump to. push and pop vs push and a generational garbage collector assemblers :: norman adams. graph structure? linear text scheme? serializing graph to minimize the span f rom jmps to the things they jump to. push and pop vs push and a generational garbage collector beta-substitution :: - ? four classic analyses:

-- union, intersection = always, mightpossibly keywords to google

-- forwards intersection

-- backwards intersection

-- forwards union

-- backwards union quickcheck properties for checking haskell code! -- why is algol important? do research TODO type inf ocaml -- neat cool person recall this -- epigrams on programming specific optimizations:

basic blocks :: - ?

dynamic software updating :: - ? hot patching :: - ?

luca cardelli maurice wilkes -- helped build the electronic delay storage automatic calculator -- cool guy

parametric polymorphism :: allows a function or data type to be written generically so that it can handle values identically without depending on their type these are generic functions, generic datatypes respectively type of 'append' is generic but is parameratized with types rank 1 polymorphism :: type variables cannot be instantiated with polymorphic types rank k polymorphism :: rank k polymorphism enforces that the quantifier may not appear ot the left of k or more arrows type inference is decidable for rank 2, but not for rank 3 or above rank-n polymorphism :: polymorphism in which quantifiers can appear to the left of arbitrarily many arrows

NEXT A Mathematical Theory of Communication (1948) [pdf]

A Mathematical Theory of Communication (1948) [pdf] - :: binary analysis, which is similar I suppose...

list of program analysis resources