UBC Wiki - User contributions [en]

Course:CPSC311/2013WT1

2013-08-29T20:58:44Z

SteveWolfman: /* Handy List of All Our Pages */

== CPSC 311 2013W1: Definition of Programming Languages ==

Programming languages is a challenging course, littered with deep ideas linked in fascinating ways and occasionally shrouded in strange terminology. Therefore, you have this wiki to help each other (and the teaching staff!) keep up with course issues.

Furthermore, we'll have open-book exams, but there's no textbook. So, what are we to do? Well, you make appendices for the midterm, and as long as they're reasonable in length, we'll print them out and provide them with the exam. Obviously, contributing to these would be a Bonus Point Accumulating Activity (i.e., Awesome).

The course wiki is also generally available for anyone to contribute to the class's learning.

You may want to start by looking at [[Course:CPSC311/|previous offerings]].

== Handy List of All Our Pages ==

(Empty so far. How sad!)

<dpl>
titlematch={{PAGENAME}}/%
namespace={{NAMESPACE}}
replaceintitle=$CPSC311/2011WT1/$,
shownamespace=false
</dpl>

[[Category:CPSC]]

Course:CPSC311/2013WT1

2013-08-29T20:58:17Z

SteveWolfman: Creating the course wiki.

== CPSC 311 2013W1: Definition of Programming Languages ==

Programming languages is a challenging course, littered with deep ideas linked in fascinating ways and occasionally shrouded in strange terminology. Therefore, you have this wiki to help each other (and the teaching staff!) keep up with course issues.

Furthermore, we'll have open-book exams, but there's no textbook. So, what are we to do? Well, you make appendices for the midterm, and as long as they're reasonable in length, we'll print them out and provide them with the exam. Obviously, contributing to these would be a Bonus Point Accumulating Activity (i.e., Awesome).

The course wiki is also generally available for anyone to contribute to the class's learning.

You may want to start by looking at [[Course:CPSC311/|previous offerings]].

== Handy List of All Our Pages ==

<dpl>
titlematch={{PAGENAME}}/%
namespace={{NAMESPACE}}
replaceintitle=$CPSC311/2011WT1/$,
shownamespace=false
</dpl>

[[Category:CPSC]]

Course:CPSC311/

2013-08-29T20:54:17Z

SteveWolfman:

CPSC 311 Course Offerings

* [[Course:CPSC311/2013WT1|2013 Winter 1]]
* [[Course:CPSC311/2011WT1|2011 Winter 1]]
* [[Course:CPSC311/2010WT1|2010 Winter 1]]

Course:CPSC311/

2013-08-29T20:53:38Z

SteveWolfman:

CPSC 311 Course Offerings

* [[Course:CPSC311/2013WT1/|2013 Winter 1]]
* [[Course:CPSC311/2011WT1/|2011 Winter 1]]
* [[Course:CPSC311/2010WT1/|2010 Winter 1]]

Course:CPSC311/

2013-08-29T20:53:17Z

SteveWolfman: Index page for CPSC 311

CPSC 311 Course Offerings

* [[Course:CPSC311/2013WT1/][2013 Winter 1]]
* [[Course:CPSC311/2011WT1/][2011 Winter 1]]
* [[Course:CPSC311/2010WT1/][2010 Winter 1]]

Course:CPSC311/2011WT1/Final Exam Appendix

2011-12-09T17:22:37Z

SteveWolfman:

= Final Appendix (Wiki, Student-Generated; credits at end in print version) =

==Formalizing Constraint Generation==
{| class="wikitable"
|-
!Expression at Node !! Generated Constraints
|-
| n, where n is a numeral || [[n]] = number
|-
| true || [[true]]=boolean
|-
| false || [[false]]=boolean
|-
| (add1 e) || [[(add1 e)]]=number [[e]]=number
|-
| (+ e1 e2) || [[(+ e1 e2)]]=number [[e1]] = number [[e2]] = number
|-
| (zero? e) || [[(zero? e)]]=boolean [[e]] = number
|-
| (ncons e1 e2) || [[(ncons e1 e2)]]=list(num) [[e1]] = number [[e2]] = list(num)
|-
| (nﬁrst e) || [[(nﬁrst e)]]=number [[e]] = list(num)
|-
| (nrest e) || [[(nrest e)]]=list(num) [[e]] = list(num)
|-
| (nempty? e) || [[(nempty? e)]]=boolean [[e]] = list(num)
|-
| nempty || [[nempty]]=list(num)
|-
| (if c t e) || [[(if c t e)]]=[[t]] [[(if c t e)]]=[[e]] [[c]]=boolean
|-
| (lambda (x) b) || [[(lambda (x) b)]]= [[x]]→[[b]]
|-
| (f a) || [[f ]] = [[a]]→[[(f a)]]
|}

== Unification Algorithm ==

Begin with an empty substitution. Push all the constraints
onto a stack. If the stack is empty, return the substitution; otherwise, pop the constraint X = Y off the stack:

# If X and Y are identical identiﬁers, do nothing.
# If X is an identiﬁer, replace all occurrences of X by Y both on the stack and in the substitution, and add X 7→ Y to the substitution.
# If Y is an identiﬁer, replace all occurrences of Y by X both on the stack and in the substitution, and add Y 7→ X to the substitution.
# If X is of the form C(X1,...,Xn) for some constructor C, 4 and Y is of the form C(Y1,...,Yn) (i.e., it has the same constructor), then push Xi = Yi for all 1 ≤ i ≤ n onto the stack.
# Otherwise, X and Y do not unify. Report an error

