# Re: Abstraction again

## Mark van Gulik — 2000-10-24 19:36:39

    Manfred (phimvt@...) wrote:

    [...]

     > Abstraction in Concatenative Languages

     [...]

     >     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.

     Agreed.

     >     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

     [...]

     >     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.

     Careful here.  Lambda rewriting rules may be used *anywhere* inside an

    expression due to the Church-Rosser thesis (I believe that's the right

    names).  Joy absolutely requires that all "rewriting" (i.e., computation)

    must occur in the "current" expression (the outermost one not pushed onto

    the call stack), and specifically at the leftmost symbol of that expression.

    That's because quotations are referentially opaque.

    [...]

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

     Interesting.  Alternatively, you might want to reserve some words to

    represent "registers" instead.  Say you want x, y, and z to be the allowable

    register names.  Then an expression (in pure Joy) of the form:

        3 4 5 [x y z] % x k z y... y n i g /%

    could simply assign 3 to x, 4 to y, and 5 to z.  The occurrences of x, y,

    and z within the expression delimited by the operators "%" and "/%" would

    simply push the current values.  If execution of one of the embedded terms,

    say "k", caused x, y, or z to be reused in another %-binding, the previous

    values could be "saved" first, and restored at the corresponding "/%".  This

    can get kind of messy if you ever try to implement exceptions, but for now

    it should be straightforwrd.  Anyone want to volunteer implementations of

    "%" and "/%" as pure Joy code?

    Then again, since being able to manipulate things in something other than

    stack order seems essential to a Joy programmer's sanity, why not simply

    introduce one more stack?  Here's a proposal for a language using two (data)

    stacks...

    "5" has the effect of pushing 5 onto the A-stack.

    "+" takes two values from the A-stack, adds them, and pushes them back onto

    the A-stack.

    "dip" is not needed.  Instead, "save" pops the A-stack, pushes that value on

    the B-stack, and then continues.  "restore" pops the B-stack, and pushes the

    value onto the A-stack.  In my opinion this is much easier to reason about

    than the way "dip" seems to expose a corner of the supposedly invisible

    execution stack.

    "Bpop" pops the B-stack.

    "Bpush" is the same as "save".

    Hm.  This isn't going where I thought it would.  If anyone can suggest a

    better direction for this, feel free.

    [...]

     >         (% 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 can be done fairly easily within ordinary Joy if the code is massaged

    to look like:

        3 4 5 [x y z] [y x y z x z z x] %

    It's more interesting if something other than x, y, or z occurs in the

    rightmost quotation.  Also, what happens if this quotation contains nested

    quotations?...

        3 4 5 [x y z] [[a m z] print-my-favorite-letters]

    Do we really not want to allow uses of z as a "free variable" inside these

    quotations?  I actually vote against allowing *any* free variables (like,

    totally Prenix normal, dude), but that's another story.

    [...]

    Mark