I hope this is not considered too long, it is actually only 2/3
of the longest I have received from the egroup. It contains my
thoughts on abstraction in a concatenative language. In a while
I plan to put a revised version on my web page. Comments from
the group are most welcome.
Manfred

Abstraction in Concatenative Languages

The prime goal of Joy is the elimination of unnecessary
complexity. Lambda calculus languages require the maintenance of
an environment which is a variable-value association. The environment
and the abstraction operation are eliminated in combinatory
calsulus which still has the algebraically useless application
operation. In Joy application is replced by composition which
has useful substitution properties.

So, lambda abstraction goes against the prime goal. The price
of lambda abstraction is increased complexity. But it may still
be worth some other benefit. Let us see.

A well-formed expression (..x..x..) containing several occurrences
of a free variable does not denote anything because of the free
variable. If these occurrences are uniformly replaced by an expression
that does denote (e.g. a constant), then the resulting whole
expression does denote a value. But one can also form lambda
abstractions, usually written with the lower case Greek letter
lambda, or just "\", or "fun". Now the lambda abstraction

fun x (..x..x..)

denotes a function. Abstractions can be passed as parameters, to be passed
further and further. But this is pointless unless the abstraction
is eventually applied to a value. The application can be written
explicitly with an infix operator "@". Let "5" be a suitable value
to which the abstraction can be applied. The application expression
now looks like this:

fun x (..x..x..) @ 5

By what is known as beta-conversion this denotes the same value as

(..5..5..)

which requires further evaluation to give a value. Clearly, if a
language does not have application, then it is pointless to have
lambda abstraction. But let us look for benefits.

Lambda abstracts do not have a name, so they are anonymous.
But they can be given a name, as in the first definition below. The
second is a more common but entirely equivalent style:

f =def fun x (..x..x..)
f(x) =def (..x..x..)

Application occurs when "f" is being called, as in the first
style below and the more common second style:

f @ 5
f(5)

So, abstraction and application are often hidden in the common
style. Inside the (..x..x..) expression any notation is possible,
it can be prefix, infix, postfix or mixfix). For a function
g(x,y) of two variables the notation might look like any of these:

g 5 7 5 g 7 5 7 g

So postfix notation is in no way specific to abstraction free
languages.

Abstraction need not be applied to constants such as "5",
but equally to complex expressions such as "(2+3)". The
application expression

fun x (..x..x..) @ (2+3)

can now be evaluated in two ways.

In normal order evaluation the argument "(2+3)" is substituted
for x to yield

( .. (2+3) .. (2+3) .. )

which is then evaluated. This might require "(2+3)" to be evaluated
twice, but it might also be that "(2+3)" does not have to be evaluated
at all.

In applicative order the argument "(2+3)" is first evaluated to
"5" which is then substituted for "x" to yield

( .. 5 .. 5 .. )

which is then evaluated. If the value "5" is indeed needed twice,
then "(2+3)" will have been evaluated only once, a saving over
normal order evaluation. But if the value is not required at all,
then evaluation of "(2+3)" was a waste compared with normal
order.

In the early masterpiece language Algol 60 these two orders,
normal and applicative, were known as "call-by-name" and "call-by-value".
Most contemporary mainstream languages use applicative order,
but some can also produce the effect of normal order. (Some
recent languages, notably Haskell, use "call-by-need" or
lazy evaluation which combines the advantages of both.)

Years ago, when I was first bumbling through Joy-scape, I asked
myself whether Joy used normal order or applicative order, and I
could never work it out properly. But now I know that without
application and abstraction the question does not make sense.

In a language without abstraction and application one might
nevertheless gain their benefits by other, perhaps similar means.
First, consider a definition of a function in a lambda calculus
language:

f(x,y,z) =def g(h(k(x),l(z,y)),i(m(z,x),n(y)))

One would not want to replicate this in a concatenative
language such as Forth or Joy by a definition in the form

f =def ...one-hellish-expression...

in which the right hand side consists of lots of swaps, dups etc..
More reasonable would a definition like

x y z f =def x k z y l h z x m y n i g

The idea is that the left side has the same shape as a call might be:

3 4 5 f

The right side of the definition uses the three parameters, and
in a call the occurrences of variables must yield the corresponding
values. So before the call of "f" the three formal parameters x, y
and z and their values 3, 4 and 5 must be entered into the environment.

Equivalently the formals might be written on the right:

f =def (% x y z) x k z y l h z x m y n i g