= Midterm 1 Material =
==Multiple Argument Function Conversion Example==
<table>
<tr>
<td>
(with (f (fun (x y z) (+ x y)))
(f 1 2))
</td>
<td>==></td>
<td>
(with (f (fun (x) (fun (y) (fun (z) (+ x y)))))
((f 1) 2)
</td>
</tr>
</table>

== Definitions ==
'''Abstract syntax''' - idealized syntax, designed for convenient use by the underlying interpreter/compiler; result of parsing a concrete syntax expression <br />
'''Concrete syntax''' - syntax written by the user; consumed by the parser <br />
'''Closure''' - a wrapper that contains an expression (function/ binding) and its environment; expression saved until it needs to be used <br />
'''CPS''' stands for Continuation-Passing Style<br />
'''Scope''': a section of the program code, either as it appears in text or during execution <br/>
'''Static Scope:''' a subtree of the abstract syntax tree; an entire expression in the code as it appears in the program text<br />
'''Dynamic Scope:''' a subtree of the dynamic execution tree; all the code which is dynamically evaluated "underneath" (in the stack) a given expression<br />
'''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. <br />
'''Higher-order Functions''' can return other functions as values and take other functions as parameters. <br />
'''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. <br />
'''Deferred Substitution''' 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. To prevent dynamic scoping, use closures to store the environment in which the functions are created<br />
'''Cache calculated substitution''' values are saved the first time they are calculated. Can be implemented by adding a mutable field to thunkVs to store the cached values.

== Eager vs. Lazy Evaluation ==

'''Lazy With'''- we reduce the named expression to a value only when we need to <br />
'''Lazy Functions'''- we do not reduce the argument to a value until necessary<br />
'''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) <br />
'''Eager'''- the named expression is reduced to a value before binding it in the environment. <br />

== Recursion implementation by patching the environment ==

'''Fixed-point of a function:''' a value that, when input to a function, is also output from the function.

interp the bound expression with a fake environment binding, and then patch that binding to point to the result of said interp afterwards using set! mutation. This creates a cyclic environment that addresses the needs of recursion. The cyclicity ensures that there is always "one more binding" for the recursive function
when we need it.

<pre>
(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 false out for the correct value
(interp body new-env))))
</pre>

== Racket syntax and General Examples==
<table>
<tr>
<td>
'''BNF'''
<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>}
</td>
<td>
'''Conditional chains'''
(cond
[(number? v) ...]
[(boolean? v) ...]
[(string? v) ...]
[else false])
</td>
<td>
'''Map''' performs a procedure on all elements of the list in order
(map (lambda (x) (* 2 x)) [1, 2, 3])
outputs [2, 4, 6]
</td>
</tr>
</table>
<table>
<tr>
<td>
'''Pattern matching'''<br>
'...' or '___' means 0 or more<br>
'..n' or '__n" means n or more<br>
'_' matches anything<br>
</td>
<td>
==>
</td>
<td>
(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 data and back-reference it as n
[else (foo)])
</td>
</tr>
</table>
<table>
<tr>
<td>
'''Begin''' evaluate expressions in order. Results are ignored except for that of last expression, which is the evaluated value.
In this case, the side-effect of printing "Hello World" occurs, however the expression overall evaluates to 4.
(begin
(+ 5 2) (printf "Hello World!\n") (+ 3 1))
</td>
<td width="40%">
'''Functions'''<br>
(lambda (x) x) ; first-class value, not used here<br>
(define f (lambda (x) x))<br>
(define (f x) x)<br>
'''Type-case''' is a conditional construct specific to a particular define-type
(type-case WAE expr
[num (n) expr]
...)
</td>
</tr>
</table>

== Racket code specific to implementation of our languages ==
'''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
<table>
<tr>
<td>
'''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?)])
</td>
<td>
'''Strict code''' (from lecture)
(define (strict val)
(if (expV? val)
(strict (interp (expV-exp val) (expV-env val)))
val))
</td>
</tr>
</table>

= Midterm 2 Material =

==State==
* Entails mutation
*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.
** The environment protects static scope while the store tracks the dynamic changes
** The environment maps identifiers to either locations (or values if there is no store) while the store maps locations to values.
*Closures do not remember state as function are to be applied using the state that exists where they are applied.

== Mutability implementation data structures ==
To support mutability in a language, we need two data structures:

'''Environment:''' This is our regular substitution list required to support static scope.
* Maps either:
** Identifiers to values: Makes sense when we are differentiating between mutable and immutable identifiers. If it is immutable, it will simply map to a regular value. If it is mutable, it will map to a boxV value with a store location stored within.
** Identifiers to store locations: ''Only'' store locations are stored within the environment. Thus, even for an immutable value, there is always a two-step lookup: the environment maps the identifier to a store location, and the store maps the store location to a value.
* Identifiers in the environment have ''lexical scope'': a particular environment belongs to a particular expression scope.
'''Store:''' This is where we keep track of dynamic variable values.
* Maps location to a value (which can be a boxV pointing to another location itself).
* The store is "threaded through" the evaluation across sub-expressions.
* Mutation occurs when we change a value in the store.

"Whereas the interpreter employs the same environment for
both arms of an addition, for instance, it cascades the store from one arm to the next and then back out
alongside the resulting 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 behavior 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

==Continuations==
'''What are they?'''
*stack is represented procedurally
*remember only the result and what is left to do (passes the state along or back to caller)
*in the presence of tail call optimization, shifts used space from the stack onto the heap (hard to tell whether a particular program requires more heap space or stack space)
<table border="1">
<th>Why?</th>
<th>Why Not?</th>
<tr>
<td width="38%">
*Saves on memory and computation (ex. tail recursion summation vs augmenting recursion summation)
*A way of simulating continuations in a language that lacks native support (useful for web applications, for instance)
*Makes consumption of stack space explicit; much easier to tell if a function is tail recursive
</td>
<td>
*get rid of machine optimizations by forcing the structure of stack into continuation
*memory wastage if no tail call optimization (so useless frames are retained on stack even though all calls are tail calls)
*need access to the source of entire program (in particular, the caller of every CPS function must be CPS'ed)
*security: what if someone outside knew how to read the stack procedure?
</td>
</tr>
</table>

==Continuation Passing Style (end in /k)==
'''Main Ideas'''
*every function takes an extra argument (its continuation)
*every argument in a function call must be an identifier, a primitive (such as if), or a lambda expression (not a call to a non-primitive function).
*every call is a tail call

'''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".

(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!

'''Example from midterm 2'''<br>
We have the following, and want to convert it to CPS
(assuming (all-pos/k) and (range/k) are correctly implemented,
and represent CPS versions of all-pos and range, respectively:
<table>
<tr>
<td>
(define (test-all-pos)
(if (all-pos (range -5 5))
'fail
'pass))
</td>
<td>
==>
</td>
<td>
(define (test-all-pos/k k)
(range/k -5 5
(lambda (range-result)
(all-pos/k range-result
(lambda (allpos-result)
(k (if allpos-result
'fail
'pass))))))
<td>
<td width="15%">
Note that this assumes '''if''' is a primitive that need not be converted into CPS.
</td>
</tr>
</table>
<table>
<tr>
<td>
(define (map f l)
(if (empty? l)
empty
(cons (f (first l))
(map f (rest l)))))
</td>
<td>
==>
</td>
<td>
(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))))))))
</td>
<td width="15%">
Note that this assumes '''empty, first, rest, and cons''' are all primitives that do not need to be converted.
</td>
</tr>
</table>

==Variables==
<table border="1">
<th>Call-by-value</th>
<th>Call-by-reference</th>
<tr>
<td width=30%>
*evaluated argument is held in a new location,
**Therefore, changes to the content of that location in the store don't affect the actual parameter
</td>
<td>
*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
</td>
</tr>
</table>
<table border="1">
<th>Stateful</th>
<th>Stateless</th>
<tr>
<td>
*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
</td>
<td>
*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
</td>
</tr>
</table>

==Web Programs==
<table>
<tr>
<td width="37%">
'''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
* e.g. lambdas become defines
</td>
<td>
'''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
</td>
</tr>
</table>

==Escaper Lambdas Example==
From assignment 7 (midterm 2 review), we want to describe the continuation of the
bolded expression (namely (* (- x 32) 5) ) below:

(define (fahrenheit-celcius-converter type x)
(case type
['Fahrenheit (/ '''(* (- x 32) 5)''' 9)]
['Celcius (+ 32 (/ (* x 9) 5))]))

(+ (fahrenheit-celcius-converter 'Fahrenheit 32)
(fahrenheit-celcius-converter 'Fahrenheit 212))

We can use escaper lambdas to do this. The continuation of the bolded expression in
the first evaluation of the function is:
(lambda^ (value) (+ (/ value 9) (fahrenheit-celcius-converter 'Fahrenheit 212)))

And the second continuation is: (lambda^ (value) (+ 0 (/ value 9)))

= Post-Midterm 2 Material =

==Lambda Calculus==
Consists of:
*1-parameter functions
*1-argument function applications
*identifiers

Shrinking of a language is achieved by showing that a given component of the language may be replaced by a combination of other components making the component unnecessary. (ex. numbers are unnecessary as they can be represented by a function that represents zero and a successor function) By creating a simplified language it is easier to construct proofs showing that the language has desired properties. (ex. correctly implements tail-call optimization, never accesses an array out of bounds, ...)

Lists:
cons_ = (lambda (f) (lambda (r) (lambda (selector) ((selector f) r))))
head_ = (lambda (p) (p (lambda (f) (lambda (r) f))))
rest_ = (lambda (p) (p (lambda (f) (lambda (r) r))))

Booleans:
if_ = (c t e) ;;only works in lazy eval
if_eager = (c (lambda (d) t) (lambda (d) e)) ;;works in eager
false = (lambda (t f) f)
true = (lambda (t f) t)

e.g. (if false (/1 0) 2)
=> (false (/1 0) 2)
=> ((lambda (t f) f) (/1 0) 2) ;; gets applied to function
=> 2

Representing zero, succession and sum using lambda calculus:
zero_ = (lambda (f) (lambda (x) x))
one_ = (lambda (f) (lambda (x) (f x)))
two_ = (lambda (f) (lambda (x) (f(f x)))) ;; the f's keep on increasing with the number
succ_ = (lambda (n) (lambda (f) (lambda (x) (f ((n f) x))))) ;; apply the function f n times
sum_ = (lambda (m) (lambda (n) ((n succ) m)))
dec_ = (lambda (n) (first ((n (lambda (p) (cons (rest p) (succ (rest p))))) (cons zero zero)))))
sub_ = (lambda (x) (lambda (y) ((y dec_) x)))
mul_ = (lambda (x) (lambda (y) ((x (sum_ y)) zero)))

==Eliminating Recursion==

While reducing the language closer to the lambda calculus, we needed a fixed-point function
to avoid the problem of having unbound errors in recursion definitions (eventually would get
to some expression of the form (f f))

These are the lecture notes that show how we created the fixed-point function and used it in
implementing factorial:
<table>
<tr>
<td>
(define _fixmaker
(lambda (fixmaker)
(lambda (f)
(f (lambda (x) (((fixmaker fixmaker) f) x))))))

;; Then, we'll give it itself:
(define _fix
((lambda (f) (f f))
_fixmaker))

;; Now, we can use fix to define recursive functions:
(define _fac
(_fix (lambda (fac)
(lambda (n)
(((_if (_zero? n))
(lambda (IGNORE) _one))
(lambda (IGNORE) ((_mul n) (fac (_pred n)))))))))
</td>
<td>
Here is the Y-combinator all of its lambadic glory:

(lambda (p)
((lambda (f)
(f f))
(lambda (f)
(p (f f)))))
</td>
</tr>
</table>

==Type Checking==

<table border="1">
<th>Advantages</th>
<th>More Advantages</th>
<th>Disadvantages</th>
<tr>
<td>
'''Safety''': A type checker can guarantee certain errors won't happen in the program before we run it.<br>
'''Readability''': Type declarations give information about the code to a programmer, and is never outdated in a program that compiles (unlike comments). This in itself is a form of '''Documentation.'''<br>
* Exploit types to make programs run faster, use less space, etc
</td>
<td>
'''Efficiency''': Type declarations document static properties at compile time, so we don't have to check them each time code is visited during run time. <br>
*Reduce time spent debugging.<br>
*Catch errors in code that is not executed by the programmer (good if test suite is weak)
* Prohibits certain kinds of terrible coding styles
</td>

<td width="20%">
'''Loses Expressiveness''': some things will never produce errors but can't be type-checked will be rejected.<br>
'''More Work at Start''': upfront work is necessary before runtime testing.
</td>

</tr>
</table>
'''Type''' - any property that can be established without executing the program. Types record kind of value not the precise value

'''A type system''' is that part of a programming language
(definition and implementation) that concerns itself with
making sure that no operations are performed on
inappropriate (types of) arguments.

A language is '''“Type Safe”''' (or just “Safe”) if it has a type
system that ensures that no operations can be performed
on inappropriate arguments without this being detected.
The property of type safety can be achieved by static
checking (=detecting before runtime), dynamic checking
(=detecting at runtime) or a combination of both!

'''Type Judgements''' - Collection of rules. One type rule for every syntactic construct. At least one type rule applies to every sub-term. A type error occurs when we are unable to construct a type judgment tree
* Relation between type judgements for functions and applications:
** Function declaration: assume arg has right type, guarantee that the body will have the promised type
** Function application: guarantee the argument has the right type for function, assume the result will have the type the function promises
<table border="1" width="100%">
<th>Function</th>
<th>Application</th>
<th>Recursion</th>
<tr>
<td align="center"><u>Г[i <- τ1] |- b : τ2</u><br>Г |- fun {i : τ1} : τ2 b} : (τ1 ->τ2</td>
<td align="center"><u>Г |- e1: τ1 -> τ2, Г |- e2: τ1</u><br> Г |- {e1 e2}: τ2 </td>
<td align="center"><u>Г[i <- τi] |- b : τ, Г[i <- τi] |- v : τi</u><br> Г |- {rec {i : τi v} b} : τ</td>
</tr>
</table>

Note: Read "Г |- exp: τ" as "Exp has type τ."

*Type Procedures (^) (polymorphic function)
e.g. map : (for all) a, b. list(a) × (a -> b) -> list(b)

'''Soundness:'''
* Def: A type system is called “type-sound” or simply “sound” iff for every program that passes the type checker and for every possible execution of an expression in that program, it is true that the (runtime) value of that expression is an element of the (static) type of the expression.
* A program '''P''' typechecks without error --> No possible runs of '''P''' have "forbidden errors"
* Typechecker says '''P''' has an error <-- Some possible runs of '''P''' have "forbidden errors"
* Soundness = "The type system gives an F to all invalid programs"
;; this is type sound
(define (type-of exp)
(error "I don't know how to type-check!"))

'''Metavariables''' - Not program variables. Stand in for program text

'''Typing Control'''
* Cannot write an infinitely long type
* Strongly Normalizing: No matter what program you write in a strongly normalized language, it will always terminate
* Typing Recursion: extend the environment for body to initiate recursion, extend again for v to sustain it

* Datatype Variant Tags -- With static type checker, only need to store variant since type is guaranteed by type checker. Better space conception

==Type Inferencing==
* Constraints are generated by traversing the abstract syntax tree and determining what types expressions are required to have by the operations that act with them.

: -> Label expressions & add all constraints for the type of that particular expression
* The unification algorithm is applied on the generated constraints: If the constraints unify a type can be determined for the expression otherwise type inferencing fails on the expression.

==Unification Algorithm==

1. If X and Y are identical identifiers, do nothing.
2. If X is an identifier, replace all occurrences of X by Y both on the stack and in the substitution, and
add X |-> Y to the substitution.
3. If Y is an identifier, replace all occurrences of Y by X both on the stack and in the substitution, and
add Y |-> X to the substitution.
4. If X is of the form C(X1,...,Xn) for some constructor C, and Y is of the form C(Y1,...,Yn) (i.e., it
has the same constructor), then push Xi=Yi for all 1 <= i <= n onto the stack.
5. Otherwise, X and Y do not unify. Report an error.

'''Occurs Check''' - Throw an error if the replacee is in the replacer (ie - recursion)

'''Principal Type''' - Imposes only enough constraints needed for type soundness, and no more

==Explicit Polymorphism==
(define length
< Λ (τ)
(lambda (l : list (τ)) : number
(cond
[(Empty? <τ> l) 0]
[(Cons? <τ> l) (add1 (length <τ> (Rest <τ> l)))]))>)
* The expression (Rest <τ> l) first applies Rest to τ, resulting in an actual rest procedure that applies to lists of values of type τ
* This procedure consumes l as an argument and proceeds as it would in the type system free case
* Every type-parameterized procedure, such as Rest or length, is a generator of infinitely many procedures that each operate on specific types.
* Type Elaborator : The phase that performs type applications.

==Implicit Polymorphism==
* Want to get new identifiers for the ones bound by the closures but not the ones in its lexical scope (lexical scope variables are shared between all applications of the closure). Only get fresh type variable for types introduced by let or letrec
<u>Г|- v : τ' Г[x <- CLOSE(τ', Г)]|- b : τ</u><br>
Г |- (let ([xv])b):τ

* to get fresh type variables:
<u>Г|- e : CLOSE(τ', Г')</u><br>
Г |- e : τ
* where τ is the same as τ', except the renaming applies only to type variables in τ' that are not bound by Г

Course:CPSC311/2011WT1/Final Exam Appendix

2011-12-07T22:35:20Z

SteveWolfman:

'''Do not remove:''' This reference sheet is the appendix for CPSC 311 2011W1 final exam. Only the first 10 printed pages are guaranteed to be printed; so be compact! Deadline for edits: 3PM 8 Dec 2011.

= Final Appendix (Wiki, Student-Generated; credits at end in print version) =

==Formalizing Constraint Generation==
{| class="wikitable"
|-
!Expression at Node !! Generated Constraints
|-
| n, where n is a numeral || [[n]] = number
|-
| true || [[true]]=boolean
|-
| false || [[false]]=boolean
|-
| (add1 e) || [[(add1 e)]]=number [[e]]=number
|-
| (+ e1 e2) || [[(+ e1 e2)]]=number [[e1]] = number [[e2]] = number
|-
| (zero? e) || [[(zero? e)]]=boolean [[e]] = number
|-
| (ncons e1 e2) || [[(ncons e1 e2)]]=list(num) [[e1]] = number [[e2]] = list(num)
|-
| (nﬁrst e) || [[(nﬁrst e)]]=number [[e]] = list(num)
|-
| (nrest e) || [[(nrest e)]]=list(num) [[e]] = list(num)
|-
| (nempty? e) || [[(nempty? e)]]=boolean [[e]] = list(num)
|-
| nempty || [[nempty]]=list(num)
|-
| (if c t e) || [[(if c t e)]]=[[t]] [[(if c t e)]]=[[e]] [[c]]=boolean
|-
| (lambda (x) b) || [[(lambda (x) b)]]= [[x]]→[[b]]
|-
| (f a) || [[f ]] = [[a]]→[[(f a)]]
|}

== Unification Algorithm ==

Begin with an empty substitution. Push all the constraints
onto a stack. If the stack is empty, return the substitution; otherwise, pop the constraint X = Y off the stack:

# If X and Y are identical identiﬁers, do nothing.
# If X is an identiﬁer, replace all occurrences of X by Y both on the stack and in the substitution, and add X 7→ Y to the substitution.
# If Y is an identiﬁer, replace all occurrences of Y by X both on the stack and in the substitution, and add Y 7→ X to the substitution.
# If X is of the form C(X1,...,Xn) for some constructor C, 4 and Y is of the form C(Y1,...,Yn) (i.e., it has the same constructor), then push Xi = Yi for all 1 ≤ i ≤ n onto the stack.
# Otherwise, X and Y do not unify. Report an erro

= Midterm 1 Material =
==Multiple Argument Function Conversion Example==
<table>
<tr>
<td>
(with (f (fun (x y z) (+ x y)))
(f 1 2))
</td>
<td>==></td>
<td>
(with (f (fun (x) (fun (y) (fun (z) (+ x y)))))
((f 1) 2)
</td>
</tr>
</table>

== Definitions ==
'''Abstract syntax''' - idealized syntax, designed for convenient use by the underlying interpreter/compiler; result of parsing a concrete syntax expression <br />
'''Concrete syntax''' - syntax written by the user; consumed by the parser <br />
'''Closure''' - a wrapper that contains an expression (function/ binding) and its environment; expression saved until it needs to be used <br />
'''CPS''' stands for Continuation-Passing Style (a.k.a. Tail Call Elimination)<br />
'''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.<br />
'''Dynamic Scope:''' The scope of an identifier's binding is the entire remainder of the execution during which that binding is in effect. <br />
'''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. <br />
'''Higher-order Functions''' can return other functions as values and take other functions as parameters. <br />
'''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. <br />
'''Deferred Substitution''' 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. To prevent dynamic scoping, use closures to store the environment in which the functions are created<br />
'''Cache calculated substitution''' values are saved the first time they are calculated. By including a 3rd field, that is either false or contains the calculated value

== Eager vs. Lazy Evaluation ==

'''Lazy With'''- we reduce the named expression to a value only when we need to <br />
'''Lazy Functions'''- we do not reduce the argument to a value until necessary<br />
'''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) <br />
'''Eager'''- the named expression is reduced to a value before being substituting it. <br />

== Recursion implementation by patching the environment ==

'''Fixed-point of a function:''' a value that, when input to a function, is also output from the function.

interp the bound expression with a fake environment binding, and then patch that binding to point to the result of said interp afterwards using set! mutation. This creates a cyclic environment that addresses the needs of recursion. The cyclicity ensures that there is always "one more binding" for the recursive function
when we need it.

<pre>
(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 false out for the correct value
(interp body new-env))))
</pre>

== Racket syntax and General Examples==
<table>
<tr>
<td>
'''BNF'''
<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>}
</td>
<td>
'''Conditional chains'''
(cond
[(number? v) ...]
[(boolean? v) ...]
[(string? v) ...]
[else false])
</td>
<td>
'''Map''' performs a procedure on all elements of the list in order
(map (lamda (x) (* 2 x)) [1, 2, 3])
outputs [2, 4, 6]
</td>
</tr>
</table>
<table>
<tr>
<td>
'''Pattern matching'''<br>
'...' or '___' means 0 or more<br>
'..n' or '__n" means n or more<br>
'_' matches anything<br>
</td>
<td>
==>
</td>
<td>
(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 data and back-reference it as n
[else (foo)])
</td>
</tr>
</table>
<table>
<tr>
<td>
'''Begin''' evaluate expressions in order. Results are ignored except for that of last expression, which is the evaluated value.
In this case, the side-effect of printing "Hello World" occurs, however the expression overall evaluates to 4.
(begin
(+ 5 2) (printf "Hello World!\n") (+ 3 1))
</td>
<td width="40%">
'''Functions'''<br>
(lambda (x) x) ; first-class value, not used here<br>
(define f (lambda (x) x))<br>
(define (f x) x)<br>
'''Type-case''' is a conditional construct specific to a particular define-type
(type-case WAE expr
[num (n) expr]
...)
</td>
</tr>
</table>

== Racket code specific to implementation of our languages ==
'''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
<table>
<tr>
<td>
'''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?)])
</td>
<td>
'''Strict code''' (from lecture)
(define (strict val)
(if (expV? val)
(strict (interp (expV-exp val) (expV-env val)))
val))
</td>
</tr>
</table>

= Midterm 2 Material =

==State==
* Entails mutation
*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.
** The environment protects static scope while the store tracks the dynamic changes
** The environment maps identifiers to either locations (or values if there is no store) while the store maps locations to values.
*Closures do not remember state as function are to be applied using the state that exists where they are applied.

== Mutability implementation data structures ==
To support mutability in a language, we need two data structures:

'''Environment:''' This is our regular substitution list required to support static scope.
* Maps either:
** Identifiers to values: Makes sense when we are differentiating between mutable and immutable identifiers. If it is immutable, it will simply map to a regular value. If it is mutable, it will map to a boxV value with a store location stored within.
** Identifiers to store locations: ''Only'' store locations are stored within the environment. Thus, even for an immutable value, there is always a two-step lookup: the environment maps the identifier to a store location, and the store maps the store location to a value.
* Identifiers in the environment have ''lexical scope'': a particular environment belongs to a particular expression scope.
'''Store:''' This is where we keep track of dynamic variable values.
* Maps location to a value (which can be a boxV pointing to another location itself).
* The store is "threaded through" the evaluation across sub-expressions.
* Mutation occurs when we change a value in the store.

"Whereas the interpreter employs the same environment for
both arms of an addition, for instance, it cascades the store from one arm to the next and then back out
alongside the resulting 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

==Continuations==
'''What are they?'''
*stack is represented procedurally
*remember only the result and what is left to do (passes the state along or back to caller)
*roughly the same idea as tail recursion
*A cps function shifts used space from the stack onto the heap (hard to tell whether a particular program requires more heap space or stack space)
<table border="1">
<th>Why?</th>
<th>Why Not?</th>
<tr>
<td width="38%">
*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)
</td>
<td>
*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?
</td>
</tr>
</table>

==Continuation Passing Style (end in /k)==
'''Main Ideas'''
*every function takes an extra argument (its continuation)
*every argument in a function call must be either a variable or a lambda expression (not a more complex expression).
*every call is a tail call

'''Example from midterm 2'''<br>
We have the following, and want to convert it to CPS
(assuming (all-pos/k) and (range/k) are correctly implemented,
and represent CPS versions of all-pos and range, respectively:
<table>
<tr>
<td>
(define (test-all-pos)
(if (all-pos (range -5 5))
'fail
'pass))
</td>
<td>
==>
</td>
<td>
(define (test-all-pos/k k)
(range/k -5 5
(lambda (range-result)
(all-pos/k range-result
(lambda (allpos-result)
(k (if allpos-result
'fail
'pass))))))
<td>
<td width="15%">
Note that this assumes '''if''' is in CPS.
</td>
</tr>
</table>
<table>
<tr>
<td>
(define (map f l)
(if (empty? l)
empty
(cons (f (first l))
(map f (rest l)))))
</td>
<td>
==>
</td>
<td>
(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))))))))
</td>
<td width="15%">
Note that this assumes '''empty, first, rest, and cons''' are all in CPS.
</td>
</tr>
</table>

==Variables==
<table border="1">
<th>Call-by-value</th>
<th>Call-by-reference</th>
<tr>
<td width=30%>
*evaluated argument is held in a new location,
**Therefore, changes to the content of that location in the store don't affect the actual parameter
</td>
<td>
*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
</td>
</tr>
</table>
<table border="1">
<th>Stateful</th>
<th>Stateless</th>
<tr>
<td>
*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
</td>
<td>
*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
</td>
</tr>
</table>

==Web Programs==
<table>
<tr>
<td width="37%">
'''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
* e.g. lambdas become defines
</td>
<td>
'''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
</td>
</tr>
</table>

==Escaper Lambdas Example==
From assignment 7 (midterm 2 review), we want to describe the continuation of the
bolded expression (namely (* (- x 32) 5) ) below:

(define (fahrenheit-celcius-converter type x)
(case type
['Fahrenheit (/ '''(* (- x 32) 5)''' 9)]
['Celcius (+ 32 (/ (* x 9) 5))]))

(+ (fahrenheit-celcius-converter 'Fahrenheit 32)
(fahrenheit-celcius-converter 'Fahrenheit 212))

We can use escaper lambdas to do this. The continuation of the bolded expression in
the first evaluation of the function is:
(lambda^ (value) (+ (/ value 9) (fahrenheit-celcius-converter 'Fahrenheit 212)))

And the second continuation is: (lambda^ (value) (+ 0 (/ value 9)))

= Post-Midterm 2 Material =

==Lambda Calculus==
Consists of:
*1-parameter functions
*1-argument function applications
*identifiers

Shrinking of a language is achieved by showing that a given component of the language may be replaced by a combination of other components making the component unnecessary. (ex. numbers are unnecessary as they can be represented by a function that represents zero and a successor function) By creating a simplified language it is easier to construct proofs showing that the language has desired properties. (ex. correctly implements tail-call optimization, never accesses an array out of bounds, ...)

Representing zero, succession and sum using lambda calculus:
zero_ = (lambda (f) (lambda (x) x)) ;; apply the function f zero times
succ_ = (lambda (n) (lambda (f) (lambda (x) (f ((n f) x))))) ;; apply the function f n times
sum_ = (lambda (m) (lambda (n) ((n succ) m)))

==Eliminating Recursion==

While reducing the language closer to the lambda calculus, we needed a fixed-point function
to avoid the problem of having unbound errors in recursion definitions (eventually would get
to some expression of the form (f f))

These are the lecture notes that show how we created the fixed-point function and used it in
implementing factorial (_mul is multiplication, _pred is predecessor (i.e. "decrement"):
<table>
<tr>
<td>
(define _fixmaker
(lambda (fixmaker)
(lambda (f)
(f (lambda (x) (((fixmaker fixmaker) f) x))))))

;; Then, we'll give it itself:
(define _fix
((lambda (f) (f f))
_fixmaker))

;; Now, we can use fix to define recursive functions:
(define _fac
(_fix (lambda (fac)
(lambda (n)
(((_if (_zero? n))
(lambda (IGNORE) _one))
(lambda (IGNORE) ((_mul n) (fac (_pred n)))))))))
</td>
<td>
Here is the Y-combinator all of its lambadic glory:

(lambda (p)
((lambda (f)
(f f))
(lambda (f)
(p (f f)))))
</td>
</tr>
</table>

==Type Checking==

<table border="1">
<th>Advantages</th>
<th>More Advantages</th>
<th>Disadvantages</th>
<tr>
<td>
'''Safety''': A type checker can guarantee certain errors won't happen in the program before we run it.<br>
'''Readability''': Type declarations give information about the code to a programmer, and is never outdated in a program that compiles (unlike comments). This in itself is a form of '''Documentation.'''<br>
* Exploit types to make programs run faster, use less space, etc
</td>
<td>
'''Efficiency''': Type declarations document static properties at compile time, so we don't have to check them each time code is visited during run time. <br>
*Reduce time spent debugging.<br>
*Catch errors in code that is not executed by the programmer (good if test suite is weak)
* Prohibits certain kinds of terrible coding styles
</td>

<td width="20%">
'''Loses Expressiveness''': some things will never produce errors but can't be type-checked will be rejected.<br>
'''More Work at Start''': upfront work is necessary before runtime testing.
</td>

</tr>
</table>
'''Type''' - any property that can be established without executing the program. Types record kind of value not the precise value

'''A type system''' is that part of a programming language
(definition and implementation) that concerns itself with
making sure that no operations are performed on
inappropriate (types of) arguments.

A language is '''“Type Safe”''' (or just “Safe”) if it has a type
system that ensures that no operations can be performed
on inappropriate arguments without this being detected.
The property of type safety can be achieved by static
checking (=detecting before runtime), dynamic checking
(=detecting at runtime) or a combination of both!

'''Type Judgements''' - Collection of rules. One type rule for every syntactic construct. At least one type rule applies to every sub-term. A type error occurs when we are unable to construct a type judgment tree
* Relation between type judments for functions and applications:
** Function declaration: assume arg has right type, guarantee that the body will have the promised type
** Function application: guarantee the argument has the right type for function, assume the result will have the type the function promises
<table border="1" width="100%">
<th>Function</th>
<th>Application</th>
<th>Recursion</th>
<tr>
<td align="center"><u>Г[i <- τ1] |- b : τ2</u><br>Г |- fun {i : τ1} : τ2 b} : (τ1 ->τ2</td>
<td align="center"><u>Г |- e1: τ1 -> τ2, Г |- e2: τ1</u><br> Г |- {e1 e2}: τ2 </td>
<td align="center"><u>Г[i <- τi] |- b : τ, Г[i <- τi] |- v : τi</u><br> Г |- {rec {i : τi v} b} : τ</td>
</tr>
</table>

*Type Procedures (^) (polymorphic function)
e.g. map : (for all) a, b. list(a) × (a -> b) -> list(b)

'''Soundness:'''
* A program '''P''' typechecks without error --> No possible runs of '''P''' have "forbidden errors"
* Typechecker says '''P''' has an error <-- Some possible runs of '''P''' have "forbidden errors"

'''Metavariables''' - Not program variables. Stand in for program text

'''Typing Control'''
* Cannot write an infinitely long type
* Strongly Normalizing: No matter what program you write in a strongly normalized language, it will always terminate
* Typing Recursion: extend the environment for body to initiate recursion, extend again for v to sustain it

* Datatype Variant Tags -- With static type checker, only need to store variant since type is guaranteed by type checker. Better space conception

==Type Inferencing==
* Constraints are generated by traversing the abstract syntax tree and determining what types expressions are required to have by the operations that act with them.

: -> Label expressions & add all constraints for the type of that particular expression
* The unification algorithm is applied on the generated constraints: If the constraints unify a type can be determined for the expression otherwise type inferencing fails on the expression.

==Unification Algorithm==

1. If X and Y are identical identifiers, do nothing.
2. If X is an identifier, replace all occurrences of X by Y both on the stack and in the substitution, and
add X |-> Y to the substitution.
3. If Y is an identifier, replace all occurrences of Y by X both on the stack and in the substitution, and
add Y |-> X to the substitution.
4. If X is of the form C(X1,...,Xn) for some constructor C, and Y is of the form C(Y1,...,Yn) (i.e., it
has the same constructor), then push Xi=Yi for all 1 <= i <= n onto the stack.
5. Otherwise, X and Y do not unify. Report an error.

'''Occurs Check''' - Throw an error if the replacee is in the replacer (ie - recursion)

'''Principal Type''' - Imposes only enough constraints needed for type soundness, and no more

==Garbage Collection==
Why manual?
1. Automatic GC is a slow and expensive process, therefore let people handle it and only do as much as is necessary.
2. Soundness over completeness -> Automatic GC cannot detect all correct instances of GC (can fail to reclaim, or reclaim too early)

Why not manual?
1. People make mistakes when de-allocating memory.
(i.e. Reclaiming something that is in use, or failing to reclaim unused memory)
2. Loss of structural simplicity
(e.g. multiple versions of the same code that differ only in memory management)
3. Loops often lose tail-calling behaviour

Algorithms for GC:
1. Pointer Counting -> Collect anything with 0 things referencing it (Cyclic Pointers!)
2. Mark and sweep
0) System is low on memory
1) Mark root set as always live, and recursively Mark down any reachable children of root set as live.
2) anything that can't be reached is trash and is Sweeped.

'''GC should demonstrate:'''
* '''Utility:''' - must reclaim enough garbage to actually help computation
* '''Soundness:''' - never reclaim something that is still needed
* '''Efficiency:''' - Run quickly

'''Space Leakage:''' - Collector not reclaiming space that we know is no longer needed (eg. global variables that are no longer needed)

==Explicit Polymorphism==
(define length
< Λ (τ)
(lambda (l : list (τ)) : number
(cond
[(Empty? <τ> l) 0]
[(Cons? <τ> l) (add1 (length <τ> (Rest <τ> l)))]))>)
* The expression (Rest <τ> l) first applies Rest to τ, resulting in an actual rest procedure that applies to lists of values of type τ
* This procedure consumes l as an argument and proceeds as it would in the type system free case
* Every type-parameterized procedure, such as Rest or length, is a generator of infinitely many procedures that each operate on specific types.
* Type Elaborator : The phase that performs type applications.

==Implicit Polymorphism==
* Want to get new identifiers for the ones bound by the closures but not the ones in its lexical scope (lexical scope variables are shared between all applications of the closure). Only get fresh type varaibale for types introduced by let or letrec
<u>Г|- v : τ' Г[x <- CLOSE(τ', Г)]|- b : τ</u><br>
Г |- (let ([xv])b):τ

* to get fresh type variables:
<u>Г|- e : CLOSE(τ', Г')</u><br>
Г |- e : τ
* where τ is the same as τ', except the renaming applies only to type variables in τ' that are not bound by Г

Course:CPSC311/2011WT1/Midterm Exam 2 Appendix

2011-11-09T16:55:19Z

SteveWolfman:

= 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 <br />
'''Concrete syntax''' - syntax written by the user; consumed by the parser <br />
'''Closure''' - a wrapper that contains an expression (function/ binding) and its environment; expression saved until it needs to be used <br />
'''CPS''' stands for Continuation-Passing Style (a.k.a. Tail Call Elimination)<br />

== 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 <br />
'''Lazy Functions'''- we do not reduce the argument to a value until necessary<br />
'''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) <br />
'''Eager'''- the named expression is reduced to a value before being substituting it. <br />

== 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])

<pre>
(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
</pre>

'''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:
#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?)])''
#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:
:# The updated store from the first computation is used for the second computation, while the same environment is used for both computations
:# 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)))))))

Course:CPSC311/2011WT1/Midterm Exam 2 Appendix

2011-11-04T21:00:17Z

SteveWolfman:

'''Do not remove:''' This reference sheet is the appendix for CPSC 311 2011W1 midterm exam #2. Only the first 8 printed pages are guaranteed to be printed; so be compact! Deadline for edits: Tue 8 Nov @ 11:59PM (generally ~24 hours before the exam).

Course:CPSC311/2011WT1/Midterm Exam 1 Appendix

2011-10-05T21:14:25Z

SteveWolfman: Prepping for printing.

= 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}))

Course:CPSC311/2011WT1/Midterm Exam 1 Appendix

2011-09-28T20:57:55Z

SteveWolfman:

'''Do not remove:''' This reference sheet is the appendix for CPSC 311 2011W1 midterm exam #1. Only the first 4 printed pages are guaranteed to be printed; so be compact! Deadline for edits: Tue 4 Oct at 9PM.

Course:CPSC311/2011WT1/Assignment 3 Gotchas

2011-09-01T03:47:11Z

SteveWolfman:

(Not clear yet that our Assignment #3 will be Haskell this year, but just in case..)

* Installing [http://haskell.org/hugs/ Hugs98] on Windows 7 (and Windows Vista?), you need to run as administrator (right-click and choose "Run as Administrator").
** The error I got was a failure to extract the file hugs98.chm --[[User:SteveWolfman|SteveWolfman]] 20:47, 31 August 2011 (PDT)
* If you run out of memory, you can increase Hug's memory by going to Options> Runtime

Course:CPSC311/2011WT1/Assignment 3 Gotchas

2011-08-16T17:41:05Z

SteveWolfman: Created page with "(Initialized with last year's content.) If you run out of memory, you can increase Hug's memory by going to Options> Runtime"

(Initialized with last year's content.)

If you run out of memory, you can increase Hug's memory by going to Options> Runtime

Course:CPSC311/2011WT1/Assignment 1 Gotchas

2011-08-16T17:40:09Z

SteveWolfman: Created page with "(Initializing with last year's content.) == Assignment #1 Gotchas for Everyone == * Don't kill yourself giving lovely errors on malformed input on this assignment. It's not re..."

(Initializing with last year's content.)

== Assignment #1 Gotchas for Everyone ==

* Don't kill yourself giving lovely errors on malformed input on this assignment. It's not required.
* The IDE (DrRacket) does not automatically save your code when ran. Save manually (and often, as the debugger likes to crash).

== Assignment #1 Gotchas for New Racketeers ==

* Focus on the guide (http://docs.racket-lang.org/guide/) to learn new elements of Racket and the general docs (http://docs.racket-lang.org/) for reference
* Don't forget to put <code>#lang plai</code> at the top of your file (or have it added automatically)

== PLAI/Racket Gotchas for Experienced Schemers ==

* <code>()</code> is '''''not''''' the empty list in Racket. Use <code>'()</code> or <code>empty</code> instead.

== Other Stuff ==

* You can access the fields of a type with a <code>type-case</code> expression, but for small accesses (like the <code>Binding</code> type), try either writing your own reusable access method that uses <code>type-case</code> or the built-in accessors based on the ''type constructor'' names, not the type's names, like: <code>binding-name</code> (lowercase like the type constructor, not uppercase like the type) and <code>binop-lhs</code> (though you'll probably want <code>type-case</code> for that one).

Course:CPSC311/2011WT1/Glossary

2011-08-16T17:38:31Z

SteveWolfman: Created page with "==Definitions== (Initialized from last year's content.) ===Data-type=== (in terms of the Racket language) Introduces a new data-type (an "algebraic" or "variant data type"). ..."

==Definitions==

(Initialized from last year's content.)

===Data-type===
(in terms of the Racket language)

Introduces a new data-type (an "algebraic" or "variant data type"). Search the Racket docs for more info: http://docs.racket-lang.org/search/index.html?q=data-type.

An explanation of how define-type works, from another course: [http://wiki.cs.grinnell.edu/mediawiki/index.php/CSC_302:_define-type CSC_302:_define-type]

===WAE===

One of the PLAI languages we'll work with: a "with arithmetic expression". In other words, an arithmetic expression that can use "with" statements in order to bind identifiers (names) to values. We also use this as the name of the type used to represent our abstract syntax tree. As defined in the PLAI textbook: [http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/plai-2007-04-26.pdf#page=32 pg 32]

===F1WAE===

A language supporting only first-order functions (functions that must be called by their defined name and so cannot be passed as parameters, returned as results, or constructed as values).

===CFWAE===

A language extending FWAE (which has first-class functions implemented using closures) to support conditionals.

Course:CPSC311/2011WT1/Handy Links

2011-08-16T17:37:33Z

SteveWolfman: Created page with "(Initialized with last year's content.) = Racket = * [http://planet.plt-scheme.org/display.ss?package=json.plt&owner=dherman Racket JSON] * [http://planet.plt-scheme.org/package..."

(Initialized with last year's content.)

= Racket =
* [http://planet.plt-scheme.org/display.ss?package=json.plt&owner=dherman Racket JSON]
* [http://planet.plt-scheme.org/package-source/dherman/json.plt/3/0/planet-docs/json/index.html Racket JSON documentation]
* [http://docs.racket-lang.org/web-server/templates.html Racket web templates:]

= Haskell =
* [http://learnyouahaskell.com/making-our-own-types-and-typeclasses Good Haskell tutorial]

Course:CPSC311/2011WT1/Midterm Exam 2 Appendix

2011-08-16T17:36:32Z

SteveWolfman:

'''Do not remove:''' This reference sheet is the appendix for CPSC 311 2011W1 midterm exam #2. Only the first 6 printed pages are guaranteed to be printed; so be compact! Deadline for edits: TO BE ANNOUNCED (generally ~24 hours before the exam).

Course:CPSC311/2011WT1/Final Exam Appendix

2011-08-16T17:36:21Z

SteveWolfman: Created page with "'''Do not remove:''' This reference sheet is the appendix for CPSC 311 2011W1 final exam. Only the first 10 printed pages are guaranteed to be printed; so be compact! Deadline ..."

Course:CPSC311/2011WT1/Midterm Exam 2 Appendix

2011-08-16T17:35:59Z

SteveWolfman: Created page with "'''Do not remove:''' This reference sheet is the appendix for CPSC 311 2011W1 midterm exam #1. Only the first 6 printed pages are guaranteed to be printed; so be compact! Deadl..."

'''Do not remove:''' This reference sheet is the appendix for CPSC 311 2011W1 midterm exam #1. Only the first 6 printed pages are guaranteed to be printed; so be compact! Deadline for edits: TO BE ANNOUNCED (generally ~24 hours before the exam).

Course:CPSC311/2011WT1/Midterm Exam 1 Appendix

2011-08-16T17:35:29Z

SteveWolfman: Created page with "'''Do not remove:''' This reference sheet is the appendix for CPSC 311 2011W1 midterm exam #1. Only the first 4 printed pages are guaranteed to be printed; so be compact! Deadl..."

Course:CPSC311/2011WT1

2011-08-16T17:33:36Z

SteveWolfman: Initialized page from 2010W1

== CPSC 311 2011W1: Definition of Programming Languages ==

Programming languages is a challenging course, littered with deep ideas linked in fascinating ways and occasionally shrouded in strange terminology. Therefore, you have this wiki to help each other (and the teaching staff!) keep up with course issues.
The course wiki is available for anyone to contribute to the class's learning. It's also a great way to earn some bonus points.

Feel free to add useful possible content to this list. Currently based off of last year.. but surely we can do better than last year! :P

* Exam Appendices
** [[Course:CPSC311/2011WT1/Midterm Exam 1 Appendix | Midterm #1 Appendix]]: fill it in, we'll print it for the exam! Maybe start from [[Course:CPSC311/2010WT1/Midterm Exam 1 Appendix]]?
** [[Course:CPSC311/2011WT1/Midterm Exam 2 Appendix | Midterm #2 Appendix]]: fill it in, we'll print it for the exam! Maybe start from [[Course:CPSC311/2010WT1/Midterm Exam 2 Appendix]]?
** [[Course:CPSC311/2011WT1/Final Exam Appendix | Final Appendix]]: fill it in, we'll print it for the exam! Maybe start from [[Course:CPSC311/2010WT1/Final Exam Appendix]]?
* A repository of people's [[Course:CPSC311/2011WT1/Lecture Notes | Lecture Notes]]. Post yours to pay it forward, in case you miss class and want to catch up!
* A collection of [[Course:CPSC311/2011WT1/Handy Links | Handy Links]] to help you find course-related info.
* Our very own [[Course:CPSC311/2011WT1/Glossary | Glossary]] of the many terms we'll run into.
* [[Course:CPSC311/2011WT1/Assignment 1 Gotchas | Assignment #1 Gotchas]], pesky things that might trip you up on rudimentary interpreters
* [[Course:CPSC311/2011WT1/Assignment 2 Gotchas | Assignment #2 Gotchas]], pesky things that might trip you up on extended interpreters
* [[Course:CPSC311/2011WT1/Assignment 3 Gotchas | Assignment #3 Gotchas]], pesky things that might trip you up as you get lazy

== Handy List of All Our Pages ==

<dpl>
titlematch={{PAGENAME}}/%
namespace={{NAMESPACE}}
replaceintitle=$CPSC311/2011WT1/$,
shownamespace=false
</dpl>

[[Category:CPSC]]

Course:CPSC311/2010WT1/Final Exam Appendix

2010-12-08T06:45:35Z

SteveWolfman:

Do not remove: This reference sheet is the appendix for the CPSC 311 2010W1 Final Exam. Only the first 10 printed pages are guaranteed to be printed; so be compact! Deadline for edits: 0900 Monday 20 December.

= Final Appendix (Wiki, Student-Generated; credits at end in print version) =

= Midterm 1 Material (copied from MT2 appendix) =

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

== 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 <br />
'''Lazy Functions'''- we do not reduce the argument to a value until necessary<br />
'''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) <br />
'''Eager'''- the named expression is reduced to a value before being substituting it. <br />

== 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])

<pre>
(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
</pre>

'''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 (copied from MT2 appendix) =

==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))))))))

Course:CPSC311/2010WT1/Final Exam Appendix

2010-12-08T06:28:34Z

SteveWolfman:

= Final Appendix (Wiki, Student-Generated; credits at end in print version) =

= Midterm 1 Material (copied from MT2 appendix) =

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

== 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 <br />
'''Lazy Functions'''- we do not reduce the argument to a value until necessary<br />
'''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) <br />
'''Eager'''- the named expression is reduced to a value before being substituting it. <br />

== 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])

<pre>
(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
</pre>

'''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 (copied from MT2 appendix) =

==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))))))))

Course:CPSC311/2010WT1/Final Exam Appendix

2010-12-08T06:27:16Z

SteveWolfman:

= Final Appendix (Wiki, Student-Generated; credits at end) =

= Midterm 1 Material (copied from MT2 appendix) =

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

== 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 <br />
'''Lazy Functions'''- we do not reduce the argument to a value until necessary<br />
'''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) <br />
'''Eager'''- the named expression is reduced to a value before being substituting it. <br />

== 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])

