CS 6510 Homework 5

Due: Tuesday, February 21st, 2017 11:59pm

Part 1 — Lazy Pairs

Implement an interpreter with lazy evaluation and the following grammar:

  <Expr> = <Num>
         | <Sym>
         | {+ <Expr> <Expr>}
         | {* <Expr> <Expr>}
         | {lambda {<id>} <Expr>}
         | {<Expr> <Expr>}
         | {let {[<id> <Expr>]} <Expr>}
         | {if0 <Expr> <Expr> <Expr>}
         | {cons <Expr> <Expr>}
         | {first <Expr>}
         | {rest <Expr>}

That is, a language with single-argument functions and application, an if-zero conditional, and cons, first, and rest operations. (The language does not include recursive bindings or records.) The cons operation does not require its second argument to be a list, so rest can also return a non-list.

Implement your interpreter with the plai-typed language, not a lazy language.

Evaluation of the interpreted langauge must be lazy, however. In particular, if a function never uses the value of an argument, then the argument expression should not be evaluated. Similarly, if the first or rest of a cons cell is never needed, then the first or rest expression should not be evaluated.

Start with more-lazy.rkt. Expand the parse function to support the new forms: if0, cons, first, and rest. Also, as in HW 5, provide an interp-expr function; the interp-expr wrapper for interp should take an expression and return either a number S-expression, `function for a function result, or `cons for a cons result. (Meanwhile, the interp function should never return the symbol `cons, just like the starting interp function never returns the symbol `function.)

  (test (interp-expr (parse '10))
        '10)
  (test (interp-expr (parse '{+ 10 17}))
        '27)
  (test (interp-expr (parse '{* 10 7}))
        '70)
  (test (interp-expr (parse '{{lambda {x} {+ x 12}}
                              {+ 1 17}}))
        '30)
  
  (test (interp-expr (parse '{let {[x 0]}
                               {let {[f {lambda {y} {+ x y}}]}
                                 {+ {f 1}
                                    {let {[x 3]}
                                      {f 2}}}}}))
        '3)
  
  (test (interp-expr (parse '{if0 0 1 2}))
        '1)
  (test (interp-expr (parse '{if0 1 1 2}))
        '2)
  
  (test (interp-expr (parse '{cons 1 2}))
        `cons)
  (test (interp-expr (parse '{first {cons 1 2}}))
        '1)
  (test (interp-expr (parse '{rest {cons 1 2}}))
        '2)
  
  ;; Lazy evaluation:
  (test (interp-expr (parse '{{lambda {x} 0}
                              {+ 1 {lambda {y} y}}}))
        '0)
  (test (interp-expr (parse '{let {[x {+ 1 {lambda {y} y}}]}
                               0}))
        '0)
  (test (interp-expr (parse '{first {cons 3
                                          {+ 1 {lambda {y} y}}}}))
        '3)
  (test (interp-expr (parse '{rest {cons {+ 1 {lambda {y} y}}
                                         4}}))
        '4)
  (test (interp-expr (parse '{first {cons 5
                                          ;; Infinite loop:
                                          {{lambda {x} {x x}}
                                           {lambda {x} {x x}}}}}))
        '5)
  
  (test (interp-expr 
         (parse 
          '{let {[mkrec
                  ;; This is call-by-name mkrec
                  ;;  (simpler than call-by-value):
                  {lambda {body-proc}
                    {let {[fX {lambda {fX}
                                {body-proc {fX fX}}}]}
                      {fX fX}}}]}
              {let {[fib
                     {mkrec
                      {lambda {fib}
                        ;; Fib:
                        {lambda {n}
                          {if0 n
                               1
                               {if0 {+ n -1}
                                    1
                                    {+ {fib {+ n -1}}
                                       {fib {+ n -2}}}}}}}}]}
                ;; Call fib on 4:
                {fib 4}}}))
        '5)

  (test (interp-expr 
         (parse 
          '{let {[mkrec
                  ;; This is call-by-name mkrec
                  ;;  (simpler than call-by-value):
                  {lambda {body-proc}
                    {let {[fX {lambda {fX}
                                {body-proc {fX fX}}}]}
                      {fX fX}}}]}
             {let {[nats-from
                    {mkrec
                     {lambda {nats-from}
                       ;; nats-from:
                       {lambda {n}
                         {cons n {nats-from {+ n 1}}}}}}]}
               {let {[list-ref
                      {mkrec
                       {lambda {list-ref}
                         ;; list-ref:
                         {lambda {n}
                           {lambda {l}
                             {if0 n
                                  {first l}
                                  {{list-ref {+ n -1}} {rest l}}}}}}}]}
                 ;; Call list-ref on infinite list:
                 {{list-ref 4} {nats-from 2}}}}}))
        '6)

Part 2 — Recursive Binding

Although we can implement recursive functions using mkrec as shown in the examples above, we cannot use that pattern to implement infinite lazy lists directly, as in (define ones (cons 1 ones)), because lists are not represented as functions.

Extend your interpreter with a letrec form for recursive binding:

  <Expr> = ....
         | {letrec {[<id> <Expr>]} <Expr>}

To implement letrec, you are allowed to use state at the plai-typed level, but the language that your interpreter implements must still be purely functional (i.e., no visible side effects).

   (test (interp-expr 
          (parse
            '{letrec {[ones {cons 1 ones}]}
               {first {rest {rest ones}}}}))
         '1)

   (test (interp-expr 
          (parse
           '{letrec {[x 1]}
              {letrec {[y 2]}
                {+ x y}}}))
         '3)
   (test (interp-expr 
          (parse
            '{letrec {[x 1]}
               {letrec {[y y]}
                 {+ x x}}}))
          '2)

   (test (interp-expr 
          (parse
            '{letrec {[ones {cons 1 ones}]}
               {letrec {[list-ref
                         {lambda {l}
                          {lambda {n}
                           {if0 n
                                {first l}
                                {{list-ref {rest l}} {+ n -1}}}}}]}
                 {+ {{list-ref ones} 42}
                    {{list-ref ones} 79}}}}))
          '2)