Re: [stack] Barebone implementation of concatenative language in c or c++

Sorry -- here's a copy slightly less mangled by my horrible webmail:

On Tue, 18 May 2010 11:16:40 -0000, "Ruurd" <[email protected]>
wrote:

> And it is not a stack language either. The order of
> evaluation is not specified. Take for instance a small
> example: 2 3 [+] i. This evaluates to 5, but I do not
> have to start the rewriting at the left.[+] i is equal
> to + and 2 3 + is equal to 5, so I can start at the
> right if I like.

A critique of ascribing this property to Joy if I may...

This view breaks down once your functions have side effects (which is the
case in Joy). Because if this, the arbitrary order reduction you're talking
about needs to be subject to side constraints regarding purity.

The utility of arbitrary order rewriting in Joy is also severely limited
by the fact that quotations are not opaque. For example, it is not valid to
rewrite [1 2 +] to [3] because the quotation may be treated as a list later
on. It is for this reason that I consider Joy's approach to quotations to
be broken; a separation of quotations from lists would solve the problem.

However, even if you do separate lists from quotations, you will end up
with other concerns about arbitrary order reduction. For example, you may
have a rule like '{A} drop == id' (where '{A}' denotes some list formed by
the list of expressions A), but that rule will not be valid in the presence
of strict evaluation if you have partial functions (as Joy does).

In short, you can say it isn't a stack language because it doesn't need to
be evaluated in a particular order, but in practice you likely want it to
be, and I believe the current Joy implementation takes this approach.

Finally, applicative languages arguably have an advantage over Joy in
terms of arbitrary order reduction. For example, take this Haskell
function:

  bi f g x = (f x, g x)

And the common Joy equivalent:

  x [F] [G] bi = x F x G

The Haskell version has the advantage that we can easily reduce 'f x'
completely independent of 'g x'. The Joy version does not have this
advantage; in general, it will be necessary to reduce 'x F' before it is
safe to reduce 'x G' because 'G' may require more than one element on the
stack. Accordingly, the applicative approach has the advantage here in
terms of order-independent reduction.

- jn