I am in the position of having to implement a Scheme functional-only
subset interpreter in Haskell, and I would like to hear your thoughts
on the subject.
My main concern are the lists. As you know, in Scheme and LISPs,
the list "type" is a subset of lists. A so-called "proper" list is
represented, as in Haskell, by nested pairs, e.g.:
(1 . (2 . (3 . () ) ) ) = (1 2 3).
However there are also "improper" lists where the last element is not
an empty list, e.g.:
(1 . (2 . 3)) = (1 2 . 3).
The reference I have to follow has the following amusing explanation:
"A chain of pairs not ending in the empty list is called an 'improper
list. Note that an improper list is not a list." Right. In the
interpreter, list elements are objects in type Datum, so we can
represent pairs with this type:
data Pair = Pair Datum Datum
The our Datum looks like:
data Datum = DatumNum Num
...
DatumPair Pair
DatumNil Nil
...
But, using this scheme:
(1) we can't define a subtype (List in Pair) where List looks
like a Pair with the second projection restricted to Nil or Lists
(2) functions defined over Pair cannot use Prelude list
functions like "take", etc.
So we could do something like this instead:
data LISPlist = Proper [Datum] | Improper [Datum] Datum
so that proper lists look and work more like Haskell lists, but now
pairs look strange, e.g., (3 . 3) would be:
Improper [DatumNum (Exact 3)] (DatumNum (Exact 3)).
Both representations are unsatisfactory, but I am inclined to use the
second because Proper lists will be more convenient to deal with using
the Prelude functions, and the Prelude functions will probably be
faster.
Still, the Pair representation is cleaner, and it is still possible
to normalize proper lists represented as Pairs into Haskell lists at
critical points in a calculation. Unfortunately, since this is an
interpreter, it might be difficult to find those critical points.
Does anyone have any thoughts on this, or experience in implementing
this?
BTW, I am also curious to hear if there is any reasonable way to
dispense with the "administrative" injections you get when building
expressions in the abstract syntax, e.g., to turn a boolean into an
expression:
Expr (Literal (SelfEval (Boolean True)))
It seems like the obvious solution is to use qualified types to get
a form of sub-typing, but if you have a function, say, that returns
different kinds of expressions, you still need to encapsulate each
possible return value of a case, for example.
I know these problems can be solved with existential types and
constructor classes (which can implement existential types), but I am
looking for Haskell 1.2 techniques.
Frank Christoph
[EMAIL PROTECTED]
