CSE341 -- Assignments -- Miranda Evaluator

Due 25 May 2000

Submission directions: Please turn in both printed and electronic copies of your code. The print submission is due in class on the due date above. You may e-mail the electronic copies to Keunwoo (klee@cs) anytime the same day. For full credit, you must follow the submission guidelines.

1. Write and test a Miranda function evaluate that evaluates a Scheme expression (for a very restricted subset of Scheme). For this assignment, consider expressions consisting of:
   • a number
   • a variable
   • an arithmetic expression using the functions +, -, *, or / (just the two-argument versions)
   • a let expression consisting of a list of names and values, and an expression to evaluate in the new environment. let expressions can of course be nested (using lexical scoping).
   Major simplification: for the basic assignment you don't need to write a parser to parse Scheme syntax. Instead, you can define some appropriate Miranda types, and write your expressions using those. For example, here are some Scheme expressions and a possible definition of these using Miranda types.

   Scheme version:     10
   Miranda version:    Num 10
   
   Scheme version:     (+ 10 (* 2 3))
   Miranda version:    Plus (Num 10) (Times (Num 2) (Num 3))
   
   Scheme version:     
        (let ((x (+ 10 20))
              (y 50))
           (+ x y))
   Miranda version:
         (Let [
              (Def "x" (Plus (Num 10) (Num 20))),
              (Def "y" (Num 50))
              ]
           (Plus (Var "x") (Var "y")))
   
   
   Scheme version:     
        (let ((x 10)
              (y 20)
              (z 30))
           (let ((x y)
                 (y (+ x 100)))
              (+ (+ x y) z)))
   Miranda version:
         (Let [
              (Def "x" (Num 10)),
              (Def "y" (Num 20)),
              (Def "z" (Num 30))]
           (Let [
                (Def "x" (Var "y")),
                (Def "y" (Plus (Var "x") (Num 100)))
                ] 
             (Plus (Plus (Var "x") (Var "y")) (Var "z"))))
   

   Test your function on these and other appropriate test cases.

   Hints: you can figure out Miranda type definitions that match the above versions, or write different versions if you prefer.

   It will be easier to test your program if you define some test variables, for example:

   test2 = Plus (Num 10) (Times (Num 2) (Num 3))
   

   Then you can just say

   evaluate test2
   

   instead of typing in a complex expression. The file ~borning/341/scheme.m on tahiti has a set of definitions that you can copy into your Miranda script. (Modify them if you use different type definitions than I did.)

   Include a type definition for all important functions in your script -- this makes debugging much easier.

   Write an auxiliary function to evaluate an expression in a given environment. You will need a way of looking up variables in environments, and forming new environments from existing ones, in a way that implements lexical scoping. An easy way to do this is to represent an environment as a list of (variable,value) pairs. Search the list for a given variable to look up its value in that environment. When you enter a new scope, append the new bindings to the front of the list to create the new environment; that way, nested declarations will mask off outer ones. Be sure and use the correct semantics for let (in particular don't implement let* semantics).

2. Write a print function that takes an expression (as defined in Question 1) and returns a string in Scheme syntax. For example, if test2 is defined as above, then print test2 should evaluate to (+ 10 (* 2 3)).

3. Extra credit (easy - 10% extra): modify print to pretty-print the expression, with suitable indentation.

4. Extra credit (hard - for 50% extra credit): write a parser to accompany your expression evaluator that parses Scheme expressions in standard Scheme syntax. If you want to try this, look at Assignment 7 and the solution from CSE 341 Autumn 1998 for some ideas on how to do this -- see Autumn 1998 CSE 341 assignments. If you want to do this, Alan can schedule an extra discussion section on Friday or Monday to talk about parsing basics -- send Alan mail.