Not really a flame-bait 
Author Message
 Not really a flame-bait

    As I come near the end of my project, that
of implementing Scheme interpreter, I almost feel like write a poem
about it.  But no, rather, I decided to write this email,
to just complain and whine about the language just a bit.

    I have started this project, so that I can use it
for modeling events.  I did not want to do a hack job; so rather than
creating a random, "new language" and stumbling along with issues that
I have never considered, I decided to explore a known
language.  I thought Scheme would be easy to implement, and that
 I can quickly move onto the next phase of my project.

    As it turned out, writing a decent Scheme interpreter
has not been straight forward.  Implementation
issues emerged out of nowhere, partly because
of its relatively deep intellectual roots.

    No doubt Scheme is a great language -- I really like it.
But my complaint/question about it is: why didn't the standardization
committees put just a tad more premium on making the
language/optimizations easier to implement?  I am asking
partly earnestly and partly rhetorically.  I think
the Scheme language is practical, but that the language
seems to strive too hard for "minimal number of restrictions,"
and consequently, it makes optimization/efficient implementation
relatively painful.for a newbie like me.

    Perhaps this is drowsiness talking, and maybe what I am
saying does not make any sense.



Sun, 09 Nov 2003 12:34:19 GMT  
 Not really a flame-bait

Quote:

>    As I come near the end of my project, that
>of implementing Scheme interpreter, I almost feel like write a poem
>about it.  But no, rather, I decided to write this email,
>to just complain and whine about the language just a bit.

That's what I call a copout!  I eagerly await the poem... :)

Quote:
>I think the Scheme language is practical, but that the language
>seems to strive too hard for "minimal number of restrictions,"
>and consequently, it makes optimization/efficient implementation
>relatively painful.for a newbie like me.

As someone who is more interested in using Scheme than implementing it, I
have the opposite perspective.  I *want* the languages I use to be simple on
the surface, have the minimal number of restrictions, and take care of all
the deep and messy issues under the hood - providing me with everything I
need and nothing I don't.  On that level, Scheme succeeds very well.  If
that makes it hard to implement, well... would it help if I sympathized?

I've only ever implemented special-purpose or toy interpreters, including
for Scheme, but it seems to me that the issues in implementing any language
are deceptively complex.  Since you've just been through this hard exercise,
why don't you summarize and tell us what it is specifically about Scheme or
its standard you found particularly hard to implement?  I'm sure I wouldn't
be the only one to find that interesting.

If I were to guess, based partly on reading the messages here recently, I
would imagine it mostly revolves around one feature: continuations and
call/cc.  Take that away (while retaining tail call ability), and Scheme has
to occupy a point closest to the intersection of the "easy to implement" and
"greatest expressive power" axes on the graph.  Even with continuations,
it's probably not far from that point.  Try implementing a C++ compiler
sometime.  It would have been a lot easier to implement a Forth interpreter,
but the result wouldn't be nearly as useful.



Sun, 09 Nov 2003 09:57:28 GMT  
 Not really a flame-bait

Quote:
> But my complaint/question about it is: why didn't the standardization
> committees put just a tad more premium on making the
> language/optimizations easier to implement?  

I'm not going to answer that question directly.  Rather, let me just
note that by layering things atop Scheme -- such as modules and types
-- you can obtain much of this compilability.  Not surprisingly, these
are the same features you (well, I) want as a user, too.

I like to say that it's wrong to think of Scheme as a programming
language, and indeed that's now quite how its standardizers intended
it.  Rather, it's a language for expressing computational ideas --
it's a procedural epistemology.  Implementability is really a side
condition on that mission.  Scheme is a shining jewel, and it's the
job of individual implementors to make some earthen variant of it that
they can compile, optimize, debug, and otherwise support.  They should
give those derivatives names that distinguish them from the original
language ("Scheme 48", "PLT Scheme", "MIT Scheme", "Guile", etc, but
never just "Scheme"), so mortals can tell diamond from dust.

Quote:
>                                         I think
> the Scheme language is practical, but that the language
> seems to strive too hard for "minimal number of restrictions,"
> and consequently, it makes optimization/efficient implementation
> relatively painful.for a newbie like me.

A language that is easily optimizable by a newbie is almost certainly
not worth my programming time.