<pre>
(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
</pre>

'''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 (copied from MT2 appendix) =

==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))))))))

Course:CPSC311/2010WT1/Final Exam Appendix

2010-12-08T06:26:28Z

SteveWolfman: Created page with '= Final Appendix (Wiki, Student-Generated; credits at end) = = Midterm 1 and 2 Material (copy of MT2 appendix) = == Definitions == '''Abstract syntax''' - idealized syntax, de…'

= Final Appendix (Wiki, Student-Generated; credits at end) =

= Midterm 1 and 2 Material (copy of MT2 appendix) =

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

== 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 <br />
'''Lazy Functions'''- we do not reduce the argument to a value until necessary<br />
'''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) <br />
'''Eager'''- the named expression is reduced to a value before being substituting it. <br />

== 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])

<pre>
(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
</pre>

'''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))))))))

Course:CPSC311/2010WT1

2010-12-08T06:24:59Z

SteveWolfman:

== CPSC 311 2010W1: Definition of Programming Languages ==

Programming languages is a challenging course, littered with deep ideas linked in fascinating ways and occasionally shrouded in strange terminology. Therefore, you have this wiki to help each other (and the teaching staff!) keep up with course issues.
The course wiki is available for anyone to contribute to the class's learning. It's also a great way to earn some bonus points.

Feel free to add useful possible content to this list:

* Exam Appendices
** [[Course:CPSC311/2010WT1/Midterm Exam 1 Appendix | Midterm #1 Appendix]]: fill it in, we'll print it for the exam!
** [[Course:CPSC311/2010WT1/Midterm Exam 2 Appendix | Midterm #2 Appendix]]: fill it in, we'll print it for the exam!
** [[Course:CPSC311/2010WT1/Final Exam Appendix | Final Appendix]]: fill it in, we'll print it for the exam!
* A repository of people's [[Course:CPSC311/2010WT1/Lecture Notes | Lecture Notes]]. Post yours in case you miss class and want to catch up!
* A collection of [[Course:CPSC311/2010WT1/Handy Links | Handy Links]] to help you find course-related info.
* Our very own [[Course:CPSC311/2010WT1/Glossary | Glossary]] of the many terms we'll run into.
* [[Course:CPSC311/2010WT1/Assignment 1 Gotchas | Assignment #1 Gotchas]], pesky things that might trip you up on rudimentary interpreters
* [[Course:CPSC311/2010WT1/Assignment 2 Gotchas | Assignment #2 Gotchas]], pesky things that might trip you up on extended interpreters
* [[Course:CPSC311/2010WT1/Assignment 3 Gotchas | Assignment #3 Gotchas]], pesky things that might trip you up as you get lazy

== Handy List of All Our Pages ==

<dpl>
titlematch={{PAGENAME}}/%
namespace={{NAMESPACE}}
replaceintitle=$CPSC311/2010WT1/$,
shownamespace=false
</dpl>

[[Category:CPSC]]

Course:CPSC311/2010WT1/Midterm Exam 2 Appendix

2010-11-02T22:52:36Z

SteveWolfman:

Course:CPSC311/2010WT1/Midterm Exam 2 Appendix

2010-11-02T22:51:38Z

SteveWolfman:

= 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 <br />
'''Concrete syntax''' - syntax written by the user; consumed by the parser <br />
'''Closure''' - a wrapper that contains an expression (function/ binding) and its environment; expression saved until it needs to be used <br />
'''CPS''' stands for Continuation-Passing Style (a.k.a. Tail Call Elimination)<br />

== 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 <br />
'''Lazy Functions'''- we do not reduce the argument to a value until necessary<br />
'''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) <br />
'''Eager'''- the named expression is reduced to a value before being substituting it. <br />

