14-FEB-05
Abstract: Complex expressions can be difficult to evaluate in Joy and in other stack-based languages, especially when some of the parameters are needed repeatedly for the computation of intermediate values. This note describes some techniques that can be valuable in such cases. The example used is the quadratic formula.
An equation of the form a * x^2 + b * x + c = 0 has either no solution in the reals, or it has two solutions in the reals ("not necessarily distinct" as they say). The solutions, if any, are given by
-b +/- sqrt(b^2 - 4 * a * c)
-----------------------------
2 * a
R. Kent Dybvig, The SCHEME Programming Languagage, 1987, p 44,
gives the following definition
(define quadratic-formula
(lambda (a b c)
(let ([minusb (0 - b)]
[radical (sqrt (- (* b b) (* 4 ( * a c))))]
[divisor (* 2 a)] )
let ([root1 (/ (+ minusb radical) divisor)]
[root2 (/ (- minusb radical) divisor)])
(cons root1 root2)))))
For a = 2, b = -4, c = -6 the solutions are x = 3 and x = -1,
and the programs gives the solutions in the form of a (dotted)
pair:
(quadratic-formula 2 -4 -6) => (3 . -1)
Dybvig remarks (p 45):
".. by employing two let expressions, the definition makes
clear the dependency of root1 and root2 on the values of
minusb, radical, and divisor. Equally important, the let
expressions make clear the lack of dependencies among minusb,
radical, and divisor and between root1 and root2."
The remainder of this note is concerned with writing a program in Joy
which does the same thing, using the Scheme program as a model. The
general plan is to develop some constructions in Joy which can play the
same role as the let-expressions in Scheme (or other languages).
The simplest let-expressions are those in which only a single expression is evaluated and given a name, which is then available in the body:
(let ([name expression])
( body ))
In Joy there is no name to be given to the value of the expression, but
the value of the expression can be pushed on top of the stack by the
nullary combinator:
[expression] nullary body
The nullary combinator executes the quotation on top on the remainder
of the stack, possibly consuming several values, and then restores
that remainder and pushes whatever top value the execution of the
quotation had produced.
But this is of no use for multiple let-expressions in which there are several names to be defined independently, as in the first half of the Scheme program in which three names are defined, or in the second half in which two are defined.
The effect of multiple let-expressions can be simulated in Joy by a simple but very useful device. The aim is to compute several values independently which are to be used later. In Joy these values are anomymous. The general pattern is
[[..] [..] [..]] [i] map
This is perhaps a surprising use of the map combinator. In all cases the
map combinator expects on top of the stack a single quotation and in most
cases below that a list or other aggregate of values. But map can also
handle the case where that list is a list of quotations to be executed. If
the single quotation is [i], the the quoted i combinator will execute each
of the three listed quotations and the map combinator assembles these into
a list of the three values that were on top of the stack at the end of the
three executions. Note that the three result values are computed
independently of each other, and each of the three computations can modify
the stack in any way, and after each of the three computations the
original stack below the list of three quotations is restored. It is these
three properties that make the device useful for structuring Joy programs.
In many cases the three values that have been computed from the three quotations are required not as a single list on top of the stack but as three independent values. Of course it is easy enough to decompose the list, in the present case by
uncons uncons uncons pop
This will work even in the rare case where the result list contains
operators, as in [2 + 3]. But the sequence of uncons'es is clumsy,
especially if the list is long. It would be preferable to use some code
which decomposes the list independently of its length. One device is the
step combinator, which expects a quotations and below that a list or other
aggregate. It successively puts the elements of the list onto the stack
and executes the quotation. The top value after each of the executions is
pushed onto the stack. In the present case the required quotation [],
which does nothing. So, for example,
1 2 3 [[pop dup *] [+] [2 *]] [i] map [] step
will leave 1 2 3 4 5 6 on top of the stack, the 6 topmost, after producing
the list [4 5 6] just after the map.
Applying these constructions mechanically to the nested multiple let-expressions in the Scheme program results in the following definition in Joy:
DEFINE
quadratic-1 == # a b c => [root1 root2 ]
[ [ pop pop 2 * ] # divisor
[ pop 0 swap - ] # minusb
[ swap dup * rollup * 4 * - sqrt ] ] # radical
[i] map [] step
[ [ + swap / ] # root1
[ - swap / ] ] # root2
[i] map [] step
[] cons cons # build pair
[ pop pop pop pop pop pop ] dip. # cleanup stack
But the program is unsatisfactory for a number of reasons:
1. Most glaringly, in line 7 the list of two roots is decomposed by [] step. But then in line 8 the two roots are recomposed to a list. So, the final [] step in line 7, and all of line 8 should be deleted.
2. In line 4 the list of three intermediate values is also decomposed by [] step. Just like a sequence of uncons operations, this will work even in the rare case where the list contains operators, as in [2 + swap]. But in the case of the quadratic formula the list of intermediate values is just a normal list of literals, namely numbers. Because of that it is possible to decompose the list by just the i combinator, which will do the same job simpler and also more efficiently.
3. In line 9 the six pops remove the three parameters (a b c) and the three inttermeddiate values (divisor minusb radical). A language such as Scheme need not (and cannot) explicitly express the disappearancce of these values. But the three parameters are no longer needed in the computation of the two roots from the three intermediate values. And yet, during that computation the three parameters are still visible. But is only by inspecting the code for the computations that it becomes apparent that the parameters are not used directly. In Scheme the independence is not (and cannot be) expressed explicitly. But it can be expressed in Joy. The three (dipped) pops for the three parameters can occur as soon as they are no longer needed, and that is immediately after the first map. Similarly the three (dipped) pops for the three intermediate values can occur after the second map. But when the number of pops is small (three in this case) we can do better than [pop pop pop] dip. The combinators nullary, unary, binary and ternary are normally used to ensure that a quoted program does not consume more than 0, 1, 2 or 3 values from the stack. They can also be used to ensure that exactly that many are consumed. So the two lots of three pops can both be expressed by the ternary combinator.
DEFINE
quadratic-2 == # a b c => [root1 root2 ]
[ [ [ pop pop 2 * ] # divisor
[ pop 0 swap - ] # minusb
[ swap dup * rollup * 4 * - sqrt ] ] # radical
[i] map ]
ternary i
[ [ [ + swap / ] # root1
[ - swap / ] ] # root2
[i] map ]
ternary.
This version of the program is the best of the three in this note. It has now been added to the numlib.joy standard library.
There is another device which sometimes can be useful, especially when the number of pops is larger than can be handled by a single combinator such as ternary. This might arise if the number of intermediate values is large, and they have been computed as a list, most probably by [i] map. In such a case that very same list can be used as the (temporary) stack for the following computations. The combinator infra expects a list and above that a quotation. It will treat the list as the stack and execute the quotation using that stack. It will return the modified list on top of the regular stack. In the present program for the quadratic formula, after the three intermediate values have been computed as a list, the remaining computation for the two roots can be done under the control of the infra combinator. Note that this is in the last line of the program below. When that returns, the required final value will be what is on top of this temporary stack, which the first element on the list, and that can be extracted with the first operator. The remaining intermediate values thereby disappear, no matter how many there were. The device is an overkill in the present case for the quadratic formula, but it can be useful elsewhere.
The device can also be used when instead several parameters there is only one, but it is a possibly long list of values. This situation does not obtain in the present case, but we can make it so by a chain of three conses into an initially empty list. This is only done in the program below to enable the first use of the infra combinator. So the following illustrates the use of the infra combinator twice, once for computing the intermediate values, and once for computing the final result. The first use relied on the ugly chain of conses at the beginninng, and would not really be recommended. But the second use would be a reasonable and more widely useful alternative to the ternary combinator. Note also that because of the infra combinator some of the order of computations needed to be different from the preceding program.
DEFINE
quadratic-3 == # a b c => [root1 root2 ]
[] cons cons cons # list of parameters
[ [ [ [dup * swap] dip * 4 * - sqrt ] # radical
[ pop 0 swap - ] # minusb
[ 2 * ] ] # divisor
[i] map ]
infra first
[ [ [ + swap / ] # root1
[ - swap / ] ] # root2
[i] map ]
infra first.