R5RS top level definitions

Hi.

Just like a billion people before me, I'm trying to write a Scheme
interpreter; more specifically, I'd like to implement R5RS Scheme.

Now I've been reading the report forwards and backwards, and I can't
understand the exact semantics of top level definitions. I read in
§5.2.1 that (define x 1) is "essentially" the same as (set! x 1) if x is
already bound. If it's not already bound, x is bound to a new location.

My problem is (probably) the interaction with top level syntax
definitions. My assumption, from reading §3.1, is that an identifier
can't be a variable and a syntactic keyword at the same time (how can
you decide on the meaning of (x) otherwise?), so if I bind an identifier
to some syntax, it becomes unbound as a variable. For instance, if I
type

(define x 1)
(define (get-x) x)
(define-syntax x ...)
(define x 2)

I would expect (get-x) to evaluate to 1, because by the time the
interpreter reaches the fourth line, x is bound to some syntax, so it's
not bound as a variable, hence the define form binds it to a new
location than the one introduced on line 1 and referenced on line 2.

Except I tested that code with Petite Chez Scheme and plt-r5rs from
Racket, and both return 2. So I'd appreciate any indication as to what
I've misunderstood.


Thanks.

--
jathd

On Saturday, August 4, 2012 5:11:15 AM UTC-4, jathd wrote:

> (define x 1)
> (define (get-x) x)
> (define-syntax x ...)
> (define x 2)
>
> I would expect (get-x) to evaluate to 1, because by the time the
> interpreter reaches the fourth line, x is bound to some syntax, so it's
> not bound as a variable, hence the define form binds it to a new
> location than the one introduced on line 1 and referenced on line 2.

That's a reasonable conclusion, but no Scheme system actually works that way. In practice, the define in line 4 overrides the define-syntax and brings the variable location back to life. In any case, the reference to x in line 2 cannot refer to the syntax, because syntax keywords are detected onlyas the first element of an expression. If you had left out line 4, calling get-x might return 1 or might return an implementation-defined object.

John Cowan <johnwcowan@gmail.com> writes:
> That's a reasonable conclusion, but no Scheme system actually works that way.
> In practice, the define in line 4 overrides the define-syntax and brings the
> variable location back to life.

Ok, so if I understand correctly, the system never creates more that one
variable binding for a given identifier. Actually, now that you say it,
this is the behaviour described by R5RS §7.2: a program p is evaluated
as ((lambda (x ...) q) <undefined> ...), where q is p in which all
definitions have been replaced by assignments.

> In any case, the reference to x in line 2 cannot refer to the syntax,

Right.

> because syntax keywords are detected only as the first element of an
> expression.

That doesn't seem to be true (in practice). For the program

(define x 1)
(define-syntax x ...)
(set! x 2)

both Petite and PLT signal an error for the third line ("cannot mutate
syntax identifier" and "invalid syntax" respectively).

> If you had left out line 4, calling get-x might return 1 or might
> return an implementation-defined object.

I don't get it; doesn't that contradict what you said above about the x
on the second line not referring to the syntax? I thought the
define-syntax shadowed the binding of x to the original location, but
why would that location suddenly contain something other than 1? The x
on line 2 *does* refer to that location, right?

--
jathd

jathd <invalid@domain.tld> wrote:
> (define x 1)
> (define (get-x) x)
> (define-syntax x ...)
> (define x 2)
>
> I would expect (get-x) to evaluate to 1, because by the time the
> interpreter reaches the fourth line, x is bound to some syntax, so it's
> not bound as a variable, hence the define form binds it to a new
> location than the one introduced on line 1 and referenced on line 2.

What you expect is a lexical binding, but what most R5RS interpreters
do is bind top-level symbols dynamically. Lexical bindings at the
top-level are also known as "hyper-lexical" bindings, because they
interfere with interactive program development. Imagine:

(define (square x) (+ x x))

(define (diagonal x) (sqrt (+ (square x) (square x))))

(diagonal 1) ==> 2 ; hmm wrong.

; Ah, let's fix SQUARE:

(define (square x) (* x x))

(diagonal 1) ==> 2 ; probably not what you expected

In a hyper-lexically scoped environment, you would have to
re-define all function that refer to SQUARE at this point for
your fix to take effect. Not good. This is why virtually all
R5RS interpreters use dynamic scoping at the top level.

R6RS formalized this behavior by introducing LETREC* and
making any top-level DEFINEs clauses of a(n imagined) LETREC*:

(letrec*
((square (lambda (x) (+ x x)))
(diagonal (lambda (x) (sqrt (+ (square x) (square x)))))
(square (lambda (x) (* x x))))
(diagonal 1))
==> 1.414213562373095

At last R6RS was good for something.

--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org