Midterm 2 Appendix (Wiki, Student-Generated; credits at end)

Midterm 1 Material (copy of old appendix)

Definitions

Abstract syntax - idealized syntax, designed for convenient use by the underlying interpreter/compiler; result of parsing a concrete syntax expression
Concrete syntax - syntax written by the user; consumed by the parser
Closure - a wrapper that contains an expression (function/ binding) and its environment; expression saved until it needs to be used
CPS stands for Continuation-Passing Style (a.k.a. Tail Call Elimination)

Static vs. Dynamic Scoping

Static Scope: In a language with static scope, the scope of an identifier's binding is a syntactically delimited region. A typical region would be the body of a function or other binding construct.

Dynamic Scope: In a language with dynamic scope, the scope of an identifier's binding is the entire remainder of the execution during which that binding is in effect. That is, in a language with dynamic scope, if a function g binds identifier n and then invokes f, then f can refer to n—and so can every other function invoked by g until it completes its execution—even though f has no locally visible binding for n.

from PLAI, p. 36

Closures and First-Class vs. First-Order Functions

First-order Functions are not values in the language. They can only be defined in a designated portion of the program, where they must be given names for use in the remainder of the program. (For a language like C, the "designated portion" is anywhere in the top-level of a source file, but not, for example, within the body of another function.) The functions in F1WAE are of this nature, which explains the 1 in the name of the language.

Higher-order Functions can return other functions as values and take other functions as parameters.

First-class Functions are values with all the rights of other values. In particular, they can be supplied as the value of arguments to functions, returned by functions as answers, constructed as values by expressions, and stored in data structures.

Deferred Substitution

Deferred Substitution Initially, we have no substitutions to perform, so the repository is empty. Every time we encounter a substitution (in the form of a with or application), we augment the repository with one more entry, recording the identiﬁer’s name and the value (if eager) or expression (if lazy) it should eventually be substituted with. We continue to evaluate without actually performing the substitution.

A side-effect of deferred substitution is dynamic scoping, which we were able to fix by using closures to store the environment from which the function was created in.

Eager vs. Lazy Evaluation

