Thursday, January 08, 2009

Fexprs? in Scheme?

“The top level is hopeless.”
     -- Matthew Flatt [1] [2] [3] [4] [5] [6] [7] [8] [9]
Scheme's top level allows for interactive evaluation such as at the REPL, where global definitions can be dynamically evaluated one by one. To allow for forward references, free variables are not a static error at the top level. But global definitions may be macros, and there's no way to know whether a forward reference is eventually going to turn out to be a value binding or a macro binding. So one simple semantics is just to assume that forward references are always value bindings and compile them as such. But then you get unsatisfying interactions like this:
> (define (f) (display (g 42)))
> (define-syntax g (syntax-rules () ((g x) (quote x))))
> (f)
reference to an identifier before its definition: g
It's worse with macro-defining macros. For example, a define/inline form would bind its definition as a macro, but the user could generally treat it as a value binding. But you'd still run into the same problem:
> (define/inline (f) (g 42))
> (define/inline (g n) (add1 n))
> (f)
reference to an identifier before its definition: g
What's in conflict in Scheme is the desire for macros to be a static, compile-time entity and the REPL to allow dynamic, incremental update to the global environment. In fact, the top level seems to be the one place in Scheme where programmers expect behavior something like Lisp's antiquated fexprs. Bear with me...

Imagine if the compiler treated any form (x . s) where x is a top-level variable reference--bound or unbound--as an uninterpreted syntax object waiting to be parsed. Then only when the form is evaluated would x be looked up in the global environment to determine how to compile the form. If x is unbound, it's a dynamic error; if it's a value, it's compiled and evaluated as a function application; if it's a macro, it's macro-expanded, compiled, and evaluated. This would accomodate any sequence of definitions and redefinitions of top-level bindings, either as value bindings, macro bindings, or both. For example:
> (define (foo x) (f x))
> (define (f x) (add1 x))
> (foo 41)
42
> (define-syntax f (syntax-rules () ((f e) (quote e))))
> (foo 41)
x
This has a lot of the similarities to fexprs; it means a function like foo is subject to dynamic reparsing: at one point it calls a function on x and at another point it applies a macro. But whereas with fexprs, any application expression may be dynamically reparsed, here this would only be the case for applications of top-level variables.

Fexprs are bad for two reasons: they make the language hard to compile efficiently and they make programs hard to understand by subjecting the basic program definition to dynamic reinterpretation. To be sure, making Scheme's top-level fexpr-like would make efficient compilation harder. But the top-level is the part of Scheme where programs are dynamically defined. Users are constantly surprised at the behavior of top-level forward references and macro definitions. What they seem to naturally expect is, in some sense, fexprs.

10 comments:

Pascal Costanza said...

Why not just use an interpreter instead of a compiler for interactive development?

Dave Herman said...

That's largely orthogonal; I'm talking about specifying the observable behavior. (Perhaps that's what you mean but then you're begging the question. "Use an interpreter" doth not a semantics make.)

Richard Cobbe said...

Thank you, Dave, for posting this! I've heard lots of people exclaim in disgust that "the top level is hopeless," but they very rarely deign to explain why.

Since the problems with it are subtle and can be explained only after a great deal of thought and experience, explanations like this are valuable to those of us who haven't gone through that process ourselves.

Shiro Kawai said...

"But the top-level is the part of Scheme where programs are dynamically defined."

Not a part of R6RS, anyway. So I guess we can treat toplevel as an ad-hoc utility, much like the debugger interface, instead of a part of rigidly defined "language". If it is only for development-time help for programmers, efficiency may be traded off for users' convenience.
Then dynamic re-compiling seems an acceptable choice to me. (Yes, it complicates implementation, but features that provide users' convenience tends to make implementation complicated in genreral).

Pascal Costanza said...

What I mean with "use an interpreter" is that you can delay the decision whether something is a macro or a function until it is actually called. In such a case, it doesn't matter whether a free reference will eventually refer to a function or a macro, because the decision can be delayed until the very last moment. That's good for interactive development.

Kazimir Majorinc said...

Dave,

related question: why eval see global lexical variables?

(define x 55)
(eval 'x) => 55

is it the same special treatment of top level, or it is natural consequence of something I do not see?

John Cowan said...

But then you get unsatisfying interactions like this:

Unsatisfying it may be in the abstract, but treating undefined references from the top level as variables is a fact of life for anyone who uses a Scheme REPL. Of the 45 Schemes that I test regularly with, all except SCM (and a few that don't support macros) have the same behavior at the REPL. Undefined forward references are treated as variables, and syntax expressions are expanded inline when a procedure invoking them is defined. Attempts to redefine syntax keywords post hoc have no effect on procedure definitions already seen, though they are effective for later procedure definitions. This is the semantics that R7RS-small prescribes for any implementation providing a REPL. (SCM does the expansion lazily, so redefining syntax will be effective if the procedure containing it has never been called.)

John Cowan said...

See also "The Tale of Professor Simpleton and Dr. Hardcase" for an explanation of the general problems with using syntax before defining it.

thesis factory said...

Hi...Nice blog. Really very interesting....!!!

Dissertation binding

thesis factory said...

Hi...Nice blog. Really very interesting....!!!


Dissertation binding