Re: [stack] Re: Jon Purdy: Why Concatenative Programming Matters

On Mar 24, 2012, at 5:35 PM, William Tanksley, Jr wrote:
> > 2) each flat (sub)expression can be reduced one step (or many steps, to reach fixpoint).
> 
> You later define "reduce" as "execute". I have to point out that some
> expressions in any Turing-complete language never reach a fixed point
> by execution.

of course, never to reach fixed point is an 'infinite loop'.
to reach fixed point is called the normal form of an expression.
see: http://en.wikipedia.org/wiki/Term_rewriting_system

> Furthermore, you later assume that the reduced expression is itself
> flat; that's not correct in my notation. It's actually possible to
> build a formal logic where that does hold, but such a logic will be
> both VERY complex and either incomplete or possible to express
> contradictions in (per Godel).

i always understood that a flat language must have this property:
that *any* expression (albeit reduced) must be flat.

> > 5) the reduction order of flat expressions doesn't matter - any reduction order will always yield the same (fixpoint) expression (confluence)
> 
> Whatever "reduce" means, it doesn't mean this. Sorry, but this would
> imply that any two expressions of the same function will always reduce
> to the same fixed form, thus allowing you to test in a finite amount
> of time whether two functions are equivalent. That's impossible.
> 

the chosen reduction order (or strategy) doesn't imply at all that you can test two different expressions for equivalence.
confluence means that you always end up with the same normal form, irrespective of reduction order.
(when there are multiple ways rewrite an expression).

confluence is a very nice property to have for a chosen reduction strategy.

consider for example the difference between lazy evaluation and eager evaluation.
with lazy evaluation, taking the first element of an (lazy) infinite list will yield a value.
not so with eager evaluation.

> > a high-level flat language would probably have more than two combinators.
> 
> More importantly, it'll have syntax to allow user-defined names -- so
> you can define any combinator you want using zeroone, and from then on
> refer to it by name.

sure, names are good.

> Implementing true/false/if/else actually isn't hard; it usually starts
> by defining "false" as "drop", and "true" as "execute". The function (
> func flag ) "if" would then simply be "execute" -- that is, it
> executes the true/false flag, and if that's a 'true' it executes the
> function; if it's a 'false' it drops the function.

actually, what you describe is very much the 'enchilada' way of doing conditionals.
for example, the following expression:

10 ? [is_ten] * .

tests for 10 and reduces to is_ten if so

10 10 ? [is_ten] * .
1 [ten] * .
[ten] .
ten

5 10 ? [is_ten] * . 
0 [ten] * .
0 .
(empty).

> -Wm

cheers,

R.