• Main
• Overview
• Resources
• Homeworks

Sample Final 3

Date: Thursday, April 18th

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:

• (FLANG {fun {<id>} <FLANG>})
  should expand to a Racket lambda form, with the FLANG-ized body
• (FLANG {call <FLANG1> <FLANG2>})
  should expand to a Racket function call (again, with the two subexpressions compiled recursively)
• (FLANG {with {<id> <FLANG1>} <FLANG2>})
  should expand to a Racket let form

(FLANG {with {add {fun {x} {fun {y} {+ x y}}}}
         {call {call add 3} 4}})

(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:

• It’s fine to write it as a simple syntax-rules macro. It won’t be strict enough — for example, it won’t check that an <id> is a Racket identifier, but that’s fine for this problem.
• To make things readable, remember that you can have the patterns look just like they appear in the BNF — since curly braces are considered a plain parenthesized expression, and <foo> is a valid identifier. But be careful to not use two <FLANG>s in cases with two subexpressions, use E1 and E2 instead.
• Also, you’ll have a single rule for both identifiers and numbers, so you can use <num/id> for that — careful with that pattern: it will match anything, so it should appear last.
• It will also lead to a language that is different from Flang in a subtle way: in the original Flang language fun always has the same meaning, and {+ ...} is always addition. In contrast, the usual way in which syntax-rules work will make it possible to shadow these bindings. It’s possible to do get the same kind of literal matching that the interpreter does, but again, ignore this for simplicity.

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"])

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))

> (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:

• + now has two rules: one for two Integer inputs and one for two Float inputs.
• Similarly, a < has two rules for two Integers and two Floats.
• One new rule was added to represent the automatic coercion.

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 (τ₂ -> τ₂), 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.