scope

lexical
every inner level can access its outer levels - widely accepted to be the correct scoping decision.

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

from "history of t"

http://www.paulgraham.com/thist.html some of these notes are prompted by this

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

aaaa

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. 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:

• go over programs forwards and backwards
• unions and intersections

– union, intersection = always, might_possibly keywords to google

• available expressiosn

– forwards intersection

• very busy expressions

– backwards intersection

• reaching definitions

– forwards union

• live variables

– backwards union

specific optimizations

dead code elimination
removes code not impacting program results. this shrinks program size and avoids irrelevant operations. this involves code that will never be executed and code that only effects dead variables – those that are nedver read from again. we can use this as opposed to optional code inclusion via a preprocessor that would perform the same task. much of the dead code this finds is created by other transformations: for example, strength reduction – we must ensure that the order of analyses is performed in the right way. historically, this is performed using information derived from data-flow analysis with an algorithm based on single assignment form.

dynamic dead code elimination
some code sections represent dead or unreachable code only under specific conditions. we can accumulate conditions at runtime to determine what processes or loadings to eliminate while we evaluate an expression.

strength reduction
most of a program's execution time is spent in a small section of code (the 'hot spot') and that code is inside a loop over and over. the compiler looks to recognize things inside the loop. this records loop invariants: values that do not change within the body of the loop, and induction variables: values iterated each time through the loop. induction variables change by known amounts. we can replace multiplication with successive weaker additions often which is an optimization. we can hoist invariants outside of the loop, such as registers. these are some good examples of strength reduction that can be used: https://en.wikipedia.org/wiki/Strength_reduction pull

dataflow analysis
gathering information about values calculated at points during a computer program. set up dataflow equations for each node of the cfg, then solve them by repeatedly calculating the output from the input, locally at each node until a fixpoint is reached – kildall's method. https://en.wikipedia.org/wiki/Data-flow_analysis pull

basic blocks :: - ? dynamic software updating :: - ? hot patching :: - ? maurice wilkes – helped build the electronic delay storage automatic calculator – cool guy Loop-invariant code motion - Wikipedia Improve Software Debugging with Binary Analysis | some guy’s blog Program analysis resources

Polymorphism

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