Sample Final 3
Date: Thursday, April 18th

 
Name:

Administrative

This exam was given in the Spring semester of 2011.

Note that in this exam the “Type System” and “Continuations” questions are relatively easy, since we went over the material in less details than in this semester.

Question Grade  
(1) Racket Programming /20
(2) Language Extension: Extending Racket /20
(3) Lazy Languages /20
(4) Language Features /20
(5) Continuations /20
(6) Type System /20
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: Racket Programming
 20 pts 


We want to implement a concept of “simple function calls”, where you apply a function in a way that forbids calling it again during the call. (This can be useful, for example, to forbid recursive calls in cases where you want to avoid infinite loops.)

To do this, we will use boxes that hold a unary function, and change the box when the function is called. This will be done by a simple-call function that recieves the boxed function and an appropriate argument. Implement this function. (Don’t forget to write a proper type.)

Here are two simple examples to demonstrate how it works:

(: add1 : (Boxof (Number -> Number)))
(define add1 (box (lambda (n) (+ n 1))))
(test (simple-call add1 9) => 10)

(: bad : (Boxof (Number -> Number)))
(define bad (box (lambda (n) (simple-call bad (+ n 1)))))
(test (simple-call bad 9) =error> "recursive calls forbidden")



 

Question 2: Language Extension: Extending Racket
 20 pts 


Throughout the semester, we have implemented a number of languages. The implementation strategy for all of these languages was a definition of an interpreter. An alternative strategy that would be useful is one that we’ve discussed in Lecture #21 and Lecture #22 is to define a new language by translating it into Racket via its macro system, which has one advantage of a simpler implementation (since it borrows more from Racket) and more functionality (since it can by used as an extension to Racket, so the full language is still there). Obviously, the fact that Racket is used to provide the semantics, it wouldn’t be as useful for learning how to implement such languages. But it’s still useful to do this to get some of Racket’s advantages, for example DrRacket’s syntax checker, or Racket’s speed.

Implement a Flang-like language on top of Racket via a single FLANG macro that serves as a kind of a Flang compiler. The macro will do the following:

and so on for the rest of the language. To make it more fun, it should work for the Flang language that has the rec form. (Note that Racket treats curly braces as other parentheses.) For example, this:
(FLANG {with {add {fun {x} {fun {y} {+ x y}}}}
         {call {call add 3} 4}})
should expand to
(let ([add (lambda (x) (lambda (y) (+ x y)))])
  ((add 3) 4))

Your macro should handle the complete language. Here is the complete BNF that it should compile:

<FLANG> ::= <num>
          | { + <FLANG> <FLANG> }
          | { - <FLANG> <FLANG> }
          | { * <FLANG> <FLANG> }
          | { / <FLANG> <FLANG> }
          | { with { <id> <FLANG> } <FLANG> }
          | { rec { <id> <FLANG> } <FLANG> }
          | <id>
          | { fun { <id> } <FLANG> }
          | { call <FLANG> <FLANG> }

Implementation notes:



 

Question 3: Lazy Languages
 20 pts 


