Sample Final 4

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.

As we have discussed in class, we can get the benefits of functional (side-effect-free) programming in an eager side-effect-full language by using thunks (nullary functions) to wrap side-effects, turning them into plain values. Using this, you get a simple functional world with no side-effects to complicate things, while still being able to conveniently interact with the “real world”.

For example, say that we have a set of Logo-like drawing primitives, including:

Now, to use these values, we need some convenient utilities. Some of these utilities can be specific to the Logo world, for example:

1. Implement this Combine constructor. (Note that the constructor itself needs to go down to the “doing something” level, since that is exactly what it abstracts away.) Remember to write a correct type and a purpose statement.
2. Add another operation called Repeat that consumes an integer N and a thunk T, and returns a new thunk that will apply T N times when invoked. For example, using this we could define a square as follows:

   (: Square : Number -> (-> Void)) ;; make a square of the given size (define (Square n) (Repeat 4 (Combine (WithPenDown (Move n)) (Turn 90))))

   Note that this could be implemented in one of two ways:
   • directly, implementing a loop that will repeat an operation N times and wrapping it in a thunk,
   • using Combine, without going down the the side-effect level and without an additional lambda (this will be easier to implement).
   Again, remember to write a correct type and a purpose statement.

In several occasions, we have seen how curried functions can be a very useful tool. To make it convenient to write curried functions, we want to extend Scheme with a new form: clambda, that creates a curried lambad. To demonstrate how it is used:

Implement this clambda form as a macro, using define-syntax and syntax-rules. You don’t need to make it work on no arguments — there is no point in currying that case. Note that the solution is relatively short (about 4-6 lines should be sufficient).

In Assignment #10 we have implemented an extension to the TOY language that has by-reference rfun functions. An alternative approach is what you get in C: extend the language with a new kind of “reference” values, which hold the box that is the location of some value. This extension should be a familiar process: we’re taking some feature of our language that is currently second-class, and we promote it to a first class value that is accessible from inside the language. In the C case, this means exposing raw machine pointers; and in our case, we take the boxes that are used to store binding values and expose them. These boxes are currently available only in the extended TOY implementation — in Scheme code, and we will make them accessible inside the language, so they can be passed around and used as any other kind of values in TOY programs.

To get a quick idea of how this extension will look like, here is a test that will eventually work:

As usual, we begin by extending the BNF,

1. To evaluate the new special form, we need to have an additional case in the body of the eval function for a Ref syntax, which should return a new RefV value holding the appropriate box:

   [(Ref name) (RefV —«fill-in»—)]

   Fill in the missing code here.