Lazy With- we reduce the named expression to a value only when we need to
Lazy Functions- we do not reduce the argument to a value until necessary
Strictness Points- the points where the implementation of a lazy language forces an expression to reduce to a value (example: in a function application, need to evaluate exactly what function to invoke, can't just leave it as a function closure)
Eager- the named expression is reduced to a value before being substituting it.

Backus-Naur Form (BNF)

A concise specification language for expressing (among other things) the concrete syntax of a programming language. A BNF often strongly suggests a corresponding abstract syntax.

Here's an example BNF for a language with arithmetic expressions, with expressions, first-class functions and applications, a conditional statement, and explicit language support for recursion. This particular language allows an arbitrary number of parameters to a function in its definition or arguments in a function application.

 <CFWAE> ::= <num>
   | {+ <CFWAE> <CFWAE>}
   | {- <CFWAE> <CFWAE>}
   | {* <CFWAE> <CFWAE>}
   | {/ <CFWAE> <CFWAE>}
   | <id>
   | {if0 <CFWAE> <CFWAE> <CFWAE>}
   | {with {<id> <CFWAE>} <CFWAE>}
   | {fun {<id> ...} <CFWAE>}
   | {<CFWAE> <CFWAE> ...}
   | {rec {<symbol> <CFWAE>} <CFWAE>}

Racket syntax, helpful procedures, and thoughts

(cond
     [(number? v) ...]
     [(boolean? v) ...]
     [(string? v) ...]
     [else false])

(match data
   [pattern  action]
      [(? number?) (foo)]                    ;; check if data is number 
      [(list a b c) (foo a b c) ]            ;; back-reference of list elements
      [((and n (? number?))) (foo n)]        ;; check if data is number and back-reference it as n
      [else (foo)]
)
;; Keep in mind that in pattern matching
;; '...' or '___' means 0 or more 
;; '..n' or '__n" means n or more 
;; '_' matches anything

begin: Evaluates all expressions passed as arguments to begin, in order, and the results are all ignored except for the last one.

> (begin (+ 5 2) (printf "Hello World!\n") (+ 3 1))
Hello World!
4

Variable definition:

(define x 3)

Function definition:

(define (funcName arg)
    (+ 1 arg))

Environment: - repository of deferred substitutions

(define-type Env
     [mtEnv]
     [anEnv (name symbol?)(value CFWAE-Value?)])

Expression Closures:

(define-type CFWAE-Value
     [numV (num number?)]
     [exprV (body CFWAE?)(env Env?)] ;; used to hold an unevaluated expression and its environment (used in lazy interp)
     [closureV (param symbol?)(body CFWAE?)(env Env?)]) ;;used to close over the existing environment to ensure static scope

map - performs a procedure on all elements of the list in order

map <procedure> <list>
(define (parseList list)
(map parse list))

Type-case

(type-case WAE expr
            [num (n) expr]
            ...)

Define-type (From assignment 1)

(define-type WAE
 [num (n number?)]
 [binop (op procedure?) (lhs WAE?) (rhs WAE?)]
 [with (b Binding?) (body WAE?)]
 [with* (lob (listof Binding?)) (body WAE?)]
 [id (name symbol?)])

Recursion interp (From lecture)

(define (interp exp env)                                                      
 (type-case CFAE exp                                                         
     ...
    (id  (name) (lookup name env))
    (fun (arg-name body) (closureV arg-name body env))
    (if0 (tst thn els) 
         (type-case CFAE-value (interp tst env) 
            (numV (n) (if (zero? n) (interp thn env) (interp els env)))
            (else (error "non numeric if0 test value"))))
    (app (fun-exp arg-exp)
         (let ((the-fun (interp fun-exp env))
               (the-arg (interp arg-exp env)))
           (type-case CFAE-value the-fun
             (closureV (arg-name body closure-env)
                       (interp body (anEnv arg-name the-arg
                                           closure-env)))
             (else (error "You can only apply closures!")))))
    (rec (bound-id named-exp body)
      (local ([define new-env (anEnv bound-id 
                                     (numV 0)
                                     env)]
              [define named-value (interp named-exp new-env)])
        (begin
          (set-anEnv-val! new-env named-value)  ;; Patches (numV 0) out for the correct value
          (interp body new-env))))
      
    
    ))

Strict code (from lecture)

(define (strict val)
 (if (expV? val)
     (strict (interp (expV-exp val) (expV-env val)))
     val))

Midterm 2 Material

State

State is "threaded through" a program in the sense that the state that results from evaluating a given function is the state in which the next sequential function is to be evaluated in.
State is inherently dynamic and so isn't supported by solely the environment, as it has static scope in our implementations.
Closures do not remember state as function are to be applied using the state that exists where they are applied.

Mutable Data Structures

Need two repositories:

Environment
- protects static scope
- maps identifier to location
- can get back to a previous location
- Identifier -> Value
Store
- tracks dynamic changes
- maps location to a value
- changes are permanent
- Location -> Value
Variables
- Identifier -> Location
- Location -> Value

Meta vs Syntactic Interpreters

Syntactic Interpreter - An interpreter that uses the interpreting language to represent only terms of the interpreted language, implementing all the corresponding behavior explicitly

doesn't use Scheme's implementation of things (like numbers)
doesn't matter how well the interpreting and interpreted languages correspond

Meta Interpreter - An interpreter that uses language features of the interpreting language to directly implement behaviour of the interpreted language

easy to write when there is a strong match between interpreted and interpreting language
uses Scheme's implementation of things (closures, procedure applications, numbers, etc)

Meta-Circular Interpreter - A meta interpreter in which the interpreting and interpreted language are the same

Only uses Scheme implementation of things

from PLAI, p.107-109

Continuations

What are they?

stack is represented procedurally
remember only the result and what is left to do (passes the state along)
roughly the same idea as tail recursion

Why?

Saves on memory and computation (ex. tail recursion summation vs augmenting recursion summation)
A way of recording state when the processing computer is not always available (ex. web-servers)

Why Not?

get rid of machine optimizations by forcing the structure of stack into continuation
memory wastage if language needlessly creates stack frames
need access to the source of entire program otherwise CPS translator may fail
security: what if someone outside knew how to read the stack procedure?

Conventions

Continuation methods usually end in /k

Variables

Call-by-value

evaluated argument is held in a new location
changes to the content of that location in the store don't affect the actual parameter

Call-by-reference

pass a reference to the actual argument, not the value
updates to the reference within the called procedure will become visible to the calling context
cheaper to use (no additional allocation) but introduce problems
to implement:
- create a closure and give it the location of the actual argument
- uses l-value: env lookup without store lookup
- any mutations to the formal parameter are now changes to the same location as the actual parameter

Stateful vs Stateless

Stateful

server maintains state information
easier to program
- don't need setup and breakdown of state at each interaction
ex: FTP
- interp of each command is relative to history of past commands

Stateless

does not retain record of prior communication
Web application must completely restore state of the computation for each interaction
server can handle higher loads
server can ignore clients who don't appear to be active
must transmit enough data to resume computation

Web Programs

Receiver - a procedure of one argument representing the pending computation

any computation not mentioned in the receiver never gets performed because of the program's termination after each iteration

Lifting - make nested procedures into top-level procedures

Make a program Web-Ready

1. Generate receivers that capture pending computations
2. Pass values to receivers instead of returning them

Implications

1. Order of evaluation
2. Transformation is global
- all procedures in program must consume an extra receiver
3. Sequentializes the program

Map Example

(define (map f l)
  (if (empty? l)
     empty
     (cons (f (first l)) 
              (map f (rest l)))))

becomes:
(define (map/k f/k list k)
  (if (empty? list)
      (k empty)
      (f/k (first list)
           (lambda (f-result)
             (map/k f/k (rest list)
                    (lambda (r-result)
                      (k (cons f-result r-result))))))))