[plt-scheme] Why isn't the car of a list of symbols a symbol?

On Jul 10, 2009, at 1:33 PM, Marco Morazan wrote:

> IMHO, calling ((quote yes) (quote no)) a list is confusing for
> beginning students. You can not use it as a list in a program unless
> you slap with an annotation (i.e. a quote). So, in a program you argue
> it is an application expression and everywhere else students must
> consider it a list?

No.  When you type it in, it's ALWAYS a list.  When you evaluate it  
(whether at the top level or as an argument to an ordinary function),  
the list is evaluated by the function-evaluation rule.  If you want  
to use it without evaluation in a context where it would normally be  
evaluated, you slap a quote on it to prevent evaluation.

> Frankly, that is adding an unnecessary level of complexity. We  
> should not have to imagine a repl without the e.

Well, no, we don't HAVE to, but that struck me as a nice simple way  
to understand the difference between syntax and semantics, between an  
expression and its value.  Do you really find it simpler to think of  
read, eval, and print as inextricably linked?

>> No question: Scheme syntax says it's a list (or, technically, a  
>> syntax
>> object, i.e. a list with decorations).
>
> I have not reviewed the parser used by DrScheme, but I would be very
> surprised if ((quote yes) (quote no)) is parsed as a list. In every
> parser I have  ever written and seen it would parse as an application
> expression. That is, the concrete syntax may have it look like a list,
> but in the abstract syntax and in reality it is not a list.

Yes, in reality (in the current implementation of DrScheme) it is a  
syntax object.  But that's just an implementation detail.  Scheme  
COULD be implemented (and I think some of the early Lisps WERE  
implemented) by parsing it as a list and writing "eval" to handle  
lists in such-and-such a way.  What any particular modern  
implementation actually does (AFAIK) is just an elaboration on this,  
adding some decorations to support error-reporting, optimizing common  
cases like function application, etc.

>> Absolutely... but let's not equate "an expression" with "the value  
>> of an
>> expression".  (* 1 2 3) and (- 10 4) are completely different  
>> syntactic
>> expressions
>
> Let's not equate an expression with a list. (* 1 2 3) and (- 10 4) are
> both application expressions. That is, they form instances of the same
> syntactic category. One *could* use a list to represent them
> internally, but that is usually not the case. In any case, in a Scheme
> *program* they are application expressions regardless of how they are
> represented internally.

If I read this correctly, you're saying that "application expression"  
is a sub-type of syntax object.  OK, I'll buy that, as an  
implementation detail.  But naming it an "application expression"  
doesn't necessarily mean anything will ever be applied to anything  
else, so it's sort of a misleading name.


>>> In the two student languages you mention when you ask what is  
>>> ((quote
>>> yes) (quote no)), you can see that Scheme considers it an  
>>> application
>>> expression. It is the *human* interpreter that introduces  
>>> ambiguity by
>>> interpreting it as a list.
>>
>> What exactly do you mean by "Scheme considers it..."?  The "read"  
>> part of
>> the read-eval-print loop has never heard of an "application  
>> expression"; it
>> converts a string into (to a first approximation) a list.  Only  
>> the "eval"
>> part considers it an application expression.
>>
>
> Usually, the input is read and parsed resulting in a parse tree. In
> this parse tree, ((quote yes) (quote no)) is an application
> expression. This all occurs *before* eval comes into the picture. So,
> that explains what I mean by "considers it."

But if you think of "application expression" as a purely syntactic  
construct, before eval comes into the picture, then there's nothing  
wrong with the application of (quote yes) to (quote no); it's just as  
good an application expression as applying sqrt to 3, or (lambda (x)  
(+ x 2)) to 5.  The error messages you quoted before came from eval,  
not from the reader, so they don't tell me anything about what the  
input "is", only what happens to it on evaluation.

I'm not sure what distinction you're drawing between a list and an  
application-expression.  What difference does it make whether a node  
in a parse tree refers to its two subtrees as "function" and  
"arglist" or as "car" and "cdr"?

> You may argue that a
> parse tree can beimplemented using lists, but that representation (or
> any other) is inconsequential as to what ((quote
> yes) (quote no)) is. It is an application expression and it is not a
> list which would require a quote.

I think you've defined lists out of existence.  How do you write a  
list?  The easiest way is as '(a b c), which is an abbreviation for  
(quote (a b c)), which is (syntactically) an application expression,  
not a list.  In fact, I can't think of ANYTHING that is still a (non- 
empty) list rather than an application expression under this definition.

Or are you instead treating '(a b c) as a literal of type "list", and  
(quote (a b c)) as an application expression that evaluates to it?  I  
guess somebody could implement a Scheme that way; I don't know  
whether DrScheme is in fact implemented that way.  It strikes me as  
an unnecessary complication.



Stephen Bloch
sbloch at adelphi.edu