Commits

Anonymous committed e98de16

Initial import of Larabee version 1.0 revision 2008.0110.

  • Participants
  • Tags rel_1_0_2008_0110

Comments (0)

Files changed (3)

+<html>
+<head>
+<title>The Larabee Programming Language</title>
+</head>
+<body>
+
+<h1>The Larabee Programming Language</h1>
+
+<h2>Introduction</h2>
+
+<p>The Larabee programming language, named after everybody's favourite
+assistant to the Chief of CONTROL, is not a happy-go-lucky language.
+Indeed no, it has plumbed the very depths of the bottomless pit of its own soul,
+only to have its true nature revealed to it too quickly, the utter shock of this
+<i>denoument</i> leaving it scarred and reeling.</p>
+
+<p>You see, Larabee has borrowed the notion of <em>branch prediction</em>
+from the realm of computer processor architecture, and has chosen to abuse it in
+one simple but rather nasty way: the interpretation of each branch instruction is not
+just <em>optimized</em> by the history of branches previously taken, it is
+semantically <em>determined</em> in part by the history of branches
+previously taken.
+Each branch taken (or not taken) increments (or decrements) a value called
+the branch prediction register (or BPR.)  The BPR begins the program at
+zero; when the BPR is positive, tests are interpreted in the usual way,
+but when the BPR is negative, the interpretation changes: the
+"then" and "else" branches are swapped.</p>
+
+<p>What's more, to prevent (or rather, to <em>stymie</em>) working around
+this by, say, coding up a lot of branches dependent on constant data to
+"doctor" the BPR to some extremely (high or) low value, no constant data
+is allowed in a Larabee program.  This has the effect of making programs
+highly dependent on their input.</p>
+
+<p>But enough of this insipidly sentimental dada.  We must move on to
+insipidly sentimental dada frought with errors and inconsistencies.  Woe!</p>
+
+<h2>Syntax</h2>
+
+<p>Larabee programs are notated as S-Expressions, familiar from LISP or
+Scheme.  This is not solely because I am too lazy to write a parser.  It is also
+very fitting for a language which has all of the abstraction and finesse
+of assembly code <i>sans</i> immediate mode.</p>
+
+<p>Larabee forms are as follows:</p>
+
+<ul>
+
+<li><code>(op <var>op</var> <var>expr1</var> <var>expr2</var>)</code>
+<p>Evaluate <var>expr1</var>, then evaluate <var>expr2</var>, then perform the operation <var>op</var> on the results.
+Valid <var>op</var>s are <code>+</code>, <code>-</code>, <code>*</code>,
+and <code>/</code>, with their usual integer meanings, and
+<code>&gt;</code>, <code>&lt;</code>, and <code>=</code>
+with their usual comparison meanings, with a result of 0 on false and 1 on true.
+Division by zero is not defined.</p>
+</li>
+
+<li><code>(test <var>cond-expr</var> <var>expr1</var> <var>expr2</var>)</code>
+
+<p><code>test</code> evaluates the <var>cond-expr</var> to get either true
+(non-zero) or false (zero).  What happens next depends on the value of the BPR.</p>
+
+<p>If the BPR is greater than or equal to 0:</p>
+
+<ul>
+<li>If <var>cond-expr</var> evaluated to true, evaluate <var>expr1</var> and decrement the BPR.</li>
+<li>If <var>cond-expr</var> evaluated to false, evaluate <var>expr2</var> and increment the BPR.</li>
+</ul>
+
+<p>On the other hand, if the BPR is less than 0:</p>
+
+<ul>
+<li>If <var>cond-expr</var> evaluated to true, evaluate <var>expr2</var> and increment the BPR.
+<li>If <var>cond-expr</var> evaluated to false, evaluate <var>expr1</var> and decrement the BPR.
+</ul>
+
+<p><code>test</code> is the lynchpin upon which Larabee's entire
+notableness, if any, rests.</p>
+
+<!--
+
+Now.  The semantics of test are as follows:
+
+Evaluate cond to a boolean.
+If cond is 'true', increment the BPR.
+If cond is 'false', decrement the BPR.
+If the BPR is greater than or equal to 0 {
+    If cond is 'true', evaluate part-a.
+    If cond is 'false', evaluate part-b.    
+}
+Else if the BPR is less than 0 {
+    If cond is 'true', evaluate part-b.
+    If cond is 'false', evaluate part-a.    
+}
+
+An alternate semantics for test are as follows:
+
+Evaluate cond to a boolean.
+
+-->
+
+</li>
+
+<li><code>(input)</code>
+<p>Waits for an integer to arrive on the input channel, and evaluates to that
+integer.</p>
+</li>
+
+<li><code>(output <var>expr</var>)</code>
+<p>Evaluates <var>expr</var> to an integer value and produces that
+integer value on the output channel.</p>
+</li>
+
+<li><code>(store <var>addr-expr</var> <var>value-expr</var>
+<var>next-expr</var>)</code>
+<p>Evaluates <var>addr-expr</var> to obtain an address, and
+<var>value-expr</var> to obtain a value, then places that value in storage
+at that address, overwriting whatever happened to be stored at that address
+previously.  After all that is said and done, evaluates to <var>next-expr</var>.</p>
+</li>
+
+<li><code>(fetch <var>addr-expr</var>)</code>
+<p>Evaluates <var>addr-expr</var> to obtain an address, then
+evaluates to whatever value is in storage at that address.  Not defined
+when the currently running Larabee program has never previously
+<code>store</code>d any value at that address.</p>
+</li>
+
+<li><code>(label <var>label</var> <var>expr</var>)</code>
+<p>Indicates that this <var>expr</var> is labelled <var>label</var>.
+Serves only as a way to reference a program location from another
+location (with a <code>goto</code>;) when executed directly,
+has no effect over and above simply evaluating <var>expr</var>.</p>
+</li>
+
+<li><code>(goto <var>label</var>)</code>
+<p>Diverts control to the expression in the leftmost, outermost occurrence of
+a label named <var>label</var>.</p>
+</li>
+
+</ul>
+
+<h2>Discussion</h2>
+
+<p>Ah, the burning question: is Larabee Turing-complete?  The burning answer is,
+I think, a technical and somewhat subtle "no".</p>
+
+<p>But first we must address our subject's special way of dealing with the world.
+As you've no doubt noticed, Larabee has "issues" with input.  (Somewhat interestingly,
+this emotional baggage was not a direct design goal; it was an unintended consequence
+of abusing branch prediction and trying to prevent it from going unabused.)
+These issues will, it turns out, haunt the language unceasingly, day in and day out,
+with despair and turmoil forever just around the corner.</p>
+
+<p>A specific hullabaloo induced by Larabee's obdurately retrograde
+(not to mention completely stupid)
+input regime is that it's simply not possible to write a program in Larabee
+which is independent of its input.  This alone may make it fail to be
+Turing-complete, for surely there are many Turing machine programs
+which are input-invariant, and these programs Larabee cannot legitimately
+aspire to one day become, or alas, even emulate.</p>
+
+<p>For example, input invariance is the underlying idea used in converting the
+usual proof of the uniform halting problem into a (less obvious) proof
+of the standard halting problem &mdash; you say, for any given input, that
+we can find a machine that erases whatever input it was given, writes the
+desired input on its tape, and proceeds to perform a computation that we can't
+decide will halt or not.</p>
+
+<p>The idea is also embodied in a traditional quine program, which produces a
+copy of itself on its output, while talking no input. That is, it doesn't matter what input
+is given to it (and this is often trivial to prove since the quine is generally witten in
+the subset of the language which does not contain any input instructions.)</p>
+
+<p>But Larabee can't do either of these things.  There is no Larabee
+program that can replace its arbitrary input with some fixed, constant choice of
+input.  And while you can write a quine, it will require a certain input to
+produce itself &mdash; there will always be other inputs which make it
+produce something different.</p>
+
+<p>"So what!" you say, being of bold philosophical bent, "it's mere mereology.
+Whether we consider the input to be part of the program or not is simply not
+relevant.  Stop trying to confuse me with details and definitions when I already know
+perfectly well what you're talking about."</p>
+
+<p>Fine, let's say that.  The customer is always right, after all...</p>
+
+<p>The problem, Wendy, is that Larabee is <em>still</em> not Turing-complete.
+But there are subtler reasons for this.  Needle-fine, almost gossamer reasons.
+Ephemeral reasons with a substantial bouquet; fruity, with notes of chocolate
+and creosote.  I doubt that I can do them justice in prose.  However, it still
+strikes me as a more promising medium than modern dance, I mean at least nominally
+anyway.</p>
+
+<p>The reason is basically that you need to know a lower bound on
+how many tests and variable accesses a Larabee program will make in advance
+of running it, so you can supply that many values in the input to ensure that
+the <code>test</code>s in the program go where you want them to go.</p>
+
+<p>(It should be noted that it was rougly at this point that Pressey reached one of the
+peaks of his so-called "referential" period, in which he was apt to provide "commentary"
+on his own work, in the form of interjections or asides, as if from the perspective of a
+historian from a much later era.  Such pretentious interruptions were generally
+not well received, except perhaps by the occasional loser such as yourself.)</p>
+
+<p>To illustrate, let's try walking through an attempt to have Larabee make a computation.
+Factorial, say.  In pseudocode, it might look like</p>
+
+<pre>a := input
+b := 1
+while a &gt; 0 {
+  b := b * a
+  a := a - 1
+}
+print b</pre>
+
+<p>Translating this one step toward Larabee, we find the
+following misty wreck on our doorstep:</p>
+
+<pre>(begin
+  (store a (input))
+  (store b 1)
+  (label loop
+    (begin
+      (store b (op * b a))
+      (store a (op - a 1))
+      (if (op &gt; a 0)
+        (goto loop) (nop))))
+  (print b))</pre>
+
+<p>Now, we can't use names, so we say that a lives at
+location 1 and b lives at location 2 and we have</p>
+
+<pre>(begin
+  (store 1 (input))
+  (store 2 1)
+  (label loop
+    (begin
+      (store 2 (op * (fetch 2) (fetch 1)))
+      (store 1 (op - (fetch 1) 1))
+      (if (op &gt; (fetch 1) 0)
+        (goto loop) (nop))))
+  (print (fetch 2)))</pre>
+
+<p>Now, we can't have constants either, so we hold our
+breath and grope around in the dark to obtain</p>
+
+<pre>(begin
+  (store (input) (input))
+  (store (input) (input))
+  (label loop
+    (begin
+      (store (input) (op * (fetch (input)) (fetch (input))))
+      (store (input) (op - (fetch (input)) (input)))
+      (if (op &gt; (fetch (input)) (input))
+        (goto loop) (nop))))
+  (print (fetch (input))))</pre>
+
+<p>...with the understanding that the appropriate inputs for this
+program are ones that have 0, 1, and 2 in the right places.
+Naturally, sadly, magnificently, other kinds of inputs will
+produce other, most likely non-factorial programs.</p>
+
+<p>Lastly, we have to give up hope of ever seeing the familiar shores of
+our homeland again, bite the bullet and kick the <code>if</code>
+habit:</p>
+
+<pre>(begin
+  (store (input) (input))
+  (store (input) (input))
+  (label loop
+    (begin
+      (store (input) (op * (fetch (input)) (fetch (input))))
+      (store (input) (op - (fetch (input)) (input)))
+      (test (op &gt; (fetch (input)) (input))
+        (goto loop) (nop))))
+  (print (fetch (input))))</pre>
+
+<p>And, oh, actually, we don't have <code>begin</code> &mdash;
+nor <code>nop</code>, neither.  Hooray!</p>
+
+<pre>(store (input) (input)
+  (store (input) (input)
+    (label loop
+      (store (input) (op * (fetch (input)) (fetch (input)))
+        (store (input) (op - (fetch (input)) (input))
+          (test (op &gt; (fetch (input)) (input))
+            (goto loop) (print (fetch (input)))))))))</pre>
+
+<p>Now, if you've been following that, and if you can imagine in the
+slightest how the input will need to look for any given integer, to
+produce the correct factorial result on the output &mdash; even <em>assuming</em>
+you added a bunch of <code>test</code>s somewhere in the program and
+fed them all the right numbers so that the important <code>test</code> turned
+out the way you wanted &mdash;
+then I needn't go to the extra trouble of a rigourous
+proof to convince you that Larabee is not Turing-complete.</p>
+
+<p>If, on the other hand, you decide to be stubborn and you say well that might be
+a very involved encoding you're forcing on the input but it's just an
+encoding and every language is going to force <em>some</em> encoding on the input
+so <em>duh</em> you haven't shown me anything <em>really</em>, I'd have to pull out the dreaded
+ARGUMENT BY ACKERMANN'S FUNCTION.  However, I'd really rather not, as it's
+late, and I'm tired.  Maybe later.</p>
+
+<p><i>(later)</i>  OK, it goes something like this.  Ackermann's
+function &mdash; which we know we need at least something that can do
+better than primitive-recursive, to compute &mdash; has a lower-bound
+complexity on the order of, well, Ackermann's function.
+(This in itself seems to be one of those mathematical oddities that seems
+wiggy when you first hear about it, then self-evident after you've thought
+about it for a few months... and, if you are lucky, no less wiggy.)
+So anyway, what does that imply about how many items would need to be
+input to a Larabee program that computes Ackermann's function?  And what does
+<em>that</em> imply about what you'd need to obtain that input in the first place?
+Hmm?  Hmm?</p>
+
+<h2>Trivia</h2>
+
+<p>There is an implementation of Larabee written in a relatively pure
+subset of Scheme.  I hesitate to call it a reference implementation, but
+it seems I have no choice in these matters.</p>
+
+<h2>Conclusion</h2>
+
+<p>It has come time to say goodbye to our subject, our illustrious monstrosity,
+our glorious bottom-feeder,  our feel-good cripple of the year.  With such a
+distressing burden to bear, what's a programming language to do?  Who could
+begrudge it seeking comfort in the arms of an understanding
+mistress, a bottle of bourbon, the Cone of Silence?  But even so, saving
+such wretched constructions from their own self-annihilation, so we may all
+learn from its example &mdash; this is one of the very reasons
+we run this Home for Wayward Calculi, is it not?</p>
+
+<p>Indeed.</p>
+
+<p>This is the place where ordinarily where I would wish you a happy something or other.
+But I shall graciously decline this time; it is all too clear that
+there is simply no happiness left.</p>
+
+<p>-Chris Pressey
+<br />January 10, 2008
+<br />Chicago, Illinois
+<br />RICHARD M. DALEY, MAYOR
+</p>
+
+</body>
+</html>
+;
+; larabee.scm - reference implementation of the Larabee programming language
+; $Id: larabee.scm 15 2008-01-09 06:09:13Z catseye $
+;
+
+;
+; Copyright (c)2006 Cat's Eye Technologies.  All rights reserved.
+;
+; Redistribution and use in source and binary forms, with or without
+; modification, are permitted provided that the following conditions
+; are met:
+;
+; 1. Redistributions of source code must retain the above copyright
+;    notices, this list of conditions and the following disclaimer.
+; 2. Redistributions in binary form must reproduce the above copyright
+;    notices, this list of conditions, and the following disclaimer in
+;    the documentation and/or other materials provided with the
+;    distribution.
+; 3. Neither the names of the copyright holders nor the names of their
+;    contributors may be used to endorse or promote products derived
+;    from this software without specific prior written permission. 
+;
+; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+; ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES INCLUDING, BUT NOT
+; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+; FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
+; COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+; INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+; BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+; CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+; LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+; ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+; POSSIBILITY OF SUCH DAMAGE.
+
+; ----------------------------------------------------------------------------
+
+;
+; Updatable store ADT (implemented in pure Scheme.)
+;
+
+(define make-empty-store
+  (lambda ()
+    (make-vector 10 0)))
+
+(define store-update
+  (lambda (store addr value)
+    (let*
+      ((new-vector (expand-store store addr))
+       (foo        (vector-set! new-vector addr value)))
+      new-vector)))
+
+(define expand-store
+  (lambda (store addr)
+    (let*
+      ((extent (if (>= addr (vector-length store))
+                 (vector->list (make-vector (- addr (vector-length store) -1) 0))
+                 '()))
+       (base   (vector->list store))
+       (full   (append extent base)))
+      (list->vector full))))
+
+(define store-retrieve
+  (lambda (store addr)
+    (vector-ref store addr)))
+
+; ----------------------------------------------------------------------------
+
+;
+; Larabee program state ADT.
+;
+; A state includes a "current value" (like an accumulator,) a store, and
+; a special unbounded integer value called the "branch predicition register,"
+; although it might be better called the "right bastard register."
+;
+
+(define make-state
+  (lambda (value bpr store)
+    (vector value bpr store)))
+
+(define get-value
+  (lambda (state)
+    (vector-ref state 0)))
+
+(define get-bpr
+  (lambda (state)
+    (vector-ref state 1)))
+
+(define get-store
+  (lambda (state)
+    (vector-ref state 2)))
+
+(define initial-state
+  (make-state 0 0 (make-empty-store)))
+
+(define bad-program
+  (make-state #f 0 (make-empty-store)))
+
+(define alter-bpr
+  (lambda (state bpr-delta)
+    (make-state (get-value state) (+ (get-bpr state) bpr-delta) (get-store state))))
+
+(define set-value
+  (lambda (state new-value)
+    (make-state new-value (get-bpr state) (get-store state))))
+
+(define state-store
+  (lambda (state addr value)
+    (let*
+      ((old-store (get-store state))
+       (new-store (store-update old-store addr value)))
+      (make-state (get-value state) (get-bpr state) new-store))))
+
+(define state-fetch
+  (lambda (state addr)
+    (let*
+      ((store (get-store state))
+       (value (store-retrieve store addr)))
+      (make-state value (get-bpr state) store))))
+
+; ----------------------------------------------------------------------------
+
+;
+; A function which can be uncommented to produce debugging output.
+;
+
+(define debug
+  (lambda (str data)
+;    (display str) (display ": ") (display data) (newline)
+    data
+  ))
+
+; ----------------------------------------------------------------------------
+
+;
+; Evaluate a Larabee expression.  Returns a Larabee state.
+;
+
+(define eval-expr
+  (lambda (expr prog state)
+    (debug "eval-expr" expr)
+    (cond
+      ((null? expr)
+        bad-program)
+      ((list? expr)
+        (let
+          ((command (car expr)))
+          (cond
+            ((eq? command 'label)
+              (let
+                ((body (caddr expr)))
+                (eval-expr body prog state)))
+            ((eq? command 'test)
+              (let
+                ((condo  (cadr expr))
+                 (expr-a (caddr expr))
+                 (expr-b (cadddr expr)))
+                (eval-test condo expr-a expr-b prog state)))
+            ((eq? command 'goto)
+              (let
+                ((label (cadr expr)))
+                (eval-goto label prog state)))
+            ((eq? command 'op)
+              (let
+                ((operator (cadr expr))
+                 (expr-a   (caddr expr))
+                 (expr-b   (cadddr expr)))
+                (eval-op operator expr-a expr-b prog state)))
+            ((eq? command 'input)
+              (eval-input prog state))
+            ((eq? command 'output)
+              (let
+                ((msg-expr (cadr expr)))
+                (eval-output msg-expr prog state)))
+            ((eq? command 'store)
+              (let
+                ((addr-expr  (cadr expr))
+                 (value-expr (caddr expr))
+                 (next-expr  (cadddr expr)))
+                (eval-store addr-expr value-expr next-expr prog state)))
+            ((eq? command 'fetch)
+              (let
+                ((addr-expr (cadr expr)))
+                (eval-fetch addr-expr prog state)))
+            (else
+              bad-program))))
+      (else
+        bad-program))))
+
+;
+; Evaluate a 'test' expression.
+;
+
+(define eval-test
+  (lambda (condo expr-a expr-b prog state)
+    (debug "eval-test" condo)
+    (let*
+      ((condo-state (eval-expr condo prog state))
+       (bool        (get-value condo-state))
+       (bpr         (get-bpr condo-state)))
+      (if (>= bpr 0)
+        (if bool
+          (eval-expr expr-a prog (alter-bpr condo-state -1))
+          (eval-expr expr-b prog (alter-bpr condo-state +1)))
+        (if bool
+          (eval-expr expr-b prog (alter-bpr condo-state +1)
+          (eval-expr expr-a prog (alter-bpr condo-state -1))))))))
+
+;
+; Evaluate a 'goto' expression.
+;
+
+(define eval-goto
+  (lambda (label prog state)
+    (debug "eval-goto" label)
+    (let
+      ((targets (find-labels prog label)))
+      (if (null? targets)
+        (begin
+          (display "No such target") (newline)
+          bad-program)
+        (begin
+          (debug "found-targets" targets)
+          (eval-expr (car targets) prog state))))))
+
+;
+; Helper function for eval-goto.
+;
+
+(define find-labels
+  (lambda (expr label)
+    (debug "find-labels" expr)
+    (cond
+      ((list? expr)
+        (let
+          ((command (car expr)))
+          (cond
+            ((eq? command 'label)
+              (let
+                ((putative-label (cadr expr))
+                 (body-expr (caddr expr)))
+                (if (eq? putative-label label)
+                  (list body-expr)
+                  (find-labels body label))))
+            ((eq? (car expr) 'test)
+              (let
+                ((condo  (cadr expr))
+                 (expr-a (caddr expr))
+                 (expr-b (cadddr expr)))
+                (append
+                  (find-labels condo label)
+                  (find-labels expr-a label)
+                  (find-labels expr-b label))))
+            ((eq? command 'op)
+              (let
+                ((expr-a   (caddr expr))
+                 (expr-b   (cadddr expr)))
+                (append
+                  (find-labels expr-a label)
+                  (find-labels expr-b label))))
+            ((eq? command 'output)
+              (let
+                ((msg-expr (cadr expr)))
+                (find-labels msg-expr label)))
+            ((eq? command 'store)
+              (let
+                ((addr-expr  (cadr expr))
+                 (value-expr (caddr expr)))
+                (append
+                  (find-labels addr-expr label)
+                  (find-labels value-expr label))))
+            ((eq? command 'fetch)
+              (let
+                ((addr-expr (cadr expr)))
+                (find-labels addr-expr label)))
+            (else
+              '()))))
+      (else
+        '()))))
+
+(define eval-op
+  (lambda (operator expr-a expr-b prog state)
+    (let*
+      ((state-a  (eval-expr expr-a prog state))
+       (value-a  (get-value state-a))
+       (state-b  (eval-expr expr-b prog state-a))
+       (value-b  (get-value state-b))
+       (value-c  (enact-op operator value-a value-b)))
+      (set-value state-b value-c))))
+
+(define enact-op
+  (lambda (operator value-a value-b)
+    (cond
+      ((eq? operator '+)
+        (+ value-a value-b))
+      ((eq? operator '-)
+        (- value-a value-b))
+      ((eq? operator '*)
+        (* value-a value-b))
+      ((eq? operator '/)
+        (/ value-a value-b))
+      ((eq? operator '>)
+        (> value-a value-b))
+      ((eq? operator '<)
+        (< value-a value-b))
+      ((eq? operator '=)
+        (eq? value-a value-b))
+      (else
+        value-a))))
+
+(define eval-input
+  (lambda (prog state)
+    (let
+      ((value (read)))
+      (if (number? value)
+        (set-value state value)
+        (begin (display "?REDO") (newline) (eval-input prog store))))))
+
+(define eval-output
+  (lambda (msg-expr prog state)
+    (let
+      ((new-state (eval-expr msg-expr prog state)))
+      (begin
+        (display (get-value new-state)) (newline)
+        new-state))))
+
+(define eval-store
+  (lambda (addr-expr value-expr next-expr prog state)
+    (let*
+      ((addr-state  (eval-expr addr-expr prog state))
+       (addr        (get-value addr-state))
+       (value-state (eval-expr value-expr prog addr-state))
+       (value       (get-value value-state))
+       (new-state   (state-store value-state addr value)))
+      (eval-expr next-expr prog new-state))))
+
+(define eval-fetch
+  (lambda (addr-expr prog state)
+    (let*
+      ((addr-state  (eval-expr addr-expr prog state))
+       (addr        (get-value addr-state)))
+      (state-fetch state addr-state))))
+
+; ----------------------------------------------------------------------------
+
+;
+; Evaluate (run) a Larabee program.
+;
+
+(define eval-larabee
+  (lambda (prog)
+    (begin
+      (eval-expr prog prog initial-state)
+      (display "OK")
+      (newline))))
+;
+; test.scm - test suite for the Larabee reference interpreter
+; $Id: test.scm 15 2008-01-09 06:09:13Z catseye $
+;
+
+(load "larabee.scm")
+
+; ----------------------------------------------------------------------------
+
+(define test1
+  (lambda ()
+    (eval-larabee '(label foo (goto foo)))
+  ))
+
+(define test2
+  (lambda ()
+    (eval-larabee '(output (op + (input) (input))))
+  ))
+
+(define test3
+  (lambda ()
+    (eval-larabee
+     '(store (input) (input)
+        (store (input) (input)
+          (label loop
+            (store (input) (op * (fetch (input)) (fetch (input)))
+              (store (input) (op - (fetch (input)) (input))
+                (test (op > (fetch (input)) (input))
+                  (goto loop) (print (fetch (input)))))))))
+    )))