Programming Language Principles

2.2.1 ε

2.2.2 Atom:

2.2.3 Concatenation

2.2.4 Alternative: |

2.2.5 Kleene Closure: *

2.2.6 Derived notations:

1. positive closure: +
   
   • a+ = aa*
2. Not:
   
   • not(a) = Σ - a we can derive this if the alphabets are finite, we can enumerate all the alphabets

2.2.7 Restrictions

2.3.1 Implementation

1. In Java
   
   1. Token type
      

      class Token {
          Kind kind;
          int pos;     \\ -----|
          int lineNum; \\ -----useful for debugging
      }
      

   2. Use each state as case in switch (Eg: START, AFTER_START)
      
   3. Enums:
      
      • they have types
      • they are ordered
      • can be used in switch case
   4. Handling comments
      
      • track pos and line number
   5. Reserved words v/s keyword
      
      • reserved word: cannot be used as identifier
      • keyword: cannot be used as identifier because they have special meaning in laguage
      • Eg: goto in java, cannot be used as identifier but is not a keyword (does nothing)
2. Handling reserved word
   
   • build identifier first then keyword
   • list all the reserved words, then check if the identifier is present in the list

2.3.2 Whitespace

2.3.3 Automatic DFA generation

3.2.1 BNF

3.2.2 EBNF

3.2.3 Example:

expr → factor | expr op factor
factor → ident | numlit | (expr)

3.6.1 LL: Left to right, Left-most derivation

1. LL Implementation
   
   • start with root
   • Peek to check next token in the input string

3.6.2 LR: Left to right, Right-most derivation

3.8.1 LL(K): look ahead k tokens

3.8.2 LL(*): can look ahead as much tokens as needed

3.8.3 First Set

1. Including ε in First
   

   S → Ay
   A → x | ε
   First(S) = {x, y}
   

3.8.4 Follow Set

S → A B
A → x | y
B → z | w

Follow(A) = {z, w} = First(B)
Follow(B) = {}

Follow(x) = Follow(A)

3.8.5 Predict Set

3.8.6 LL(1) Rule

3.8.7 Recursive decent parsing working

3.8.8 Left recrusive grammar

1. Left recursive removal
   

   A → A σ | β
   can be replaced with
   A → β B
   B → σ B | ε
   
   how to: expand the original grammar to get feel of the language (Strings generated)
   A → A σ | β
   will give: β σ, β σ σ, β σ σ σ...
   note that strings start with β and have several trailing σ
   so rewrite grammar to represent this using non left recursive grammar:
   A → β | B
   B → σ B | ε
   

3.8.9 associativity and precedence

1. Associativity
   
   • operator group left to right or right to left.
   • Eg: 10 - 4 - 5 means (10 - 4) - 5 rather than 10 - (4 - 5)
2. Precedence
   
   • some operator group tightly than others
   • Eg: 10 - 4 × 3 = 10 - 12 rather than 6 × 3
3. Inbuilt associativity and precedence
   

   • we can make grammar in such a way that associativity and precedence is handled automatically.

     expr → term | expr add_op term
     term → factor | term mult_op factor
     factor → id | number | (expr)
     add_op → + | -
     mult_op → × | ÷
     

   • in above example, note how we have introduced term to make sure mult_op is grouped more tightly than add_op
   • since operators are left associative, we have expr (which has potential to produce more add_op) always to left of add_op

3.9.1 Grammar Simplication

3.9.2 Handling errors

1. Halt
   
   • Halt and print error messages
   • Easy to implement
   • inconvinient for programmar
2. Recovery
   
   1. panic mode
      
      • define safe symbols that delimit "clean" point
      • delete tokens until safe symbol
   2. phrase recovery
      
      • different set of safe symbols in different context.
   3. context specific
      
   4. exception based
      

3.10.1 Backtracking Algorithms

3.10.2 Predictive Algorithms

