Sample Midterm 3Date:   Tuesday, October 9th

Administrative

This is a sample midterm that was given in the 2017 fall semester.

QuestionGrade 
(1) Stateful Racket Programming /20
(2) Fill in the blanks /15
(3) BNF Grammar /15
(4) Structural Recursion with ASTs /20
(5) Extending the FLANG Language /20
(6) Schlac /20
(7) Language Features /15
Total /125

Question 1. Stateful Racket Programming20 pts

In class, we have seen how closures can be used to implement objects, possibly with local state. Here’s an example for such an implementation of a “bank account” object. Note that we ignore types in this question, and also note how withdraw! is implemented using deposit!:

(define (make-account)
  (define money (box 0))
  (define (account msg)
    (match msg
      ['balance
      (unbox money)]
      [(list 'deposit! amt)
      (set-box! money (+ (unbox money) amt))]
      [(list 'withdraw! amt)
      (deposit! account (- amt))]))
  account)
;; method definitions
(define (balance act) (act 'balance))
(define (deposit!  act amt) (act (list 'deposit!  amt)))
(define (withdraw! act amt) (act (list 'withdraw! amt)))

;; tests
(define a (make-account))
(define b (make-account))
(test (balance a) => 0)
(test (balance b) => 0)
(deposit!  a 100)
(deposit!  b 1000)
(deposit!  a 20)
(withdraw! b 100)
(test (balance a) => 120)
(test (balance b) => 900)

Go over this code and make sure you understand how it works.

We want to extend the functionality of these bank account objects: introduce “sub accounts” that are tied to a parent account. This can be done in a number of ways – we’ll shoot for a simple implementation: add two more methods for creating a sub-account and for transferring money from a parent account to a child account. Here are the “method” definitions:

(define (make-sub act) (act 'make-sub))
(define (transfer! from to amt) (from (list 'transfer! to amt)))

You need three additions to the above code to make this work:

You can write only the two new match cases for the new messages, and for the state you can write just the required definition IF you also write EXACTLY where it should be added.

To make things clear, here are some additional tests that can be added to the existing list of tests:

(define a1 (make-sub a))
(transfer! a a1 50)
(test (balance a1) => 50)
(test (balance a ) => 70)
(test (transfer! a b 10) =error> "can only transfer to a sub-account")

Question 2. Fill in the blanks15 pts

For each one of the following expressions, write a definition for blank in Racket that makes the expression evaluate to 660. For example, a correct answer for this expression:

(* (blank) 2)

is:

(define blank (lambda () 330))

If you think that it is impossible to write such a definition, explain why this is the case. Remember: this is Racket, not Schlac or FLANG, or any other language that we’ve seen. In other words, assume a language of #lang pl. More accurately, unless explicitly asked, assume a #lang pl untyped — the language that doesn’t do any type checking — so you do not need to write types. Also, assume NO MUTATION is allowed.

(Note: you’re doing the “filling-in” via a definition of blank, not with some literal substitution.)

Do this for the following expressions.

a. (blank 6 6 0)

b. (blank (lambda (x) blank))

c. ((second (blank)))

d. (blank ((lambda (blank) (blank blank)) (lambda (blank) (blank blank))))

e. ((lambda (blank) (blank blank)) (blank blank))

Question 3. BNF Grammar15 pts

Extend the Flang BNF so that it is possible to write a bunch of definition forms that look like {def <id> E} at the beginning of a code blocks (before the actual expression), where code blocks are

Here is an example of valid code in the revised language:

{def x 1}
{with {x 3}
  {def x 4}
  {def foo {fun {x} {def y x} {+ x y}}}
  {call foo x}}

Note: for full credit, do this properly, without repeating stuff.

Question 4. Structural Recursion with ASTs20 pts

We have seen in class that we can treat a with expression in the same way as we treat a call expression with a fun and an immediate argument. The rule was that these two expressions have the same exact meaning:

{with {<id> <E1>} <E2>}
{call {fun {<id>} <E2>} <E1>}

In other words, we can make with a derived form – we write an evaluation rule for with expressions which simply uses the evaluation rules for call and fun:

eval({with {x E1} E2}) = eval({call {fun {x} E2} E1})

Write an eliminate-withs transformer function that consumes a Flang AST expressions and returns an equivalent one that has all with expressions replaced by calls. Here is a quick test case to demonstrate this:

(test (eliminate-withs (parse "{with {x 5} {with {y x} {+ x 1}}}"))
      => (parse "{call {fun {x} {call {fun {y} {+ x 1}} x}} 5}"))

Don’t forget to add a proper type declaration and a purpose statement.

Question 5. Extending the FLANG Language20 pts

We want to extend the Flang langugae with a new feature called upref. This will be a new special form that holds an identifier name and a positive integer N, and it evaluates to the value of the Nth binding of that identifer in the runtime environment. Again, we use a few tests to demonstrate this extension:

(test (run "{upref x 1}") =error> "...")
(test (run "{with {x 1} {upref x 1}}") =error> "...")
(test (run "{with {x 1} {with {x 2} {upref x 1}}}") => 1)
(test (run "{with {x 1} {with {x 2} {upref x 2}}}") =error> "...")
(test (run "{with {x 1} {with {x 2} {with {x 3} {upref x 1}}}}") => 2)
(test (run "{with {x 1} {with {x 2} {with {x 3} {upref x 2}}}}") => 1)
(test (run "{with {x 1} {with {x 2} {with {x 3} {upref x 3}}}}") =error> "...")
(test (run "{with {x 1}
              {with {f {fun {x} {upref x 1}}}
                {call f 2}}}") => 1)
(test (run "{with {x 1}
              {with {f {fun {x} {upref x 1}}}
                {with {x 3}
                  {call f 2}}}}") => 1)
(test (run "{with {x 3} {with {x 2} {with {x 1} {upref x {+ 1 1}}}}}") => 3)
(test (run "{with {x 3} {with {x 2} {with {x 1} {upref x x}}}}") => 2)

Note the last two tests: the Nth argument is a plain expression, which is evaluated as usual.

To implement this on top of the (flang-env.rkt)[Flang langugae that uses environments], we need to:

The main step is extending eval to handle these expressions:

(: eval : FLANG ENV -> VAL)
;; evaluates FLANG expressions by reducing them to values
(define (eval expr env)
  (cases expr
    ...same...
    [(Upref name level) ...fill-in...]))

Your job is to do so. You don’t need to copy any code, it’s enough to specify just the new case.

It is best to do this using a new helper function – but since it is similar to lookup, you can just redefine it instead of writing a helper. If you choose to do so, also write how existing uses are changed, otherwise, if you write a helper then include its type and a purpose statement. (Choose wisely!)

Question 6. Schlac20 pts

Question 6a.

We want to implement a cond for Schlac. There is, however, one important disadvantage of an implicitly-curried language like Schlac (or ML, or Haskell): it cannot handle functions with a variable-arity conveinently.

If instead we simply make it receive a list of (bool T) pairs, such a function is pretty simple. To clarify, we’ll make this function consume a list of values, each one is a cons of a boolean and a result.

To make it even simpler, we can write code that assumes that one condition will always be true, and therefore just not check if we reached the end of the input list.

Implement this function.

Here is a sample test for this function:

(test (->nat (cond (cons (cons #t 1)
                        (cons (cons #t 2)
                              (cons (cons #t 3)
                                    null)))))
      => '1)

This demonstrates the inconvenience that results from the lack of variable-arity functionality. We can use a helper for cases of a known arity, for example, use a list3 definition instead of the above mess:

;; helper for convenience
(define list3 (lambda (a b c) (cons a (cons b (cons c null)))))
(test (->nat (cond (list3 (cons #t 1) (cons #t 2) (cons #t 3)))) => '1)
(test (->nat (cond (list3 (cons #f 1) (cons #t 2) (cons #t 3)))) => '2)
(test (->nat (cond (list3 (cons #t 1) (cons #f 2) (cons #t 3)))) => '1)
(test (->nat (cond (list3 (cons #f 1) (cons #f 2) (cons #t 3)))) => '3)

Question 6b.

The above is clearly impractical as a generally convenient function.

There is a way to make things more convenient though: use a “special” kind of a value that signals the end of the argument list. For a cond function, it makes sense to consume arguments where every odd-place argument is a boolean, and stop as soon as we get a different special value that is not a boolean.

Such a definition can be tricky, since it’s a function that may return a function that consumes additional arguments, or it might return the actual result of the whole cond. The details of such an implementation are not important, but if you want to play with it, here is a working version – it defines a special else: value to be used kind-of like an else keyword:

#lang pl schlac+
(define else: (lambda (x y) #t))
(define is-else? ...fill-in...)
(define/rec cond-helper
  (lambda (k c x)
    (if (is-else? c)
      (k x)
      (cond-helper (if c (lambda (_) (k x)) k)))))
(define cond (cond-helper identity))
;; tests
(test (->nat (cond else: 3)) => '3)
(test (->nat (cond #t 1 #f 2 else: 3)) => '1)
(test (->nat (cond #f 1 #t 2 else: 3)) => '2)
(test (->nat (cond #t 1 #t 2 else: 3)) => '1)
(test (->nat (cond #f 1 #f 2 else: 3)) => '3)
(test (->nat (cond #f 1 #f 2 #f 3 #f 4 else: 5)) => '5)
(test (->nat (cond #f 1 #t 2 #f 3 #t 4 else: 5)) => '2)

The important part here is the else: definition, which must be distinguishable from boolean values:

(define else: (lambda (x y) #t))

What you need to do to complete this code is to implement the is-else? predicate:

(define is-else? ...fill-in...)

To be clear, all we need is to distinguish it from the two boolean values. Here are three tests that demonstrate this:

(test (->bool (not (is-else? #f))))
(test (->bool (not (is-else? #t))))
(test (->bool (is-else? else:)))

Question 7. Language Features15 pts

Unless told otherwise, choose the best answer in each of the following questions. (Note that there could be several answers that are correct, but one should be the most accurate.)

Question 7a.

Why is it that in Schlac we can define cond as a plain function but in Racket it must be some special syntax?

  1. Schlac is a simple language with almost no builtins other than functions and applications. Because of this everything in this language is always done with just function definitions.

  2. Schlac is a lazy language; Racket is eager so it must use special forms with their own evaluation rules to implement short-circuiting.

  3. Racket could have used function definitions for things like cond as well, but then error messages would be very confusing.

  4. Racket uses lexical scope, but Schlac is dynamically scoped (needed for recursive functions).

Question 7b.

In the Schlac implementation of the simple version of cond, why does it make sense to have it assume that at least one condition is true? That is, why does it make sense to not have some default return value like Racket’s void?

  1. The language is very simple, so we avoid extra features like returning a default value.

  2. We cannot have default values because of the variable arity problem.

  3. We could have added a default, but since it’s a functional language it doesn’t make sense to do so.

  4. We could have added a default, but it would be nearly useless because there is no such value that can be used in all expected result type contexts.

Question 7c.

In the Flang extension that we have implemented above we added a new kind of an upref identifier reference. An important issue is here is whether our language is still one that can be compiled or not. Can it?

  1. No. The fact that we can do this kind of upref dynamically at runtime means that we get a dynamically scoped language, and as we have discussed in class, such languages cannot be compiled. (Since the “offset” of a variable reference cannot be determined before running the code.

  2. Almost, but no. The only problem is that the level is an expression and therefore not known before runtime. If we instead restrict the language to require an actual integer, then the resulting language could be compiled.

  3. Almost, but no. Since all of the references are visible in the source code, we can still tell which binding is referenced at each upvar expression but this works only if our language is not extended to have a conditional expression like if. Such an expression means that we can have code that goes an arbitrary number of levels at runtime, so we cannot tell statically which binding it refers to.

  4. Yes. Since the syntax still allows us to see the lexical structure of the code, we can still analyze it and compile it using de-Bruijn indexes. Even if we have a conditional if form added to the language we can see the lexical structure of the code since an upref expression returns a value, which means that we cannot do two (or more) uprefs somehow.

  5. Yes. Since the syntax still allows us to see the lexical structure of the code, we can still analyze it and compile it using de-Bruijn indexes. If we have a conditional if form added to the language we will need to use a lazy evaluation strategy anyway, and that means that we don’t get expressions with a dynamically determined scope.