Wed Jun 25 10:46:45 CEST 2008
Joy and rewriting
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
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.