1. LL(1)
   
   • Left to right scan of token
   • Leftmost derivation
   • (1): 1 token of lookahead
   1. Parse Table
      

      1. E → int
      2. E → (E Op E)
      3. Op → +
      4. Op → *
      

      	int	(	)	+	*
      E	1	2
      Op				3	4

      1. Example:
         

         	E $	(int + (int + int)) $
         2	(E Op E) $	(int + (int + int)) $
         	E Op E) $	int + (int + int)) $
         1	int Op E) $	int + (int + int)) $
         	Op E) $	+ (int + int)) $
         3	+ E) $	+ (int + int)) $
         	E) $	(int + int)) $
         2	(E Op E)) $	(int + int)) $
         	E Op E)) $	int + int)) $
         1	int Op E)) $	int + int)) $
         	Op E)) $	+ int)) $
         3	+ E)) $	+ int)) $
         	E)) $	int)) $
         1	int)) $	int)) $
         	$	$

   2. Construction of Parse table
      
      1. Intuition
         

         The next character should uniquely identify a production, so we should pick a production that ultimately starts with that character

      2. First Sets
         

         The First(A) is the set of terminals that can be at the start of a string produced by A.

         • we can use First set to make parsing table.
         • if rules contain ε productions, then we have to look through the non terminals and see First of the next non terminal
           • For A → α where α has ε in First set then: First(A) = First(A) ∪ {ε}
           • For A → α t ω, where α First set contains ε and t is terminal: First(A) = First(A) ∪ {t}
           • For A → α B ω, where B is non terminal and α has ε in First set: First(A) = First(A) ∪ First(B)
      3. Follow Set
         

         Follow(A) is set of all terminal symbols that can immediately follow a
         subsequence derived from A in a sequence derived from start symbol, S.
         

         Num → Sign Digits
         Sign → + | - | ε
         
         Sign has ε production, so First(Sign) will contain First(Digits)
         

         • The follow set represents the set of terminals that might come after a given non terminal.
           • If B → α A ω then: Follow(A) = Follow(A) ∪ First*(ω)
           • If B → α A ω and ε ⊂ First*(ω) then: Follow(A) = Follow(A) ∪ Follow(B)
           • In other words, follow of a symbol is that which can come after that, so that if that symbol goes to ε then the follow can appear. If the next symbol → ε then add follow of parent
      4. Final Construction
         
         • For each rule A → ω, for each terminal t ⊂ First*(ω) set T[A, t] = ω (at A if you see t, use production to goto ω)
         • For each rule A → ω, if ε ⊂ First*(ω): set T[A, t] = ω for each t ⊂ Follow(A) (at A, if A can ε and t can be produced by follow then take ε path and let A get lost)
   3. Limitation of LL(1)
      
      • Left recursion

        • can be eliminated

          A → A ω | α
          rewrite as
          A → α B
          B → ω B | ε
          
          Explanation:
          A can produce α ω, α ω ω ..., starts with α
          second rule for repeating ω and ε for stopping
          

      • Left factoring

        E → T
        E → T + E
        T → int
        T → (E)
        
        rewrite as:
        E → TY
        Y → + E | ε
        ...
        

   4. Condition for LL(1):
      

      A grammar G is LL(1) iff for any productions A → ω1 and A → ω2 the sets:
      First(ω1 Follow(A)) and
      First(ω2 Follow(A))
      are disjoint
      

      This condition is equivalent to saying that there are no conflicts in the table

4.2.1 Static Allocation

1. Languages without recursion
   
   • some languages such as Fortran (before Fortran90), did not have recursion.
   • as a result, only one invocation of subroutine will be active at a time.
   • space for the variables can be allocated statically and avoid runtime overhead of creation and destruction.
2. Constants
   
   • constants can be allocated space during compile time, since their value can be shared across recursive calls.
   • Some constants value cannot be determined until runtime. Such elaboration-time constants are allocated on stack.

4.2.2 Stack Allocation

4.2.3 Heap Allocation

4.3.1 Static Scope

1. Hole in scope
   
   • A name-to-object binding that is hidden by a nested declaration of the same name is said to have a hole in its scope.
     • or we can say the closer object has eclipsed the outer definition.
   • Some languages may have qualifier to access outer scope variables.
