Course:CPSC311/2011WT1/Midterm Exam 1 Appendix
Definitions
Abstract syntax - idealized syntax, designed for convenient use by the underlying interpreter/compiler; result of parsing a concrete syntax expression; carries more semantic structure than the concrete syntax (which is usually a simpler structure like a string of tokens or a tree of s-expressions)
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
Binding instance - a binding instance of an identifier is the instance of the identifier that gives it its value. In WAE, the <id> position of a with is the only binding instance
Bound instance - an identifier is bound if it is contained within the scope of a binding instance of its name
Free instance - an identifier not contained in the scope of any binding instance of its name is said to be free
Substitution - to substitue identifier i in e with expression v, replace all free instances of i in e with v
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 means that substitutions are accumulated in a repository called the environment. Initially, we have no substitutions to perform, so the environment is empty. Every time we encounter a substitution (in the form of a with or application), we augment the environment 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, the function being applied needs to be evaluated so that its argument may be substituted and its body evaluated)
Eager- all expressions that need to be evaluated are evaluated as soon as they are encountered; expressions are never wrapped up and reduced to a value in the future. In particular, substitutions are evaluated when the substitution is made and not when the substituted identifier is evaluated.
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>}
Objectives of Functions
- Encapsulate and re-use code (defer evaluation of the function body)
- Parameterize behaviour over dynamic context (take parameters)
- Be opaque to the dynamic context, "close over" the static context (analogous to building a wall to block dynamic context, but having a window that allows the parameters to be passed in to "close over" the static context)
Racket syntax & helpful procedures
(cond [Condition1 Result1] [Condition2 Result2] .... [ConditionN ResultN])
(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
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?)])
Substitution
(define (sub-all-free-instances-of sub-id expr repl)
(type-case WAE expr
[num (n) expr]
[add (l r) (add (sub-all-free-instances-of sub-id l repl)
(sub-all-free-instances-of sub-id r repl))]
[sub (l r) (sub (sub-all-free-instances-of sub-id l repl)
(sub-all-free-instances-of sub-id r repl))]
[with (this-id named-e body)
(if (symbol=? sub-id this-id)
(with this-id
(sub-all-free-instances-of sub-id named-e repl)
body)
(with this-id
(sub-all-free-instances-of sub-id named-e repl)
(sub-all-free-instances-of sub-id body repl)))
]
[id (name)
(if (symbol=? name sub-id)
repl
expr)]
))
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))))
))
Examples of using functions
(run '{{fun {x y z} {- {- x y} z}} 2 3 4})
(run '{if0 (+ 5 -5) 0 1})
(run '{with {double {fun {x} {/ x x}}} {double 10}})
(pre-process(parse '{{fun {x y z} {- {- x y} z}} 2 3 4}))