Static Analysis
http://www.paulgraham.com/thist.html some of these notes are prompted by this scope
- lexical
every inner level can access its outer levels - widely accepted to be the correct scoping de cision
- dynamic
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 https://github.com/julian-zucker?tab=repositories cool stuff https://github.com/julian-zucker/arbiter -- 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 https://dl.acm.org/doi/10.1145/12276.13333 http://mumble.net/~jar/tproject/ -- forgot this history thing http://www.dourish.com/goodies/jargon.html -- 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:
go over programs forwards and backwards
unions and intersections
-- union, intersection = always, mightpossibly keywords to google
available expressiosn
-- forwards intersection
very busy expressions
-- backwards intersection
reaching definitions
-- forwards union
live variables
-- backwards union quickcheck properties for checking haskell code! http://ken.friislarsen.net/blog/ https://en.wikipedia.org/wiki/ALGOL -- why is algol important? do research TODO http://www.aosabook.org/en/llvm.html type inf ocaml http://mumble.net/~jar/ -- neat https://en.wikipedia.org/wiki/Daniel_S._Weld cool person http://www.ccs.neu.edu/home/shivers/scribblings.html recall this https://en.wikipedia.org/wiki/Alan_Perlis -- epigrams on programming http://www.aosabook.org/en/llvm.html 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 va riables :: 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
- 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 https://en.wikipedia.org/wiki/Static_single_assignment_form https://en.wikipedia.org/wiki/George_Hotz https://en.wikipedia.org/wiki/Just-in-time_compilation
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] - https://news.ycombinator.com/item?id=23035107
https://hal.inria.fr/hal-01093327 https://hal.inria.fr/tel-01102401 https://sed-bso.gitlabpages.inria.fr/sonarqube/ https://hal.inria.fr/hal-01588422 https://en.wikipedia.org/wiki/Loop-invariant_code_motion https://h313.info/blog/cpp/security/binary-analysis/2020/11/06/improve-software-debugging-with-binary-analysis.html :: binary analysis, which is similar I suppose...