2. Objects in lexically surrounding scopes
   
   • the frames of surrounding subroutines are already active on the stack.
   1. Static Chain
      

      • link to the surrounding block's stack

        (blockA) {
            (blockB) {
                (blockC) {
                }
                (blockD) {
                }
            }
        }
        

      • in above example, during execution of blockD, the scope for blockB has to be active. Thus, during execution of blockD, the stack will look like: A calls B calls D calls C

        blockC
        blockD
        blockB
        blockA

        • C and D have static link to B
        • B has static link to A

4.3.2 Declaration Order

1. Forward Reference
   

   An attempt to use a name before it's declaration

   • Mixed strategy used by languages
     • In Java/C++, members are visible through out the class even before defined.
     • Python, Scheme and Module2 does it differently. Refer book page: 133.
2. Declaration and Definition
   
   • to implement mutually recursive data structures (example: manager and employee) C,C++ has declaration and definition.
   • Declaration gives enough information to compiler about it's name and scope.
   • Definition gives actual implementation details.
3. Redeclaration
   
   • most dynamic languages overwrites the older value.

   • In ML, however, the old meaning of variable is accessible to the functions defined before redeclation.

     let x = 1;
     let f y = x + y;
     f 2 (* gives 3 *)
     let x = 3
     f 2 (* we might expect 5, but the output is 3 (1 + 2) *)
     

   • In other languages like Scheme, stores bindings of names in known locations. Whereas in ML, program is compiled that access old meaning of variable.
   1. TODO does ML simply substitute the value of variable while defining the function?
      

      Maybe because it is immutable.

4.3.3 Dynamic Scoping

4.3.4 Implementing Scope

