[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gnu-arch-users] Round III: xl and all that
|
From: |
Tom Lord |
|
Subject: |
[Gnu-arch-users] Round III: xl and all that |
|
Date: |
Fri, 23 Jul 2004 18:55:06 -0700 (PDT) |
Really... this is almost worked out well enough now to convert into
code which should go pretty quickly once it starts....
xl1: xl0 + expressions
An xl1 program is similar to an xl0 program, except that (some)
_expressions_ are permitted on the right-hand-side of definitions.
A (trivial) sample xl1 program is:
(define x-squared (* x x))
(define x 42)
This is about what expressions are permitted in xl1 and what those
expressions mean.
We state (or reiterate) two restrictions at the outset:
1. Formulas may not be syntactically recurisve.
The formula for the definition of variable V can
not (directly or indirectly) refer to the formula
for variable V.
2. The "operator position" of a function call can
only contain a built-in function. (This is an xl1-only
restriction that will be slightly relaxed in full xl.)
* xl1 Programs as Data
An xl1 program can be written as constant data (an association)
as in this example which is a transcription-into-data of the short
program above:
'#( type => program
x-squared => (* x x)
x => 42 )
* The xl1 Reduction Machine
An xl1 virtual machine has three registers:
$program
Always contains the current state of the
program being evaluated.
$goal
Always contains a symbol; the name of the
variable whose value is being demanded.
$subgoal
Always contains a symbol; the name of the
variable whose value is currently being computed.
Suppose that we want to evaluate our sample program, above, to
obtain the value of `x-squared'. We would initialize the VM to:
$program = '#( type => program
x-squared => (* x x)
x => 42 )
$goal = 'x-squared
$subgoal = 'x-squared
Evaluation consists of a series of _cycles_. Each cycle makes
a simplification to $program and/or adjusts $goal and $subgoal.
Simplifications to $program always bring the program closer to being
fully evaluated. For example, while compute `x-squared', we
might simply:
$program = '#( type => program
x-squared => (* x x)
x => 42 )
---->
$program = '#( type => program
x-squared => (* 42 42)
x => 42 )
Eventually, after enough cycles, every definition in a program can
be reduced to either a self-evaluating value or quoted value.
Fully reduced, our trivial program becomes:
$program = '#( type => program
x-squared => 1764
x => 42 )
* What Happens in One Cycle
During each cycle, one of three things occurs:
1. A "trivial subexpression" of the program is replaced
by its reduced value.
2. The (virtual) machine halts normally.
or
3. The (virtual) machine halts in an error condition.
The most interesting case is (1): reducing trivial subexpressions to
their values.
A subexpression is _trivial_ if:
a. It is a function call and all arguments to the function
are either self-evaluating values or quoted constants.
A trivial function call can be replaced by its value
produced by calling a built-in primitive function.
b. It is a conditional expression and the first <test> clause
of the conditional is either self-evaluating or a quoted
constant.
If the <test> is not #false, then the entire conditional
can be replaced with just the <consequent> from that branch.
If the test is #false, the first clause can be removed from
the conditional. If the conditional is empty, it can be
reduced to #undefined
c. It is a variable reference and the variable definition is
or has been reduced to a self-evaluating value or quoted
constant. The variable reference can be replaced by the
constant.
A program may contain _many_ trivial subexpressions: which one is
reduced in a given cycle?
That is controlled by the $goal and $subgoal registers.
At all times, $subgoal contains a symbol, the name of a variable
defined by the program. The immediate purpose of the next cycle
to run is to make progress evaluating that value.
Therefore, (normally) the trivial subexpression that is reduced in
a given cycle is a subexpression of the expression defining the
variable named in $subgaol
In the program:
(define a (+ b c))
(define b 1)
(define c 2)
(define d (- c b))
with
$subgoal == 'a
the subexpressions `b' and `c' in the definition of `a' are
trivial subexpressions, suitable for reduction, because they
are subexpressions of the variable named in $subgoal.
The same subexpressions, 'c' and 'b' in the definition of `d'
are _not_ candidates for reduction because `d' is not named
by $subgoal.
There is still ambiguity, though: which subexpression is reduced
first? `b' or `c'?
In a normal function call, the _left-most_ subexpression that is not
already a self-evaluating or quoted constant is reduced.
In other words, at the start of the cycle:
$program = '#( type => program
a => (+ b c)
b => 1
c => 2
d => (- c b) )
$subgoal = 'a
then by the "left-most trivial under $subgoal" rule, at the end
of the cycle the VM registers contain:
$program = '#( type => program
a => (+ 1 c)
b => 1
c => 2
d => (- c b) )
$subgoal = 'a
Applying the rule again, after the next cycle:
$program = '#( type => program
a => (+ 1 2)
b => 1
c => 2
d => (- c b) )
$subgoal = 'a
If a function call has no non-constant parameters then it is
itself a trivial expression. The next cycle brings:
$program = '#( type => program
a => 3
b => 1
c => 2
d => (- c b) )
$subgoal = 'a
(We haven't needed the $goal register yet. We will eventually but
for now...)
The above execution is not the only one permitted. The execution
above is what happens if $sobgoal never changes from 'a. However,
the virtual machine is allowed to vary the contents of $subgoal
freely. For example a vm might alternate, every other cycle,
between subgoal `a' and subgoal `d', resulting in this trace:
$program = '#( type => program
a => (+ b c)
b => 1
c => 2
d => (- c b) )
$subgoal = 'a
-->
$program = '#( type => program
a => (+ 1 c)
b => 1
c => 2
d => (- c b) )
$subgoal = 'd
-->
$program = '#( type => program
a => (+ 1 c)
b => 1
c => 2
d => (- 2 b) )
$subgoal = 'a
-->
$program = '#( type => program
a => (+ 1 2)
b => 1
c => 2
d => (- 2 b) )
$subgoal = 'd
-->
$program = '#( type => program
a => (+ 1 2)
b => 1
c => 2
d => (- 2 1) )
$subgoal = 'a
-->
$program = '#( type => program
a => 3
b => 1
c => 2
d => (- 2 1) )
$subgoal = 'a
-->
$program = '#( type => program
a => 3
b => 1
c => 2
d => 1 )
$subgoal = 'a
The rule stated for conditionals up there might seem a little
opaque. Here are two traces which illustrate it:
For the program:
(define x 1)
(define y 2)
(define z (cond
((= x 1) 'hello)
((= y 8) 'goodbye)))
the trace is:
$program = '#( type => program
x => 1
y => 2
z => (cond ((= x 1) 'hello)
((= y 8) 'goodbye)) )
$subgoal = 'z
-->
$program = '#( type => program
x => 1
y => 2
z => (cond ((= 1 1) 'hello)
((= y 8) 'goodbye)) )
$subgoal = 'z
-->
$program = '#( type => program
x => 1
y => 2
z => (cond (#t 'hello)
((= y 8) 'goodbye)) )
$subgoal = 'z
-->
$program = '#( type => program
x => 1
y => 2
z => 'hello )
$subgoal = 'z
at which point z is fully reduced.
A slight variation:
(define x 1)
(define y 2)
(define z (cond
((= x 7) 'hello)
((= y 8) 'goodbye)))
also has an illustrative trace:
$program = '#( type => program
x => 1
y => 2
z => (cond ((= x 7) 'hello)
((= y 8) 'goodbye)) )
$subgoal = 'z
-->
$program = '#( type => program
x => 1
y => 2
z => (cond ((= 1 7) 'hello)
((= y 8) 'goodbye)) )
$subgoal = 'z
-->
$program = '#( type => program
x => 1
y => 2
z => (cond (#f 'hello)
((= y 8) 'goodbye)) )
$subgoal = 'z
-->
$program = '#( type => program
x => 1
y => 2
z => (cond ((= y 8) 'goodbye)) )
$subgoal = 'z
-->
[...]
-->
$program = '#( type => program
x => 1
y => 2
z => (cond (#f 'goodbye)) )
$subgoal = 'z
-->
$program = '#( type => program
x => 1
y => 2
z => (cond) )
$subgoal = 'z
-->
$program = '#( type => program
x => 1
y => 2
z => #undefined )
$subgoal = 'z
which is again fully reduced and halts normally.
* xl1 Goals and Subgoals
Consider how we might evaluate:
(define maybe-prime (- two-power 1))
(define two-power (power 2 N))
(define N 3)
using only the rules we have so far. The trace if we want to
obtain `maybe-prime' would go:
$program = '#( type => program
maybe-prime => (- two-power 1)
two-power => (power 2 N)
N => 3 )
$subgoal = 'maybe-prime
-->
???
We immediately need to reduce `two-power' but that variable has not
yet been reduced to a constant. One way to do that would be
by replacing the variable reference with its definition anyway, as
in:
;;; NOT THE NEXT STEP, REALLY
;;;
$program = '#( type => program
maybe-prime => (- (power 2 N) 1)
two-power => (power 2 N)
N => 3 )
$subgoal = 'maybe-prime
that rule _would_ eventually get the right answer now what if
someone also demanded the value of `two-power'. Then the function
call `(power 2 N)' will have to be evaluated twice which certainly
seems wasteful and counter-intuitive, at least.
So, the real answer is just to change the subgoal:
$program = '#( type => program
maybe-prime => (- two-power 1)
two-power => (power 2 N)
N => 3 )
$subgoal = 'maybe-prime
-->
$program = '#( type => program
maybe-prime => (- two-power 1)
two-power => (power 2 N)
N => 3 )
$subgoal = 'two-power
The program hasn't changed but the goal has. Further reductions
will eventually lead to:
$program = '#( type => program
maybe-prime => (- two-power 1)
two-power => 8
N => 3 )
$subgoal = 'two-power
but then what? $subgoal is fully reduced. The VM has "forgotten"
that the goal was to compute `maybe-prime'.
That's where the $goal register comes in. Our complete VM state,
initially, is actually:
$program = '#( type => program
maybe-prime => (- two-power 1)
two-power => (power 2 N)
N => 3 )
$subgoal = 'maybe-prime
$goal = 'maybe-prime
$goal says "Our overall goal is `maybe-prime'" and $subgoal says
"The immediate goal is `maybe-prime'".
The first step in the reduction has to try to reduce `two-power' in
the definition of `maybe-prime'. It does that by changing the
$subgoal but leaving $goal alone:
$program = '#( type => program
maybe-prime => (- two-power 1)
two-power => (power 2 N)
N => 3 )
$subgoal = 'two-power
$goal = 'maybe-prime
Following the usual reduction rules, that eventually becomes:
[...]
-->
$program = '#( type => program
maybe-prime => (- two-power 1)
two-power => 8
N => 3 )
$subgoal = 'two-power
$goal = 'maybe-prime
The rule for what happens when $goal and $subgoal are different, and
$subgoal is fully reduced, is that $goal is copied to $subgoal:
-->
$program = '#( type => program
maybe-prime => (- two-power 1)
two-power => 8
N => 3 )
$subgoal = 'maybe-prime
$goal = 'maybe-prime
Then, because `two-power' is fully reduced, the rest of execution is
trivial, eventually leading to:
-->
$program = '#( type => program
maybe-prime => 7
two-power => 8
N => 3 )
$subgoal = 'maybe-prime
$goal = 'maybe-prime
In this state, because $subgoal is fully reduced _and_ because $goal
and $subgoal are the same, the machine halts normally.
* Summary and Looking Forward
The above definition of expression evaluation in xl1 gives a fairly
simple and intuitive idea of how reduction takes place and how it
interacts with concurrent demand for more than one variable from
a single program run.
One drawback of the operational model given above is that it is
based on always reducing the "left-most" or "next-needed" trivial
subexpression. Which subexpression that is requires a recursive
search through the current program state: fairly expensive if
implemented naively.
A future post will show given an alternative (but equivalent)
operational model for xl1. The alternative will have the advantage
that it can be implemented in xl1 itself!
The xl1-in-xl1 interpreter is a short but interesting xl1 program.
It computes the changes that occur in virtual machine registers
during one "micro-cycle". Each cycle in the definition given in
this message corresponds to a (finite) sequence of micro-cycles.
The C interface to an xl1 interpreter would do well to include
direct access to the VM. One can imagine an entry point like:
new_vm_state = run_for_k_microcycles (old_vm_state, k);
That function `run_for_k_microcycles' is the essense of an xl1
interpreter.
We'll have a (short) xl1 program that effectively specifies
`run_for_k_microcycles' and so the next step is obvious:
Write a (special purpose) xl1 -> C compiler which can take the
xl1 version of run_for_k_microcycles and translate it into the
C function. Given the very simple nature of xl1, this is not
so daunting a task as it might sound at first.
-t
----
Like my work on GNU arch, Pika Scheme, and other technical contributions
to the public sphere? Show your support!
https://www.paypal.com/xclick/business=lord%40emf.net&item_name=support+for+arch+and+other+free+software+efforts+by+tom+lord&no_note=1&tax=0¤cy_code=USD
and
address@hidden for www.moneybookers.com payments.
-----
"Hello, all of you boys and girls,
I'd like to take you to the inside world."
- Claypool
- [Gnu-arch-users] Round III: xl and all that,
Tom Lord <=