Functionandcompiler

  • Programming Language Syntax (Ch. 2.1-2.3.3)
  • Logic Programming and Prolog (Ch. 12)
  • Scoping (Ch. 3.1-3.3)
  • Programming Language Semantics (Sc. Ch. 4.1-4.3)
  • Functional programming (Ch. 11)
  • Scheme and Haskell, map/fold questions
  • Lambda calculus (Ch. 11 Companion)
  • Data abstraction: Types (Ch. 7, 8)
  • Control abstraction: Parameter Passing (Ch. 9.1-9.3)
  • Object-oriented languages (10.1-10.2)
  • Concurrency (13.1). “What can go wrong?” questions

  • Dynamic languages (Ch. 14 optional)

  • Syntax is the form or structure of expressions, statements, and program units of a given language
  • Semantics is the meaning of expressions, statements and program units of a given language

Formal languages (Lecture 2 plus chapters)

  • Regular languages: Finite Automaton
    • Regular expressions
    • DFAs
    • Use of regular languages in programming languages

important

  • A character
  • The empty string, denoted by e
  • Two regular expressions next to each other: R1R2
  • R1 R2
  • R*: zero or mmore, (a b)*
  • Context-free languages: Push-down Automaton
    • Context-free grammars
    • Derivation, parse, ambiguity
    • Use of CFGs in programming languages
    • Expression grammars, precedence, and associativity

important

  • A grammar consists of a set of terminals, set of nonterminals, a set of productions, and a start symbol
  • Terminals are the characters in the alphabet
  • Nonterminals represent language constructs
  • Productions are rules for forming syntactically correct constructs
  • Start symbol tells where to start applying the rules
  • Regular grammars
    • Each left-hand-side (lhs) has exactly one nonterminal
    • Each right-hand-side (rhs) is one of the following
      • terminal symbol
      • nonterminal symbol
      • nonterminal followed by a terminal
  • Context-free grammars have rules of the form:
    • Each left-hand-side has exactly one nonterminal
    • Each right-hand-side contains an arbitrary sequence of terminals and nonterminals
  • left/right-most derivation -> Parse
    • A parse starts with the string of terminals, and at each step, replaces the right-handside (rhs) of a production with the left-handside (lhs) of that production.
    • A grammar is ambiguous if some string can be generated by two or more distinct parse trees
  • Scanner is essentially a Finite Automaton
  • Comments are usually handled by the scanner, which essentially is a DFA. Handling multiline comments would require recognizing (/)n(/)n which is beyond the power of a DFA.

