Homework #10: Extending a (byte code) continuation based interpreter
Out: Friday, March 31st, Due: Thursday, April 13th, 11:59pm

Background

The language for this homework is:

#lang plait

In this assignment you will start with the interpreter from Lecture 18 and add some list-related primitives to it. Unlike Homework 8, we’ll be taking a dynamically typed approach, and allow things like e.g.

{rest {cons {fun {x} x} 1}}

to evaluate to 1.

Some preliminary changes have been made to the byte code FLANG interpreter for you

Added builtin identifier empty for the empty list, along with builtin function non-empty? so the following tests pass ( (read-int is defined in in the given skeleton).

(test (read-int (run `42)) 42)
(test/exn (read-int (run `empty)) "expected number")
(test (ref (run `empty) 0) tag:EmptyListV)
(test (read-int (run `{non-empty? empty})) 0)

Defined FLANG variants Cons, First, and Rest to represent analogous operations to cons, first, rest in racket. Updated compile with appropriate .... based stubs to get things compiling again.

Updated the parser to understand concrete syntax for cons, first, rest. Added the following tests

(test (parse `{cons 1 2}) (Cons (Num 1) (Num 2)))
(test (parse `{first {cons 1 2}}) (First (Cons (Num 1) (Num 2))))
(test (parse `{rest {cons 1 2}}) (Rest (Cons (Num 1) (Num 2))))

Note that an earlier version of byte code FLANG interpreter had the read-int function defined inside the test submodule. You need it defined in the top level module for the handin server.

Part 1: Compilation to byte code for first and rest

Use the given tags tag:Cons, tag:First and tag:Rest for byte compiled syntax to update the compile function to pass the following tests:

(reset!)
(test (compile (parse `{cons 1 2}) (EmptyCompileEnv)) 4)
(test (vector-elements code-memory 0 7)
      (list tag:Num 1 tag:Num 2 tag:Cons 0 2))

(reset!)
(test (compile (parse `{first {cons 1 2}}) (EmptyCompileEnv)) 7)
(test (vector-elements code-memory 0 9)
      (list tag:Num 1 tag:Num 2 tag:Cons 0 2 tag:First 4))

(reset!)
(test (compile (parse `{rest {cons 1 2}}) (EmptyCompileEnv)) 7)
(test (vector-elements code-memory 0 9)
      (list tag:Num 1 tag:Num 2 tag:Cons 0 2 tag:Rest 4))

Part 2: Interpretation

Use the given tags tag:Cons, tag:consSecondK, and tag:doConsK to add appropriate cases for the new tags to interp and continue so that cons syntax is properly intepreted. A simple test that does not need first or rest is as follows
(let ([result (run `{cons 1 2})]) (begin (test (ref result 0) tag:ConsV) (test (read-int (ref result 1)) 1) (test (read-int (ref result 2)) 2)))
Use the given tags to extend interp and continue to handle first and rest. Your updated code should pass the following tests.
(test (read-int (run `{first {cons 1 2}})) 1) (test (read-int (run `{rest {cons 1 2}})) 2)

Part 3: GC

Update move and update to handle the new tags you used above. You will have to take into account both the size and the shape (i.e. what is contained in each slot). One subtlty is that code references (i.e. indexes into code-memory) do not need to be relocated. A low level sanity check for the updated GC is as follows

(let ([result (run `{cons 2 {cons 1 0}})])
  (begin
    (test (ref result 0) tag:ConsV)
    (test (read-int (ref result 1)) 2)
    (test (ref result 2) tag:ConsV)
    (gc)
    (test (ref v-reg 0) tag:ConsV)
    (test (read-int (ref v-reg 1)) 2)))

With the given definition of MEMORY-SIZE as 128, the following should pass, and invoke gc multiple times.

(test
 (read-int
  (run
  `{{fun {mkrec}
       {{fun {sum} {sum {cons 4 {cons 3 {cons 2 {cons 1 empty}}}}}}
        {mkrec
         {fun {sum}
              {fun {lst}
                   {if0 {non-empty? lst}
                        0
                        {+ {first lst} {sum {rest lst}}}}}}}}}
   {fun {body-proc}
       {{fun {fX} {fX fX}}
        {fun {fX} {body-proc {fun {x} {{fX fX} x}}}}}}}))
 10)

Finally

Make sure you have complete test coverage.