Homework #15: SlugOut: ? Wednesday, March 14th, Due: ? Monday, April 9th, 11:00pm


The language for this homework is:

#lang pl 15

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.

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, 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 SLOTH 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:

"{begin2 {print 'What is your name?'}
          {read {fun {name}
                  {begin2 {print 'Your name is '''}
                          {begin2 {print name}
                                  {print '''\n'}}}}}}")

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:

{ with-stx {<id> { <id> ... } { <pattern> <pattern> } ...}
    <SLUG> }

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:

"{with-stx {do ???}
    {do {print 'What is your name?\n'}
        {name <- {read}}
        {print 'What is your email?\n'}
        {email <- {read}}
        {print 'Your address is '''}
        {print name}
        {print ' <'}
        {print email}
        {print '>''\n'}}}")

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:

"{with-stx {do {<-}
                {{do {id <- {read}} next more ...}
                {{do {print str} next more ...}
                {{do expr}
        … same as above …

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

"{bind {{incref {fun {b}
                  {unref b
                    {fun {curval}
                      {set-ref! b {+ 1 curval}}}}}}}
    {newref 0
      {fun {i}
          {incref i}
            {print 'i now holds: '}
            {unref i
              {fun {v}
                {begin2 {print {number->string v}}
                        {print '\n'}}}}}}}}}")

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:

"{with-stx {do {<-}
    {bind {{incref {fun {b}
                    {do {curval <- {unref b}}
                        {set-ref! b {+ 1 curval}}}}}}
      {do {i <- {newref 0}}
          {incref i}
          {print 'i now holds: '}
          {v <- {unref i}}
          {print {number->string v}}
          {print '\n'}}}}")

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.