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

Robbert van Dalen <[email protected]> wrote:
>> So, for example, "01" evaluates as follows:
>> "01" =
>> [] [q] [k] "1" =
>> [] [q] [k] k =
>> [] k.
> but the result
> [] k
> cannot be expressed with the defined combinators 0 and 1, except implicitly with "01"
> isn't that a problem?

Looking elsewhere in your email, I see the problem. This is a good
time to ask that implied question: "is there any difference between
[]k and drop, or between 0011 and q"?

No, it's not a problem, and there's no detectable difference. "01"
performs the action "drop" requires. There are other ways to implement
"drop" as well, all of them taking more bits, more time, and more
stack space. They're perfectly valid implementations of drop, but this
is the one I told you about. (There are good complexity theory reasons
to prefer "01" to any of the others.)

> aren't there actually five combinators?
> q
> k
> [q]
> [k]
> []

There are a countably infinite number of combinators, and zeroone can
express all of them. I'm not showing you [q] and [k] because they're
fairly ugly. [], on the other hand, is quick to produce from memory.
[] = "00101".

One effective way to prove that a base is complete is to use it to
produce all of the combinators in a known complete set. I'll do
that... But not now.

> but "0011" isn't q, only after reduction.

See above :-).

>>> does such flat base mean that you can cut an valid expression anywhere to produce two valid expressions?
> what about these - more strong - requirements?:

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

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). Using zeroone formally requires
understanding how zeroone works internally first, which is what we're
doing now. It's possible to perform all program transformations by
replacing substrings with different strings (that's called "formal
logic"), but before we can talk about how that works we have to
understand how to discover the meaning of a substring so that we can
prove that the two substrings have the same meaning.

I consider flat formal logic a "later" step, not for now. For now, we
use the semantics of the language to assist in proofs, rather than
doing things formally. Although we ARE using formal logic on the
semantics, it isn't a flat formal logic.

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

> note: reduction = execution,
> i prefer to discuss concatenative programming languages in terms of abstract (expression) rewriting.

That's the only way I've really worked it out at this point, so I agree.

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

>> Even more esoteric, though, is the question of what else can happen to
>> a flat language. I vaguely suspect that a flat language might be able
>> to address control flow. Such a language would not be concatenative in
>> the same sense, although it would hold the same aspect in other ways.
>> I don't know what it would be.

> may be flatness can be preserved if there can't be a construct such as *if-then-else*
> may be a flat language should reduce postfix expressions (containing a choice), to both choices.

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.

> R.

-Wm