Course:CPSC311/2011WT1/Midterm Exam 2 Appendix

From UBC Wiki

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 identifier’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))

Laziness with Caching

(define-type CFAE/L-Value
  ...
 [exprV (env Env?) (body CFAE/L?) 
        (cached-version (or/c boolean? CFAE/L-Value?))]
 ... )

Cached strictness (from lecture-code):

 [exprV (env body cached-version) 
          (if (equal? cached-version false)
              (begin
                (printf "First eval of ~a.~n" body)
                (local ([define cv (strict (interp-env env body))])
                  (begin
                    (set-exprV-cached-version! val cv)
                    cv)))
              (begin
                (printf "Using cached version of ~a.~n" body)
                cached-version))]

In `interp`:

[app (fun-expr arg-expr)
        (local ([define fun-value (val-to-type closureV?
                                               (interp-env env fun-expr))]
                [define fun-param (closureV-param-name fun-value)]
                [define fun-body  (closureV-body fun-value)]
                [define fun-env   (closureV-env fun-value)]
                [define value     (exprV env arg-expr false)])
          (interp-env (anEnv fun-param value fun-env) fun-body))]

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:

  1. Environment
    • protects static scope
    • maps identifier to location
    • can get back to a previous location
    • Identifier -> Location i.e. [aSub (name symbol?)(location number?)(env Env?)])
  2. Store
    • tracks dynamic changes
    • maps location to a value
    • changes are permanent
    • Location -> Value
  • Variables
    • Identifier -> Location
    • Location -> Value

Scope and Extent

scope (or lexical scope)
the portion of program text where an identifier is bound. Identifiers in the environment have a limited scope.
extent (or dynamic extent)
the portion of program execution during which a value persists in the store. Values in the store have a potentially unlimited extent.
threading
describes the flow of the store from one arm of a computation to the next, then back out with the returning value. We say that the store is threaded through program execution.

Note how this differs from the flow of the environment:

  1. The updated store from the first computation is used for the second computation, while the same environment is used for both computations
  2. As we return, we pass the updated store, but not the environment (we are exiting our scope).

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

Implementing Continuations

Making Continuations Explicit

(define-type CFAE-Value 
  [numV (n number?)] 
  [closureV (p procedure?)])
;; interp : CFAE Env receiver → doesn’t return 
(define (interp expr env k)
  (type-case CFAE expr 
    [num (n) (k (numV n))] 
    [add (l r) (interp l env
                      (lambda (lv) 
                        (interp r env
                                (lambda (rv)
                                  (k (num+ lv rv))))))]
   [if0 (test truth falsity) 
        (interp test env
                (lambda (tv)
                  (if (num-zero? tv)
                      (interp truth env k)
                      (interp falsity env k))))] 
   [id (v) (k (lookup v env))]
   [fun (param body)
        (k (closureV (lambda (arg-val dyn-k)
                       (interp body 
                               aSub param arg-val env) 
                        dyn-k))))] 
 [app (fun-expr arg-expr)
     (interp fun-expr env 
             (lambda (fun-val)
               (interp arg-expr env 
                       (lambda (arg-val)
                         ((closureV-p fun-val) arg-val k)))))]))

Adding continuations as language constructs

(define-type KCFAE-Value 
  [numV (n number?)]
  [closureV (p procedure?)] 
  [contV (c procedure?)])
;; interp : KCFAE Env receiver → doesn’t return 
 (define (interp expr env k)
 (type-case KCFAE expr 
  [num (n) (k (numV n))] 
  [add (l r) 
      (interp l env
              (lambda (lv) (interp r env
                                   (lambda (rv)
                                     (k (num+ lv rv))))))]
 [if0 (test truth falsity) 
      (interp test env
              (lambda (tv)
                (if (num-zero? tv)
                    (interp truth env k)
                    (interp falsity env k))))]
 [id (v) (k (lookup v env))]
 [fun (param body)
      (k (closureV (lambda (arg-val dyn-k)
                     (interp body 
                             (aSub param arg-val env) 
                             dyn-k))))] 
 [app (fun-expr arg-expr)
      (interp fun-expr env 
              (lambda (fun-val)
                (interp arg-expr env 
                        (lambda (arg-val)
                          (type-case KCFAE-Value fun-val
                            [closureV (c) (c arg-val k)]
                            [contV (c) (c arg-val)]
                            [else (error ”not an applicable value”)])))))]
 
 [bindcc (cont-var body)
         (interp body
                 (aSub cont-var
                       (contV (lambda (val)
                                (k val)))
                       env)
                 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 i.e. [define arg-loc (env-lookup (id-name arg-expr) env)] where arg-expr is syntactically a variable.
      • unlike in call-by-value, we do not interpret the arg-expr before dispatching the closure. This is to prevent reducing the arg-expr from a store-location to a value, thus defeating the purpose!
    • uses l-value: env lookup without store lookup; NB. an l-value is the location of the value in the store. Termed so because it exists on the left-hand-side of an expression when bound to value.
    • 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))))))))

The Y Combinator

The generic representation of the Y combinator:

(lambda (p)
    ((lambda (f)
       (f f))
      (lambda (f)
              (p (f f)))))


As applied to recursive factorial:

((lambda (marf)
  (marf marf))
        (lambda (f)
            (lambda (n)
               (if (zero? n)
                          1
                          (* n ((f f) (- n 1)))))))

