Sample Final 1Date: Monday, April 26th | |
| |
AdministrativeThis exam was given in the Spring semester of 2008.
| |
| |
Remember: the correct answers are short. Also, questions that ask for a
verbal answer rather than code should still be answered correctly and
based on facts.
Question 1: Scheme Programming | 15 pts |
As you now know, lexical scope can be used as a form of security. For
example, the following program demonstrates using a closure as a
check,where a bank account is represented as a box holding a number:
(define-type Account = (Boxof Number))
(: make-check : Account Number -> (-> Void))
;; Creates a closure for withdrawing a given amount of money from the
;; account.
(define (make-check account amount)
(lambda () (set-box! account (- (unbox account) amount))))
;; Example of using a check object:
(let ([my-account (box 1000)])
(your-function (make-check my-account 100))) |
The security aspect of this code is that your-function can now
modify my-account, but only by subtracting a fixed amount from it.
There is a major problem in this piece of code: the “check” closure
can be called multiple times — which is clearly a flaw in any
reasonable banking system! To fix this, write a higher-order function
called one-shot that consumes a nullary function (one with a type of
(-> Void)) and returns a new nullary function that can be used at
most one time. The resulting thunk will work just like the input when
used for the first time, but throw an error if it is used again. Using
your definition, make-check would be fixed as follows:
(: make-check : Account Number -> (-> Void))
;; Creates a closure for withdrawing a given amount of money from the
;; account.
(define (make-check account amount)
(one-shot (lambda ()
(set-box! account (- (unbox account) amount))))) |
Remember to write a proper type and purpose statement.
Question 2: Language Extension: Extending Scheme | 20 pts |
In many cases, a new macro definition in Scheme has exactly one syntax rule
and no keywords. For example, we’ve seen the following definition in
class:
(define-syntax orelse
(syntax-rules ()
[(orelse <expr1> <expr2>)
(let ((temp <expr1>))
(if temp temp <expr2>))])) |
This would be simpler if there was a way to write a definition that looks
more like a function definition:
(define-syntax-rule (orelse <expr1> <expr2>)
(let ((temp <expr1>))
(if temp temp <expr2>))) |
This is actually possible: it can be implemented as a macro. Implement the
define-syntax-rule macro. (Note that it is a macro that defines
macros!)
Question 3: Language Features: Macros | 25 pts |
A common misconception is that a facility such as define-syntax-rule
can conveniently replace define whenever you want an inlined function.
There are, however, multiple problems with this. For each of the following
pieces of code, describe the problem that you would get if define was
replaced by define-syntax-rule or vice versa. (Remember: short
descriptions!)
(define (fact n)
(if (= n 0) 1 (* n (fact (sub1 n)))))
(fact 5) |
(define-syntax-rule (twice expr)
(begin expr expr))
(twice (printf "Hey!\n")) |
(define (diagonal x)
(let ([x (* x x)])
(sqrt (+ x x))))
(diagonal 1) |
(define-syntax-rule (do-list x list body)
(for-each (lambda (x) body) list))
(do-list x '(1 2 3) (printf "x = ~s\n" x)) |
(define (square x)
(* x x))
(map square '(1 2 3)) |
Question 4: The Beehive Language | 15 pts |
As shown in class, lazy languages are particularly relevant for parallel
computing: the lack of side-effects mean that we are free to force
promises in any order and also in parallel. Related to this, it is
simple to take a lazy language implementation such as our Sloth
language, and modify it so expressions are all evaluated in parallel.
To do this, the first thing we need is some primitive functionality for
threads. In PLT Scheme we have two functions for this:
(: thread : (-> Void) -> Thread)
;; (thread thunk) starts a new thread that runs the given
;; thunk, and returns a thread descriptor. The return value of
;; the thread is ignored (so its type is specified as `Void').
(: thread-wait : Thread -> Void)
;; (thread-wait thread) consumes a thread descriptor and
;; waits for it to terminate. |
We will create a new ‘Beehive’ language based on the call-by-need version
of the Sloth language — the one that caches promise results. Using this
version of Sloth as a basis is going to make a Beehive implementation very
easy, a few local changes to the code is all we need. (The relevant
portion of the Sloth code is attached to the exam.)
We begin by modifying promises to hold a thread descriptor for the
running computation:
(define-type VAL
...
[ExprV (expr SLOTH) (env ENV)
(thread Thread) (cache (Boxof (U #f VAL)))]) |
There are only two places that deal with ExprV promises:
eval-promise creates them, and strict forces them. Both
definitions will need to be modified (and the rest of the code stays the
same, modulo changing SLOTH to BEEHIVE). Begin with the new
eval-promise implementation — write the missing expression in the
following definition:
;; eval-promise : BEEHIVE env -> VAL (the ExprV variant)
;; used instead of `eval' to create an evaluation promise
(define (eval-promise expr env)
(let ([b (box #f)])
(ExprV expr env (thread ???) b))) |
(Hint: the threaded code is where the evaluation result is computed and
stored in the box.)
The last change is to the strict function. It will be quite simple:
all you need to do is wait for the thread to finish its work, and pull
out the computed result. (Note that the computations are initiated in
eval-promise, so there is no use of eval in this function.) Be
careful when you do this: the evaluation might have had an error, and in
that case the thread will be done, but you will find no value in the
box!
Question 5: Language Features: Beehive | 20 pts |
- On one hand, our our Beehive language is not a lazy
(call-by-need) language. Explain why.
- On the other hand, it is very close to a lazy language. For
example, consider IO. Explain (briefly!).
Question 6: Type System | 20 pts |
The following is the beginning of a simple extension for the Picky language
definition with a new Integer type. Only the grammar is extended:
there is a new <int> terminal that stands for integer numerals (and
<num> is for other numbers), and there is a new Integer syntax for
types.
<PICKY> ::= <num>
| <int>
| <id>
| { fun { <id> : <TYPE> } : <TYPE> <PICKY> }
| { + <PICKY> <PICKY> }
| { call <PICKY> <PICKY> }
<TYPE> ::= Number
| Integer
| ( <TYPE> -> <TYPE> )
Γ |- n : Number
Γ |- x : Γ(x)
Γ |- a : Number Γ |- b : Number
Γ |- {+ a b} : Number
Γ[x:=τ1] |- E : τ2
Γ |- {fun {x : τ1} : τ2 E} : (τ1 -> τ2)
Γ |- f : (τ1 -> τ2) Γ |- v : τ1
Γ |- {call f v} : τ2 |
The real work is, of course, in extending the type rules. We need to add
three more rules. The first one is an axiom that specifies that numbers
that use an integer syntax have the Integer type:
(This is assuming that i stands for an <int> syntax.)
The next two rules to add are
- A subtyping rule: it should make it possible to use
integers where numbers are expected. In other words, it
should say that every integer is also a number.
- A rule for integer addition. (Without such a rule, we
cannot write an addition expression that is typed as an
Integer.)
Write these two rules.
The Core SLOTH Implementation
The following is the core of the cached SLOTH implementation from class.