notes

Personal notes
git clone git://git.laack.co/notes.git
Log | Files | Refs

CraftingInterpreters.md (4685B)


      1 # Crafting Interpreters
      2 
      3 **Source:** [craftinginterpreters.com](https://craftinginterpreters.com)
      4 
      5 ## Links
      6 
      7 - [Tree Walk Interpreter](TreeWalkInterpreter.md)
      8 
      9 ## Concepts
     10 
     11 - Lox
     12 - Lexing
     13     - scanning
     14     - lexical analysis
     15 - Lexer
     16     - A lexer takes a stream of characters and groups them together into tokens
     17 - Token
     18     - Chunk of characters with syntactic meaning in the language
     19 - Parsing
     20     - We go from syntax to grammar by generating an AST 
     21 - Static Analysis
     22     - The above two steps are fairly consistent across languages, this one is not
     23     - Some common static analysis steps
     24         - binding / resolution
     25             - find identifier definitions and associate them
     26             - this has to consider scopes, and in statically typed languages we'd perform type checking here
     27 - all of the above are considered the "frontend". below is the "middle end" (an addition at some point as compilers got more complex, making frontend and backend unsatisfactory).
     28     - The middle end is focused on intermediate representations, not tied to the source or destination forms
     29 - optimization
     30 	- constant folding
     31 		- at compile time compute computable values
     32 			- u32Max = (2**32) - 1
     33 				- -> u32Max = 4294967295
     34     			- ctr = (7 - 12) * (20 + 29)
     35     				- -> ctr = -245
     36 - backend
     37     - code generation
     38         - this is the final step of compilation, where we generate the target code
     39         - asm
     40             - timeless
     41         - bytecode
     42             - named as so due to these instructions frequently being one byte in size
     43             - options
     44                 - vm
     45                   - run the code on a vm that supports the bytecode as it's isa
     46                   - specifically these are process or language virtual machines, not to be confused with system virtual machines
     47                 - small compiler to go directly to machine
     48 
     49 - runtime
     50 	- in the context of compiled languages, like go, the runtime would be stuff like the gc which is baked into the executable
     51 	- for interpreted languages, this is often something like the python interpreter, which manages some program state
     52 	- broadly, the runtime is the set of things provided by the language that help out during execution time
     53 - single pass compilers
     54     - category of compiler that doesn't generate an ast, instead parsing and code gening in one pass
     55     - this is actually something that dictated design decisions for c, causing it to have things like only allowing references to functions defined above the current function
     56 - tree walk interpreter
     57 	- simple interpreter approach that generates an ast, and than walks it while executing the program
     58 - transpiler
     59 	- disagree with the word because it is just a compiler with a specific target, but this is basically the general idea of using IRs as an easy exit without doing the hard work in the backend
     60 - jit
     61     - this is what the jvm is, clr (common language runtime from MS), and js (in browsers) use
     62     - quite complex, considers hotspots during execution to determine if further optimizations are warranted to generated code
     63 - expression vs statement
     64     - an expression evaluates to a value while a statement has an effect
     65 - context-free grammars
     66     - we used a regular language for our lexical grammar, but we need something more powerful for parsing
     67     - this more powerful form is context-free grammars, which allow arbitrarily deep nesting, unlike regular languages
     68     - each production in a context free grammar is a head, the starting point, and a body, describing what it generates
     69         - the body is a list of symbols, some of which may be terminals and some of which may be non-terminals
     70             - non-terminals is a reference to another rule in the grammar. if this is a reference to the current rule, we notice we have recursion which can't exist in regular languages.
     71         - example:
     72             - breakfast→ protein "with" breakfast "on the side" ;
     73             - breakfast→ protein ;
     74             - breakfast→ bread ;
     75             - protein→ crispiness "crispy" "bacon" ;
     76             - protein→ "sausage" ;
     77             - protein→ cooked "eggs" ;
     78             - crispiness → "really" ;
     79             - crispiness → "really" crispiness ;
     80             - cooked→ "scrambled" ;
     81             - cooked→ "poached" ;
     82             - cooked→ "fried" ;
     83             - bread→ "toast" ;
     84             - bread→ "biscuits" ;
     85             - bread→ "English muffin" ;
     86         - each line above is a production, and derivations are evaluations of a given production
     87             - during derivation, we may need to evaluate further productions, as is the case for breakfast which requires the derivation of a protein or bread.