AdministrativeThis exam was given in the Fall semester of 2012. |
| ||||||||||||||||||||||||||||
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.
Implement a delayed function that receives an arbitrary unary function f, and a (non-empty) list of appropriate inputs xs, and produces a delayed version d. During the creation of d, f should be called on each of the given inputs, and the list of results should be remembered as a “buffer”. From now on, whenever the resulting d is called, it will call f on that value and save it at the end of the buffer but return and remove the first value in it. An example will clarify this better:
(define f1 (delayed add1 '(0))) (test (f1 10) => 1) (test (f1 20) => 11) (test (f1 30) => 21) (define f2 (delayed list '(x y z))) (test (f2 'a) => '(x)) (test (f2 'b) => '(y)) (test (f2 'c) => '(z)) (test (f2 'd) => '(a)) (test (f1 40) => 31) |
Note that you must use a proper type (f can have any kind of input and output). In addition, using append to implement a queue is usually not a good idea since it’s inefficient, but don’t worry about this in your implementation.
We want to extend the Picky language with a new type: pairs. This requires adding three new forms — pair to create a pair, and fst and snd to access it:
<PICKY> ::= <num>
| <id>
| ...
| {pair E1 E2}
| {fst E}
| {snd E} |
Extend the type judgments with three rules for these — use x for a pair, as in A x B. Note that pair is a syntax in code, and x is a syntax in types — just like fun and -> respectively.
(You can assume that you’re extending the rules in the PICKY3 source code, though for this question it doesn’t matter which version you use.)
Now that we have the type judgments in place, we need to continue and implement the new functionality. We do this as an extension of the PICKY3 source code (and it does matter here).
The usual bits are easy:
eval({pair E1 E2},env) = pair(eval(E1,env), eval(E2,env))
eval({fst E},env) = fst(eval(E,env))
eval({snd E},env) = snd(eval(E,env)) |
(define-type PICKY [Num Number] ... [Pair PICKY PICKY] [Fst PICKY] [Snd PICKY]) |
(define (parse-sexpr sexpr)
(match sexpr
[(number: n) (Num n)]
...
[(list 'pair l r) (Pair (parse-sexpr l) (parse-sexpr r))]
[(list 'fst x) (Fst (parse-sexpr x))]
[(list 'snd x) (Snd (parse-sexpr x))]
[else (error 'parse-sexpr
"bad expression syntax in ~s" sexpr)])) |
(define-type VAL [NumV Number] [BoolV Boolean] [FunV Symbol PICKY ENV] [PairV VAL VAL]) |
(define (eval expr env)
(cases expr
[(Num n) (NumV n)]
...
[(Pair l r) (PairV (eval l env) (eval r env))]
[(Fst p)
(let ([v (eval p env)])
(cases v
[(PairV l r) l]
[else (error 'eval "`fst' expects a pair, got: ~s" v)]))]
[(Snd p)
(let ([v (eval p env)])
(cases v
[(PairV l r) r]
[else (error 'eval "`snd' expects a pair, got: ~s" v)]))])) |
Now that the evaluator is properly extended, we need to implement the interesting bits — making the type checker deal with pairs. There are three places that need to be extended.
As we’ve seen, there are similarities between the CPS conversion that we used for the implementation of the web language and our encoding of side-effects in a lazy language. One way to make this similarity concrete would be to implement similar functionality to our addition server in the Slug lazy language, using its IO encoding.
To do this, consider the continuation-based web reading function from class (only using read-line instead of read):
(define (web-read/k prompt k)
(set-box! what-next
(lambda ()
(printf "~a: " prompt)
(k (read-line))))
(error 'web-read/k "enter (resume) to continue")) |
(define (execute-read receiver)
(execute-receiver receiver read-line))
(define (execute-receiver receiver producer)
(cases receiver
[(FunV names body env)
(execute-val
(eval body (extend names (list (wrap-in-val (producer))) env)))]
[else (error 'execute-receiver "expecting a receiver function")])) |
(define (execute-read receiver)
(cases receiver
[(FunV names body env)
(execute-val
(eval body (extend names (list (wrap-in-val (read-line))) env)))]
[else (error 'execute-receiver "expecting a receiver function")])) |
Now, to demonstrate the similarity, you need to show how execute-read can be modified so it works in a stateless environment such as a web server. Re-write it, assuming that you have the same what-next global box. You can ignore the prompt for this question.
When we discussed continuations, we have implemented a DSL that has continuations by a CPS transformation. We did this formally via a CPS macro that did the transformation, and a CPS-code macro that used it to convert a complete program. (See CPS-LANGUAGE for these macros.)
One feature that is obviously missing is a conditional. Extend this DSL by adding a conversion rule for if expressions.
Another important feature that is missing from our CPS language is functions of any arity. Dealing with functions of any arity is going to be difficult, so instead, you’ll just extend the language to allow functions (and function calls) of two arguments in addition to unary ones. Note that these are still just user-defined functions and calls to them.
You need to do three things:
Note that where you add the new cases in the two macros can be important, so for a solution, you should write the full definitions of the two macros. Don’t forget that this is an extension that is added to the one from the last question, so make sure that your answer includes your if case too.
In the following questions choose the single best answer (unless told otherwise).
(CPS-code (define (f x) (g x))
(define (g x) (+ 10 x))
(f 1)) |
Dealing with functions of any arity is going to be difficult [...]What makes it difficult?