2. Now that we have a working way to construct these values, we need to implement a way to use them. We do this with a new setref! primitive function, that can be used as:

   {setref! foo bar}

   to set the value referenced by foo to the bar value. However, we need to implement it directly rather than construct it with scheme-func->prim-val. First, the binding is added with:

   (define global-environment (FrameEnv (list (list '+ (scheme-func->prim-val +)) ...same... (list 'setref! (box (PrimV setref-function))) ;; values ...same...) (EmptyEnv)))

   and now we need to implement it as setref-function. We need to follow the same calling protocol as for all primitive functions, meaning that it should be a function from a list of VAL inputs to a VAL output, and and this means that we need to check that we’re getting the right number of input arguments. Finally, we also need to make sure that the value that we receive is indeed a RefV:

   (: setref-function : (Listof VAL) -> VAL) ;; the implementation of the builtin "set-ref!" function that changes ;; the contents of a ref value (define (setref-function args) (if (= (length args) 2) (cases (car args) [(RefV b) —«fill-in»—] [else (error 'setref! "got a non-ref value: ~s" (car args))]) (error 'setref! "bad number of arguments, expecting two")))

   Fill in the missing code.
   (Hint: there are two expressions that are needed there. (But both are very short.))
3. Now comes an important part: users will often want features that make their life easier, even when in the long run the potential for problems is higher. In this case, your users want to be able to treat these reference values (RefV for you) as if they were not there. For example, in the sample test code given above note that the mutation expression is:

   {setref! x {+ x 1}}

   so x is used as a plain value too. To give our users the maximum comfort (and maximize their chance of shooting their feet), we’re going to implement this. First, we write a utility function that consumes some VAL, and if it happens to be a RefV, it will dereference it, otherwise it will return the value it received as-is:

   (: deref-value : VAL -> VAL) ;; utility function that automatically converts a ref value to a plain ;; value (define (deref-value val) —«fill-in»—)

   Fill in the missing part. Note that this is again a very simple function (to be more specific, you don’t need any loops or recursion or evaluation).
4. Finally, we need to use this deref-value in places where a value is needed. The first such place is in the primitive function application, in the body of scheme-func->prim-val. This code:

   (map (lambda: ([a : VAL]) (cases a [(ScmV v) v] [else (error ...)])) args)

   needs the value held in a — so we change it to:

   (map (lambda: ([a : VAL]) (cases (deref-value a) [(ScmV v) v] [else (error ...)])) args)

   There are three more places that need to use deref-value, find them. (You only need to specify which expressions need it, there’s no need to actually change the code.)

Question 3 was somewhat similar to the Sloth implementation in that a certain value is automatically converted to another one. But there is one thing that we did in the Sloth implementation, but didn’t do here: in Sloth, note that there is a second boolean argument to scheme-func->prim-val, which determines if values are forced or not, and was used in a particular way by the global list binding (of the Sloth language).

You need to figure out what is it exactly that is missing, and how it would affect the code if it is added as in the Sloth implementation. That is, understand what the extra boolean flag causes if our evaluator is also extended with it. You will need to assume that the language is also extended with list or cons.

Once you know what will change, demonstrate this: you need to write a sample program for our extended TOY evaluator, such that it will return a different result if the boolean flag is added (and the code in scheme-func->prim-val is changed to use it as Sloth does) or if not.

(Note: it’s TOY sample code that is needed here.)

In the following sub-questions, you should choose the valid answer. Only one should be chosen, unless the question explicitly says otherwise.

1. In Question 3 we have added ref as a new built-in special form, rather than a primitive function — unlike setref!. Is it not possible to implement it as a function instead?
   1. It is possible, but implementing it as a new form makes the implementation faster.
   2. It is possible, but implementing it as a new form makes the implementation simpler.
   3. It is possible to do that: functions have uniform evaluation rules, but we could do what we did with set-ref!, and implement the function directly in a way that can access the box.
   4. It is not possible to do that: functions have uniform evaluation rules, so any function we would write would receive a plain value instead of the box.
   5. It is not possible to do that, because the new function would need to use eval, which leads to an infinite loop that prevents getting any actual box value.
2. Does it make sense to define a while macro in a lazy language? There are two of valid answers here, you need to find both. (Note: they don’t have to be both Yes or No answers (*wink* *wink*).)
   1. No, just like it doesn’t make sense in plain Scheme, otherwise it would have been part of the language.
   2. No, because an implementation of while in Scheme relies on having proper tail calls, and lazy languages cannot support that.
   3. No, because macros are not needed in a lazy language.
   4. No, because while is only useful with side-effects, and side-effects are problematic in a lazy language.
   5. Yes — in exactly the same way that it makes sense to do that in plain Scheme.
   6. Yes, but since it’s a lazy language, it could be defined as a simple function.
   7. Yes, provided that we have a representation that encodes side effects, but then it could be defined as a simple function.
3. In Lecture #17 we’ve seen how we can implement a TOY to Scheme compiler (more precisely TOY to our dialect of Typed Scheme). As a TOY programmer, how can you determine whether the language is compiled using this or interpreted as usual?
   1. You write an infinite loop and see if the stack blows up.
   2. Impossible: you could use an infinite loop, but that TOY implementation doesn’t have bindrec, so no loops are possible.
   3. Impossible: the compiler that we designed preserves the semantics of the original language.
   4. You write a TOY expression with a type error in it, and if it’s compiled to Scheme, then the resulting Scheme code would fail to typecheck and throw an error, otherwise it will run fine.
   5. You write code that implements the naive fib function, and measure how fast it runs with a sufficiently large input number. The difference between a compiled language and an interpreted one will be obvious since the first is going to be much faster.
   6. You write code that generates code at runtime, if it’s gets compiled then the resulting lanugage will not have a compiler and therefore will have a runtime error, otherwise it will work fine.
4. Is there any danger in having recursive types in the typed-scheme-based language that we used in the course?
   1. There is no danger with recursive types.
   2. Typed Scheme doesn’t have recursive types.
   3. Our dialect of typed scheme doesn’t have recursive types.
   4. Even if we didn’t have recursive types explicitly, we could emulate them using the Y combinator, so there is no new danger.
   5. Using a recursive type is dangerous because it can get the type checker stuck in an infinite loop.
   6. Using a recursive type is useful, but if you have typed macros it is easy to get the type checker stuck in an infinite loop.
   7. The type language is lazy, so there is no problems with recursion.

Finally, to continue with the spirit of mutation, we will extend the statically-typed Picky language with mutation. Start with the basic Picky language definition, given here so you don’t need to wonder which version you need:

You need to add the following to the BNF:

• a Void type
• a set! expression (with the usual syntax)
• a begin expression, with only two subforms for simplicity

Once you have that, write two new typing judgements — one for set!, which should evaluate to a Void value, and one for begin, which should evaluate to the result of its second (and last) subexpression. Be careful with set! — it should not be possible to change the type of an identifier, since this will break the invariants that the type checker enforces.