Version: 3
Last Modified: October 11, 2012, 5:47pm
Changes:
String.iteri. You may, however, be interested in
the library function List.iter. (4 points)inflate : float list -> float -> float ->
float * float such that inflate lst money rate
processes all the purchases in lst in this fashion, given
initial balance money and inflation rate rate.
Do not use folds or recursion. We have provided you a purely
functional version, inflate_fn, for you to check your
results against.
(5 points)
For this problem, you will implement an interpreter for a simplified version of the Scheme language. Scheme is a functional language whose semantics are very much like OCaml. Evaluation follows the environment model presented in class very closely.
We have provided a lexical analyzer and parser that can take a string
input, parse it as a Scheme program, and output an
abstract
syntax tree (AST) representing the code. The input program is
converted to a tree of type Ast.expr, defined in the
Ast module. Unlike OCaml, there is not a
lot of static typechecking done, so you will find the syntax of Scheme
quite a bit less restrictive than OCaml (not necessarily a good thing).
Your job will be to write functions for evaluating the AST that is returned from the parser. You will also have to check for various runtime type errors (such as applying an if-then-else to a non-Boolean), and to raise a runtime type error if the types of the expressions do not make sense in a given context.
A few Scheme programs are provided in the file etc/input.txt
. Here is a sample run with our solution code.
zardoz > (load "etc/input.txt") >>>> >> >> >> zardoz > (fact 4) >> 24 zardoz > (length (list 0 0 0)) >> 3 zardoz > (rev (list 1 2 3 4)) >> (4 3 2 1) zardoz > (cons 1 2) >> (1 . 2) zardoz > (fib 10) >> (55 34 21 13 8 5 3 2 1 1 0) zardoz > ((lambda (x y) (- x y)) 3110 2110) >> 1000 zardoz >
cons pairsnil.Undef that is used internally
for creating recursive definitions and is not available to the Scheme
programmer. The following code, taken from heap.ml, declares
the type value. When an expression is evaluated successfully,
the resulting value is an entity of this type.
type value = Int of int | Str of string | Bool of bool
| Closure of expr * env
| Cons of value * value | Nil
| Undef
| Character | Escaped |
|---|---|
| \ | \\ |
| " | \" |
| <newline> | \n |
| <tab> | \t |
Ast.Fun_e of Ast.id list * Ast.expr
Ast.Fun_e of Ast.id list * Ast.expr
Ast.Def_e of Ast.id list * Ast.exprThere is also a definerec version for creating recursive functions.
Ast.Def_e of Ast.id list * Ast.exprThere is also a definerec version for creating recursive functions.
Ast.If_e of Ast.expr * Ast.expr * Ast.expr.
| BO | AST Name | Meaning |
|---|---|---|
| + | Ast.Plus | Integer addition |
| - | Ast.Minus | Integer subtraction |
| * | Ast.Mul | Integer multiplication |
| / | Ast.Div | Integer division |
| % | Ast.Mod | Integer modulus |
| = | Ast.Eq | Comparison (equality) |
| != | Ast.Neq | Comparison (inequality) |
| < | Ast.Lt | Comparison (less than) |
| <= | Ast.Leq | Comparison (less than or equal to) |
| > | Ast.Gt | Comparison (greater than) |
| >= | Ast.Geq | Comparison (greater than or equal to) |
| & | Ast.And | Logical AND |
| | | Ast.Or | Logical OR |
Ast.Binop_e of op * expr * expr
| UO | AST Name | Meaning |
|---|---|---|
| - | Ast.Neg | Negate (subtract from 0) |
| ~ | Ast.Not | Logical complement |
| car | Ast.Car | Take the first element of a cons pair |
| cdr | Ast.Cdr | Take the second element of a cons pair |
| null | Ast.Null | Return true if the argument is nil, otherwise return false |
| load | Ast.Load | Read a file (specified by a string-valued argument) from disk |
Ast.Unop_e of op * expr
(cons e1 e2),
when evaluated, should recursively evaluate
e1 and e2, then
create a value of the form Cons (v1, v2)
from the resulting values.
There are corresponding projections car and cdr that
extract the first and second components of a pair, respectively; thus
(car (cons 1 2)) = 1 (cdr (cons 1 2)) = 2
The names car and cdr are historical; they stand for
contents of the address register and contents of the
decrement register, respectively, and refer to hardware components
of the IBM 704 computer on which LISP was
originally implemented in the late 1950s.
The special entity nil is used with cons
to form lists. Lists in Scheme are sequences of objects combined using
cons and terminated by nil. For example, the list
(cons 1 (cons 2 (cons 3 nil)))is the Scheme equivalent of the OCaml list
[1;2;3].
The object nil
serves as the empty list, and is analogous to the OCaml [].
The AST representation of nil is Ast.Nil_e.
There is a shorthand way to create lists in Scheme. Instead of typing
(cons 1 (cons 2 (cons 3 nil)))one can type
(list 1 2 3)and the resulting value is the same list. The output form of a list, i.e. the string that should be printed by your interpreter when you type either of the above expressions at the prompt, is
(1 2 3).
The display form of the value (cons 1 2) is (1 . 2).
Thus if you type (cons 1 2) at
your Scheme interpreter, it should respond with (1 . 2). Note,
however, that if the second component is nil instead of 2,
it should respond with (1), because in that case it is a
list of one element 1.
More generally, if you have any sequence of objects combined with
cons, but not terminated with nil, then
the output form puts a dot before the last element.
Thus
(cons 1 (cons 2 3)) = (1 2 . 3) (cons 1 (cons 2 nil)) = (1 2)and
(cons (cons 1 2) (cons 3 4)) = ((1 . 2) 3 . 4) (cons (cons 1 2) (cons 3 nil)) = ((1 . 2) 3)
Operations in Scheme are all represented in prefix notation and must be
enclosed in parentheses. For instance, to add 5 and 7, we would type
(+ 5 7). There is no notion of precedence and all compound
expressions must be enclosed in parentheses. For instance, the OCaml
expression 5 + (2 * 7) would be written
(+ 5 (* 2 7)) in Scheme.
Comparisons may be performed on Int, String, and Bool types, while arithmetic operators are valid only on Ints, and boolean operations are valid only on Bools.
Variables can be bound to values in several ways. Top-level global
variables are bound using the define keyword. Local
variables are bound using the let keyword. The
expression (let x 5 (* 2 x)) is equivalent to the OCaml
let x = 5 in 2*x.
Finally, anonymous functions are defined using the lambda
keyword. These can be bound to variables using define or
let. For example, (lambda x (* 2 x)) in Scheme is
equivalent to fun x -> 2*x in OCaml, and
(let f (lambda x (* 2 x)) (f 4)) in Scheme is equivalent
to let f = fun x -> 2*x in (f 4) in OCaml.
Furthermore, anonymous functions of several variables can also be
defined with lambda. For example,
(let f (lambda (x y z) (+ (+ x y) z)) (f 1 2 3))
is equivalent to the OCaml
let f = fun x y z -> x + y + z in f 1 2 3.
If we would like to use define to bind functions of one or
more variables at the top level, we can write
(define (f x y) (+ x y))
or
(define f (lambda (x y) (+ x y))) .
If the function is recursive, use letrec and
definerec instead.
These behave identically to let and define,
respectively, except that before the second argument is evaluated, the
function name is included in the environment bound to a dummy value
(Undef); then after the second argument is evaluated, the
binding is updated to that value. This means that the function name may
occur in the function body so that the function may call itself recursively.
An if expression evaluates its first argument, checks that it
is a boolean, and if so, evaluates the second or third argument according
as the value of the first argument is true or
false, respectively. The values of second and third
arguments need not be of the same type.
When applied to a cons pair, car returns the first
component, while cdr returns the second. You can test whether
a list is empty using the null operator.
The load operator can be used to load and interpret
the contents of a file. The operators load, define,
and definerec may be used only at the top level.
The interpreter we implemented exhibits an eager evaluation strategy by
default. That is to say, expressions are thoroughly evaluated when they
are bound to a variable, such as by a let statement, or by being passed
as an argument to a function.
Lazy evaluation
is an alternative to this strategy. Under lazy evaluation,
expressions are not evaluated until it is absolutely necessary to do so.
We will simulate lazy evaluation through two additional keywords:
delay and force.
Applying delay to an expression creates a thunk, which can
be thought of as a closure that takes no parameters but still preserves its
environment at the time of the delay. The thunk represents a suspended
computation that will not proceed until forced.
Applying force to a delayed expression causes the expression
to be evaluated in the environment from when it was delayed. If the
expression being forced was not delayed, then the expression is just evaluated
normally.
With lazy evaluation, we can create a stream, which is basically a lazy list. The only things that are stored at any one time are the head of the list, and the delayed expression that would generate the remainder of the stream. Here is a sample run with our code.
zardoz > (load "etc/lazy.txt") [...] zardoz > (take 10 naturals) >> (0 1 2 3 4 5 6 7 8 9) zardoz > (take 10 (drop 50 naturals)) >> (50 51 52 53 54 55 56 57 58 59) zardoz > (define st (from_list (list 4 86 6 9 3 0))) >> (4 .) zardoz > (stream_hd st) >> 4 zardoz > (to_list (stream_tl st)) >> (86 6 9 3 0) zardoz > (nth st 4) >> 3
mli files.
You must implement functions in the following files:
value_to_string.
Str values, simply output the appropriate
string, and for Int and Bool values,
simply use OCaml's string casting methods. nil as ().cons values in the form (x . y)
for a single pair of values, or for nested Cons of the form
(Cons x (Cons y (Cons z t))) output the value
as (x y z . t), placing a dot only before the final
element. Note that if the Cons is nested differently, say as
(Cons (Cons x y) (Cons z t)), then we would represent
this as ((x . y) z . t), since the first element
of the Cons is now itself the value (Cons x y)
rather than simply x. (x y z t),
without any dot. This format is used only for displaying
values in the output, and will not actually work as valid Scheme
expressions.Undef should print to a foreboding message,
because they should never appear in the top level.
lookup, update,
and bind, according to their specifications in
the interface.
eval. This should take in an
Ast.expr and a Heap.env and return a
Heap.value, which is the result of the expression,
evaluated in the environment. If type errors occur,
raise a runtime exception.
apply. This takes in two
Heap.value items, the first being a closure and the
second being the argument, and returns another Heap.value,
the result of the function applied to the argument in the closure's
environment. If the first value is not a closure containing a function,
raise a runtime exception.
eval_one. This should handle any top
level operations (declarations and loads) that can't exist elsewhere in a
program. Any declarations made in a loaded file should be included in
the scope of the remainder of the calling program.
mli files. However,
you should be sure not to change any existing definitions or types.
interpreter.exe which you can execute
to launch the command line interface.
ps4.zip containing the following files:
eval.ml, repl.ml, heap.ml,
ast.ml, util.ml, eval.mli,
repl.mli, heap.mli, ast.mli,
and util.mli.
fold_left,
fold_right, and map that behave the same
as their OCaml counterparts. (3 points each = 9 total)
@ sign in OCaml does,
this function should take two lists and return the second one
appended to the first one, preserving order. (2 points)
flatten should take in a list of lists and
return a single list that is the concatenation of all the input lists.
Ordering should be preserved. (2 points)
quicksort such that (quicksort l) will
return a list with the same elements as l, but sorted
in ascending order. (7 points)
A file scheme.scm containing your implementations.