Sample Final 3

Date: Wednesday, April 23rd

Name:

Administrative

This exam was given last semester.

Question	Grade
(1) Scheme Programming		/24
(2) Language Extension: Extending Scheme		/24
(3) The TOY Language		/24
(4) Programming in Lazy Scheme		/24
(5) SLUG & Type System		/24
*Total*		/120

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

24 pts

As we have seen, statically-typed languages have several significant advantages. One way to gain some of these advantages in a dynamically typed language like Scheme is to use dynamically-checked contracts. The idea is to wrap functions so that input arguments are checked, and the resulting value is also checked (in case the function itself is buggy). Here is an example for doing this manually to get a contracted add function:

;; add : Number Number -> Number ;; adds two numbers, with manually constructed contract checking (define (add x y) (unless (number? x) (error 'add "bad input: ~s" x)) (unless (number? y) (error 'add "bad input: ~s" y)) (let ([result (+ x y)]) ; <-- this is the actual function body (unless (number? result) (error 'add "bad output: ~s" result)) result))

(One of the main points in contract checking is proper blame assignment. Note that in this code, errors due to bad inputs blames whoever called add, and in the last error add's own implementation is blamed.)
To make this easier, write a contract-binfun function that does the wrapping. For example, to bind add to a function equivalent to the above using this function:

(define add (contract-binfun 'add ; name for error messages number? number? ; inputs number? ; output (lambda (x y) (+ x y)) ; the actual function ))

Note that contract-binfun work only for binary functions.
Remember to write proper contract (in the usual comment) and purpose statement for your definition.

Question 2: Language Extension: Extending Scheme

24 pts

The contract functionality is very useful, but using a wrapper function is verbose enough to make it awkward to write and to read. We can use a macro definition to make it simpler, and the main benefit is that a more concise syntax will be close enough to a definition in a statically typed language that there will be no need for a contract line comment. Also, it will be easy to make it work for function with any number of arguments.
To do this, you should write a cdefine syntax definitions to use for definitions of contracted functions. (Note that such definitions work only for function definitions.) For example, here is the definition of a contratced add, resulting in the same function as in the previous question:

(cdefine (add [x : number?] [y : number?]) : number? (+ x y))

Implement the cdefine syntax. Note that the ‘:’s in this expression are literal keywords. Also note that the resulting macro should work for definitions with any number of arguments.

Question 3: The TOY Language

24 pts

In several occasions during the course we discussed features that we implement versus features that we inherit from Scheme. Consider the TOY evaluator (which was extended in Assignment #7 to include a recursive binder form). We're going to investigate how it deals with tail calls.

The first question to ask is whether TOY is doing tail-call optimization like Scheme. Suggest an expression that can test that. (Write the expression, and the expected behavior if TOY is doing tail-call optimization and the behavior otherwise.)
Is TOY optimizing tail-calls? (In other words, how would you expect the above test to go?)
If you think that TOY is optimizing tail-calls, explain how it achieves that: is it done explicitly, or is it MzScheme's behavior that we inherit?
If you think that it is not optimizing tail-calls, explain why that happens.
In both cases, you should use the code at the end of the exam for your answer. Any kind of answer should be strictly based on that code.

Question 4: Programming in Lazy Scheme

24 pts

As we have seen, macros can be useful in a lazy language too. Although less necessary than in an eager language (since controlling evaluation is not an issue), we saw that it is still useful for new binding forms (like new looping constructs, or implementing the do syntax in SLUG).
Consider plain (eager) Scheme for a moment: the way we achieve laziness in Scheme is by wrapping code in a thunk (a nullary function). In fact, we discussed Scheme's delay form, which was implemented as a macro, and using a thunk to delay evaluation of a piece of code.
The question is: assuming that we get define-syntax in Lazy Scheme, can we implement the mirrored feature — a strict special form — using only a macro definition? Provide such a definition if you think it is possible, otherwise explain why it is impossible.

In an attempt to test that this strict feature is working as it should (which is possible regardless of the implementation technique), your friend Bob tries the following expressions:

(strict (+ 1 2)) (+ 1 (strict (* 3 4))) (define (foo x) (* 2 (strict (+ x 1))))

You explain to him that these tests are bogus — they don't show that strict is doing what it should do, because you could simply define it as a procedure that satisfies these tests:

(define (bad-strict x) x) ; works for the above tests.

Write an expression that uses such a strict special form that demonstrates that it is, indeed, doing strict evaluation. Your expression should have a (strict something) subexpression, and evaluating the expression with just something should result in a different behavior.

Question 5: SLUG & Type System

24 pts

The SLUG extensions that were done in Assignment #9 included an IO facility, which works by building IO descriptions rather than performing IO operations. We have seen that side-effect-related functionality in a strict world have corresponding parts in the lazy IO-description world. An example for a side-effect construct in (eager) Scheme is a one-sided if, which makes sense only when it is used with a side-effect; for example:

(if (< x 100) (printf "Too small"))

The implicit ‘else’ branch in this case is a no-op. Our SLUG extension did not include such a no-op, but it is easy to define one. For this, complete the missing parts in the followiong SLUG code:

{bind {{no-op missing₁}} ; the no-op definition {fun {x} ; a function that should use no-op {if {< x 100} {print "Too small"} missing₂}}}

(Hint: this is very easy.)

A (static) type system is just as useful (and maybe even more) in a lazy language than it is in an eager language. This is particularly true when we deal with IO descriptions. For example, this would be the typing judgement for a print expression in a typed version of SLUG:

Γ |- x : String Γ |- {print x} : IO

Write similar judgements for begin2 and for read.

The Basic TOY Implementation

The following is the core of the extended TOY implementation from Assignment #7, to be used in the TOY question.

;; eval-body : (Listof TOY) ENV -> VAL
;; evaluates a list of expressions, return the last value.
(define (eval-body exprs env)
  (if (null? exprs)
    (error 'eval-body "got an empty body")
    (let ([1st-value   (eval (first exprs) env)]
          [other-exprs (rest exprs)])
      (if (null? other-exprs)
        1st-value
        (eval-body other-exprs env)))))

;; eval : TOY env -> VAL
;; evaluates TOY expressions.
(define (eval expr env)
  (cases expr
    [(Num n) (ScmV n)]
    [(Id v) (unbox (lookup v env))]
    [(Bind names exprs bound-body)
     (eval-body bound-body
                (extend names
                        (map (lambda (e) (eval e env)) exprs)
                        env))]
    [(BindRec names exprs bound-body)
     (eval-body bound-body (extend-rec names exprs env))]
    [(Fun names bound-body)
     (FunV names bound-body env)]
    [(RFun names bound-body)
     (RFunV names bound-body env)]
    [(Call fun-expr arg-exprs)
     (let ([fval (eval fun-expr env)]
           ;; delay the evaluation of the arguments (use if needed)
           [arg-vals (lambda ()
                       (map (lambda (e) (eval e env)) arg-exprs))])
       (cases fval
         [(PrimV proc) (proc (arg-vals))]
         [(FunV names body fun-env)
          (eval-body body (extend names (arg-vals) fun-env))]
         [(RFunV names body fun-env)
          (if (andmap Id? arg-exprs)
            (let ([boxes (map (lambda (id) (lookup (Id-name id) env))
                              arg-exprs)])
              (eval-body body (extend-boxes names boxes fun-env)))
            (error 'eval "ref-functions expect only identifiers"))]
         [else (error 'eval "function call with a non-function: ~s"
                      fval)]))]
    [(If cond-expr then-expr else-expr)
     (eval (if (cases (eval cond-expr env)
                 [(ScmV v) v] ; Scheme value => use as boolean
                 [else #t])   ; other values are always true
             then-expr
             else-expr)
           env)]
    [(Set id expr)
     ;; note the use of two expressions in this branch
     (set-box! (lookup id env) (eval expr env))
     bogus]))

;; run : String -> Any
;; evaluate a TOY program contained in a string
(define (run str)
  (let ([result (eval (parse str) global-environment)])
    (cases result
      [(ScmV v) v]
      [else (error 'run
                   "evaluation returned a bad value: ~s" result)])))