Re: [stack] Flat sublanguages of concatenative languages

Michael Nedzelsky <[email protected]> wrote:
> I have thought a little about it, below the result of my attempt to better
> understand the notion of flatness in concatenative languages.

I don't understand what you're saying.

> Summary (Joy language).
> Joy programs denote unary functions from stacks to stacks.
> The stack is a finite object, so the set X of all stacks is a denumerable set.

I had to think about this. Yes, the stack is finite. It can also only
be filled by computable objects, so every item on the stack (no matter
how complicated) is also finite.

> Every partial computable function from P(X) which can be represented by some
> Joy program, can also be represented by some program from a flat subset of
> Joy language.

Is this the theorem you're building in this post? It looks like your
main point is that every concatenative program can be represented by a
flat program (in Joy in specific, and below you prove that it's true
in general for all concatenative languages).

This seems like an intuitively correct result. Non-flat programs are
simply flat programs with the addition of "program literals". A
program literal is a static representation of a program; a flat
program which worked in the same way would have to build the program
dynamically. And dynamic building is at least as capable as static
building.

By the way, were you here during our extensive discussion of flat
concatenative languages a couple of months ago? We wound up
characterizing the maximally flattest concatenative language, named
"01" (because those are the only symbols in it), and providing a few
examples, including implementations and a brute-force construction
searcher.

> Michael Nedzelsky

-Billy