CSSE 304 Day 27
Return graded exam
Add set! to our interpreter
Copyright By PowCoder代写 加微信 powcoder
Warm-up for call/cc
Escape procedures
Exam 2 format
Exam 2 is Tuesday evening
Three parts:
Written part (estimate: 25-35 points)
Computer part, non-interpreter problem(s) (estimate: 10-20 points)
Comp. part, interpreter problem(s) (estimate: 25-40 points)
25 out of 100 points are for the E&C part.
Potential Topics for Exam 2
environments and closures diagrams (done)
programming with lists (and nested lists)
grammars (and code that follows the grammar)
processing s-lists
procedural abstraction (list-recur, sn-list-recur, etc.)
curried procedures, procedures that return procedures
mutation (set!, set-car!, set-cdr!)
persistent data (OO-approach, and memoization)
case-lambda
define-syntax difference between syntactic extension & procedure definition)
abstract data types: interface, representation & implementation
Abstract data types, representation-independence, define-datatype and cases
free & bound variable occurrences, lexical address
Parsing, working with parsed expressions
Enhance interpreter (you need to bring your working interpreter code)
(Not until final exam) Continuations, write code in CPS
(final) Multi-value returns (values, call-with-values, with-values, mvlet)
Show that you are a good programmer/problem solver.
If you have questions old about exam solutions, ask them on Piazza so everyone can see the conversation.
I don’t have to try to make the exam difficult.
With this list of topics, I have to try hard to keep it from being impossible!
One more thing …
One more thing that is necessary for success on exam 2:
You must be a good programmer/problem solver and be reasonably fast at it
Should have been true before you got to this course
Doing the HW should have enhanced your skills
IMO: A student who understands the concepts but cannot apply them to new situations is a C student.
What kinds of exam grades does a C student in this class have?
The one thing to avoid:
A call to a substantial procedure in a non-tail position.
apply-k is a substantial procedure; make-k is not.
Whenever you get an answer without doing a substantial call, call apply-k.
Ask “what happens next”, and put it on the outside of the remaining code, with later things “inside”, as part of the continuation.
If you think the continuation of a recursive call should be (lambda(v) v), there’s a good chance that your code is not actually in tail form.
Regardless of what the server says, no credit if code is not in tail form
Interpreter Next Step
Add set! to the interpreted language
Binding vs. Assignment
A binding creates a new name and associated value.
In Scheme, accomplished by define, let, letrec, or application of a closure
An assignment changes the value of a variable an existing binding.
set!, or top-level define of an already-defined variable.
Add set! to the interpreter
r-values vs l-values
x = x + 1;
We need a way of changing the value of a bound variable
Why doesn’t the current setup support this?
How can we fix this?
Recap: Add set! to the interpreter
ADT approach: Add a new environment observer:
(apply-env-ref env var) returns a reference to the variable in question.
(deref ref) gets the value stored in the location that is referenced by ref.
(set-ref! ref value) changes the value stored there
If we have apply-env-ref, then apply-env does not have to be a basic operation of the environment datatype:
(define apply-env
(lambda (env var)
(deref (apply-env-ref env var))))
but it may be more efficient to implement apply-env directly (in a representation-dependent way).
Recap: Implementing set!
Once we have references, it is easy.
A new clause for eval-exp’s cases:
[set!-exp (id exp)
(apply-env-ref env id)
(eval-exp exp env))]
All that is left to do is to implement references!
(we’ll look at multiple approaches)
Recap: Implementing apply-env-ref, deref, set-ref!, extend-env
Use a cell abstract data type.
(cell value) creates a cell containing the value.
(cell-ref cell) gives us the value in the cell.
(cell-set! cell value) replaces the value in the cell.
(cell? obj) asks if an object is a cell.
Use these to implement references.
First step: In the extend-env implementation, replace vals with (map cell vals)
(define cell (lambda (val) (cons val ‘this-is-a-cell)))
(define cell-ref car)
(define cell-set! set-cdr!)
(define cell? (lambda (c) (and (pair? c) (eq? (cdr c) ‘this-is-a-cell))))))
A summary of the ADTs that we have so far:
Environment
(empty-env)
(extend-env vars vals env)
(apply-env env id)
(apply-env-ref env id)
(deref ref)
(set-ref! ref val)
(cell val)
(cell-ref cell)
(set-cell! cell val)
(cell? obj)
We use references to implement the new environment interface.
We use cells to implement references within an environment.
Now we need to implement cells.
representation? code?
(define cell (lambda (x) (cons x ‘this-is-a-cell)))
Write the names of the four procedures on the board before leaving this slide.
Implementing the cell ADT
Use define-datatype.
Use a pair for each cell.
Use box data type .
See the Users Guide
Cell ADT Box implementation
(cell value) (box value)
(cell? obj) (box? obj)
(cell-ref cell) (unbox cell)
(cell-set! cell value) (set-box! cell value)
A17: You will add set! to your interpreter
Can we do mutation in other ways?
Alternative using the ribcage with vectors approach to environment implementation
See the ribcage diagram on next slide.
A reference is a datatype whose fields are a vector and an index. I recommend that you investigate this one.
deref is implemented using vector-ref
set-ref! is implemented using vector-set!
A“normal” memory model . . .
A single vector for all vaues
A reference is an index (an address)
Allocation and Garbage Collection?
Give students a few minutes to do this one
Mutation solution: Uses the ribcage implementation of environments.
Top-level define
Note that define and set! do very different things
dynamic global environment vs static local environments
Should local environments extend the global environment?
If you do it, be careful!
If you do it, I do not want to help you with debugging that requires tracing!
Warm-up for call/cc
Escape procedures
call/cc involves both receivers and escape
procedures, so we look at both of those first
What we’ll do today and next time is loosely based the book Scheme and the Art of Programming by and .
A receiver is an argument (which happens to also be a procedure) passed to a procedure, with the intention that the procedure will eventually pass values to that receiver.
Example: The continuations that we pass to CPS procedures are receivers.
Sometimes receivers are called “callbacks”
Old Receiver Example:
call-with-values
> (call-with-values
(lambda () (values 3 4))
list is a receiver
(we previously called it the consumer)
new receiver example
(call-with-output-file “myfile.ss”
(lambda (p) ; this is the “receiver”
(let f ([ls list-to-be-printed])
(if (not (null? ls))
(write (car ls) p)
(newline p)
(f (cdr ls)))))))
From TSPL: The following shows the use of call-with-output-file to write a list of objects (the value of list-to-be-printed), separated by newlines, to the file named by “myfile.ss.”
(define call-with-output-file
(lambda (filename proc)
(let ((p (open-output-file filename)))
(let ((v (proc p)))
(close-output-port p)
The receiver expects to receive an output port as its argument
Review of Continuations
Consider the evaluation of the expression:
(let ([x (+ y 2)])
(if (< x 4) 5 (- x 6))
What is the continuation of
(+ y 2) ? 6 ?
(- x 6) ? (< x 4) ?
I plan to go slow. Please don't let anything go over your head today. We can revisit anything!
An escape procedure
Suppose that we have a procedure escape-+ that adds its arguments and returns this sum as the final answer, no matter what the context.
(* (escape‑+ 5 6) 3)
(escape-+ (escape-+ 2 4) 5)
We can say that escape-+ ignores the current continuation, or "escapes from" the current continuation.
Answers: 11, 6
Escaper (a mostly fictitious procedure)
More generally, suppose that we have a procedure escaper that takes a procedure as an argument and returns an equivalent escape procedure.
(escaper +) creates a procedure that is equivalent to escape-+
(+ 3 ((escaper +) 4 5))
(+ ((escaper (lambda (x)
(- (* x 3) 7)))
4)
Answers: 9, 8
If you want to experiment with escaper, you can define it by
loading escaper.ss in the following way:
escaper.ss is linked from the schedule page
C:\Users\anderson>cd C:\SVN\304\www\Resources
C:\SVN\304\www\Resources>petite escaper.ss
Petite Version 9.5
Copyright 1984-2017 Cisco Systems, Inc.
> ((call/cc receiver-4))
escaper is defined
> (cdr ((escaper cdr) ‘(4 5 6)))
You can experiment with escaper
Escape Procedures
Let p be a procedure. If an application of p abandons the current continuation and does something else instead, we call p an escape procedure.
An example of a Scheme escape procedure that we have already used:
Is escaper an escape procedure?
Answers: error, exit
/docProps/thumbnail.jpeg
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com