Michael Nedzelsky — 2007-05-03 07:17:03

It is very interesting that Joy have a flat sublanguage which is represent the
same set of functions.

I have thought a little about it, below the result of my attempt to better
understand the notion of flatness in concatenative languages.

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.
We can choose some effective enumeration of this set and define as usual the
set P(X) of all partial computable function from X into X.
Every Joy program denote some partial computable function from the set of all
stacks into itself.
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.

Now consider this situation in more general case.

Let L be a (syntactically) concatenative language, X be a denumerable set.
Assume that we have some fixed effective enumeration of X.
Let also P(X) be a set of all partial computable functions from X into X.
We assume that the semantics of L is given by some mapping
s: L -> P(X), i.e. the meaning of a program p \in L is the partial computable
function s(p) \in P(X).

Theorem.
If s(L) = P(X), i.e. every partial computable function on X can be
represented by some program in language L, then there exists three programs
a, b, c \in L such that every partial computable function on X can be
represented by concatenation of programs a, b and c. In other words, for
every program p \in L there exists a program
x1 x2 ... xN, where each xi \in {a, b, c}
which represent the same partial computable function.

The proof is more or less straightforward (we must use the existence of the
universal partial recursive function).

Michael Nedzelsky

William Tanksley, Jr — 2007-05-03 14:25:55

Michael Nedzelsky <MichaelNedzelsky@...> 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

Manfred Von Thun — 2007-05-04 08:49:52

Languages of course have all sorts of syntactic and semantic properties.
One useful kind of question to ask is this: which properties of a given
language
are inherited by all of its sublanguages? or of its superlanguages?

Suppose X, Y, Z are languages, X is a sublanguage of Y, and Y is a
sublanguage
of Z. One might write this as X <= Y <= Z.

Now suppose P is a property of Y. Does X have P? Does Z have P? For some
properties P there will be a clear answer. Some properties are ³inherited
downwards², from Y to X. Some properties are ³inherited upwards², fro Y to
Z. From what I can determine, the downwards inherited properties are always
restrictions (good or bad) of some sort. The upwards inherited properties
are the opposite, and I cannot think of a single word which captures what I
mean. Some trivial syntactic properties:

Downwards: ³the letter ³e² is not allowed in identifiers²
Upwards: ³A line of code may contain up to 255 bytes²

Some semantic ones:

Down: ³integers may not exceed 16 bits²
Up: ³Array subscripts may be up to 32 bits²

Now let X, Y, Z be concatenative languages. Let P be ³is flat².
Given the flatness of Y, can we infer anything about the flatness
of X or of Z? My immediate reaction would be ³of course X will be
flat² and ³we can¹t say anything about the flatness of Z². But
I have learnt to mistrust my immediate reactions. Any views?

- Manfred

[Non-text portions of this message have been removed]

William Tanksley, Jr — 2007-05-04 14:02:27

Manfred Von Thun <m.vonthun@...> wrote:

> Suppose X, Y, Z are languages, X is a sublanguage of Y, and Y is a
> sublanguage of Z. One might write this as X <= Y <= Z.

> Now let X, Y, Z be concatenative languages. Let P be ³is flat².
> Given the flatness of Y, can we infer anything about the flatness
> of X or of Z? My immediate reaction would be ³of course X will be
> flat² and ³we can¹t say anything about the flatness of Z². But
> I have learnt to mistrust my immediate reactions. Any views?

This depends on our definitions. If I read things correctly, a
sublanguage of a flat language _must_ be flat. Of course, a
superlanguage of a flat language need not be flat (and may not be
concatenative).

For example, Joy is a concatenative language, but the entire thing
(considered with all its definition syntax) is not purely
concatenative. (There's nothing wrong with that!) So in that sense,
the concatenative language we refer to as Joy has a non-concatenative
superlanguage that we use every time we program in it.

> - Manfred

-Billy

chris glur — 2007-05-05 17:21:16

I signed on to this mail-list via an unfamiliar gmail account.

I haven't got time to analyse the posts now.
So I'm saving them as ascii-text.
Email is supposed to be text ?

Why has this mail of Fri, May 4, 2007, got these
funny 'raised' numerals "1,2,3" in with the alpha
chars ?
eg:-

> flat² and ³we can¹t say anything about the flatness of Z².

== Chris Glur.

John Cowan — 2007-05-05 21:06:15

chris glur scripsit:

> Email is supposed to be text ?

Email can be text or other things, and text need not be ASCII.

> Why has this mail of Fri, May 4, 2007, got these
> funny 'raised' numerals "1,2,3" in with the alpha
> chars ?