== 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])

<pre>
(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
</pre>

'''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))))))))

Course:CPSC311/2010WT1/Midterm Exam 2 Appendix

2010-11-02T22:51:26Z

SteveWolfman:

= Midterm 2 Appendix (Wiki, Student-Generated) =

= 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 <br />
'''Concrete syntax''' - syntax written by the user; consumed by the parser <br />
'''Closure''' - a wrapper that contains an expression (function/ binding) and its environment; expression saved until it needs to be used <br />
'''CPS''' stands for Continuation-Passing Style (a.k.a. Tail Call Elimination)<br />

== 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 <br />
'''Lazy Functions'''- we do not reduce the argument to a value until necessary<br />
'''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) <br />
'''Eager'''- the named expression is reduced to a value before being substituting it. <br />

== 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])

<pre>
(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
</pre>

'''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))))))))

Course:CPSC311/2010WT1/Midterm Exam 2 Appendix

2010-10-27T20:06:01Z

SteveWolfman:

'''Do not remove:''' This reference sheet is the appendix for CPSC 311 2010W1 midterm exam #2. Only the first 6 printed pages are guaranteed to be printed; so be compact! Deadline for edits: 2000 Monday 1 November.

= 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

== 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
[Condition1 Result1]
[Condition2 Result2]
....
[ConditionN ResultN])

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

<pre>
(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
</pre>

'''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))

