[plt-scheme] to define, or to let

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Sun Mar 21 22:19:08 EST 2004

On Mar 21, 2004, at 9:33 PM, Bradd W. Szonye wrote:

> Note that a compiler *cannot* reorganize code with side effects if you
> specify left-to-right evaluation. It cannot even reorganize CONSes,
> because the compiler cannot determine whether it's safe to move
> allocations.

This is of course complete nonsense. Sorry but I have no other words 
for that.

A language comes with an observational equivalence relation, which the 
evaluator and the language syntax define. If two statements are 
interchangeable and the compiler can prove it, then it can exchange the 
two. Period.


  (begin (set! x 5) (set! y 3)) =~ (begin (set! y 3) (set! x 5))

 From this it follows that for any identifier f

  (f (begin (set! x 5) (set! y 3))) =~ (f (begin (set! y 3) (set! x 5)))

See the order of evaluation doesn't even play a role here. f's an 
identifier, and begin specifies an order of evaluation. Of course, 
since Scheme per se doesn't do threads, you can go even further:

  (f (set! x 5) (set! y 3)) =~ (f (set! y 3) (set! x 5))

[and I forgot whether set! returns void by R5RS. If not, let's assume 
that it always returns the same value and let's hope this isn't 
controversial.] The point is that Scheme programs cannot observe this 

I can roll up many more of the claims made on this topic, and it all 
dates back to Plotkin's old papers (and a tiny bit to my thesis).

Yes, this an extremely simple example but don't bother to tackle the 
specifics. It generalizes to a pretty rich theory. [A theory is a 
system of equations, axiomatizable or not. In Scheme's case, some 
interesting fragment is axiomatizable. That's a part of Ian Mason's 
dissertation. Also 15 years old.]

;; ---

My general position is that programming is equally about correct and 
incorrect programs. Scripting is fun. Writing programs in a dynamically 
typed language is fun. But as the programs "grow" up, they need more 
and more stability. That means, we must be able to equip the language 
with tools that help us discover errors and that help us describe our 
thoughts. A language [family] as weakly specified as R5RS is not a good 
basis for this "growing up business." It starts with the unspecified 
order of evaluation and continues with all the other places where R5RS 
is wishy-washy about errors.

;; ---

Is it possible to provide a complete specification of a language? I 
don't know. Languages are huge, complex artifacts. Take a look at the 
number system. Take a look at thread systems and similar things. I 
don't know whether we can do an adequate job. But that shouldn't 
prevent us from doing better than we have done in the past.  That's 
part of what PLT is about and I sure hope we can stay the course.

-- Matthias

Posted on the users mailing list.