1. Static Scope:
   
   • never delete anything from symbol table.
   • Most variations on static scoping can be handled by augmenting a basic dictionary style symbol table with enter_scope and leave_scope operations to keep track of visibility.
   1. LeBlanc and Cook Table
      
      • Each scope, as it is encountered, is assigned a serial number.
        • Eg: The outermost scope is given number 0 (the one containing predefined variables
        • The scope containing programmer defined global variables is given 1 and so on.
      • All names are entered into single large hash table
        • Each entry contains symbol name, category (variable, constant, type, procedure, fieldname, paramter), scope number and other details.
      • Symbol table has scope stack that indicates the scopes that compose the current referencing environment.
      • To look up a name in the table, we scan the hash table, for each entry in the table, we search scope stack to check scope of that entry has scope visible.
2. Dynamic Scope:
   
   1. A-list (Association list)
      
      • a simple list of name-value pairs.
      • When used to implement dynamic scoping it functions as stack: new declarations are pushed as they are encountered and popped as the end of the scope in which they appear.
   2. Central Reference table
      
      • maintains a mapping from names to current meanings.
      • new entries are added in front of the chain (bucket list (when key collides))
      • lookup returns the entry at front of the chain.
      • on exit, delete the entry at front.

4.3.5 Shallow and Deep binding (passing subroutine as parameter)

def sub1:
    def sub2:
        print x # prints 3 (deep), 4 (shallow)
    def sub3:
        x = 3
        sub4(sub2) # <- deep binding created here
    def sub4 (subx):
        x = 4
        subx() # <- shallow binding created here
    x = 1
    sub3()

1. Deep Binding
   
   • referencing environment is the one when reference is created
   • in the example, binding x = 3 is created when we pass sub2
2. Shallow Binding
   
   • referencing environment is the one during routine is called
   • in the example, binding x = 4 is created when we call subx
3. Deep Binding and Closure
   
   • Note that Deep binding has reference to the binding environment.
   • if we pass this subroutine (second class citizen), the subroutine can access the environment deep in the stack.
   • but this still can be implemented using stack and pointers. No need to allocate space on heap.
   • the issue arises when we return the subroutine and the stack unwinds. In this case to have closure we need unlimited extent and thus space allocation for the subroutine on stack. See 4.3.6.4

4.3.6 First Class and unlimited extent

1. First Class
   
   • can be passed as parameter
   • can be returned from subroutine
   • can be assigned to a variable
2. Second Class
   
   • can be passed as parameter
   • can not be returned from subroutine
   • can not be assigned to variable
3. Third Class
   
   • cannot be passed as parameter
   • cannot be returned from subroutine
   • cannot be assigned to variable
4. Misc: Unlimited Extent
   
   • check 4.3.5.3, unlimited extent needed only in case of first class function, second class can do with stack allocation.
   • if we return subroutine and that subroutine has access to local variable in surrounding subroutine,
     • we cannot use stack based allocation for local variables
     • the allocation must be on heap
     • handled by garbage collection
   • C do not have nested subroutine
     • can have pure stack based allocation for local variables
   • Scheme will have heap based allocation for local variables
   • Imperative languages avoid first class for avoiding heap based local variable allocation.
   1. Function Object/Object Closure/Functor
      
      • to implement closure in imperative language such as Java, we can store the context in object's field.

      • example:

        interface IntFunc {
          public int call(int i);
        }
        class PlusX implements IntFunc {
          final int X;
          PlusX(int n) { x = n; }
          public int call(int i) { return i + x; }
        }
        

        Here we are saving the closure context in object field int X

5.3.1 Synthesized

5.3.2 Inherited

5.3.3 Attribute Flow

6.3.1 value model

6.3.2 reference model

6.3.3 Boxing

6.3.4 Initialization

1. Dynamic Check
   
   • can assign IEEE standard NaN value to uninitialized number and be checked at runtime.
   • use of NaN results in hardware interrupt.
2. Static Check
   
   • check if code flow through any path leads to assigning value to variable before use.

6.3.5 Ordering within expressions

a - f(b) - c * d;
f(a, g(b), h(c));

6.3.6 Mathematical Identities

c = b - a + d
// rearrange as
c = d - a + b

6.3.7 Switch Case

6.3.8 Applicative and Normal Order Evaluation

6.3.9 Non determinacy

7.6.1 Records (structs)

7.6.2 Variant Records (Union)

7.6.3 Arrays

7.6.4 Sets

7.6.5 Pointers

7.6.6 Lists

7.6.7 Files

7.8.1 Structural Equivalence

7.8.2 Name Equivalence

7.9.1 Nonconverting Type Cast

7.9.2 Coercion

7.12.1 Generic Implementation

8.3.1 Storage allocation

1. Stack Allocation
   
   1. Dope Vector
      
      • datastructure used to hold information about data object about its memory layout
      • has information about lower bound of each dimension
      • size
      • the dope vector for record indicates the offset of each field from beginning of the record.
      • C supports dynamic shape for both parameters and local variables
        • to ensure local object can be found using a known offset from frame pointer the stack is divided into two parts:
          1. Fixed sized part: variable whose size is known statically goes here
          2. Variable sized part: whose size is not know until elaboration time goes here along with pointer to it and dope vector goes to fixed sized part
2. Heap Allocation
   
   • if number of dimension of dynamic array is know statically then dope vector can be kept with pointer to data on stack. If dimension is not know then vector is kept at the beginning of the heap block instead.
   1. Memory layout for multi-dimension array
      
      • Column Major: columns kept together
      • Row Major: rows kept together
      • Affect cache lines, if elements are accessed in a way that results in cache miss then it will affect performance.
      • Fortran has column major
      • 2d array may be implemented as array of pointers.
        • more space required
        • allows rows of different sizes
3. Summary
   

   Lifetime	shape	allocation region
   global	static	static global memory
   local	static	stack
   local	bound at elaboration time	stack with indirection (dope vector)
   arbitrary	bound at elaboration time	heap (size doesn't change)
   arbitrary	arbitrary	vector

   • In third case, space is allocated at end of stack (after temporaries), dope vector contains pointer to base address.

8.6.1 Value Model

8.6.2 Reference Model

8.6.3 Dangling Pointers

8.6.4 Garbage Collection

1. Algorithms
   
   • mark and sweep
   • Pointer reversal
   • Stop and copy

11.4.1 Reduction Rules

1. δ (delta)
   
   • used for built in constant
   • (+ 2 3) →_δ 5
2. β (beta)
   
   • replace all occurrences of bound variable in the body with supplied parameter.
   • ((λ x. E1) E2)
     • Replace all occurrences of E1 with E2 in function body
   • Ex: (λ x. * 2 x) 5 →_β (* 2 5)
     • this can be further evaluated →_δ 10
3. α (alpha)
   
   • rename bound variable
   • (λ x. E(x)) →_α (λ y. E(y))
   • Ex: (λ x. x + 1) →_α (λ y. y + 1)
4. η (eta)
   
   • remove unnecessary abstractions
   • (λ x. f) →_η f
   • (λ x. + 2 3) →_η (+ 2 3) →_δ 5

11.4.2 Normal Form

1. Can every λ expression be reduced to normal form
   
   • (λ x. x x) (λ x. x x)
   • No
   • Since λ expression can model never terminating expression, it is as powerful as Turing machine.
   1. Church's thesis
      

      The effective computable functions on the positive integers are precisely those functions definable in the pure λ calculus (and computable by Turing machine)

2. Is there more than one way to reduce a λ expression
   
   • Yes
   • ((λ x. + (λ y. 4) x) 3)
     1. →_β (+ (λ y. 4) 3) →_η (+ 4 3) →_δ 7
     2. →_η ((λ x. + 4 x) 3) →_β (+ 4 3) →_δ 7
3. if there is more than one to reduce, does each lead to same normal form expression
   
   • Yes
   1. Church-Rosser Theorem
      
      • If an expression can be reduced in two different ways to two normal forms then these normal forms are same up to α conversion
      • Also called as diamond property
        • this does not imply that if a normal form exists, then any redex will work. (See example below)
4. Is there a reduction strategy that guarantees that a normal form will be produced (if there is one)
   
   • Yes
   1. Standardization Theorem
      
      • If an expression has normal form, then a leftmost outermost reduction at each state is guaranteed to reach that normal form.
      • δ or β does not always reduce: ((λ x. λ y. y) ((λ z. z z)(λ z. z z)))
        1. taking outermost redex →_η (λ y. y)
        2. taking innnermost redex →_β ((λ x. λ y. y) ((λ z. z z)(λ z. z z))) →_β …

11.5.1 Normal Order

11.5.2 Applicative Order

11.5.3 Comparison

1. ∞ computation
   

   (define eternity
     (λ ()
       (eternity)))
   
   (define zero
     (λ (x)
       0))
   
   (zero eternity)
   

   • normal order: gives 0 immediately
   • applicative order: in this case, may not return
2. Argument Evaluation
   

   fun sqr x = x * x;
   sqr(sqr(sqr(2)))
   
   (* in case of normal order evaluation
   = sqr(sqr(2)) * sqr(sqr(2))
   = sqr(2) * sqr(2) * sq(sqr(2))
   ...
   redundant computations
   *)
   
   (* in case of applicative order reduction
   = sqr(sqr(4))
   = sqr(16)
   = 256
   *)
   

3. Graph Reduction (Lazy Evaluation)
   
   • has pointer to expression
   • save the result of expression after evaluation
   • can pass argument unevaluated – normal order
   • can save against long/∞ computation

11.6.1 if true a b = a

11.6.2 if false a b = b

11.7.1 Fixed Points

13.2.1 Abstract Syntax

13.2.2 Syntactic Domain

13.2.3 Semantic Domain

13.2.4 Semantic Functions

1. Function Definitions
   

   execute[|load N|] (stack, output) = (value[|N|] :: stack, output)
   execute[|+|] (x::y::xs, output) = ((x + y)::xs, output)
   execute[|*|] (x::y::xs, output) = ((x * y)::xs, output
   execute[|out|] (x::xs, output) = (xs, output @ x)
   execute[|I1 I2|] = execute[|I2|] . execute[|I1|]
   meaning[|P|] = execute[|I|] [] []  //empty stack and output
   

   • note: execute [|I1 I2|] = execute[|I2|] . execute[|I1|] is function composition
     • output of execute[|I1|] is fed to execute[|I2|] as input
     • f . g = f(g)

13.3.1 Abstract Syntax

13.3.2 Syntactic Domain

13.3.3 Semantic Domain

13.3.4 Semantic functions

1. store
   
   • store is a function which maps Id to (Integer, undefined)
   • Base case for store is empty, where everything is mapped to undefined
   • sto₀: - → undefined
   • sto₁: maps one id to integer, rest delegated to sto₀

   • sto₂: maps another id to integer, rest delegated to sto₁, so on…

     update (sto_n, id, int_i) x = if (x = id)
                                     then int_i
                                     else sto_n x
     
     (*
     here,
     (update (sto_n, id, val)) returns a function
       which maps id -> val, else
       delegated to sto_n
     *)
     

2. evaluate
   

   evaluate[|N|] sto = value [|N|]
   evaluate[|id|] sto = sto(Id)
   evaluate[|E1 + E2|] sto = evaluate[|E1|] sto + evaluate[|E2|] sto
   evaluate[|skip|] sto = sto
   evaluate[|id := E|] sto = update(sto, id, evaluate[|E|] sto)
   evaluate[|C1 C2|] sto = evaluate[|C2|].evaluate[|C1|]
   meaning[|C|] = evaluate[|C|] empty
   

13.3.5 Meaning

13.3.6 if statements

execute [|if E then C1 else C2|] state =
if (evaluate[|E|] state)
then evaluate[|C1|] state
else evaluate[|C2|]

13.3.7 while statements

execute [|while E do C|] (sto, in, out)
//unroll the loop
if (evaluate[|E|] (sto, in, out))
then execute [|while E do C|] . evaluate C
else skip

// loop is a fixed point
let loop = λ s:state .
             if (evaluate[|E|] s)
             then (loop (execute [|C|] s)) // ← recursively call loop
             else s
in loop
end

13.3.8 Nested Scopes

1. Environment and Location
   

   Environment	identifier → location (address)
   Store	location → value
   env	location + unbound
   store	location → storableType + unused + undefined

   • unused: not to bound to an identifier
   • undefined: no value stored yet
2. extendEnv
   

   extendEnv (env, id₀, loc) id₁ = if (id₀ = id₁) then loc else env id₁

3. update store
   

   update (sto, loc₀, val) loc₁ = if loc₁ = loc₀ then val else sto loc₁

14.2.1 Assignment Axiom

{ Q[V := E] and E is defined }
V := E
{ Q }

14.2.2 Stronger and Weaker assertions

14.2.3 Inference Rules

1. Strengthen the precondition
   

   P ⊃ Q, {Q} S {R}
   —————–----------
   {P} S {R}
   

   • P is stronger than Q
   • S in a state satisfying Q will result in state satisfying R
   • anywhere where P is satisfied, Q is also satisfied
   • ∴ the final state will satisfy R
     • this may seem counter intuitive if we consider S to a function which maps all pre to post condition
     • S is just a function which will get R if any one state of precondition is true.
     • The states allowed by P is subset of state allowed by Q (since P has stronger constraints)
2. Weaken the postcondition
   

   P ⊃ R, {Q} S {P}
   ----------------
   {Q} S {R}
   

   • P is stronger than R
   • S gets from Q to P
   • any state satisfying P will satisfy R
   • ∴ S gets Q to R
3. Sequence Rule
   

   {P} S0 {Q}, {Q} S1 {R}
   ----------------------
   {P} S0 S1 {R]
   

14.2.4 Some facts

1. A and B ⊇ A
2. A ⊇ A or B
3. {false} S {P}
4. {P} S {true}

14.2.5 Application in programming languages

14.2.6 Some rules about ⊃

A ⊃ C
———--------
A and B ⊃ C

A or B ⊃ C
------------
A ⊃ C, B ⊃ C

A ⊃ C
----------
A ⊃ B or C

A ⊃ B, A ⊃ C
------------
A ⊃ B and C

A ⊃ B and C
------------
A ⊃ B, A ⊃ C

A ⊃ C, B ⊃ C
------------
A or B ⊃ C