where "%" is, for the moment, a fantasy abstraction operator
whose exact nature is to be determined below. Using this style
the right hand side can be used outside definitions, can be
passed on as a parameter, and can be eventually used with actual
parameters 3, 4 and 5, or with any others. We seem to end up
with abstraction and application which just happens to use postfix
notation for no deep reason. But then we are back to square one.

If you look at the previous paragraph there was no mention
of a stack and relateded concepts. My first version of that paragraph
needed considerable cleansing. But now I shall rewrite the
essential parts for a concatenativee stack language where everything
denotes a unary stack function, even the "5" or the variable "x"
inside "(..x..x..)". In the example, the occurrence of "x" should
have the same effect on the stack as the occurrence of "5",
either one pushes the number 5 onto the stack.

The function "f" is a unary stack function which expects a stack
of at least three values. It yields a stack from which the three
values have been popped and a new value has been pushed. That
value is obtained from the body of the abstraction by letting
each occurrence of a variable denote the stack function which
pushes the corresponding value of the three that were originally
popped.

Since f was defined by the right hand side, the previous
paragraph is also true of the right side of the definition:

(% x y z) (x k z y l h z x m y n i g)

Only the second pair of parentheses has been added to indicate
the scope of the abstraction. Just as "f" above, this expression
denotes a unary stack function which pops three values and pushes
one return value. In general such "%"-abstractions denote
unary stack functions like everything else in a concatenative
language.

The above unary stack function can be composed with three
others, say those denoted by "3", "4" and "5":

3 4 5 (% x y z)(x k z y l h z x m y n i g)

Here the original gap between ")" and "(" has been removed,
and all the other gaps outside "(% x y z)" have been lengthened.
This expression denotes a unary stack function, and all the
longer gaps denote the composition of unary stack functions.
There is no application, and hence the "%"-abstraction is not
a lambda abstraction. There is composition instead, the
"%"-abstractor abstracts the top three values of the stack.

To spell out the contrast again, in the lambda calculus
"5" denotes a function and "(% x)(..)" would denote a function,
in a concatenative language both "5" and "(% x)(..)" denote
unary stack functions.

In the lambda calculus abstractions can be nested,
just as in logic quantification can be nested. The same is true
here:

(% x y z)( ... (%x w)(..) ...)

In the inner (..) any "x" or "w" pushes the value of the inner
abstraction, and any "y" or "z" pushes the value of the outer
abstraction. In the leading "..." or the trailing "..." any "x",
"y" or "z" pushes the values from the initial, outer abstraction.

It is useful to look at some special cases which can serve
to rearrange the top few elements of the stack:

(% x y z)(x) == pop pop
(%x y z)(y x) == pop swap
(% x y z)(y x y z x z z x) == a complex rearrangement

This assumes that the order of the variables is supposed to match
the order in which the values have been pushed: inside "(% ..)"
the last variable gets the top of stack as its value.

But it is not obvious that this is how it should be handled. After
all the stack is just a list, and when writing a list we normally
write the first element first. (If the language has an operator
which pushes the stack onto the stack, this seems obvious. Joy
has just that operator, appropriately called "stack".) So one
might reverse the order in which the variables in "(%..)"
are to be bound: the first variable is bound to the top element
and so on. Furthermore, it might be useful to bind a variable
to the rest of the stack, too. Now the "%"-binding operator
is beginning to look similar to the list notation used by
the language Prolog:

(% [S1 S2 S3 | R]) (..S2..S1..R..S3..S1..)

the variables "S1", "S2" and "S3" would be bound to the top
three values on top of the stack, in that order, and variable "R"
would be bound to the remainder of the stack. All four variables
can be used inside the second parenthesised expression.

Following the lead of Prolog, one should go further. The top
few elements of the stack might include a list that is known to
contain, say, at least two elements. Then an abstraction might
look like this:

(% [S1 S2 [L1 L2 | L] S4 | R]) (...)

would bind "S1" and "S2" to the first and second elements of the stack,
it would bind "L1", "L2" and "L" to the first, second and rest of
the list which is the third element of the stack, and it would bind
"S4" and "R" to the fourth element and the remainder of the stack.
At the start of "(...)" the top four elements of the stack have
been popped, and inside "(...)" all seven variables are accessible.
The details of the concrete syntax needs some cleaning up, perhaps.

The above discussion has shown that some kind of abstraction
facility does fit in with concatenative languages such as Forth
and Joy: the mechanism is fully compatible with the central tenet
that concatenation of programs denotes composition of unary functions.
But much more discussion is needed to determine whether it is
worth implementing. Any implementor should have experience with
pattern matching or unification. (Any volunteers for Joy?)

Abstraction - again

phimvt@lurac.latrobe.edu.au — 2000-10-24 08:45:46