Administrative

The language for this homework is:

In this homework you are given an extended version of the cached SLOTH evaluator, which you will further improve on. To keep things in the world of slow animals, the new language is called SLUG. Begin your work with the Slug source. The extensions to SLOTH that makes it SLUG are described below, make sure you understand the code before you modify it.

Don’t panic! This homework requires understanding of a few lectures, and reading through some code. Make sure you understand the material, and go through this work according to the specified steps.

SLUG extensions for I/O

The Slug source is extended in several ways to support I/O. Make sure you understand these changes before you begin your work.

• First, SLUG has string values in addition to other types — which affects both parsing and evaluation. In SLUG code, you use '...' for strings, for example:

  (run "{list 1 'foo'}")

  To include a quote in a SLUG string, repeat it twice. (Racket escapes like “\n” are also supported.)

• Second, there is a type definition for I/O descriptions: IO. It has cases for the three building blocks of I/O side effects — output, input, and sequencing of two I/O operations.

• This type can be used in SLUG programs — its constructors are available in the global environment as print, read, and begin2. Note that they’re bound as non-strict primitive functions, which means that they can (and usually will) hold ExprV closures.

• There is a section that is labeled as “I/O Execution”, which is in charge of “translating” I/O descriptions into actual actions. This is where you will do your work.

• Finally, in addition to the main run function, there is a new toplevel entry point — run-io. This is like run but it expects an IO result, uses execute-val to execute the actions that are described in this result, and that uses a number of functions for the various variants.

  Note how execute-val serves as a table of specification for strictness points — for example, the print and read operations are strict (we need a proper string value or a receiver function), but begin2 simply sequences the two operations, so we must not force the second value before we’re done executing the first (this is especially important in infinite printout loops).

Your task

The “I/O Execution” section is incomplete. The three execute-? functions are not really doing anything and you need to implement their functionality. Some tests are included at the bottom of the file, which should help you make sure that your implementation works. Note that these tests use a new form of the test form — using a given string as simulated input with input:, and testing its simulated output with =output>. For reading you should use the read-line function (with no arguments), and for writing a string you should be using display.

Note also that execute-receiver is a generic helper for invoking a receiver function, it will be useful in other cases below. It expects a SLUG receiver value (a FunV), and a producer thunk to get a value to send to the receiver. The reason the latter is a thunk is that it might include a side-effect, and we shouldn’t perform such a side-effect if the receiver is bad. Make sure that it uses wrap-in-val to wrap the value, because the value might itself be a VAL. (This will be relevant below.)

For example, to prompt and read a name, and then print it, you build a read-description that contains a function and does the printout:

Note how this does not depend on the order of evaluation in the lazy SLUG language: the order is enforced by the perform-i/o loop, which exists in the strict world. In this example, the last part is not forced until a value is read — so it is always executed after the first part.

Macros for I/O

Another extension to SLUG is that it has a generic macro preprocessor. An additional input syntax — with-stx — specifies macro transformers in a way that is similar to Racket’s syntax-rules. The syntax of with-stx is:

• The first identifier names the new syntax. (with-stx is limited to a single (local) syntax definition.)

• Then there is a list of identifiers that are literal keywords that are expected to appear in code that uses this macro. (Enclosed in braces.)

• Then there is a sequence of pattern pairs, each has an input pattern and an output pattern. These specify the rewrite rules that make the actual transformation.

• Finally, there is an expression which is subject to rewrites using this macro.

The pattern pairs and literal keyword list are similar to the ones in syntax-rules, and the transformer is generated via the new make-transformer function that is included in the language.

Macro expansion is implemented during parse, which now carries around an environment-like argument holding bindings for syntax transformers. Whenever parse encounters a with-stx input, it builds a transformer function and adds it to the recursive call. All forms are first checked — if their first expression is a name that is a registered macro name, then the transformer is applied and parsing continues with the result. (Note that these macros are simple sexpr-based transformations, they’re not hygienic.)

For example, there is a test at the bottom of the file that implements a let macro that is equivalent to bind, except that it is translated to function calls, and then it implements a let* form as shown in class.

Your task

As seen above, you can now do I/O in your lazy language, but the syntax for doing this is very inconvenient. Your job is to write a do macro that will make things easier to write. For example, the new syntax will allow running this:

For this question, all you need to do is to fill in the macro body which is marked in the above code. To make things easier, here is a bit more from this macro — you have three cases to complete:

(Note that <- is a literal keyword that is expected to appear in places where do is used, and note that read and print can actually stand for any name.)

This code is included at the bottom of the file.

Mutation in a Lazy Language

The same approach can be used to deal with mutation: we can add boxes to the language, and handle them through operation descriptions in the same way that we handled I/O — in fact, we can extend IO with new descriptions.

Note: there is an important technical problem with boxes: we will want to use Racket boxes inside RktV wrappers, and detect when a wrapped value is a box using box?, but the box? predicate is not useful in that Typed Racket will not allow you to do any box-related operation on something that passed a box? test. The reason for this is the lack of subtype relationship between all Boxof values — even if you know that something is a box using box?, you don’t know what type it is supposed to have. To avoid this, we use a new kind of mutable type: a ref. This type has the same interface as boxes (and it’s actually implemented using a box), except that it always holds an Any value. You don’t need to implement it — the implementation is provided as part of the given Slug source. Inside the SLUG language we could have used box as the user provided functionality, but we’ll use ref there too, to reduce confusion.

Implement mutation in steps:

1. Add three cases to the IO type definition:

   ;; I/O descriptions
   (define-type IO
     [Print    VAL]      ; String
     [ReadLine VAL]      ; receiver: String -> IO
     [Begin2  VAL VAL]  ; IO IO
     ;; mutation
     [NewRef  VAL VAL]  ; init, receiver for new ref
     [UnRef    VAL VAL]  ; ref, receiver for its value
     [SetRef  VAL VAL]) ; ref, new value

2. Add bindings for the new operations: newref, unref, set-ref!,

3. Update execute-val, and add execute-newref, execute-unref, and execute-set-ref. execute-receiver will be useful here too. Be careful with strictness points — generally speaking, you will need proper ref values, but the initial value for a new ref, or the value that is put into a ref should not be forced unless they’re actually used.

You can try the following example to test your implementation:

More Macros

Finally, use the same approach as above — extend the previous macro so the new constructs can also be used in a do context. You should be able to get to the following code:

Hints: (a) begin with the same syntax rewriter you had above, and generalize the patterns — replace {read} by a general {f x ...} pattern (on both sides), and replace {print str} by expr (on both sides); (b) you still need only three rewrite rules in the with-stx; (c) note that in all cases, the receiver argument is always the last one.