Re: [Gnu-arch-users] arch roadmap 1 (and "what's tom up to")

[Tom Lord]

    > From: "Pierce T.Wetter III" <address@hidden>

    >   Of course, really, if I now understand correctly, Tom wants to compile 
    > pika code into Furth, and use pika code in arch. That's quite different, 
    > because its not furth that Tom wants to embed into arch, its scheme.

You don't understand _quite_ correctly, mostly I think because I
haven't managed to articulate something very well.

1. Scheme (mostly because of closures, continuations, and tail-calls)
   is a good (not perfect) candidate for a universal intermediate
   language.       Many languages, tiny and large, have natural 
   translations into Scheme such that a Scheme compiler with only
   fairly old-hat optimizations will produce halfway-decent code
   from the translation.

   It's folklore, among Schemer's, that closures, continuations and
   tail calls amount to the same thing as (effectively) direct access
   to a CPU's PC.  You can write code that generates, essentially, a
   machine language "jump" instruction to an arbitrary target.  You
   can more or less directly manipulate a CPU's frame pointer
   register, without restriction.  Thus, whatever weird
   flow-of-control you want, you can implement directly in Scheme.
   Whatever weird scoping rules you want, you can map them onto
   Scheme.

   In other words, Scheme is in some sense kind of an idealized
   macro-assembler:  the full power of the underlying CPU is 
   exposed.   You aren't locked into a fixed set of flow of control
   concepts as you are in most languages.   You aren't restricted to a
   tree-shaped dynamic call-trace.


2. Alas, Scheme isn't a perfect candidate for a universal intermediate
   language precisely because, to use it as such, you have to rely on
   an optimizing Scheme compiler to get you from Scheme to an actual
   execution.  There are many such compilers but few that are wildly
   portable and none that are small and simple.   The concept that
   Scheme is a universal, high-level macro assembler has been
   demonstrated more "in the lab" than "in the field".

   That'll change, I predict, within our professional lifetimes.
   There are plenty of people who actively work on reducing the proven
   theory into pragmatic practice.   But it'll be a few years more
   before Scheme is as handy to reach for as C.

   _Even_when_ an optimizing Scheme compiler is common-place, it's
   _still_ not always the best choice as universal assembly language.  
   Why?  Because the optimizations done by such a compiler can be 
   pretty tricky:  to get the generated code you want, you may have 
   to think pretty hard about what kind of Scheme input you need.
   The resulting Scheme-generator can wind up being very fragile: a
   seemingly innocent change can trash the output you'll get from a 
   Scheme compiler, even if the VM machine code you were aiming for is
   conceptually very simple.


3. At the same time, although Scheme has the famous denotational
   semantics in the standard, it also has a famous but not-formalized
   _operational_ semantics.   Putting it crudely, there is a well
   known idealized "Scheme Machine" -- a virtual machine (essentially
   Furth-like) on which Scheme is easy to implement.

   The optimizations of an optimizing Scheme compiler apply when
   translating Scheme to a Furth-like VM but, much more importantly,
   describing (in VM terms) the desired translation for a piece of
   code is fairly easy.  

   In other words, sometimes it's much easier to write something that
   generates code directly for a Scheme VM than to write something
   that generates Scheme that produces that same VM code.


4. Therefore, in a sense, while Scheme is _abstractly_ an ideal 
   intermediate language for many high-level languages, tiny and
   large, a Furthish Scheme VM is _pragmatically_ an ideal 
   intermediate langauge.

   Targeting the VM directly, rather than via Scheme, means that I
   don't have "trick" a Scheme compiler into generating exactly the
   VM code I want.


5. A very simple-minded implementation of a Furthish-VM is 
   simple to write and maintain and is a tiny program.  At 
   the same time, it's totally practical to use such a simple-minded
   implementation for many kinds of programs.

   This just reinforces the idea that a Furthish VM is the ideal
   interemediate language:  you can get it running in just a few
   weeks, it's only a few K-lines of code.

   Best of all, if you go this route, you pretty much know that you're
   making a good long-term decision:  Scheme (and Scheme VM's)
   "universal" character is long established.

   In contrast, Tcl (to pick one example) _also_ has a tiny core,
   easy to implement and maintain.   It has nearly all the virtues
   of a Furthish VM.   But it fails because the Tcl VM is a lousy
   candidate for a universal intermediate language.   Suppose that
   you need something like continuations, for example:  the Tcl C 
   API (and to an extent, the semantics of Tcl) mean that you are
   out of luck.


So it's not (from the arch perspective) that I want to compile Pika
to Furth VM.   Rather, it's that:

  a) we need some high-level language tools in arch

  b) all such language can reasonably be written to translate 
     into Furth

  c) Furth is practical in the same way that arch is practical:
     relatively small and simple.

It's sort of like I can commit to a Furth VM without precluding 
what the high-level language tools in arch look like beyond that.
So, that's what I'm doing.

(I have some ideas about specific languages to use in various places
but nothing _quite_ worth trying to write an essay about yet.  Code
first.)


    >    Then the question is whether it make sense to use scheme in config 
    > files...

Often not, I suspect.  The next question is whether it makes sense to
use a Schemish-VM to interpret any tiny languages that do show up 
in arch.   I think: "yes".

-t