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

On Tue, 18 May 2010 23:27:19 -0400, John Cowan <[email protected]> wrote:
> John Nowak scripsit:
> 
>> Sure, it's simple, but what's beautiful about it? It's a bit like
having 
>> Scheme without lambda really. 
> 
> Scheme (and other applicative languages) need lambda or something like
> it because they need to bind names locally.  Joy has only global names,
> so it doesn't need any such abstraction: non-primitive functions are
> literally nothing but lists of objects, where every object in Joy has
> both a datum interpretation ('3' means 3) and a function interpretation
> ('3' means "accept a sequence, return an equivalent sequence but with
> 3 pushed on it").

I think you're maybe missing my point. I'm aware Scheme needs lambda to
bind names. However, there is no reason lambda needs to form *opaque*
abstractions. In Pico Lisp, it does not; you can modify a lambda as if it
were a pile of conses and atoms. In most Lisps, however, it does form
opaque abstractions because of the many advantages of having your functions
be opaque. I believe the benefits of opaque abstractions would apply to Joy
regardless of the issue of binding.

> But Haskell only permits arbitrary-order reduction *because* it is
> pure and lazy.  If you define bi in ML, you'll get a function which
> must be evaluated left to right, because it returns bottom if f does.
> That's why I say concatenation is not directly relevant.

Let me put it another way. It's easy to have a parallel 'bi' in an ML-like
language with the type '(a -> b) -> (c -> d) -> (a, c) -> (b, d)'. You
can't do this in the concatenative setting because bi has the type 'R a [R
-> S] [S a -> T] -> T' and hence it is not possible to enforce that the
quotation on the top of the stack does not use more than one element. You
*could* give it a type like 'R a [R -> S] [a -> T] -> S ++ T', but this
sort of type level concatenation is undecidable. 

Even if your language is eager and you're not considering parallel
combinators, there are still benefits to the applicative approach. In
particular, you can reduce and transform 'f x' in strictness-preserving
ways without worrying about the arity of 'g x'. This is useful when doing
algebraic manipulation of programs regardless of your evaluation mechanism.

- jn