Re: [Gnu-arch-users] new language, arch, furth, etc.

[Tom Lord]

    > From: Jan Hudec <address@hidden>

    > On Tue, Jul 20, 2004 at 23:28:57 -0400, Phil Frost wrote:
    > > Flamewar aside, I don't think restricting execution to a finite number
    > > of steps means much of anything. All computers today are not truly
    > > turing complete because they have limited storage. Bounding execution to
    > > a finite number of steps doesn't make the language any simpler either.
    > > All it does is make deep recursion or long loops impossible, and place
    > > an upper bound on the computational power of the program, but not the
    > > complexity of the language.

    > As I read Tom, I don't think he is going to guarantee the finiteness by
    > simply cutting the program after some time, but rather by not providing
    > the minimalization primitive. Though it's hard to not provide it --
    > recursive functions do minimalization.

Right.  There's some hints about that in the first "Round II" message.

The plan for spelling out the rest of the spec is, roughly:

1. Add the operational model and tighten the spec.

   xl uses normal-order evaluation (although ordinary function
   calls behave like applicative-order calls).

   Every variable is computed at most once.

   Normal subexpressions in a program are executed at most once.
   There are some (finite) looping constructs planned that
   imply a subexpression in the source text can sometimes be
   executed more than once (but with different bindings in place).

   I'll brute force excluding recursive functions by forbidding 
   all forms of syntactic recursion and nearly all forms of higher
   order functions.

   I'll point out that the resulting language can be implemented 
   in just a few K lines of code.


2. Add procedural and syntactic abstraction.

   xl programs will be able to define named, top-level, non-recursive
   functions, both those which use applicative-order and those which
   use normal-order evaluation, the former giving a form of procedural
   abstraction, the latter syntactic abstraction.   This complicates
   the "everything is evaluated at most once" rule a little bit more
   but not too terribly.

   This adds to the complexity of an interpreter but not very much
   (hundreds of lines of code?).


4. Remark on side-effecting functions.

   Given the well-defined (and usefully defined) execution order,
   built-in functions can reasonably side-effect the environment
   (not the running program).

   This adds nothing new to the interpreter -- it just points out
   that the interpreter has some interesting uses.   It's a 
   better `make(1)' than make.   It's useful for writing many
   shell commands (most of cmd-*.c could be replaced by it).
   It wouldn't make a bad CGI language or web server plugin-language
   but it can be made even better for that.

That'll be xl and then there's a fork: in one direction, working out
the specifics of how xl is used in arch for version vars and other
purposes; in the other direction, mentioning an extended language,
"xxl".

xxl will add reflexive capabilities to xl, in particular the ability
for one xl program to ask for results from another xl program.

At that point it's easy to "reveal" that xl is really something very
familiar: a language for writing "basic blocks".  xl is an interesting
language because it provides referential transparency yet maps simply
and controllably onto side-effects during execution;   it provides for
multiple entry points to a block, demand-driven execution, and thread
safety.   If only the core types I've described are used in an
implementation, not only programs and static data but the entire state
of a running program is externalizable:  xl makes process migration
pretty easy.

So when xxl programs are able to invoke other xxl programs, now you can
build up (recursive) function calls from that.   You have fully
general flow of control.

One interesting trick that can happen in xxl is to _not_ reify as
values an xxl program invoked as a coroutine.  Instead, give
coroutines names and use those for reference.  Large and interesting
classes of coroutines don't have to be unique executions -- they can
be recomputed on demand, computed redundently, etc.  I'm sorely
tempted to push this approach sufficiently far that xxl remains, like
xl, a language that is safe for reference-counting memory management
(no cyclic DAGs of values possible).

An xxl interpreter will turn out to be xl interpreter plus some new
primitives: almost certainly less than double the size of xl.  It will
turn out to be useful for demand driven, distributed computation over
unreliable/untrustworthy networks, providing for easy-to-create
optional add-ons for process migration and persistence.  In that
context, I think it will be useful to provide some primitives that can
generate XML from xl values....

-t