# Flat sublanguages of concatenative languages

## 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 ?

     The result of a failure to convert from the MacRoman character set,

    where those characters are curly quotes, to ISO 8859-1 (Latin-1)

    or its superset Windows-1252, where they are superscript digits.

    --

    John Cowan    http://ccil.org/~cowan    cowan@...

    Economists were put on this planet to make astrologers look good.

            --Leo McGarry