the nature of '()
Nick Keighley
I'm trying to implement a scheme interpreter (probably not the first
person on comp.lang.scheme to do this!). I'm not expecting it to to
serve any purpose apart from from teaching me a little bit about
scheme.
I saw the simple interpreters in SICP and I had two thoughts about
them. The first was "wow that's so simple" and the second was "isn't
this too easy because an implementation of scheme in scheme is doing a
lot of stuff for you". For instance the handling of symbols and memory
managment. It also avoided interesting things like continuations.
I'm currently implementing quote and in particular '() the
representation of null. I can see two ways to deal with '(). It can
either be dealt with as a special case in read. '(1 2) is represented
internally as (quote (1 2)). And then evaled as (1 2). But should '()
be represented as (quote ()) and evaled as (), or should it be
translated by the reader as (). To a certain extent internal
representations are the implementor's business. I'm almost pursuded
that the Lisp people are right and that a null list should be a
special magic symbol. So should I treat the sequence of characters
"'()" simply as a magic syntactic sequence that represents the null
pointer? Say as something that might be spelled "nil".
This has been fun and educational. Trying to build sexps in Imperitive
Langugage De Jour (ILDJ) has been interesting. At some points I've
coded things in scheme then hand translated them into ILDJ. It was
easier to think in scheme. My test suite contains such gems as
list_obj.set_pair (
cons (Object(1), cons (
Object (cons (Object(2), cons (Object(3), null_object))),
cons (Object(4), null_object)))
);
I've learned why you cons lists then reverse them and I'm currently
probably going down a blind alley with three different sorts of
(incompatible) dynamically allocated objects.
Sorry for the stream-of-conciousness-post but hopefully some of it
made sense
--
scheme might be the purple pill
Nils M Holm
> But should '()
> be represented as (quote ()) and evaled as (), or should it be
> translated by the reader as ().
If the reader translates '() to (), then how can you distinguish
between '() and ()? Is () a valid Scheme form?
--
Nils M Holm | http://t3x.org
Nick Keighley
> Nick Keighley <nick_keighley_nos...@hotmail.com> wrote:
> > But should '()
> > be represented as (quote ()) and evaled as (), or should it be
> > translated by the reader as ().
>
> If the reader translates '() to (), then how can you distinguish
> between '() and ()? Is () a valid Scheme form?
chicken says "illegal non-atomic form" and gambit "Ill formed
expression". So I guess not.
Jay Reynolds Freeman
the single-quote, and then goes on and calls an S-expression-reading
routine to find out what it is that is going to be quoted. If that
routine sees an empty list, then the reader constructs a special
object that happens to print out as (). (Wraith Scheme is a tagged-
object implementation, and there is a whole tag reserved for just the
empty list.) On the other hand, if the reader sees an unquoted pair
of parentheses at top-level -- that is, if you mistakenly typed ()
instead of '() -- it reports an error.
Jay Reynolds Freeman
Jay_Reynol...@mac.com
http://web.mac.com/Jay_Reynolds_Freeman
Pascal Costanza
> The way I did it in Wraith Scheme is basically this: The reader sees
> the single-quote, and then goes on and calls an S-expression-reading
> routine to find out what it is that is going to be quoted. If that
> routine sees an empty list, then the reader constructs a special
> object that happens to print out as (). (Wraith Scheme is a tagged-
> object implementation, and there is a whole tag reserved for just the
> empty list.) On the other hand, if the reader sees an unquoted pair
> of parentheses at top-level -- that is, if you mistakenly typed ()
> instead of '() -- it reports an error.
Is there a specific reason why Scheme doesn't just accept () as a
shorthand for '(), as is the case in Lisp?
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Pascal J. Bourguignon
> On 25/05/2010 13:35, Jay Reynolds Freeman wrote:
>> The way I did it in Wraith Scheme is basically this: The reader sees
>> the single-quote, and then goes on and calls an S-expression-reading
>> routine to find out what it is that is going to be quoted. If that
>> routine sees an empty list, then the reader constructs a special
>> object that happens to print out as (). (Wraith Scheme is a tagged-
>> object implementation, and there is a whole tag reserved for just the
>> empty list.) On the other hand, if the reader sees an unquoted pair
>> of parentheses at top-level -- that is, if you mistakenly typed ()
>> instead of '() -- it reports an error.
>
> Is there a specific reason why Scheme doesn't just accept () as a
> shorthand for '(), as is the case in Lisp?
Yes. The Specifications of Scheme.
That should be a Specific enough reason, no? :-)
Notice that in CL, () is read as the symbol CL:NIL, and evaluating
CL:NIL results into CL:NIL since it's defined as self-evaluating
constant. (The final result is therefore the same, when you evaluate
() or '(), but you go thru different branches of the CL:EVAL
function).
In the case of Scheme, () is read as an empty list, which is not a
symbol. When trying to evaluate it, since it is a list, we try to
evaluate the elements, and then call the result of (car '()) with the
results of the (cdr '()) as argument. Oops, (car '()) or (cdr '()) is
defined to signal an error in R5RS!
So to define () as a shorthand for '() in CL, you just need to do nothing,
while to do the same in Scheme you would have to specify an exception
to the evaluation model.
--
__Pascal Bourguignon__
http://www.informatimago.com
Nick Keighley
wrote:
> The way I did it in Wraith Scheme is basically this: The reader sees
> the single-quote, and then goes on and calls an S-expression-reading
> routine to find out what it is that is going to be quoted. If that
> routine sees an empty list, then the reader constructs a special
> object that happens to print out as ().
that's what I was considering
> (Wraith Scheme is a tagged-
> object implementation, and there is a whole tag reserved for just the
> empty list.)
me too. At the moment not doing anything special seems to work (ie.
representing it as (quote ()) )
> On the other hand, if the reader sees an unquoted pair
> of parentheses at top-level -- that is, if you mistakenly typed ()
> instead of '() -- it reports an error.
hmm. My code justs treats it like an empty list at them moment! But I
think that was sheer luck!
Nick Keighley
wrote:
plainly I have some work to do!
Nick Keighley
er... my code had empty list defined as self evaluating. Which is
wrong.
But when I modified that it failed to spot that empty list was a
function application (it's not a pair) and dropped into the "unknown
expression type" bin. Should an empty list be recognised as a function
application? SICP doesn't seem to do so...
Pascal J. Bourguignon
If you are implementing R5RS, you can always refer to the formal
syntax and semantics.
http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-10.html
First, () is not a syntactically valid word.
It is a <list> and a <datum>, but not an <expression>.
On the other hand, 7.2.3 says that "Definition of K deliberately
omitted.", so perhaps you can define it so that (eval '()) returns ().
There is still quite an amount of hand waving in this chapter 7...
Nick Keighley
wrote:
well I'd already read R5RS but I'm a bit out of my depth with
denotational semantics.
> First, () is not a syntactically valid word.
> It is a <list> and a <datum>, but not an <expression>.
>
> On the other hand, 7.2.3 says that "Definition of K deliberately
> omitted.", so perhaps you can define it so that (eval '()) returns ().
>
> There is still quite an amount of hand waving in this chapter 7...
:-)
so its not a complete semantics?
Nils M Holm
> > If you are implementing R5RS, you can always refer to the formal
> > syntax and semantics.
> >
> > http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-10.html
>
> well I'd already read R5RS but I'm a bit out of my depth with
> denotational semantics.
>
> > First, () is not a syntactically valid word.
> > It is a <list> and a <datum>, but not an <expression>.
You do not have to go to the semantic level to find out that
() is not a valid expression. As Pascal already pointed out,
it cannot be produced by the R5RS grammar. See in particular
the <expression>, <procedure call>, and <literal> productions
in (long line!):
http://www.schemers.org/Documents/Standards/R5RS/HTML/r5rs-Z-H-10.html#%_sec_7.1.3
That being said, the detection of () is often a bit cumbersome
to implement, so quite a few implementations silently map it
to '().
Pascal J. Bourguignon
>> There is still quite an amount of hand waving in this chapter 7...
>
> :-)
>
> so its not a complete semantics?
Well, indeed, it seems I just discovered that it wasn't really
complete, and cannot answer to your question. Once you've got some
reading and some evaluating (eg of quote) done, then it specifies the
semantics. But it doesn't express the semantics of quote.
I guess that's because they have difficulties with the different
environments, read, compilation, load, execution. They didn't bother
to specify formally what it '(a "b") means because a and "b" have to
be different objects in the different environments.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Tom Lord
whether or not #f and '() are or are not the same value.
They were permitted to be the same and some implementations
made them the same.
In such an implementation, (eval '()) would have been
*require* to return #f / ().
In all of these years I've never seen anyone offer
any strong objective evidence that the empty list and
#f should be different. I've seen arguments for it.
I've not seen any really convincing arguments.
Some say that it's conceptually cleaner, perhaps
easier to learn. Since I'm reasonably sure I don't
agree as a matter of opinion, is there any objective
evidence in support of that?
I've vaguely heard that the distinction is vital to
optimizing compilation. Has this been demonstrated
through measurement?
Allowing () as short-hand for '() is not the same
thing as eq'ing () and #f. The issues are different.
They do overlap regarding this question about the
evaluation rule for (eval '()).
-t
Nils M Holm
> In all of these years I've never seen anyone offer
> any strong objective evidence that the empty list and
> #f should be different. I've seen arguments for it.
> I've not seen any really convincing arguments.
The only one I came across is efficiency. If I understand
the RnRS for n<4 correctly, while #f and '() are both false,
they are still distinct object, so that, for example,
(1 . #f) is not a list. So in order to find out whether or
not an object represents a true value, you must make sure
it is neither '() nor #f, while in R5RS, you just have to
check that it is not #f.
At least this is why I decided to make '() =/= #f in my own
R4RS implementation. I have never measured the difference
in real-life programs, though, so you may consider this
argument to be just another opinion.