Parsing

  • For any CFG, one can build a parser that runs in O(n3)
  • (LL and LR) parse tree
    • root 2 leaf -> A left-most derivation -> Always expand the leftmost nonterminal
    • leaf to root -> A right-most derivation in reverse
  • LL Parsing (Lectures 3 and 4 plus chapters)
    • Recursive-descent parsing, recursive-descent routines
    • LL(1) grammars -> left-to-right, left-most derivation, need k=1 tokens of lookahead to predict
    • LL(1) parsing tables
      • One dimension is nonterminal to expand
      • Other dimension is lookahead token
      • We are interested in one token of lookahead
    • FIRST, FOLLOW, PREDICT
      • FIRST(α) is the set of terminals a that begin the strings derived from
      • FOLLOW(A) is the set of terminals b (including special end-of-input marker $$) that can appear immediately to the right of A in some sentential form
    • LL(1) conflicts
      • remove left-recursive
  • Logic programming concepts (Lecture 5 plus chapters
    • Declarative programming
    • Horn clause, resolution principle (replace) ``` h :- b1,…,bn. Horn Clause with no tail is a fact rainy(seattle) Horn Clause with a tail is a rule snowy(X) :- rainy(X),cold(X)

c(X) :- h(X,Y). For all values of X, c(X) is true if there exist a value of Y such that h(X,Y) is true

rule1:-likes(eve,V),person(V). add a rule “X[snowy(X) <- rainly(X) ^ cold(X)]

is =


- **Prolog** (Lectures 5, 6, and 7 plus chapters)
   - constants(lower-case letter), Variables(upper-case letter), Consists of an atom, called a functor and a list of arguments.
   - Prolog concepts: search tree, rule ordering, unification, backtracking, backward chaining
       - and/or
       - Unifies parent (goal), with child (head-of-clause)
   - Prolog programming: lists and recursion, arithmetic, backtracking cut, negation-by-failure, generate-and-test



- Binding and scoping (Lecture 8 plus reading)
   - Static (before execution) and Dynamic (during execution) 
       - Static storage – an object is given absolute address, which is the same throughout execution
          - Program code
          - Global variables
          - Tables of type data (e.g., inheritance structure)
          - Dispatch tables (VFTs) and other tables
       - Stack storage – stack objects are allocated on a run-time stack at subroutine call and deallocated at return
          - What data is stored on the stack?
          - Local variables, including parameters
          - fp points to a location at the start of current frame
              - In higher memory (but lower on picture)
          - sp points to the next available location on stack (or the last used location on some machines)
              - In lower memory (but higher up on picture)
          - Compiler-generated temporaries (i.e., for expression evaluation)
          - Bookkeeping (stack management) information
          - Return address
          - BP>SP, 0x01020304 stored as ```04 03 02 01``` next address
       - Heap storage - long-lived objects are allocated and deallocated at arbitrary times during execution
   - Object lifetime
   - Combined view of memory
   - Stack management
   - Scoping (in languages where functions are third-class values)
       - Scoping rules: map variable to location
       Rule: a variable is visible if it is declared in its own block or in a textually surrounding block and it is not ‘hidden’ by a binding in a closer block (i.e., there is no hole in scope)
   - Static and dynamic links
       - Bookkeeping required to maintain the static link
       - Dynamic link points to the caller frame, this is essentially old fp stored on frame
   - Static (lexical) scoping
       - mapped at compile time
   - Dynamic scoping
       - Allows for local variable declaration
       - Use of variable is resolved to the declaration of that variable in the most recently invoked and not yet terminated frame. I.e., lookup proceeds from closest predecessor on stack to furthest






- Attribute grammars
   - Attributes
   - Attribute rules
   - Decorated parse trees
   - Bottom-up (i.e., S-attributed) grammars

## Scheme (Lectures 12 and 13, plus chapters)
- S-expression syntax
   - S-expr ::= Name | Number | ( { S-expr } )
   - cons = [car::cdr]
   - (car (cdr (cdr ‘((a) b (c d)) ))) = (caddr ‘((a) b (c d)) )
- Lists and recursion
- Shallow and deep recursion
- Equality
- A variable is a location that holds a value
   - Reference model for variables
   - Every variable is an l-value
- Higher-order functions
- map, foldl, and foldr
- Programming with map, foldl, and foldr
- Tail recursion
- Binding with let, let*, letrec
- Scoping in Scheme
- Closures and closure bindings

;(define (fun) ; (lambda (a) (+ 1 a)))

((fun) 4)

; (map f list)

(define (mymap f lis) (if (null? lis) ‘() (cons (f (car lis)) (mymap f (cdr lis)))))

(define (atomcount2 s) (cond ((atom? s) 1) (else (apply + (mymap atomcount2 s)))))

(atomcount2 ‘(1 (2 (3)) (5)))

(apply append (…))

A closure can be used as a function

(let ((x 10) (y (* 2 x))) (* x y)) (let* ((x 10) (y (* 2 x))) (* x y))



## Scoping, revisited
- Static scoping
   - Reference environment
   - Functions as third-class values vs.
   - Functions as first-class values
- Dynamic scoping
   - With shallow binding
   - With deep binding
   - Deep binding binds the environment at the time a procedure is passed as an argument.
   - Shallow binding binds the environment at the time a procedure is actually called.

## Lambda calculus (Lectures 15 and 16)
- Syntax and semantics
  - lx. x z = lx. ( x z ) = ( lx. ( x z ) ) = 
  - ( lx. x z ) ≠ ( ( lx. x ) z )
  - f(x,y) = x+y, becomes (lx.ly. x + y)
  - (lx.ly. x + y) 2 3 = (ly. 2 + y) 3 = 2 + 3 = 5
- Free and bound variables
  - (lx.ly. x y) (y w) => (lx.lz. x z) (y w)
     - ( lz. x z ) [(y w)/x] => ( lz. (y w) z ) 
     - rename + apply the reduction
- Substitution
- Rules of the Lambda calculus
   - Alpha-conversion
   - Beta-reduction
- Normal forms
- Reduction strategies
   - Normal order
   - Applicative order

- Haskell (Lectures 19 and 20)
   - Basic syntax
      - map, foldl, foldr, filter
      - “\x->” is “λx.”
   - Algebraic data types
   - Pattern matching
   - Lazy evaluation
      - It won’t evaluate an expression until it is needed
   - Types and type inference
   - Basics of type classes and Maybe monad
      - Reduces to answers in Normal Form
      - Uses applicative order reduction
      - ```[ x | x <- [1,2,3,4], x `mod` 2 == 0 ]```

- Data abstraction and types (Lecture 21)
   - Types and type systems
   - Type equivalence
      - are field names part of the struct constructed type?
      - are array bounds part of the array constructed type?
   - Types in C  structural, loose

- Parameter passing mechanisms (Lecture 22)
   - Call by value
   - Call by reference Aliasing, dangerous
   - Call by value-result
   - Call by name: Argument is an expression and deferred until needed
      - What reduction strategy corresponds to call by name? Normal order reduction
      - What reduction strategy corresponds to call by value? Applicative order reduction
   - Call by sharing

- Object-oriented languages and polymorphism (Lecture 23)
   - Subtype polymorphism
   - Parametric polymorphism
   - Explicit parametric polymorphism
   - Implicit parametric polymorphism

- Concurrency in Java (Lecture 24)
   - Threads and tasks
   - Synchronized blocks
   - Concurrency errors
   - Data races
   - Atomicity violations

data MyList a = EMPTY | CONS a (MyList a) deriving (Show, Eq)

data Tree a = LEAF a NODE a (Tree a) (Tree a) deriving (Show, Eq)

preOrder :: Tree a -> [a] preOrder (LEAF x) = [x] preOrder (NODE x t1 t2) = [x] ++ (preOrder t1) ++ (preOrder t2)

myTree = NODE “zero” (NODE “zero” (LEAF “one”) (LEAF “two”)) (NODE “zero” (LEAF “three”) (LEAF “four”))

ok2 _ _ [] = [] ok2 f c (x:xs) = (f c x):(ok2 f c xs)

fun_a = let x = 0 fun_c f = let x = 1 in f x fun_d y = x + y fun_b = let x = 3 in (fun_c fun_d) in fun_b

fun lis = let f [] acc = acc f (x:xs) acc = f xs (acc ++ [y++[x]|y<-acc]) in f lis [[]]

unique :: [Integer] -> [Integer] unique a = uniquetail a []

uniquetail :: [Integer] -> [Integer] -> [Integer] uniquetail [] total = total uniquetail (a:ax) total | iscontain a total = uniquetail ax total | otherwise = uniquetail ax (a:total)

iscontain :: Integer -> [Integer] -> Bool iscontain _ [] = False iscontain b (a:ax) | a == b = True | otherwise = iscontain b ax

ip :: [Integer] -> [Integer] -> Integer ip a b = iptail a b 0

iptail :: [Integer] -> [Integer] -> Integer -> Integer iptail [] [] ans = ans iptail (a:ax) (b:bx) ans = iptail ax bx (a*b+ans)

x = [1]:[2]:[3]:[] – main = putStrLn $ show (MyList 1) – main = print (typeof ok2) (fun [1, 2, 3]) main = print (fun [1, 3, 5])

(define (square x) (* x x))

(define (zero x) (if (= x 0) #t #f))

(define square2 (lambda (n) (* n n)))

(define (zerocheck? x) (cond ((= x 0) #t) (else #f)))

(define (len x) (cond ((null? x) 0) (else (+ 1 (len (cdr x))))))

(define (app x y) (cond ((null? x) y) ((null? y) x) (else (cons (car x) (app (cdr x) y)))))

(define (fun x) (cond ((null? x) 0) ((atom? x) 1) (else (+ (fun (car x)) (fun (cdr x)))) ))

(define (atomcount x) (cond ((null? x) 0) ((atom? x) 1) (else (+ (atomcount (car x)) (atomcount (cdr x)))) ))

(define (f g x) (g x))

(f number? 0) (f len ‘(1 (2 3))) (f (lambda (x) (* 2 x)) 3)

(zero 1) (zero (* 1 0)) (zerocheck? 1) (square 6) (app ‘(5 9) ‘(a (4) 6)) (fun ‘(1 (2 (3)) (5))) (atomcount ‘(1 (2 (3)) (5))) (eq? 1 1)

(let ((x 2)) (let ((y 1)) (+ x y)))

(define curried-plus (lambda (a) (lambda (b) (+ a b)))) ((curried-plus 2) 3)

(let ((x 10)) (let ((fun (lambda (y) (+ y x)))) (let ((x 5)) (* x (fun 3) ) ) ) ) ;(foldr + ‘(1 2 3) 0)

(define (iscontain ele unilis) (if (null? unilis) #f (if (eq? ele (car unilis)) #t (iscontain ele (cdr unilis)) ) ) )

(define (uniquetail lis unilis) (if (null? lis) unilis (if (iscontain (car lis) unilis) (uniquetail (cdr lis) unilis) (uniquetail (cdr lis) (cons (car lis) unilis)) ) ) )

(define (unique lis) (uniquetail lis ‘()))

(unique ‘(1 2 3 3))

(define (iptail a b ans) (if (null? a) ans (iptail (cdr a) (cdr b) (+ (* (car a) (car b)) ans) ) ) )

(define (ip a b) (iptail a b 0))

(ip ‘(1 2 3) ‘(6 5 4))

(define (foldr op lis id) (if (null? lis) id (op (car lis) (foldr op (cdr lis) id)) ) )

(define (total-sum lis) (if (null? lis) 0 (+ (car lis) (total-sum (cdr lis))) ) )

(define flattenlist (lambda (ls) (foldr (lambda (e a) (if (list? e) (append (flattenlist e) a) (cons e a))) ls ‘())))

(define (total-all lis) (total-sum (flattenlist lis)))

(flattenlist ‘(1 2 3 ((4)) (5))) (total-all ‘(1 2 3 ((4)) (5))) ```

Written on December 13, 2020