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.

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

Computer Security said...

Thanks for the information. It's very useful.I really enjoyed your blog. aol-desktop-gold-download

richard said...

Nice Post Very Informative and knowledgeable, Keep doing it
We provide Computer Antivirus Support to Your System, We protect it from from damamging. As we all Know Everything is getting Digital, So Dont You think there is aneed to protect your system.
For Support Visit- mcafee.com/activate
norton.com/setup
norton.com/setup

richard said...

Nice Post with great source of knowledge , keep doing this work
We Need to protect our system from antivirus attack and malware.As everything is getting digitally developed.
mcafee.com/activate

richard said...

Nice Post with great source of knowledge , keep doing this work
Protect your system from antivirus attack and damage
norton.com/setup

Zoe said...

Thanks for posting such a valuable information
best christmas gifts for mom
best gifts for dad 2020
best baby gifts 2020

OneVanilla Balance Check said...

Thanks for sharing this information...

onevanilla gift card
onevanilla check balance
onevanilla balance check
onevanilla balance
onevanilla card balance
onevanilla prepaid visa card balance
www onevanilla balance
check my vanilla visa balance
onevanilla prepaid visa card
vanilla balance
onevanilla balance
one vanilla balance
check onevanilla balance
check vanilla balance
check one vanilla balance
onevanilla gift balance
onevanilla master card balance
onevanilla balance ceck
onevanilla balance check online
onevanilla online balance check
onevanilla balance visa
onevanilla visa balance
onevanilla prepaid balance
onevanilla mastercard balance
onevanilla card balance check
onevanilla prepaid balance check

Movies2Club.com said...

This is very interesting, You are an excessively professional blogger.
I have joined your feed and sit up for seeking extra of your great post.
Also, I've shared your site in my social networks

tamil new movie download
new movie download
new hindi movie download
new tamil movie download
new south movie download
new bollywood movie download
tamil new movie free download
new hd movie download
new hollywood movie download
new south movie hindi dubbed download
south movie download
south movie hindi dubbed download
south hindi dubbed movie download
south hindi dubbed sky movie download
new south movie 2019 hindi dubbed download
hollywood movie download
hollywood movie in hindi download
hollywood movie download in hindi
hollywood movie hindi dubbed download

Onevanilla Visa Balance said...

Thanks for the great comment buddy! You inspired me too by these beautiful words. Keep blogging on and achieve your goals. No one can stop you if you have guts to do something.
All The Best!
Thankyou
https://www.icedvanillalatte.com/check-onevanilla-gift-card-balance/
Onevanilla Card
Onevanilla Prepaid Visa Card Onevanilla Prepaid Card Onevanilla Balance Onevanilla Check Balance Onevanilla Card Balance Onevanilla Gift Card Balance Onevanilla Visa Card Onevanilla Prepaid Visa Card Balance Onevanilla Prepaid Card Balance Onevanilla Visa Balance OneVanilla Prepaid Mastercard Balance Onevanilla Prepaid Balance Check Onevanilla Card Balance One Vanilla Mastercard Balance Onevanilla Card Onevanilla Prepaid Visa Card Onevanilla Prepaid Card Onevanilla Balance Onevanilla Check Balance Onevanilla Card Balance Onevanilla Gift Card Balance Onevanilla Visa Card Onevanilla Prepaid Visa Card Balance Onevanilla Prepaid Card Balance Onevanilla Visa Balance OneVanilla Prepaid Mastercard Balance Onevanilla Prepaid Balance

soliha said...

kaspersky activation process online help and support regarding your product
stay safe and secure by activating your kaspersky antivirus

soliha said...

kaspersky activation process online help and support regarding your product
stay safe and secure by activating your kaspersky antivirus

soliha said...

kaspersky activation process online help and support regarding your product
stay safe and secure by activating your kaspersky antivirus

soliha said...

kaspersky activation process online help and support regarding your product
stay safe and secure by activating your kaspersky antivirus

soliha said...

kaspersky activation process online help and support regarding your product
stay safe and secure by activating your kaspersky antivirus

Target Visa Gift Card Balance Check said...

Great. It is very useful information. Thanks for giving us this meaningful and helpful information...

target visa gift card balance,
target visa balance,
target visa card balance,
check target visa gift card balance,
target visa prepaid card balance,
mybalancenow target,
check mybalancenow,
target prepaid visa balance,
visa prepaid card balance target,
target visa check balance,
visa target gift card balance,
target visa debit gift card balance,
check my target visa gift card balance,
target balance check,
check balance on target visa gift card,
target visa prepaid card,
target prepaid card visa,
target visa gift card balance check,
target visa gift card check balance,

soliha said...

kaspersky activation process online help and support regarding your product
stay safe and secure by activating your kaspersky antivirus

soliha said...

