CS 5510 Homework 5

Due: Wednesday, October 21st, 2009 9:40am

Implement an interpreter with lazy evaluation and the following grammar:

  <CNSFAL> = <number>
          | {+ <CNSFAL> <CNSFAL>}
          | {- <CNSFAL> <CNSFAL>}
          | <id>
          | {fun {<id>} <CNSFAL>}
          | {<CNSFAL> <CNSFAL>}
          | {if0 <CNSFAL> <CNSFAL> <CNSFAL>}
          | {cns <CNSFAL> <CNSFAL>}
          | {fst <CNSFAL>}
          | {rst <CNSFAL>}

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.

Implement your interpreter with the PLAI 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 cfal.ss. Expand the parse function to support the new forms: if0, cns, fst, and rst. Also, as in HW 3, provide an interp-expr function; the interp-expr wrapper for interp should take an expression and return either a number, 'func for a function result, or 'cons for a cons result. (Meanwhile, the interp function should never return 'cons, just like the starting interp function never returns 'func.)

  (test (interp-expr (parse 10))
        10)
  (test (interp-expr (parse '{+ 10 17}))
        27)
  (test (interp-expr (parse '{- 10 7}))
        3)
  (test (interp-expr (parse '{{fun {x} {+ x 12}}
                              {+ 1 17}}))
        30)
  
  (test (interp-expr (parse '{{fun {x}
                                   {{fun {f}
                                         {+ {f 1}
                                            {{fun {x}
                                                  {f 2}}
                                             3}}}
                                    {fun {y} {+ x y}}}}
                              0}))
        3)
  
  (test (interp-expr (parse '{if0 0 1 2}))
        1)
  (test (interp-expr (parse '{if0 1 1 2}))
        2)
  
  (test (interp-expr (parse '{cns 1 2}))
        'cons)
  (test (interp-expr (parse '{fst {cns 1 2}}))
        1)
  (test (interp-expr (parse '{rst {cns 1 2}}))
        2)
  
  ;; Lazy evaluation:
  (test (interp-expr (parse '{{fun {x} 0}
                              {+ 1 {fun {y} y}}}))
        0)
  (test (interp-expr (parse '{fst {cns 3
                                       {+ 1 {fun {y} y}}}}))
        3)
  (test (interp-expr (parse '{fst {cns 5
                                       ;; Infinite loop:
                                       {{fun {x} {x x}}
                                        {fun {x} {x x}}}}}))
        5)
  
  (test (interp-expr 
         (parse 
          '{{fun {mkrec}
                 {{fun {fib}
                       ;; Call fib on 4:
                       {fib 4}}
                  ;; Create recursive fib:
                  {mkrec
                   {fun {fib}
                        ;; Fib:
                        {fun {n}
                             {if0 n
                                  1
                                  {if0 {- n 1}
                                       1
                                       {+ {fib {- n 1}}
                                          {fib {- n 2}}}}}}}}}}
            ;; This is call-by-name mkrec
            ;;  (simpler than call-by-value):
            {fun {body-proc}
                 {{fun {fX}
                       {fX fX}}
                  {fun {fX}
                       {body-proc {fX fX}}}}}}))
        5)
  
  (test (interp-expr 
         (parse 
          '{{fun {mkrec}
                 {{fun {nats-from}
                       {{fun {list-ref}
                             ;; Call list-ref on infinite list:
                             {{list-ref 4} {nats-from 2}}}
                        ;; Create recursive take:
                        {mkrec
                         {fun {list-ref}
                              ;; list-ref:
                              {fun {n}
                                   {fun {l}
                                        {if0 n
                                             {fst l}
                                             {{list-ref {- n 1}} {rst l}}}}}}}}}
                  ;; Create recursive nats-from, which generates
                  ;;  an infinite list of numbers:
                  {mkrec
                   {fun {nats-from}
                        ;; nats-from:
                        {fun {n}
                             {cns n {nats-from {+ n 1}}}}}}}}
            ;; This is call-by-name mkrec:
            {fun {body-proc}
                 {{fun {fX}
                       {fX fX}}
                  {fun {fX}
                       {body-proc {fX fX}}}}}}))
        6)