Re: Re: [stack] S-K Construction of Dip?

Brent L Kerby <[email protected]> wrote:
> > Let me first say that recasting combinatorial operations in terms of a
> > flat concatenative language has made it MUCH easier for me to reason
> > about them. I definitely don't understand them completely, but somehow
> > the reasoning seems more in line with my brain's workings. One of my
> > friends felt the same way. Am I just mentally disturbed from years of
> > Forth use and abuse, or is there actually something simpler here?

> Well, although building flat bases (e.g., {o, k}) has been great fun, to me
> it seems like this system is only simpler in a fairly artificial way.

It's simpler in a syntactic sense, not in a semantic sense. That's not
artificial; syntax is a fundemental attribute of a language. However,
the conversion we did to acheive flatness was a tradeoff; our
semantics became in some ways more complex, and undeniably it takes
many more characters to express the same meaning.

So although I don't agree that the simplicity is any kind of illusion,
I certainly also agree that our flat languages (so far) are not
describable as "superior" to the old systems -- except perhaps for
very narrow purposes (but that's always true).

One of the narrow realms of superiority is how we can measure
complexity; a flat expression can be expressed as a bitstring, while a
non-flat expression cannot.

Another narrow realm is that of understanding; it's fundamentally true
that one can always break apart a flat expression in any way that
helps one understand it; there's no "wrong" way to break it apart.
There are many wrong ways to break apart a tree, and few of them are
obvious while the tree is encoded "on paper".

> This is because the system, in a sense, is not flat at all. True, we can
> express programs using flat syntax; but, once these programs start
> executing, they start building programs on the stack that aren't flat.
> So the system has to deal with non-flat programs in the course of
> execution anyway.

I agree. I don't see this as any kind of problem, but I do suspect
that there are better ways to express things in flat notation than the
one we've chosen. The semantics we're using, in particular, were
designed for a different purpose.

> And to do anything non-trivial the programmer needs non-flat programs,

This seems to me to be fundamentally true, simply a tautology,
starting with the axiom "every semantically flat program is trivial."
I don't see any way around that axiom; it makes sense.

> only he isn't allowed to express them directly, but rather is forced to
> construct them in a flat manner, with his hands tied behind his back,
> so to speak.

Well, this isn't fair in general. Every language ties your hands
behind your back to some extent; it's always easier to say some things
than it is to say others. The same complaint could be made about
dataflow languages in general when comparing them to parameter-based
languages, for example -- yet I'd argue that although there truly is a
tradeoff, the tradeoff is fair.

I can't argue this about the languages we've built. There is a
tradeoff, but the tradeoff doesn't seem entirely fair.

> So, we ask, is it possible to modify our approach to give us a more
> "genuine" flat system? Well, to really be flat, we would have to not
> be able to push programs onto the stack, since that's the first level
> of non-flatness. And if we can't do that, that leaves literally nothing
> left that we can do, assuming we've started with just the concatenative
> combinators, where programs are the only type of data. So, a "genuine"
> flat system would have to be quite different. Special support would be
> needed for loops and conditionals, since these could no longer be
> implemented with the (rather meager) remaining set of combinators
> (which could only shuffle the stack, not perform restructuring or
> execution).

I don't know if your definition of "genuinely flat" is correct. Your
requirement for "special support for loops and conditionals" requires
semantic non-flatness, though, by any definition I can see. A
conditional or loop, by definition, has to choose whether or not to
execute a function, which means that the function has to be passed to
the conditional in some way.

One conceivable possibility of doing this would be to switch from our
single-stack definition to a stack and a queue (the queue contains the
continuation), and allow a "combinator" to modify the queue. I don't
know what, if anything, such a system would look like; I haven't
pursued it because I have some other requirements percolating that it
doesn't seem like such a system could fit.

> I don't know. The way I see it, non-flatness is roughly equivalent
> to the ability to do higher-order programming, which is a good
> property of a system.

Semanticly, yes. We've already proven that this is NOT syntactically
true -- and that is an important result.

> But, if you can show me a really nice flat programming language,
> you may be able to change my mind :-)

:-)

I'm very grateful for your help on this; it's been educational and
fun.  I don't know if I'll ever come up with a nice _completely_ flat
programming language; I may possibly come up with some ideas which can
make a nice language flatter.

One thing I'm looking at now is the fact that the word "flat" implies
that a function can be split in half. But our languages only can
express a single function -- this means that they can't take advantage
of their own flatness.

The obvious thing that pops to mind is to add a "dictionary" data
structure, and perhaps a couple of "combinators" that do a lookup in
it or add a definition to it. This makes spaghetti code out of our
programs, which is certainly one way of handling such things :-/.

A less obvious solution (better than my dictionary, but still not what
I want) was suggested by Landau in his research on genetic algorithms
(and related things); I would give you a link, but citeseer isn't
working. In short, he has his programs build a transition network, and
then executes that.

I'll respond more later. This is already plenty long.

> - Brent

-William