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