Course:CPSC311/2010WT1/Midterm Exam 2 Appendix

2010-10-27T20:04:27Z

SteveWolfman: Created page with ''''Do not remove:''' This reference sheet is the appendix for CPSC 311 2010W1 midterm exam #2. Only the first 6 printed pages are guaranteed to be printed; so be compact! Deadl…'

Course:CPSC311/2010WT1

2010-10-27T20:03:44Z

SteveWolfman: /* CPSC 311 2010W1: Definition of Programming Languages */

== CPSC 311 2010W1: Definition of Programming Languages ==

Programming languages is a challenging course, littered with deep ideas linked in fascinating ways and occasionally shrouded in strange terminology. Therefore, you have this wiki to help each other (and the teaching staff!) keep up with course issues.
The course wiki is available for anyone to contribute to the class's learning. It's also a great way to earn some bonus points.

Feel free to add useful possible content to this list:

* Exam Appendices
** [[Course:CPSC311/2010WT1/Midterm Exam 1 Appendix | Midterm #1 Appendix]]: fill it in, we'll print it for the exam!
** [[Course:CPSC311/2010WT1/Midterm Exam 2 Appendix | Midterm #2 Appendix]]: fill it in, we'll print it for the exam!
* A repository of people's [[Course:CPSC311/2010WT1/Lecture Notes | Lecture Notes]]. Post yours in case you miss class and want to catch up!
* A collection of [[Course:CPSC311/2010WT1/Handy Links | Handy Links]] to help you find course-related info.
* Our very own [[Course:CPSC311/2010WT1/Glossary | Glossary]] of the many terms we'll run into.
* [[Course:CPSC311/2010WT1/Assignment 1 Gotchas | Assignment #1 Gotchas]], pesky things that might trip you up on rudimentary interpreters
* [[Course:CPSC311/2010WT1/Assignment 2 Gotchas | Assignment #2 Gotchas]], pesky things that might trip you up on extended interpreters
* [[Course:CPSC311/2010WT1/Assignment 3 Gotchas | Assignment #3 Gotchas]], pesky things that might trip you up as you get lazy

== Handy List of All Our Pages ==

<dpl>
titlematch={{PAGENAME}}/%
namespace={{NAMESPACE}}
shownamespace=false
</dpl>

[[Category:CPSC]]

Course:CPSC311/2010WT1/Midterm Exam 1 Appendix

2010-10-07T17:46:44Z

SteveWolfman:

= 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

= 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
[Condition1 Result1]
[Condition2 Result2]
....
[ConditionN ResultN])

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

<pre>
(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
</pre>

'''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))

Course:CPSC311/2010WT1/Midterm Exam 1 Appendix

2010-10-07T17:45:50Z

SteveWolfman:

'''Do not remove:''' This reference sheet is the appendix for CPSC 311 2010W1 midterm exam #1. Only the first 4 printed pages are guaranteed to be printed; so be compact! Deadline for edits: 2000 Wednesday 6 October.

= 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

= 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
[Condition1 Result1]
[Condition2 Result2]
....
[ConditionN ResultN])

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

<pre>
(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
</pre>

'''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))

Course:CPSC311/2010WT1/Glossary

2010-10-05T19:11:04Z

SteveWolfman: /* CFWAE */

==Definitions==

===Data-type===
(in terms of the Racket language)

Introduces a new data-type (an "algebraic" or "variant data type"). Search the Racket docs for more info: http://docs.racket-lang.org/search/index.html?q=data-type.

An explanation of how define-type works, from another course: [http://wiki.cs.grinnell.edu/mediawiki/index.php/CSC_302:_define-type CSC_302:_define-type]

===WAE===

One of the PLAI languages we'll work with: a "with arithmetic expression". In other words, an arithmetic expression that can use "with" statements in order to bind identifiers (names) to values. We also use this as the name of the type used to represent our abstract syntax tree. As defined in the PLAI textbook: [http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/plai-2007-04-26.pdf#page=32 pg 32]

===F1WAE===

A language supporting only first-order functions (functions that must be called by their defined name and so cannot be passed as parameters, returned as results, or constructed as values).

===CFWAE===

A language extending FWAE (which has first-class functions implemented using closures) to support conditionals.

Course:CPSC311/2010WT1/Glossary

2010-10-05T19:10:39Z

SteveWolfman: /* F1WAE */

Course:CPSC311/2010WT1/Midterm Exam 1 Appendix

2010-10-04T20:28:15Z

SteveWolfman:

'''Do not remove:''' This reference sheet is the appendix for CPSC 311 2010W1 midterm exam #1. Only the first 4 printed pages are guaranteed to be printed; so be compact! Deadline for edits: 2000 Wednesday 6 October.

= 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.

'''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, 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.

= 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

'''Eager'''- the named expression is reduced to a value before being substituting it.

= Racket syntax, helpful procedures, and thoughts =

(cond
[Condition1 Result1]
[Condition2 Result2]
....
[ConditionN ResultN])

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

<pre>
(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
</pre>

'''Variable definition:'''
(define x 3)

'''Function definition:'''
(define (funcName arg)
(+ 1 arg))

'''map''' performs a procedure on all elements of the list in order
(define (parseList list)
(map parse list))

Course:CPSC311/2010WT1/Midterm Exam 1 Appendix

2010-09-27T21:13:54Z

SteveWolfman:

'''Do not remove:''' This reference sheet is the appendix for CPSC 311 2010W1 midterm exam #1. Only the first 4 printed pages are guaranteed to be printed; so be compact! Deadline for edits: 2000 Wednesday 6 October.

= Static vs. Dynamic Scoping =

= Closures and First-Class vs. First-Order Functions =

= Racket syntax, helpful procedures, and thoughts =

Course:CPSC311/2010WT1/Midterm Exam 1 Appendix

2010-09-27T21:10:57Z

SteveWolfman: Created page with '= CPSC 311 2010W1 Midterm Exam #1 Reference Sheet = '''Do not remove:''' This reference sheet is the appendix for CPSC 311 2010W1 midterm exam #1. Only the first 4 printed page…'

= CPSC 311 2010W1 Midterm Exam #1 Reference Sheet =

'''Do not remove:''' This reference sheet is the appendix for CPSC 311 2010W1 midterm exam #1. Only the first 4 printed pages are guaranteed to be printed; so be compact! Deadline for edits: 2000 Wednesday 6 October.

Course:CPSC311/2010WT1

2010-09-27T21:08:33Z

SteveWolfman: /* CPSC 311 2010W1: Definition of Programming Languages */

== CPSC 311 2010W1: Definition of Programming Languages ==

Programming languages is a challenging course, littered with deep ideas linked in fascinating ways and occasionally shrouded in strange terminology. Therefore, you have this wiki to help each other (and the teaching staff!) keep up with course issues.
The course wiki is available for anyone to contribute to the class's learning. It's also a great way to earn some bonus points.

Feel free to add useful possible content to this list:

* Exam Appendices
** [[Course:CPSC311/2010WT1/Midterm Exam 1 Appendix | Midterm #1 Appendix]]: fill it in, we'll print it for the exam!
* A repository of people's [[Course:CPSC311/2010WT1/Lecture Notes | Lecture Notes]]. Post yours in case you miss class and want to catch up!
* A collection of [[Course:CPSC311/2010WT1/Handy Links | Handy Links]] to help you find course-related info.
* Our very own [[Course:CPSC311/2010WT1/Glossary | Glossary]] of the many terms we'll run into.
* [[Course:CPSC311/2010WT1/Assignment 1 Gotchas | Assignment #1 Gotchas]], pesky things that might trip you up on rudimentary interpreters
* [[Course:CPSC311/2010WT1/Assignment 2 Gotchas | Assignment #2 Gotchas]], pesky things that might trip you up on extended interpreters
* [[Course:CPSC311/2010WT1/Assignment 3 Gotchas | Assignment #3 Gotchas]], pesky things that might trip you up as you get lazy

== Handy List of All Our Pages ==

<dpl>
titlematch={{PAGENAME}}/%
namespace={{NAMESPACE}}
shownamespace=false
</dpl>

[[Category:CPSC]]

Course:CPSC311/2010WT1/Lecture Notes/2010-09-13/NNek

2010-09-14T16:14:23Z

SteveWolfman:

== CPSC 311 September 13 2010 ==

<pre>
(define-type OpMapping
[opMapping (op symbol?) (impl procedure?)])

(opMapping '+ +)

Racket is cool. Why? Functions can be passed as values, second thing is that Racket Data looks like Racket programs, or vice versa

Concrete Syntax: (+ 5 7) == 5 + 7 == (5 7 +)

Abstract Syntax, a single way to represent the different forms of concrete syntax, generally forms trees

Statement, executes next statement after executing itself

Expression, returns a value (in Racket, expressions are functions)

Normally: Lexer (text) -> (tokens) Parser (abstract syntax tree) -> Interpreter (value)

<nowiki>
Useful for checking for errors on tests:

(define (failed-tests)
(reverse (filter (lambda (x) (not (symbol=? (first x) 'good))) plai-all-test-results)))</nowiki>

Alt-p previous, alt-n next

Case, checks a symbol, cond checks a condition
</pre>

Course:CPSC311/2010WT1/Lecture Notes/2010-09-13/NNek

2010-09-14T16:13:49Z

SteveWolfman:

== CPSC 311 September 13 2010 ==

<pre>
(define-type OpMapping
[opMapping (op symbol?) (impl procedure?)]
)
(opMapping ‘+ +)

Racket is cool. Why? Functions can be passed as values, second thing is that Racket Data looks like Racket programs, or vice versa

Concrete Syntax: (+ 5 7) == 5 + 7 == (5 7 +)

Abstract Syntax, a single way to represent the different forms of concrete syntax, generally forms trees

Statement, executes next statement after executing itself

Expression, returns a value (in Racket, expressions are functions)

Normally: Lexar (text) -> Parser (tokens) (abstract syntax tree) -> Interpreter (value)

<nowiki>
Useful for checking for errors on tests:

(define (failed-tests)
(reverse (filter (lambda (x) (not (symbol=? (first x) 'good))) plai-all-test-results)))</nowiki>

Alt-p previous, alt-n next

Case, checks a symbol, cond checks a condition
</pre>

Course:CPSC311/2010WT1/Lecture Notes/2010-09-10/NNek

2010-09-14T16:13:26Z

SteveWolfman:

== CPSC 311 September 10 2010 ==

<pre>
Redefining an existing function shadows the old one

Lambda: introduces a function without a name, becomes a function value

<nowiki>ie:
(define (only-pos lon)
(filter (lambda (num) ( > num 0)) lon))</nowiki>

‘(num) does not work, as it will return the list (num)

If statement:
(cond
[boolean-expr result-expr]
[]
[]
[else ])

(cons 1 2) gives (1 . 2), why does our cons work? Because we are always appending a listof numbers as the second argument.
</pre>

Course:CPSC311/2010WT1/Lecture Notes

2010-09-14T03:35:29Z

SteveWolfman:

== Lecture Notes ==

Perhaps a format like this would work well?

* 2010-09-08
** [[Course:CPSC311/2010WT1/Lecture Notes/2010-09-08/Steve | Steve's notes]]
* 2010-09-10
** [[Course:CPSC311/2010WT1/Lecture Notes/2010-09-10/NNek | NNek's Notes]]
* 2010-09-13
** [[Course:CPSC311/2010WT1/Lecture Notes/2010-09-13/NNek | NNek's notes]]

Course:CPSC311/2010WT1/Lecture Notes/2010-09-10/Steve

2010-09-14T03:34:58Z

SteveWolfman: moved Course:CPSC311/2010WT1/Lecture Notes/2010-09-10/Steve to Course:CPSC311/2010WT1/Lecture Notes/2010-09-10/NNek: Attribute to author.

#REDIRECT [[Course:CPSC311/2010WT1/Lecture Notes/2010-09-10/NNek]]

Course:CPSC311/2010WT1/Lecture Notes/2010-09-10/NNek

2010-09-14T03:34:58Z

SteveWolfman: moved Course:CPSC311/2010WT1/Lecture Notes/2010-09-10/Steve to Course:CPSC311/2010WT1/Lecture Notes/2010-09-10/NNek: Attribute to author.

CPSC 311 September 10 2010

Redefining an existing function shadows the old one

Lambda: introduces a function without a name, becomes a function value

<nowiki>ie:
(define (only-pos lon)
(filter (lambda (num) ( > num 0)) lon))</nowiki>

‘(num) does not work, as it will return the list (num)

If statement:
(cond
[boolean-expr result-expr]
[]
[]
[else ])

(cons 1 2) gives (1 . 2), why does our cons work? Because we are always appending a listof numbers as the second argument.

Course:CPSC311/2010WT1/Lecture Notes/2010-09-13/Steve

2010-09-14T03:34:28Z

SteveWolfman: moved Course:CPSC311/2010WT1/Lecture Notes/2010-09-13/Steve to Course:CPSC311/2010WT1/Lecture Notes/2010-09-13/NNek: Attribute to notes author.

#REDIRECT [[Course:CPSC311/2010WT1/Lecture Notes/2010-09-13/NNek]]

Course:CPSC311/2010WT1/Lecture Notes/2010-09-13/NNek

2010-09-14T03:34:28Z

SteveWolfman: moved Course:CPSC311/2010WT1/Lecture Notes/2010-09-13/Steve to Course:CPSC311/2010WT1/Lecture Notes/2010-09-13/NNek: Attribute to notes author.

CPSC 311 September 13 2010

(define-type OpMapping
[opMapping (op symbol?) (impl procedure?)]
)
(opMapping ‘+ +)

Racket is cool. Why? Functions can be passed as values, second thing is that Racket Data looks like Racket programs, or vice versa

Concrete Syntax: (+ 5 7) == 5 + 7 == (5 7 +)

Abstract Syntax, a single way to represent the different forms of concrete syntax, generally forms trees

Statement, executes next statement after executing itself

Expression, returns a value (in Racket, expressions are functions)

Normally: Lexar (text) -> Parser (tokens) (abstract syntax tree) -> Interpreter (value)

<nowiki>
Useful for checking for errors on tests:

(define (failed-tests)
(reverse (filter (lambda (x) (not (symbol=? (first x) 'good))) plai-all-test-results)))</nowiki>

Alt-p previous, alt-n next

Case, checks a symbol, cond checks a condition

Course:CPSC311/2010WT1/Glossary

2010-09-13T22:23:45Z

SteveWolfman: /* Data-type */

==Definitions==

===WAE===

One of the PLAI languages we'll work with: a "with arithmetic expression". In other words, an arithmetic expression that can use "with" statements in order to bind identifiers (names) to values. We also use this as the name of the type used to represent our abstract syntax tree. (A link into the textbook would be handy; someone want to splice it in? Syntax for links into PDFs available on the notes page of the website.)

===Data-type===
(in terms of the Racket language)

Introduces a new data-type (an "algebraic" or "variant data type"). Search the Racket docs for more info: http://docs.racket-lang.org/search/index.html?q=data-type.

Course:CPSC311/2010WT1/Glossary

2010-09-13T22:21:57Z

SteveWolfman: /* WAE */