# Abstraction - again

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

    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?)