As we have seen, cond in the lazy language (#lang pl lazy, not Schlac) that we have used in class was still a special form (a macro). The reason for that is a technicality: it has a syntax that is different from functions — for example, if it was a function then something like this:

(cond [(> x 0) "positive"]
      [(< x 0) "negative"]
      [else    "zero"])
would fail because it would treat the boolean result as a function, and it would also fail because else wouldn’t be bound. A possible way around this is to use lists — a list of a condition and a result for each clause, and a list containing all clauses (since we can’t write variable arity functions). For the purpose of this question, you can assume that each clause has one result expression (since it’s a lazy language, there is no point in multiple expressions: we don’t use side effects.)

Such a cond function would be used a little differently:

(cond (list (list (> x 0) "positive")
            (list (< x 0) "negative")
            (list else    "zero")))

If it’s possible to write such a function, then do so. Remember that you need to deal with else too — and it should throw an error if no clauses succeed (which never happens if there’s an else clause, of course). Also, remember that we didn’t have types in the lazy language, so write an informal contract in a comment for your definition(s).

If it can’t be done, then you need to explain (shortly!) why it is not possible.



 

Question 4: Language Features
 20 pts 


In the following questions choose the single best answer (unless told otherwise).

  1. Does it make sense to implement a lazy language with dynamic scope?
    1. Yes. As we have seen, dynamic scope has certain advantages that are just as applicable in a lazy language as they are in a strict one. For example, changing a configuration argument for some dynamic extent.
    2. No. As we have seen, a lazy language benefits even more from a static type system — for example, it makes it possible to restrict cons so that it constructs only proper lists. (Unlike the lazy language that we’ve seen, where we could use cons with an arbitrary second argument.) But we’ve seen that a static type system cannot fit a dynamically scoped language, exactly because it is static.
    3. Yes. Dynamic scope is closely related to a dynamically typed language, and the lazy language that we have used in class was dynamically typed. (It would be nice to have a statically typed language, but the fact that there are also advantages for dynamic typing applies to dynamic scope too.)
    4. No. A dynamic scope essentially means that some binding changes during execution of some “body expression”, but in a lazy language execution can (and usually does) happen later, when execution of the surrounding form is already done.
  2. In the automaton macro that we’ve written in Homework #15, we could write any expression for the new state in a rule. For example:
    (lambda (something?)
      (automaton start end
        [start : x -> (if something? state1 state2)]
        [state1 : ...]
        [state2 : ...]
        [end : ...]))
    Can we do the same for the matched input token? If not, what’s needed to make it possible? (See the solution of that homework for the implementation that this question is talking about.)
    1. Yes, we could do the same with the input token. Looking at the solution, you can see that the pattern variable that the input stream is a plain variable, so any expression could be compared with it.
    2. We can almost do the same with the input token. The problem is that the generated code has one binding for stream, which means that it can only test one possible token expression, which is obviously insufficient. To make it possible we will need to generate several new identifiers, one for each transition rule. (For example, using generate-temporaries.)
    3. We cannot use an expression for the input token only because input-sym is quoted in the resulting match clause, so it matches only literal symbols. To be able to do that, we would just need to remove those quotes it.
    4. We cannot use an expression for the input token only because input-sym is quoted in the resulting match clause, so it matches only literal symbols. To be able to do that, we would need to unquote it, which means that we would need to convert the match to a cond (since we don’t know how to match something against an expression).
    5. It’s impossible to get this to work, since automatons are inherently limited, and can never use any expressions.
  3. In the lazy language question we’ve discussed the option of implementing cond as a function. Whether this is possible or not, there must be some connection to implementing cond as a function in a strict language. What is that connection?
    1. The lazy world and the strict world are unrelated with respect to a cond implementation, since the two kinds of semantics are very different. Therefore, there is no such connection.
    2. The connection is that we could implement cond in the same way if we use thunks instead values. This would work, but would be less convenient to use.
    3. It is impossible to implement cond as a function in a lazy language. This is obviously related to the fact that it’s impossible to define it as a function in a astrict language too.
    4. It is possible to define cond in the same way in a strict language. However, such a definition would be very difficult, since we will need to write the code in continuation passing style (CPS) to make it have the same semantics as the lazy language.
  4. In Lecture #22 we have seen an implementation of a for loop. What is the difference between these for loops and, say, a Javascript for loop? (Reminder: choose the most appropriate answer.)
    1. There is no difference — the whole point was to define a conventional for loop.
    2. Our for loop was implemented on top of Racket, in user code.
    3. Our for loop was creating a new binding for each iteration, instead of mutating a single binding. This means that we can create closures that close over the index value.
    4. Both languages have closures, but our implementation relies on a statically scoped language.
    5. Our macro was extended to implement a (for x in some-list do ...), something that Javascript loops cannot do.


 

Question 5: Continuations
 20 pts 


In the last lecture, we have seen some translations of code to continuation passing style. We wish to implement a “web app” that reads numbers in a loop, stopping as soon as the numbers sum up to a positive number. This application is initiated with a positive-sum/k function, and the loop is implemented by a positive-loop/k function. These would be the continuation passing style translation of the following code:

(define (positive-sum) ; entry point
  (positive-loop 0))
(define (positive-loop sum)
  (let ([sum (+ sum (web-read "A number"))])
    (if (> sum 0)
      sum
      (positive-loop sum))))

To make things easier, here is a skeleton code for you to fill in:

(define (positive-loop/k sum k)
  (web-read/k "A number"
              ...fill-in...))
(define (positive-sum/k k)
  (positive-loop/k 0 k))
and here is an interaction example that demonstrates the working code:
> (positive-sum/k web-display)
web-read/k: enter (resume) to continue
> (resume)
A number: -1
web-read/k: enter (resume) to continue
> (resume)
A number: -10
web-read/k: enter (resume) to continue
> (resume)
A number: 5
web-read/k: enter (resume) to continue
> (resume)
A number: 100
web-output: 94



 

Question 6: Type System
 20 pts 


In the exam that was given last year (the third one) the Picky type system was extended by separating the Number type into Integer and Float, with the notion of the first being a subtype of the second, and using automatic coercion when mixed number types are used. To summarize the changes that this lead to:

For reference, here is the extended BNF and the new type judgments:

<PICKY> ::= <int>
          | <fpnum>
          | <id>
          | { fun { <id> : <TYPE> } : <TYPE> <PICKY> }
          | { with { <id> : <TYPE> <PICKY> } <PICKY> }
          | { rec  { <id> : <TYPE> <PICKY> } <PICKY> }
          | { + <PICKY> <PICKY> }
          | { < <PICKY> <PICKY> }
          | { call <PICKY> <PICKY> }
          | { if <PICKY> <PICKY> <PICKY> }

<TYPE>  ::= Integer
          | Float
          | Boolean
          | ( <TYPE> -> <TYPE> )

Γ ⊢ i : Integer            ; <--- i is for all literal integers

Γ ⊢ fp : Float             ; <--- fp is for floating point numbers

Γ ⊢ x : Γ(x)

Γ ⊢ E : Integer
———————————————            ; <--- the coercion rule
 Γ ⊢ E : Float

Γ ⊢ a : Integer   Γ ⊢ b : Integer
—————————————————————————————————
      Γ ⊢ {+ a b} : Integer

Γ ⊢ a : Float   Γ ⊢ b : Float
—————————————————————————————
     Γ ⊢ {+ a b} : Float

Γ ⊢ a : Integer   Γ ⊢ b : Integer
—————————————————————————————————
      Γ ⊢ {< a b} : Boolean

Γ ⊢ a : Float   Γ ⊢ b : Float
—————————————————————————————
    Γ ⊢ {< a b} : Boolean

          Γ[x:=τ1] ⊢ E : τ2
——————————————————————————————————————
Γ ⊢ {fun {x : τ1} : τ2 E} : (τ1 -> τ2)

Γ ⊢ f : (τ1 -> τ2)  Γ ⊢ v : τ1
——————————————————————————————
     Γ ⊢ {call f v} : τ2

Γ ⊢ c : Boolean   Γ ⊢ t : τ   Γ ⊢ e : τ
———————————————————————————————————————
          Γ ⊢ {if c t e} : τ

Γ ⊢ v : τ1   Γ[x:=τ1] ⊢ E : τ2
——————————————————————————————
 Γ ⊢ {with {x : τ1 v} E} : τ2

Γ[x:=τ2] ⊢ E : τ   Γ[x:=τ2] ⊢ v : τ2
————————————————————————————————————
     Γ ⊢ {rec {x : τ2 v} E} : τ

The reason that there’s no need for additional numeric rules for + and < is that when needed, the coercion rule can be used to complete a proof, and that represents automatic coercion that the language will do. Here’s an example that requires this, since the two inputs have different number types:

Γ ⊢ 1 : Integer
———————————————
Γ ⊢ 1 : Float   Γ ⊢ 2.3 : Float
———————————————————————————————
     Γ ⊢ {+ 1 2.3} : Float

This language works fine, but one thing is that we can’t see the subtype relation between the two function types. For example, a function type that returns an Integer can be considered as one that returns a Float.

  1. Write the rules that express that — you will need two of them.
  2. Show that a (τ -> τ) function is not a subtype of any other 2 -> τ2), other than itself. This needs to be shown for both options of (Integer -> Integer) or (Float -> Float). Note that there’s no easy way to say that something is not derived by the system, so it’s enough to list the derivations that are needed in each case (two in each) and point at the derivation that is impossible.