in CFAE:

 {with {marf {fun {warf}
                                   {{fun {f} {f f}}
                                    {fun {rfg}
                                         {warf {fun {ignore} {rfg rfg}}}}}}}
                        {with {fact {marf {fun {fact}
                                               {fun {n}
                                                    {if0 n 1 {* n {{fact 0} {- n 1}}}}}}}}
                              {fact 5}}}


Continuation Passing Style rules

(1) Convert each function f to f/k and take an extra continuation argument.

(2) Find the "next step to take" (the "sequentialized" version of the program, just like we did when we threaded the store!).

(3) If that step is in tail position, great! If it's a value, apply the continuation to it. If it's a function call, pass the continuation to the function call.

(4) If that step is not in tail position, cut it from its current location, replace it with a placeholder value (it!), write it in tail position (at the front), and give it a lambda that takes that placeholder as a parameter and includes the whole rest of the function as its body. Then, repeat from (2) on the whole rest of the function!

Disadvantages to CPS

(1) It requires access to the source of the entire problem. If a procedure is defined in a library for which we don’t have access to the source, or is perhaps written in a different language (as map often is), then the CPS translator will either fail to run or will produce potentially erroneous output (i.e., code that does not properly restore the state of the computation).

(2) By replacing the machine’s stack with an explicit representation in the form of receivers, it inhibits optimizations built into compilers and microprocessor architectures.

(3) As we will see in Section 20.4, executing a program in CPS also assumes that the run-time system will not needlessly create stack frames (since the stack is entirely represented by the receiver). Since many languages (such as C and Java) do anyway, the program consumes memory unnecessarily. In an extreme case, a Java or C program that would have executed without exhausting memory will run out of memory after conversion into CPS.

Recursion Support Code

Figure 11.3: Meta-Circular Interpreter

(define (number-or-procedure? v) 
 (or (number? v)
     (procedure? v)))
(define-type Env 
 [mtSub]
 [aSub (name symbol?)
       (value number-or-procedure?) 
       (env Env?)])
;;lookup : symbol Env → number-or-procedure 
(define (lookup name env)
 (type-case Env env
   [mtSub () (error ’lookup ”no binding for identifier”)] 
   [aSub (bound-name bound-value rest-env)
       (if (symbol=? bound-name name) 
           bound-value
           (lookup name rest-env))]))
;; interp : FAE Env → number-or-procedure 
 (define (interp expr env)
  (type-case FAE expr
    [num (n) n]
    [add (l r) (+ (interp l env) (interp r env))] 
    [id (v) (lookup v env)]
    [fun (bound-id bound-body)
      (lambda (arg-val) 
        (interp bound-body
                (aSub bound-id arg-val env)))] 
    [app (fun-expr arg-expr)
      (local ([define fun-val (interp fun-expr env)]
              [define arg-val (interp arg-expr env)])
        (fun-val arg-val))]))

Figure 11.4: Recursion: Support Code with Procedural Representation of Environments

(define-type RCFAE-Value 
  [numV (n number?)] 
  [closureV (param symbol?)
            (body RCFAE?) 
            (env Env?)])
(define (Env? x) 
  (procedure? x))
(define (mtSub) 
  (lambda (name)
    (error ’lookup ”no binding for identifier”)))
(define (aSub bound-name bound-value env) 
  (lambda (want-name)
    (cond
      [(symbol=? want-name bound-name)
       bound-value] 
      [else (lookup want-name env)])))
(define (cyclically-bind-and-interp bound-name named-expr env) 
  (local ([define rec-ext-env
            (lambda (want-name) 
              (cond
                [(symbol=? want-name bound-name) 
                 (closureV (fun-param named-expr)
                           (fun-body named-expr)
                           rec-ext-env)]
                [else (lookup want-name env)]))])
    rec-ext-env))
(define (lookup name env)
  (env name))

Examples: (From 2010W1 MT#2)

Converting the following function into CPS:

 (define (range i n)
   (if (> i n)
       empty
       (cons i (range (+ i 1) n))))
;; 1) Convert function range to range/k

 (define (range/k i n k)
   (if (> i n)
       empty
       (cons i (range/k (+i 1) n 
                 (lambda () 'todo)))))

 ;; Find the next step(s) to take: empty and (range (+i 1) n)
 ;; empty is a value in tail position, so we just apply the continuation to it.

 (define (range/k i n k)
   (if (> i n)
       (k empty)
       (cons i (range/k (+i 1) n 
                (lambda () 'todo)))))

 ;; (range ...) step is not in tail position.
 ;; Cut it from its current position, and replace it with a placeholder.
 ;; Write it in tail position, and give it an appropriate lambda.

 (define (range/k i n k)
   (if (> i n)
      (k empty)
      (range/k (+i 1) n
        (lambda (r-result)              ; Takes placeholder as parameter
          (cons i (r-result)))))))       ; includes rest of program as body

 ;; Now, we need to continue step 2) from the body of the lambda
 ;; The next step to take is (cons...)
 ;;  We can treat it like a value and apply the continuation to it.

 (define (range/k i n k)
  (if (> i n)
      (k empty)
      (range/k (+i 1) n
        (lambda (r-result)
          (k (cons i (r-result)))))))