Most compiler writers go through a lengthy phase of education and
almost guild-like apprenticeship over several years.  Why should
Scheme be held to a different standard?  If anything, Scheme, by
placing a premium on the programmer's pithiness, should be especially
frustrating to implementors.  Sounds like your experiences were just
about right.  And now that you've been stricken several times by
devils hiding in the shadows of parentheses, it looks like you've
obtained a profound understanding of Scheme.  Don't regret.  Revel.
(And then contribute hacking cycles to your favorite ball of mud. <-;)

Shriram



Sun, 09 Nov 2003 11:19:32 GMT  
 Not really a flame-bait

Quote:
>     No doubt Scheme is a great language -- I really like it.
> But my complaint/question about it is: why didn't the standardization
> committees put just a tad more premium on making the
> language/optimizations easier to implement?  I am asking
> partly earnestly and partly rhetorically.  I think
> the Scheme language is practical, but that the language
> seems to strive too hard for "minimal number of restrictions,"
> and consequently, it makes optimization/efficient implementation
> relatively painful.for a newbie like me.

Has not someone on this newsgroup opined that Scheme culture is
deeply implementor-centric? Just interesting, how different opinions
can be...

And, compliments for Ji-Young. To see glimpses of a Scheme
implementation emerging from Tumbolia unto this world was most
entertaining, to say the least.

 -BSm



Sun, 09 Nov 2003 12:15:58 GMT  
 Not really a flame-bait


Quote:
>    I have started this project, so that I can use it
>for modeling events.  I did not want to do a hack job; so rather than
>creating a random, "new language" and stumbling along with issues that
>I have never considered, I decided to explore a known
>language.  I thought Scheme would be easy to implement, and that
> I can quickly move onto the next phase of my project.

Perhaps I should have asked this before, but why didn't you
use an existing implementation, such as PLT Scheme, SCM or Guile?

Quote:
>    As it turned out, writing a decent Scheme interpreter
>has not been straight forward.  

Well, what would you expect?

Quote:
> I think
>the Scheme language is practical, but that the language
>seems to strive too hard for "minimal number of restrictions,"
>and consequently, it makes optimization/efficient implementation
>relatively painful.for a newbie like me.

Scheme is supposed to be easy on the user, not on the implementor.
Nobody said writing an optimized implementation would be easy.
OTOH, what *is* usually claimed is that a non-optimizing
Scheme-in-Scheme interpreter is pretty easy, and this is true.
However, in such a meta-circular interpreter one avoids having to write:
1. the garbage collector
2. the full numerical tower
3. read and write
4. call/cc

Stephan

--
ir. Stephan H.M.J. Houben
tel. +31-40-2475518 / +31-40-2743497



Sun, 09 Nov 2003 16:33:58 GMT  
 Not really a flame-bait
Hi,

Quote:

>I've only ever implemented special-purpose or toy interpreters, including
>for Scheme, but it seems to me that the issues in implementing any language
>are deceptively complex.  Since you've just been through this hard
exercise,
>why don't you summarize and tell us what it is specifically about Scheme or
>its standard you found particularly hard to implement?  I'm sure I wouldn't
>be the only one to find that interesting.

    Implementing Scheme interpreter circles around several relatively
difficult issues (for some of us), IMHO:

    (0) figuring out what technical issues are important.

    I could  not find something that lists all the important
issues.  Usually, a book or a reference lists a limited set.

    The most important issues do not become apparent
until you implement things, and then you realize you have
to un-implement them, and do more research on the Net.

    (1) memory management

     I am sure many of you have seen me littering this newgroup
with questions on this topic. .  I wish someone simply
told me in the beginning "use either  a generational collector or
Boehm's mark and sweep collector.  Forget the rest."  Otherwise,
one has to deal with issues on stack v. heap, generational collector and
locality of reference.  Also, one has to choose among
many types of collectors, which means one has to learn about
them.

    (2) "compiler" optimization

    The hard part is figuring out which optimizations have
clear impact on your system.  With all due respect to experts
here, I found two optimizations to be "must".  Once-called
function inlining and compiling let as a closureless procedure.
Unboxing is probably important, but I have not implemented one.
Redundant expression elimination, constant propagation, etc,
are probably important too, but I think their impact is less,
especially if the source scheme code is well written..

    (3) Macros

    Define-syntax required significant amount of effort to
