Chris Rathman wrote:
Translated the first section of SICP Chapter #4 into Alice - the
eval/apply interpreter. Not sure if I'm on the right track, but since
the remainder of the book leverages off the interpreter, I thought I'd
ask for suggestions on cleaning up the code.
Very nice! Don't know why you think you might be off track, to me it
looks good. I only have minor comments:
* The definition of environment would be simpler and closer to SICP if
you just said "type env = frame list", with "type frame = value
Frame.map". That would also allow you to reuse some list combinators for
lookup and update.
* The structural comparison with "ValBool true" in eval (case TmIf) is
not valid SML. It only works here because Alice does not yet implement
equality types, but that will change (better use a case). Likewise the
real comparison in apply_primitive_procedure (use Real.==).
* You could take advantage of currying in the cases TmApplication and
TmBegin if you defined eval in curried form.
* It does not seem to make sense to define ValClosure to carry a *list*
of terms - you never use it.
* If you want to be ML-ish then you could also simplify lambdas and
application to single argument constructions. Instead of variable arity
there, I would probably combine and generalise TmUnit/ValUnit and
TmPair/ValPair to a single TmTuple/ValTuple (or just rely on currying).
* In the valueToString function, note that Char.toString does perform
escaping. For symmetry, you might want to do the same for strings (via
String.toString). Also, I'd probably add quotes.
* A rather more sophisticated change would be to simplify
apply_primitive_procedure by introducing an auxiliary datatype with
higher-order constructors:
datatype Primitive = PrimIntToInt of int -> int
| PrimIntTimesIntToInt of int * int -> int
| ...
fun
| apply_primitive_procedure (PrimIntToInt f, [ValInt v]) = ValInt(f v)
| apply_primitive_procedure (PrimIntTimesIntToInt f, [ValInt v1,
ValInt v2]) = ValInt(f(v1, v2))
Frame.insert(frame, "~", ValPrimitive(PrimIntToInt op~));
Frame.insert(frame, "+", ValPrimitive(PrimIntTimeIntToInt op+));
Well, for overloaded or generic identifiers you actually had to
introduce special constructors:
| PrimNumTimesNumToBool of
{int : int*int -> bool, real : real*real -> bool}
| apply_primitive_procedure (PrimNumTimesNumToInt{int, ...}, [ValInt
v1, ValInt v2]) = ValBool(f(v1, v2))
| apply_primitive_procedure (PrimNumTimesNumToInt{real, ...},
[ValReal v1, ValReal v2]) = ValBool(f(v1, v2))
The main problem that I see (beyond not having lex/parse) is that I'm
not sure how to handle "let".
Let should be simple, computationally it is just a combination of lambda
and apply:
let x = e1 in e2 == (fn x => e2)(e1)
So you can copy&paste&specialise the evaluation rules.
Also the primitives seem to be exploding,
If you want to reduce primitives, I'd probably throw out reals and
chars, since they do not provide anything interesting.
I'd prefer to actually have it be a
metacircular ML but since ML is a much larger and involved language,
that's not currently in the cards.
The only "meta-circular", full SML I'm aware of is Hamlet - and that is
quite big... ;-)
Cheers,
- Andreas
_______________________________________________
alice-users mailing list
[email protected]
http://www.ps.uni-sb.de/mailman/listinfo/alice-users
