Wed Jun 25 10:46:45 CEST 2008

Joy and rewriting

The setting:

  Any programming language can be given a rewriting system, but for
  Joy it's particularly simple.

The idea is thus to put it on top: a rewriting system as a
metaprogramming system: a source code transformation.
( Actually, no. It seems to be about giving a full semantics to a Joy
program using JUST rewrite rules. )

 Q: Does it make a difference if the rewriting system works on the
    source language (as in Joy) or the target language (as in Purrr)?

It becomes interesting at the point where "The role of the stack" is
discussed: reduction strategies.

There's this 'duality' between programs and stacks that's right in the
middle of my representation. Looks like Manfred was there first:

   This is the key for a semantics without a stack: Joy programs
   denote unary functions taking one program as arguments and giving
   one program as value. The literals denote append operations; the
   program returned as value is like the program given as argument,
   except that it has the literal appended to it. The operators denote
   replacement operations, the last few items in the argument program
   have to be replaced by the result of applying the
   operator. Similarly the combinators also denote (higher order)
   functions from programs to programs, the result program depends on
   the combinator and the last few quotations of the argument program.

   It is clear that such a semantics without a stack is possible and
   that it is merely a rephrasing of the semantics with a
   stack. Purists would probably prefer a system with such a lean
   ontology in which there are essentially just programs operating on
   other programs. But most programmers are so familiar with stacks
   that it seems more helpful to give a semantics with a stack.

This is exactly what the Purrr primitive macros do: they take programs
to programs. Essentials:

   PRIMITIVES: rewrite rules as endomaps of target machine
   code. semantics of concatenative program expressed in terms of
   these primitive machine rules is the composition of these rules
   applied to the empty target program.

   COMPOSITION: already hinted above: ordinary composition serves as
   the main abstraction mechanism to construct new endomaps of target
   machine code.

   PARTIAL EVALUATION: The 'stack' shows up here as the local view of
   target machine code. If the target language has a notion of a run
   time parameter stack, there is a possibility for staging: moving
   computations to compile time while preserving semantics.

In "Quotation revisited" Manfred talks about the "draconian" measure
of not equating lists and quoted programs. In Scheme terms, this is
about constructing lambda expressions vs. quasiquotation + eval. Using
the solution of only allowing the construction of quotations, but not
the destruction (intensional definition, defined by its properties),
isn't really that bad. (It's how Scat does it: all quotations are
opaque, no reflection.)

 Q: For Purrr it's possible to talk a whole lot about the semantics
    of macros without even mentioning target semantics. Does it make
    sense to see target semantics as an extension of the semantics
    introduced by the rewriting rules, to capture the cases that the
    rules don't handle: those that are somewhat general? Or is it
    better to see the macro semantics as the extension of limited
    target runtime semantics.

So, to relate Purrr and Joy a bit more: using rewrite primitives and
function composition, Purrr will reduce a program to a value whenever
it is a pure program. However, the target semantics isn't pure, so not
all programs can be completely reduced.