implement in c++.  The two most helpful items were
(1) Clinger's implementation, written in Scheme and (2) a paper
by Rees that describes the overall ideas behind macro
compiler, expander, and lambda parameter relabelling.

=======================

    The following two are worth mentioning, even though
they require no brain melting.

    (4) Overall interpreter framework

    Local environments, closures, lexical addressing, the interpreter's
 underlying data structures, tail recursion, "compiling" internal
definitions,
top-level environment, partial-continuations, etc.  All these
require time to understand.

    (5) Extensions (e.g., integration with CORBA,
transaction system, etc.)

    It is just fun stuff.

=======================

    These two require a heading, just because
they are troublemakers.

    (6) call/cc and set!

    These two open a door to your skull and just sit there,
and not come out.

=======================================

Quote:
> Try implementing a C++ compiler
>sometime.

    That is a funny comment -- you know, I do
have to make a living  :)


Sun, 09 Nov 2003 21:47:51 GMT  
 Not really a flame-bait

Quote:
>     The hard part is figuring out which optimizations have
> clear impact on your system.  With all due respect to experts
> here, I found two optimizations to be "must".  Once-called
> function inlining [...]

So I'm curious: what does your compiler do with

  ((lambda (x) (x x)) (lambda (x) (x x)))

?

[With acks to Bruce Duba.]

Shriram



Sun, 09 Nov 2003 22:03:32 GMT  
 Not really a flame-bait

Quote:

> Scheme is supposed to be easy on the user, not on the implementor.
> Nobody said writing an optimized implementation would be easy.
> OTOH, what *is* usually claimed is that a non-optimizing
> Scheme-in-Scheme interpreter is pretty easy, and this is true.
> However, in such a meta-circular interpreter one avoids having to write:
> 1. the garbage collector
> 2. the full numerical tower
> 3. read and write
> 4. call/cc

Call/cc is trivial to implement if you represent the call stack as a
linked list allocated from the same heap as everything else.
Read/write and a simple garbage collector aren't all that difficult
either.  Full numerics are quite a bit of work, but they aren't
required.

One of the more difficult things, actually, is syntax-rules, which
even scheme-in-scheme interpreters have to deal with.

Writing a slow but minimally r5rs-compliant system really is pretty
easy, as such things go.

-al



Sun, 09 Nov 2003 22:44:16 GMT  
 Not really a flame-bait
Hi

Quote:


>>     The hard part is figuring out which optimizations have
>> clear impact on your system.  With all due respect to experts
>> here, I found two optimizations to be "must".  Once-called
>> function inlining [...]

>So I'm curious: what does your compiler do with

>  ((lambda (x) (x x)) (lambda (x) (x x)))

>?

    Perhaps "inlining" is not the right word.

    The compiler first compiles the argument into
a lambda "object."  Then it compiles the operator,
into a "closureless lambda object."
(for which no closure is created during evaluation).
The two lambda expressions are treated differently
because they occupy different positions within the expression.

    Using those two, the compiler produces an application.

    I would guess what my compiler does is similar to
what MzScheme does.  I believe you told me that it
compiles ((lambda (x) (x x)) (lambda (x) (x x))) as a let
expression.



Sun, 09 Nov 2003 22:51:16 GMT  
 Not really a flame-bait
Hi,

Quote:

>I like to say that it's wrong to think of Scheme as a programming
>language, and indeed that's now quite how its standardizers intended
>it.  Rather, it's a language for expressing computational ideas --
>it's a procedural epistemology.  Implementability is really a side
>condition on that mission.

    I think one of Scheme standardization committees'
concerns should have been promoting the language's
acceptance by the rest of the world.  Scheme's popularity,
while it is not the goal of those who seek knowledge,
can only help Scheme community (directly or indirectly).

     For something useful to be popular, I think, it has to be simple
to understand, and simple to implement.

Quote:
> If anything, Scheme, by placing a premium on the programmer's
> pithiness, should be especially
>frustrating to implementers.

    To implement something like PLT, you are probably right.  That
system, Petite Chez Scheme, Twobit, etc., are in class by themselves.
(I have not personally played with other systems, so I maybe omitting
other great systems).

    But for a "minimal." non-crappy implementation, which maybe
necessary to develop as a basis for a larger application,
I wish there was a clear cut guideline, much like XML spec.

