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

On Jul 10, 2009, at 9:42 AM, Marco Morazan wrote:

> It is a shame that quote is ommitted by the print part of the repl.
> Two identical expressions can be interpreted by those beginning as two
> different things. Think about it carefully, is ((lambda  (x) (+ x 1))
> 4) a list or an application expression? What does Scheme syntax say?

No question: Scheme syntax says it's a list (or, technically, a  
syntax object, i.e. a list with decorations).  Scheme semantics  
(which depends on the current environment bindings, etc.) treats it  
as an application expression.

I wrote, in my hypothetical "RPL" language:
>>> ((quote yes) (quote no))
>> (cons (cons 'quote (cons 'yes empty)) (cons (cons 'quote (cons 'no  
>> empty)) empty)

to which Marco rebutted, using BSL language:
> Welcome to DrScheme, version 4.2 [3m].
> Language: Beginning Student; memory limit: 128 megabytes.
>> ((quote yes) (quote no))
> function call: expected a defined name or a primitive operation name
> after an open parenthesis, but found something else
>
>
> Welcome to DrScheme, version 4.2 [3m].
> Language: Beginning Student with List Abbreviations; memory limit: 128
> megabytes.
>> ((quote yes) (quote no))
> function call: expected a defined name or a primitive operation name
> after an open parenthesis, but found something else

Of course this is what you get if you type these expressions into a  
read-eval-print loop.  But if you type them into a read-print loop,  
so you see what they ARE, rather than what they EVALUATE TO, you'll  
get the results I described.

> 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.

> The value of an expression is ALWAYS what it evaluates to  
> regardless of the printing convention used.

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 that happen to have the same value when  
evaluated in a particular language with a particular environment; in  
a different language or environment, they might NOT evaluate to the  
same thing.  Likewise, ((quote yes) (quote no)) is a perfectly good  
syntactic expression that happens to be unevaluable in a particular  
language with a particular environment; in a different language or  
environment, it might evaluate to (quote maybe).


This leaves open the question of how best to explain this to  
students.  For some, the distinction between an expression and its  
value is too abstract, so until they're ready for this distinction,  
you may have to come up with some other hand-waving dodge.  But is  
that really necessary?  The last time I taught Principles of  
Programming Languages (4th semester, college), I pointed out that,  
although the most obvious question to ask about an expression is  
"what is its value?", other equally-interesting questions are "how  
many operators does it have?" and "does it contain any free  
variables?"  Even in my beginning-programming-for-non-majors course,  
I have students draw syntax diagrams (with nested boxes, each box  
labeled with a syntax rule) and observe that two expressions with the  
same value may have completely different syntax diagrams.


Stephen Bloch
sbloch at adelphi.edu