kaspersky activation process online help and support regarding your product
stay safe and secure by activating your kaspersky antivirus

soliha said...

kaspersky activation process online help and support regarding your product
stay safe and secure by activating your kaspersky antivirus

soliha said...

kaspersky activation process online help and support regarding your product
stay safe and secure by activating your kaspersky antivirus

Anonymous said...

Hey guys, anybody wanna buy some antivirus software? Ten dollars!

Shit, I forgot the link.

Anonymous said...

Interface your gadget to the Internet and go to the App Store.
Search and "Download" the Amazon prime video application.
When the document is downloaded and introduced, open the application.
You will see an alternative – "Register on Amazon site", click on this.
A 6 digit code will show up on the screen.
Note down this code cautiously. This is amazon.com/mytv enter code.
Presently open the Amazon site – Amazon.com/mytv.com and sign in with account subtleties.
Presently enter the Amazon enactment code and snap on "Proceed".
You will get the compliment message on your TV screen after the effective enactment.
Start Enjoying the amazon prime videos on your device.
If you are facing some issue in that process then you can visit :
primevideo.com/mytv
www.amazon.com/mytv registration
www.primevideo.com/mytv
www.amazon.com/mytv enter code

peter hawks said...

/My Amazon prime video TV Help
=============================
www.amazon.com/mytv - Enter Mytv Code - PrimeVideo.com
visit Amazon MYTV Enter code or www.primevideo.com/mytv and enter Amazon activation code to activate amazon prime videos on your smart tv and pc

primevideo.com/mytv code said...


Copy and paste the web link link in your web browser that is www.amazon.com/mytv. Login to your prime video account using your prime video login credentials. After that enter the activation code you have on your screen .Devices Compatible with Prime Video. Exclusive content and Amazon Original series Enjoy exclusive movies and TV shows on your device.

Anonymous said...

YouTube is just one of those available stations on many Roku apparatus, also you may sign in with your YouTube accounts to view most your programs and play lists. You might even apply your smartphone, tabletcomputer, or computer to get and play with YouTube videos onto your own Roku rather than employing the Roku remote.
youtube.com/activate
www.youtube.com/activate

Anonymous said...

Tubi's complimentary streaming agency is a pleasing surprise, even with a vast assortment of quirky and classic pictures and television collection. It's ad-supported, nevertheless, you'll run in to more adverts on freetoair than simply while seeing among Tubi's b movies.
tubi.tv/activate
tubi.tv/activate enter code
tubi.tv/activate

needofindia said...

ram 8gb ddr4 3200mhz laptop .. Designed to help your system run faster and smoother, Crucial Laptop Memory is ... Module type: SODIMM

Anonymous said...

explainer video company in delhi
explainer video company in gurgaon
viral video maker
explainer video company in bangalore
explainer video company in hyderabad
explainer video production company
explainer video bangalore
explainer video company in mumbai
explainer video production house
app explainer video
animated explainer video company
explainer video production
explainer video services
best explainer video companies
explainer video company in india
explainer video company in india
animated video production companies
explainer video company india
explainer video india
manufacturing logistics
infographic animation
best video production company in bangalore
explainer videos india
cartoon video cartoon
whiteboard explainer videos
animated video production
2d animation cost per second in india
video making company
animated video company
custom video
animation video cost in india
product explainer video
video production bangalore
video production company in bangalore
3d animation process
video production company bangalore
whiteboard video maker
whiteboard animation video maker
2d animation company in india
cartoon animation video maker
corporate video production bangalore
how many step process for creating a 3d animation
corporate video production companies
animated movie maker
viral video maker
explainer video company
corporate video production companies
explainer video company
explainer video company in delhi top explainer video
Animated Explainer Video
Live Action Explainer Video
Whiteboard Explainer Video

Angel calista said...

Error in PayPal login passwordThis happens when you don't enter the correct login credentials at the sign-up page. To reset your password,Password to PayPalGo to https://sites.google.com/view/paypal-loginss/questions/faq1440 to learn how to regain access.starbucks gift card balance
Play.google.com/redeem
paypal sign in
amazon.com code
amazon code
cash app login

Instagram Video Download said...

Instagram video download serivce by MyInstaSave.com, allows to download Instagram videos and photos, reels online. It is a really simple Instagram video downloader, story saver etc.

instagram video download
instagram reels download
instagram video downloader
instagram story download

buy ielts certificate without exam said...


https://www.britishcertifications.com/

https://www.worldpethelpers.com/

my holidays said...

Thank you for keeping me updated with this site. Chardham Yatra Package

RSM Enterprises said...

Tadalafil 10mg Tablets are used to treat the physical problems of erectile dysfunction in men.
Buy Generic Cialis 10mg

Alex-Danvers said...

check vanilla gift card balance,
check sephora gift card balance,
check target gift card balance,
target gift card balance,