Quote:
> Sounds like your experiences were just
>about right.  And now that you've been stricken several times by
>devils hiding in the shadows of parentheses, it looks like you've
>obtained a profound understanding of Scheme.  Don't regret.  Revel.
>(And then contribute hacking cycles to your favorite ball of mud. <-;)

    Thank you for your encouragement!   :)


Sun, 09 Nov 2003 23:00:03 GMT  
 Not really a flame-bait
Hi

Quote:
>And, compliments for Ji-Young. To see glimpses of a Scheme
>implementation emerging from Tumbolia unto this world was most
>entertaining, to say the least.

    Why, thank you!

    I must admit, it is quite humbling to I type in so many
"I am confused.  You are right." messages.

    I am grateful to everyone here; you and others
 have been patient and kind in fielding my queries.



Sun, 09 Nov 2003 23:16:19 GMT  
 Not really a flame-bait

Quote:


> >     The hard part is figuring out which optimizations have
> > clear impact on your system.  With all due respect to experts
> > here, I found two optimizations to be "must".  Once-called
> > function inlining [...]

> So I'm curious: what does your compiler do with

>   ((lambda (x) (x x)) (lambda (x) (x x)))

I don't see any once-called function in this program.

Matthias



Sun, 09 Nov 2003 23:19:06 GMT  
 Not really a flame-bait
Hi

Quote:
>Perhaps I should have asked this before, but why didn't you
>use an existing implementation, such as PLT Scheme, SCM or Guile?

    I needed to an interpreter whose internals I
can modify.  That meant I had to learn about interpreters
and how they worked. No better way to learn, than to write one.

    I would have loved to use MzScheme,
but (1) its GNU license was not what I could use
and (2) it is a large system.  I could not make
head or tail of it at first, let alone hacking its internals.

Quote:
>Scheme is supposed to be easy on the user, not on the implementor.
>Nobody said writing an optimized implementation would be easy.

    I guess you are right.  I wish it were otherwise, though --
I think if it were easier to implement, there would be more
implementations and more users as well.

Quote:
>OTOH, what *is* usually claimed is that a non-optimizing
>Scheme-in-Scheme interpreter is pretty easy [...]

    I don't believe these implementations would be too useful
for industrial strength applications.


Sun, 09 Nov 2003 23:59:28 GMT  
 Not really a flame-bait

Quote:
> >   ((lambda (x) (x x)) (lambda (x) (x x)))

> I don't see any once-called function in this program.

The procedure that results from the first of the two lambda
expressions is called exactly once.

By "once-called function inlining", I think Ji-Yong D. Chung
means not creating a closure for explicit lambda expressions
in call position, which is often called "LET optimization".

Will



Mon, 10 Nov 2003 02:04:25 GMT  
 Not really a flame-bait

Quote:

> > >   ((lambda (x) (x x)) (lambda (x) (x x)))

> > I don't see any once-called function in this program.

> The procedure that results from the first of the two lambda
> expressions is called exactly once.

> By "once-called function inlining", I think Ji-Yong D. Chung
> means not creating a closure for explicit lambda expressions
> in call position, which is often called "LET optimization".

Fine.  But that would give us

   (let ((x (lambda (x) (x x))))
      (x x))

which, as far as I can tell, is a perfectly fine version of the
original.  Why did Shriram think that the "optimization" would
not be applicable/useful here?

Matthias



Mon, 10 Nov 2003 02:52:49 GMT  
 
 [ 38 post ]  Go to page: [1] [2] [3]

 Relevant Pages 

1. Interesting, Was: Mac vs PC FLAME BAIT Par EXELENCE

2. FLAME BAIT!

3. Objects for ANS Forth FLAME BAIT!

4. G.C as disqualifier (Flame-Bait)

5. GC as disqualifier (Flame-Bait)

6. Warning: Flame Bait

7. Microsoft Flame Bait

8. Window Systems and Forth (was: Mac vs PC FLAME BAIT Par EXELENCE)

9. A few questions comparing Fortran and C; (Not a flame bait)

10. Ichibah flames, and flames out over, Ada 9X

11. portable Forth, who cares? ... FLAME BAIT!

12. Mac vs PC FLAME BAIT Par EXELENCE, was Re: Hang on, isn't Forth , out of date now?

 

 
Powered by phpBB® Forum Software