# S-K Construction of Dip?

## Christopher Diggins — 2007-02-21 17:59:05

    From http://tunes.org/~iepos/joy.html

    This sentence never quite sat well with me:

    "however, there is no way to form "dip" or "sip" using just "s" and

    "k" because, roughly speaking, they provide no way to dequote items

    buried in the stack."

    I may have found a counter-example:

    We know that we can construct: c b and i from s

    Then we can go on to define:

    swap = [] c

    cons = [] b

    zap = [] k

    unit = [] [zap] s

    cat = swap [i] cons swap cons

    And finally:

    dip = swap unit cat i

    Can anyone verify if this is this correct for me?

    Thanks,

    Chrstopher

## Manfred Von Thun — 2007-02-22 03:03:33

    I think you are wrong about cons.

    First consideration: The pure (data independent) stack shufflers swap, dup,

    rollup,and also pure combinators like i and dip, cannot be used to define

    data (numbers,strings,lists) dependent operations and combinators

    Second: in my scheme of things b is a combinator which expects two

    quotations. It executes both, first the quotation second from the top, and

    then the other. It satisfies the law:  b = [i] dip i. I assume you mean the

    same

    Third, the combinator  satisfies the law:  i = [] b. The two laws are true,

    and either could be used as a definition. But you could not use both as

    definitions because of the circularity.

    Hence: [...] [] b  = [...] [i] dip i = ... [] i = .... [] i = ....

    In other words what you called cons is just the i combinator. Hope this

    helps.

    Another law: b = concat i. This assumes that  concat is already given.

    But normally concat has to be defined in terms of cons. Alternatively,

    given concat and unitlist, define cons = [unitlist] dip concat.

    New year¹s greetings to all. I have been reading the recent contributions

    but could not contribute for lack of understanding and my sparse time here

    at uni. But I shall report separately on what I have been doing at home.

      - Manfred

     On 22/2/07 4:59 AM, "Christopher Diggins" <cdiggins@...> wrote:

    >

    >

    >

    >

    > From http://tunes.org/~iepos/joy.html

    >

    > This sentence never quite sat well with me:

    >

    > "however, there is no way to form "dip" or "sip" using just "s" and "k"

    > because, roughly speaking, they provide no way to dequote items buried in

    > the stack."

    >

    > I may have found a counter-example:

    >

    > We know that we can construct: c b and i from s

    >

    > Then we can go on to define:

    >

    > swap = [] c cons = [] b zap = [] k unit = [] [zap] s cat = swap [i] cons

    > swap cons

    >

    > And finally:

    >

    > dip = swap unit cat i

    >

    > Can anyone verify if this is this correct for me?

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

## Christopher Diggins — 2007-02-22 03:33:25

    Hmm... most of the constructions I used (except dip and cons) were lifted

    directly from Brent's article.

    It sounds like perhaps the your definition of b differs from Brent's?

    I'll have to look into this in more depth.

    I look forward to hearing more about your work!

    Cheers,

    Christopher

     On 2/21/07, Manfred Von Thun <m.vonthun@...> wrote:

    >

    >   I think you are wrong about cons.

    >

    > First consideration: The pure (data independent) stack shufflers swap,

    > dup,

    > rollup,and also pure combinators like i and dip, cannot be used to define

    > data (numbers,strings,lists) dependent operations and combinators

    >

    > Second: in my scheme of things b is a combinator which expects two

    > quotations. It executes both, first the quotation second from the top, and

    > then the other. It satisfies the law: b = [i] dip i. I assume you mean the

    > same

    >

    > Third, the combinator satisfies the law: i = [] b. The two laws are true,

    > and either could be used as a definition. But you could not use both as

    > definitions because of the circularity.

    >

    > Hence: [...] [] b = [...] [i] dip i = ... [] i = .... [] i = ....

    >

    > In other words what you called cons is just the i combinator. Hope this

    > helps.

    >

    > Another law: b = concat i. This assumes that concat is already given.

    > But normally concat has to be defined in terms of cons. Alternatively,

    > given concat and unitlist, define cons = [unitlist] dip concat.

    >

    > New year¹s greetings to all. I have been reading the recent contributions

    > but could not contribute for lack of understanding and my sparse time here

    > at uni. But I shall report separately on what I have been doing at home.

    >

    > - Manfred

    >

    > On 22/2/07 4:59 AM, "Christopher Diggins" <cdiggins@...<cdiggins%40gmail.com>>

    > wrote:

    >

    > >

    > >

    > >

    > >

    > > From http://tunes.org/~iepos/joy.html

    > >

    > > This sentence never quite sat well with me:

    > >

    > > "however, there is no way to form "dip" or "sip" using just "s" and "k"

    > > because, roughly speaking, they provide no way to dequote items buried

    > in

    > > the stack."

    > >

    > > I may have found a counter-example:

    > >

    > > We know that we can construct: c b and i from s

    > >

    > > Then we can go on to define:

    > >

    > > swap = [] c cons = [] b zap = [] k unit = [] [zap] s cat = swap [i] cons

    > > swap cons

    > >

    > > And finally:

    > >

    > > dip = swap unit cat i

    > >

    > > Can anyone verify if this is this correct for me?

    >

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

    >

    >

    >

    --

    http://www.cdiggins.com

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

## Brent L Kerby — 2007-02-22 06:55:37

    > I may have found a counter-example:

     The only problematic construction is "cat":

     > cat = swap [i] cons swap cons

     "[i] cons" is a no-op acting on one stack item:

       [A] [i] cons

    == [[A] i]

    == [A]

    So that would make

       cat = swap swap cons == cons

    which can't be right.

    In any case, I confess it was a bit rash of me to make that claim (that "dip" cannot be constructed from {s,k}) without offering any substantial justification. So let's see if we can remedy that.

    To do this carefully, we need to make a recursive definition: Say that a concatenative expression "x1 x2 x3 ... xn" (where each term xi is either an atom or a quotation) is "dip-free" relative to a set of indeterminates {A, B, ...}  if the following property holds for each xi:

    a) If xi is an atom, then for any j > i, xj must neither be, nor (in the case xj is a quotation) contain, any of the indeterminates {A, B, ...}.

    b) If xi is a quotation, then its body must be dip-free.

    I.e, an expression is dip-free if no indeterminates (whether quoted or not) occur to the right of any (dequoted) atom, and if the same holds for any (sub-)quotation.

    So, for example, the following expressions are dip-free relative to {A, B}:

    [B] [A]

    [B] A []

    [A] B s [k]

    [[B] A] [A []] B [s] k

    while the following are not:

    A [B]

    [B A]

    k [A] [B]

    [A] [k] [k] s [B]

    Now the key observation is that a dip-free expression remains dip-free when the reduction rules for "s" and "k" are applied

    [C] [B] [A] s => [[C] B] [C] A

        [B] [A] k => A

    (Although the converse is not true: it is possible for a non-dip-free expression to become dip-free after application of "k"'s rule, e.g., "A [B] [] k => A").

    To see this, consider an arbitrary expression containing an "s" or "k" redex (i.e., an expression matching the left side of the reduction rule for "s" or "k"). For the moment, assume the redex occurs at the top level of the expression, i.e., not inside a quotation. So, in the case of "s", we have an expression

    x1 x2 ... xn [q1] [q2] [q3] s z1 z2 ... zn

    (where the xi's and zi's are atoms or quotations, while the qi's are arbitrary concatenative expressions), which we assume is dip-free, and which reduces to

    x1 x2 ... xn [[q1] q2] [q1] q3 z1 z2 ... zn

    which we verify is also dip-free, by carefully checking that each term satisfies the property in the definition: Each xi satisfies it, since (in the case xi is an atom) no new indeterminates have been introduced to the right of xi, and in the case xi is a quotation, its body remains unchanged and hence dip-free. It is satisfied for [[q1] q2] since q1 and q2, and hence "[q1] q2", are dip-free (Take a moment to check this most important step. It would break down if, for example, the quotation had been [q1 [q2]] or [q1 q2], since q1 might include an atom and q2 could contain an indeterminate). It is satisfied for [q1] since q1 is dip-free. Now, before looking at q3, notice that z1, z2, ..., zn do not contain any indeterminates, since they follow the atom "s" in the original expression. So then, for each term in q3, the property is satisfied since, if the term is an atom then it will contain no indeterminates after it since "q3" is dip-free and z1, z2, ..., zn contain no indeterminates, while if the term is a quotation, its body remains unchanged. Likewise, we easily verify that the property holds for z1, z2, ..., zn. A similar argument applies to "k".

    And now, suppose the redex occurs inside a quotation, so that we have an expression

    x1 x2 ... xn [q] z1 z2 ... zn

    assumed to be dip-free, reducing to

    x1 x2 ... xn [q'] z1 z2 ... zn

    Then q must be dip-free, so by the above argument (and applying induction on the depth of nested quotations in which the redex appears), q' must also be dip-free. So the property holds for [q']. And, the property holds for each xi and zi in the new expression, since for the atoms, no new indeterminates have been introduced to their right, while for the quotations, their bodies remains unchanged and hence dip-free.

    That proves that the reduction rules for "s" and "k" preserve the dip-free property. So then, finally, suppose "x" were some concatenative expression over {s,k} constituting a construction "dip", so that we have a reduction

    [B] [A] x ==> A [B]

    This is impossible because the left side is dip-free relative to {A, B} but the right side is not, while the right-hand side is obtained from the left-hand side only applying the reduction rules for {s, k}, which we showed preserve the dip-free property. So we cannot construct "dip" from {s,k}. Therefore, we cannot construct "cat" from {s,k} either, since otherwise this would enable the construction of "dip" which you mentioned

      dip = swap unit cat i

    Alternatively, we could prove directly that "cat" is inconstructible from {s,k} since "[B A]" is not dip-free relative to {A, B}.

    So there we have it! It took some work, but considering the somewhat counterintuitive yet fundamental nature of the result, I think it was worth taking the time to address properly.

    Does that clear things up?

    - Brent

    P.S., Manfred,

    Christopher and I are using "b" to refer to the following combinator:

    [Z] [Y] [X] b == [[Z] Y] X

    which is the concatenative version of the classical "B" combinator (as "s", "c", "w", "k", and "i" are the concatenative versions of the classical S, C, W, K, and I combinators), while your "b" is

    [Y] [X] b == Y X

    I didn't notice you had already defined "b", so sorry about that; I wasn't intending to create a conflict in the notation.

## Christopher Diggins — 2007-02-23 05:42:40

    Thank you very much for patiently explaining the concept and proof of "dip

    free" constructions to me Brent, I greatly appreciate it.

    - Christopher

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

## William Tanksley, Jr — 2007-02-23 17:37:54

    Brent L Kerby <bkerby@...> wrote:

     > Does that clear things up?

     Thank you!

    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?

    Anyhow:

    I find it interesting that completeness is different between

    applicative and concatenative languages (for example, {s,k} is a

    complete applicative basis, but not is not complete when

    concatenative).

    Thinking about this, I'm guessing that this is because application

    forms a syntactic tree, so that it's possible to talk about a

    combinator's "siblings". Concatenation forms a syntactic list (not

    nested), so although elements can have a child, there are no syntactic

    siblings.

    My theory: Therefore, because the syntax doesn't provide that

    operation, the semantics have to provide it. And indeed, every

    complete basis we've produced has combinators that can provide access

    at the same level to either of two elements. In other words, the

    combinators must include some way of making two different elements

    into (equal) siblings.

    The problem with this theory is that the cake combinator in {cake,k}

    is an obvious counterexample:

    [B] [A] cake == [[B] A] [A [B]]

    Clearly, A and B are not siblings here. Of course, constructing concat

    is possible, which obviously makes siblings out of A and B, but is it

    somehow less theoretically pure to have a basis in which the siblings

    are not explicit in the provided basis combinators? My theory suggests

    something like that, but I (intuitively) find it difficult to believe.

    Is there a better theory? Or should I reform my intuitions instead,

    and accept the theory (thereby condemning {cake,k} to contempt and

    contumely)?

     > - Brent

     -William (Billy)

## Brent L Kerby — 2007-02-24 10:45:52

    > 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. 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. And to do anything non-trivial the programmer needs non-flat programs, 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.

    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. 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. It seems to be a fundamental part of the Joy programming paradigm. And for that matter, any programming language that supports loops and conditionals is going to be (conceptually) non-flat in the sense that programs have structure; we think of them as being divided into pieces, subpieces, etc. The syntax may or may not reflect this; but if it doesn't, I would say it's just because it's been artificially obscured.

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

     > I find it interesting that completeness is different between

    > applicative and concatenative languages (for example, {s,k} is a

    > complete applicative basis, but not is not complete when

    > concatenative).

     Right. When we map the applicative combinators to concatenative ones in the obvious way, the image of this map is not a complete (concatenative) set. But it's interesting to note that, in the other direction, things turn out differently. I.e., the image of the natural map (or at least, what I'm calling the natural map) from concatenative combinators to applicative ones _is_, remarkably enough, a complete applicative set. Here's the map I'm talking about: Call the map P, defined recursively as follows:

    P(id)   = \c.c

    P(x)    = \c.xc

    P(f g)  = \c.F(Gc)

    P([f])  = \c.cF

    P(x\ f) = \cx.Fc

    where "f" and "g" are arbitrary concatenative expressions, F is P(f), G is P(g), "x" is any variable, and "c" is some variable distinct from "x" and which does not occur in "f" or "g". Actually, to make P well-defined as a map from concatenative lambda-forms to applicative lambda-forms (not merely over the equivalence classes of such forms), we need to restrict "f" (or, alternatively, "g") to be either a variable or a quotation (but not a concatenation) in order to force a unique parsing of the concatenative expression. This is a technical detail which may or may not be important to us, depending on what we're trying to do with the map.

    It would take some work (which I'll skip, for now) to show that this map respects the reduction rules of the two systems (i.e., that f reduces to g if and only if P(f) reduces to P(g)).

    Anyhow, although the map may at first appear strange and complicated, it really isn't so bad. Essentially, it maps any concatenative program to a function whose first parameter is treated as a continuation (hence the name "c"); an additional parameter is taken (in curried fashion, of course) for each input stack item, top item first; the body of the function is an application of the continuation to each output stack item. Note that although concatenation maps to function composition (a nifty property), we aren't exactly modelling concatenative programs as functions from a stack to a stack (if we were, concatenation would actually need to map to _reverse_ composition). It's possible to construct a map which does precisely that, but it's considerably more complicated and not as natural, in my opinion.

    Anyhow, here are what some standard Joy combinators map to by P (Exercise: verify these):

    P(id)   = \c.c == I

    P(i)    = \cx.xc == T

    P(dup)  = \cx.cxx == W

    P(zap)  = \cx.c == K

    P(cons) = \cxy.c(\d.ydx) == \cxy.c(Cyx)

    P(cat)  = \cxy.c(\d.x(yd)) == \cxy.c(Bxy)

    P(dip)  = \cxy.x(cy) == CB

    where I, B, C, W, and K are the following standard applicative combinators:

    Ix   == x

    Bfgx == f(gx)

    Cfxy == fyx

    Wfx  == fxx

    Kxy  == x

    Now, it is well-known that {I, B, C, W, K} form a complete applicative basis. So far, we have I, W, and K, so we only need to show that we can construct B and C.

    Well, B comes easily: Just apply I to P(cat) (let's define Cat = P(cat)). We get

    Cat I

    == (\cxy.c(Bxy)) I

    == \xy.I(Bxy)

    == \xy.Bxy

    == B

    Now, we can almost get C by applying I to P(cons) (defining Cons = P(cons)):

    Cons I

    == (\cxy.c(Cyx)) I

    == \xy.I(Cyx)

    == \xy.Cyx

    == CC

    This is just a varient of C that takes its first two parameters in reverse order. And there is a construction of C from this combinator (which I found by computer search, although it's quite simple):

    C = CC(CC)(CC)

    The verification:

    CC(CC)(CC)fxy

    == C(CC)(CC)fxy

    == CCf(CC)xy

    == C(CC)fxy

    == CCxfy

    == Cfxy

    So there we have it! The image of P is a complete applicative set! What is perhaps even more surprising is that we didn't need to use the image of "i" or "dip". So the image under P of the _incomplete_ set {id, dup, zap, cons, cat} is a complete applicative set. This set, {id, dup, zap, cons, cat}, is not only incomplete, it's really severely incomplete. These are proper combinators, none of which performs any reordering on its parameters; therefore it is impossible to construct "dip", or even "swap", from them. Moreover, none of them perform dequotation, so it is not even possible to construct "i" from them.

    In any case, note that I'm not claiming P is surjective (i.e., that it maps onto to every applicative combinator), only that it maps onto a complete subset of the applicative combinators. If P (or rather, the version of P which operates on equivalence classes of lambda-forms rather than the forms themselves -- call it P^, "P-hat") is surjective, then it would be an isomorphism between the concatenative and applicative systems of combinators (the well-definedness and injectivity of P^ follow from the fact that P respects reduction). I doubt that such an isomorphism exists but don't know how to prove this. This is really the fundamental question about the relationship between concatenative and applicative combinators: are the two systems isomorphic?

    Well, actually, this is two questions, since there are two main versions of both systems, namely one with the "principle of extensionality" (i.e., one with an "eta-reduction" rule, ensuring "[] dip == id" in the concatenative system, and "BI == I" in the applicative), and one without. The map P above is designed to work either way (although the two systems must either both have, or both not have, eta-reduction). The part to be careful with is

    P(x) = \c.xc

    in the definition of P. If we have eta-reduction, we can replace this with

    P(x) = x

    However, if we don't have eta-reduction, this change will break the essential property of P, i.e., that it respects reduction. For then we would have

    P([x] y\ y)

    =  \c.(\d.dx)((\ey.ye)c))

    => \c.(\d.dx)(\y.yc)

    => \c.(\y.yc)x

    => \c.xc

    P(x) = x

    where

      [x] y\ y => x

    but not

     P([x] y\ y) => P(x)

    since without eta-reduction, \c.xc does not reduce to x. So P, in this case, would not respect reduction. For this argument, I'm using a special case of the Church-Rosser property, that an (applicative) combinator has a unique normal form (i.e., a form with no redexes) if it has one at all. (The general case states that if A, B, and C are lambda-forms with A=>B and A=>C, then there is a form D such that B=>D and C=>D. This essentially says that if you can get a form to reduce to two different forms (by choosing different redexes to reduce), you can perform further reduction to converge again to a common form. This an intuitive idea which is nevertheless highly non-trivial to prove). Although I'm not relying on it here, it would also be nice to know if an analogous "Church-Rosser" property holds for concatenative combinators.

     > [B] [A] cake == [[B] A] [A [B]]

    >

    > Clearly, A and B are not siblings here. Of course, constructing concat

    > is possible, which obviously makes siblings out of A and B, but is it

    > somehow less theoretically pure to have a basis in which the siblings

    > are not explicit in the provided basis combinators?

     Well, the construction of "cat" in terms of {cake,k} relies on transparent quotation; ultimately, it's the same construction as this one from i, dip, and cons:

      cat == [[i] dip i] cons cons

    which works like so:

    [B] [A] [[i] dip i] cons cons

    == [B] [[A] [i] dip i] cons

    == [[B] [A] [i] dip i]

    == [[B] i [A] i]

    == [B A]

    To construct "cat" from {cake,k}, transparent quotation is fundamentally necessary. For, if we assume opaque quotation and consider reducing the expression

      [B] [A] x

    where "x" is a combination over {cake,k}, we see that each reduction step preserves the property that no quotation contains (in the shallow sense) more than one (dequoted) indeterminate, so that we can never reach [B A]. Therefore, "cat" is inconstructible in {cake,k} under opaque quotation. So, {cake,k} is not complete in as strong a sense as, for example, {q,k} (from which all combinators are constructible, even assuming opaque quotation):

      [B] [A] q == [[B]] [A B]

      [B] [A] k == A

    In addition, I'd say "q" is a bit nicer than "cake" since, aside from being simpler, it has the pretty property that it produces a (unit) quotation and a concatenation, which correspond precisely to the two syntactic constructions of the language. This may not be particularly significant in the grand scheme of things, but we have to admit that it's a bit nifty. So I'm perfectly fine with "condemning {cake,k} to contempt and contumely" :-)

     > -William (Billy)

     - Brent

## William Tanksley, Jr — 2007-02-24 22:17:02

    Brent L Kerby <bkerby@...> 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

## William Tanksley, Jr — 2007-03-03 01:33:21

    Brent L Kerby <bkerby@...> wrote:

     > > I find it interesting that completeness is different between

    > > applicative and concatenative languages (for example, {s,k} is a

    > > complete applicative basis, but not is not complete when

    > > concatenative).

    > Right. When we map the applicative combinators to concatenative

    > ones in the obvious way, the image of this map is not a complete

    > (concatenative) set. But it's interesting to note that, in the other

    > direction, things turn out differently. I.e., the image of the natural

    > map (or at least, what I'm calling the natural map) from

    > concatenative combinators to applicative ones _is_, remarkably

    > enough, a complete applicative set.

     This would seem to generally fit my theory -- that applicative syntax

    is more powerful in its greater complexity, because an applicative

    syntax allows a language to directly express the concept of

    "siblings". Whenever a function takes two parameters, those parameters

    are "siblings". The only way to connote the concept of siblings in a

    concatenative language is to build the putative siblings into a list.

     > So there we have it! The image of P is a complete applicative set!

    > What is perhaps even more surprising is that we didn't need to

    > use the image of "i" or "dip".

     I noticed the lack of need for "i" much earlier. At first I thought

    this was a problem with our notation (since the applicative notation

    doesn't even have a concept of dequotation), but I believe now that

    it's not a problem: it's a result of how concatenative notation can't

    denote siblings, so a runtime concept (quotation) must take its place.

     > In any case, note that I'm not claiming P is surjective

    > (i.e., that it maps onto to every applicative combinator),

    > only that it maps onto a complete subset of the applicative

    > combinators.

     I know many of those terms, but I don't know what "complete subset"

    means. Does it mean "a subset of combinators which includes a complete

    base"? If so, that makes sense.

     > If P (or rather, the version of P which operates on equivalence

    > classes of lambda-forms rather than the forms themselves --

    > call it P^, "P-hat") is surjective, then it would be an isomorphism

    > between the concatenative and applicative systems of

    > combinators (the well-definedness and injectivity of P^ follow from

    > the fact that P respects reduction). I doubt that such an isomorphism

    > exists but don't know how to prove this. This is really the fundamental

    > question about the relationship between concatenative and

    > applicative combinators: are the two systems isomorphic?

     This last question definitely nags at me in one way, which I can't

    define. I have a nagging doubt that we're missing something.

    In another way it seems evident (after much exploration) that the

    systems are "equivalent" (in the sense that a program in one can

    always be expressed in the other). But I don't know too much about

    isomorphism, except that it's more complex than that... I've only had

    a general undergrad intro to modern algebra (groups, fields, algebras,

    etc).

     > For this argument, I'm using a special case of the

    > Church-Rosser property, that an (applicative) combinator

    > has a unique normal form (i.e., a form with no redexes) if

    > it has one at all. (The general case states that if A, B, and

    > C are lambda-forms with A=>B and A=>C, then there is a

    > form D such that B=>D and C=>D. This essentially says

    > that if you can get a form to reduce to two different forms

    > (by choosing different redexes to reduce), you can perform

    > further reduction to converge again to a common form. This

    > an intuitive idea which is nevertheless highly non-trivial to

    > prove). Although I'm not relying on it here, it would also be

    > nice to know if an analogous "Church-Rosser" property holds

    > for concatenative combinators.

     Is this something of what you mean by "isomorphism"? That would indeed

    be an awesome property. There are a lot of very simple things that are

    obvious about flat concatenative languages (for example, it makes

    sense that once you understand the meaning of a bitstring without

    context, you therefore know its meaning in any context), but there are

    also a lot of things that seem to take more work to parse out (for

    example, some "optimizations" seem to be very complex to express

    formally).

    (Sorry for the informal terminology. I'm very new at this.)

     > > [B] [A] cake == [[B] A] [A [B]]

    > > Clearly, A and B are not siblings here. Of course, constructing concat

    > > is possible, which obviously makes siblings out of A and B, but is it

    > > somehow less theoretically pure to have a basis in which the siblings

    > > are not explicit in the provided basis combinators?

    > Well, the construction of "cat" in terms of {cake,k} relies on transparent

    > quotation; ultimately, it's the same construction as this one from i, dip,

    > and cons:

     Ah! And this helps me understand what "transparent quotation" means at

    a semantic level. My implementation (01.py) clearly uses transparent

    quotation, since it executes combinators at the earliest opportunity

    (in fact, I think it actually might execute them too soon... I need to

    work on that).

     >Therefore, "cat" is inconstructible in {cake,k} under opaque

    >quotation. So, {cake,k} is not complete in as strong a sense

    >as, for example, {q,k} (from which all combinators are constructible,

    >even assuming opaque quotation):

     YES! I'm starting to "get it".

     > In addition, I'd say "q" is a bit nicer than "cake" since, aside from

    > being simpler, it has the pretty property that it produces a (unit)

    > quotation and a concatenation, which correspond precisely to

    > the two syntactic constructions of the language. This may not

    > be particularly significant in the grand scheme of things, but we

    > have to admit that it's a bit nifty.

     Hmmm... I'm a ways from being knowledgable enough to be able to admit

    that. I'll take your word for it, after I play around with your

    joys.exe program a bit more. I'm not sure how I'm going to get any

    different results; in particular, getting a concat seems to be

    essential to completeness. I suspect that the only way to do anything

    else would be to have a combinator which took more parameters (and

    that just seems like it'd be less efficient).

    Hmm again.

     > So I'm perfectly fine with "condemning {cake,k} to contempt and

    > contumely" :-)

     It's one of the things I'm qualified to do, having studied ancient literature.

    Would you like fries with that?

     > - Brent

     -Billy

## Manfred Von Thun — 2007-03-09 02:43:28

    On 22/2/07 5:55 PM, "Brent L Kerby" <bkerby@...> wrote:

     >

    >

    >

    > [..]

    > - Brent

    >

    > P.S., Manfred,

    >

    > Christopher and I are using "b" to refer to the following combinator:

    >

    > [Z] [Y] [X] b == [[Z] Y] X

    >

    > which is the concatenative version of the classical "B" combinator (as "s",

    > "c", "w", "k", and "i" are the concatenative versions of the classical S, C,

    > W, K, and I combinators), while your "b" is

    >

    > [Y] [X] b == Y X

    >

    > I didn't notice you had already defined "b", so sorry about that; I wasn't

    > intending to create a conflict in the notation.

    >

     Thanks for the clarification, my mistake really.

      - Manfred

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

## Manfred Von Thun — 2007-03-09 03:26:09

    On 24/2/07 9:45 PM, "Brent L Kerby" <bkerby@...> wrote:

    [..]

    > But, if you can show me a really nice flat programming language, you may be

    > able to change my mind :-)

    >

    Not a NICE flat programming language, but interesting in the present

    context:

    machine language or assembler.

    Consider a very small procedural programming language with nesting: A

    statement is either an assignment, or a compound statement which is a

    sequence of statements, or a conditional consisting of a test and a

    statement, or a loop consisting of a test and a statement. (Not even

    procedure calls allowed). So a statement can contain other statements,

    nested arbitrarily deeply. Nothing flat here.

    Compile into machine language or assembler. Assignments translate into a

    sequence of instructions, but that is of no interest here.  Compound

    statements translate into the sequence of instructions produced by the

    sequence of statements, also of no interest. But interestingly, conditionals

    and loops are  translated into a FLAT sequence of instructions containing

    two new instructions that are not in the source language: conditional and

    unconditional JUMP instructions. We also have the notion of a program

    counter, which is simply incremented by most instructions. Only the JUMP

    instructions change the program counter explicitly.

    We have: nested source language, flat target language. Price: extra

    instructions in the target language, plus new concept.

    A possible technique for flattening a concatenative language? Probably

    yes. But the flattened version will not be pretty.

    If the procedural language also has callable procedures, there is another

    level of nesting. It is flattened by introducing a runtime stack and new

    instructions CALL and RETURN for pushing and popping return addresses.

    Powerful? Yes. Pretty? No.

    Maybe this will give people some ideas about flattening concatenative

    languages.

      - Manfred

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

## John Cowan — 2007-03-09 05:42:44

    Manfred Von Thun scripsit:

     > We have: nested source language, flat target language. Price: extra

    > instructions in the target language, plus new concept.

     Actually, we can do without them.  The machine whose sole instruction

    is "subtract 1 from data item D, and if it is now zero, jump to

    instruction J, otherwise continue" is known to be Turing-complete.

    Of course you end up using a lot of them.

    --

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

    We want more school houses and less jails; more books and less arsenals;

    more learning and less vice; more constant work and less crime; more

    leisure and less greed; more justice and less revenge; in fact, more of

    the opportunities to cultivate our better natures.  --Samuel Gompers

## Manfred Von Thun — 2007-03-09 07:31:26

    For a long time I had been dreaming of static type checking for Joy, and

    perhaps even a Joy compiler of some kind.  Only recently did I have a lucky

    thought: why not look at Prolog as an implementation language? (Prolog =

    PROgramming in LOGic  - if you are willing to do violence to anybody¹s

    definition of logic. Apart from the name, a wonderful language with

    backtracking and unification(two sided pattern matching).

    I had had an some experience with Prolog starting 25 years ago, but dropped

    any involvement after the Japanese ³5-th generation language²  programme

    faded. But I had written some very early Joy interpreters in Prolog.

    Found an old SWI-prolog on my inherited home computer, and started

    what turned out to be very fruitful 6 weeks.

    Implementing core Joy is ridiculously simple. There are transformation

    rules for turning one stack into another:

        swap turns [X, Y | S] into [Y, X | S].

        + turns [I, J | S] into [K | S]  :-  K is I + J.

    This readable syntax is what Prolog allows you to do. The four occurrence of

    ³ | S mean ³the rest of the stack². The definition for swap has no

    condition, the one for + has as condition the little bit after the :-

    ³turnstyle². Everything else is in the same style, even the combinators

    I am leaving out the annoying fact that Prolog needs a comma as a separator

    between listi items. I am also leaving out that I use a simple preprocessor

    (written in Prolog, of course), which ³decorates² literals in programs, or

    the stack, or in quotations, with type information. To keep things simple,

    at the moment I only allow two types: numbers and lists.

    For core Joy I only have the basic stack and list shufflers, which all do

    not have a body in their definition, just like swap above. Only one

    arithmetic operator, +, so far, and quite a few combinators including the

    recursive step and map. That is the core interpreter.

    In principle it sounds easy to turn any interpreter into a compiler: in the

    program to be compiled, for each instruction of the source language, emit

    the instructions of the target language which the interpreter would be

    executing if it were running that program.

    In practice this is a dreadful undertaking if the implementation language is

    C, as it is in my version on the web. Essentially one would be writing

    something as complex as the original interpreter, or more complex. Also, it

    is not easy to have to maintain two large programs, especially if the

    language is developing. Better to have only one version, and have a program

    to turn the interpreter into the compiler. Or have a definitional version

    (perhaps in M4), which can produce the interpreter or the compiler.

    Prolog (like Joy) has the wonderful capability of allowing one to look at

    the bodies of definitions (by ³clause²), doing something with these bodies

    and constructing something that can later be executed (by ³call²). Languages

    such as the Algol descendents cannot do this. I do not know whether (the

    interpreted implementations of) the Lisps can (John Cowan: ?).

    So Prolog allows Prolog programs to inspect other Prolog programs like the

    above snippets for swap and +. This means it is extremely simple to write

    all kinds of meta programs.

    One kind are interpreters, which mimic the operation of Joy with some

    variation. For example, I have written a simple tracer which behaves like

    the i combinator but also writes out every step taken during the execution

    of the quoted parameter, even if that quotation contains calls to other

    combinators like the recursive step and map and their parameters. There

    are several variations to this general idea.

    The other kind are compilers which, just like i again, expect a quotation

    (written in Joy) and leave behind a translation into Prolog. One interesting

    feature of this process is that stack and list shufflers just disappear from

    that translation, because all their work is essentially summarised in the

    stack description for the before- and after-stack of the entire quotation.

    Redundant stack and list operations just disappear. Optimisation for nix!

    The output of the compilation is a typically rather short program in Prolog

    which needs to be called to do any work. Compilation and calling satisfies

    the equation:

         compile call  ==  i

    In fact there are already variations on the compile/call theme.

    I am still learning about the various possibilities of meta programs, and I

    intend to explore the area further, especially since it is so easy to do in

    Prolog.

    So far I do not have definitions in Joy. I have left this for later, because

    the intention is of course to store not the Joy form of a program but

    preferably its compiled form in Prolog.

    I¹ll be happy to answer any questions. Also, I intend to report further on

    any progress. But I will have to learn how to move files from my PC at home

    to my Emac here at (what used to be) work. Only then will I be able to send

    examples to this group.

    To the concatenative language smiths: best wishes with you efforts.

    - Manfred

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

## Manfred Von Thun — 2007-03-09 07:38:41

    On 9/3/07 4:42 PM, "John Cowan" <cowan@...> wrote:

     >

    > Manfred Von Thun scripsit:

    >

    >> > We have: nested source language, flat target language. Price: extra

    >> > instructions in the target language, plus new concept.

    >

    > Actually, we can do without them.  The machine whose sole instruction

    > is "subtract 1 from data item D, and if it is now zero, jump to

    > instruction J, otherwise continue" is known to be Turing-complete.

    > Of course you end up using a lot of them.

     So, are we hoping for a single instruction flat concatenative language?

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

## Christopher Diggins — 2007-03-09 07:54:11

    > For a long time I had been dreaming of static type checking for Joy,

     Have you looked at the most recent Cat paper

    (http://www.cat-language.com/paper.html)? It could prove to be a

    useful starting point for designing a type system and type checker for

    Joy (and even a type inference algorithm).

    Cheers,

    Christopher

## William Tanksley, Jr — 2007-03-09 15:16:03

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

     > On 24/2/07 9:45 PM, "Brent L Kerby" <bkerby@...> wrote:

    > > But, if you can show me a really nice flat programming language, you may be

    > > able to change my mind :-)

    > Not a NICE flat programming language, but interesting in the present

    > context: machine language or assembler.

     I've been hammering this in my mind, but I can't get it to work out right.

     > Compile into machine language or assembler. Assignments translate into a

    > sequence of instructions, but that is of no interest here.  Compound

    > statements translate into the sequence of instructions produced by the

    > sequence of statements, also of no interest. But interestingly, conditionals

    > and loops are  translated into a FLAT sequence of instructions containing

    > two new instructions that are not in the source language: conditional and

    > unconditional JUMP instructions. We also have the notion of a program

    > counter, which is simply incremented by most instructions. Only the JUMP

    > instructions change the program counter explicitly.

     The problem is that machine language/assembler uses explicit offsets

    to express jumps and branches, and those destroy referential

    transparency. In effect, you can't split a valid program into two

    arbitrary parts and have the two parts still be valid -- if you cut in

    the middle of a branch, the branch will then lead off into nowhere.

     > A possible technique for flattening a concatenative language? Probably

    > yes. But the flattened version will not be pretty.

     Pretty is not yet my concern. But this isn't flat.

    But I do suspect there's something to this. I just have to figure out

    what I'm missing.

     >   - Manfred

     -Billy

## William Tanksley, Jr — 2007-03-09 15:19:17

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

     > "John Cowan" <cowan@...> wrote:

    > > Actually, we can do without them.  The machine whose sole instruction

    > > is "subtract 1 from data item D, and if it is now zero, jump to

    > > instruction J, otherwise continue" is known to be Turing-complete.

    > > Of course you end up using a lot of them.

    > So, are we hoping for a single instruction flat concatenative language?

     Grin. Unfortunately, that's neither single-instruction nor flat. Its

    instruction stream consists of (data index ,jump offset) pairs, so in

    effect if both are 8-bit you have 16-bit instructions; that's 64,000

    instructions. It's not flat because, again, you can't break apart a

    valid definition and get as a result two valid definitions.

    -Billy

## John Cowan — 2007-03-10 20:31:27

    Manfred Von Thun scripsit:

     > Prolog (like Joy) has the wonderful capability of allowing one to

    > look at the bodies of definitions (by "clause"), doing something with

    > these bodies and constructing something that can later be executed (by

    > "call"). Languages such as the Algol descendents cannot do this. I do

    > not know whether (the interpreted implementations of) the Lisps can

    > (John Cowan: ?).

     Very few Lisps allow you to recover the source form of a definition

    from its executable form (decompiling), but essentially all allow you

    to evaluate source at run time, and some allow you to go from source to

    executable form at run time (compiling).  Even Lisp interpreters

    generally do at least some compiling (expanding macros, for example).

    --

    John Cowan                                cowan@...

    I amar prestar aen, han mathon ne nen,    http://www.ccil.org/~cowan

    han mathon ne chae, a han noston ne 'wilith.  --Galadriel, LOTR:FOTR

## Manfred Von Thun — 2007-03-14 02:54:15

    On 9/3/07 6:54 PM, "Christopher Diggins" <cdiggins@...> wrote:

    I did look at your paper and read it with great interest. I am not really

    competent

    to judge the details, so I cannot help you in any substantial way. I had

    some

    superficial acquaintance with natural deduction rules for typing, but have

    never

    used the them in earnest. But it is a formalism which I should study and

    perhaps

    use to describe typed Joy. Actually the type inference that I use for the

    Joy-to-Prolog

    compiler is so automatic when writing in Prolog that it is barely visible.

    It is simply

    this:

    IF      a turns  S into T1

    AND   b turns T2 into U1

    AND   c turns U2 into V

    THEN    [a b c] turns S into V

    where there have to be the unifications T1=T2 and U1=U2. All that is

    automatic.

    There are two compilers at present, both about 18 lines long. One produces

    lengthy Prolog code which is still more efficient than the Joy source. The

    other produces optimised Prolog code in which all the stack-and

    list-shuffling

    is done at compile time and leaves no trace in the Prolog code. All thanks

    to

    Prolog¹s unification.

    I also had a look at your implementation in C#. It looks much cleaner than

    my Joy implementation. Thanks in part perhaps to C#, but only in part.

    You are also a better programmer than I am. Well done.

      - Manfred

    >

    >

    >> > For a long time I had been dreaming of static type checking for Joy,

    >> >

    > Have you looked at the most recent Cat paper

    > (http://www.cat-language.com/paper.html)? It could prove to be a useful

    > starting point for designing a type system and type checker for Joy (and

    > even a type inference algorithm).

    >

    > Cheers, Christopher

    >

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

## Manfred Von Thun — 2007-03-14 05:11:16

    Thanks for this, I had a vague suspicion that it might be so for

    the Lisps. In fact for any interpreter written in some implementation

    language it seems that the natural way to do it is to translate it into an

    intermediate form from which the source cannot be retrieved. But one could

    translate into a (passive) data structure which allows recovering the source

    form and can also be interpreted.

    On the two occasions when I tried to understand ³The Art of the Meta-Object

    Protocol² (or similar), I failed to get the point. The meta-interpreters and

    meta-compilers that I am writing now all look at the definitions of the

    Joy-in-Prolog interpreter and do something with it. Maybe something will

    click in my mind eventually. I was lucky having (re-)stumbled upon Prolog so

    early.

     On 11/3/07 7:31 AM, "John Cowan" <cowan@...> wrote:

    > Manfred Von Thun scripsit:

    >

    >> > Prolog (like Joy) has the wonderful capability of allowing one to look at

    >> the

    >> > bodies of definitions (by "clause"), doing something with these bodies and

    >> > constructing something that can later be executed (by "call"). Languages

    >> such

    >> > as the Algol descendents cannot do this. I do not know whether (the

    >> > interpreted implementations of) the Lisps can (John Cowan: ?).

    >> >

    > Very few Lisps allow you to recover the source form of a definition from its

    > executable form (decompiling), but essentially all allow you to evaluate

    > source at run time, and some allow you to go from source to executable form

    > at run time (compiling).  Even Lisp interpreters generally do at least some

    > compiling (expanding macros, for example).

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

## Manfred Von Thun — 2007-03-14 06:04:11

    On 10/3/07 2:16 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

     > I've been hammering this in my mind, but I can't get it to work out right.

    >

    >> > Compile into machine language or assembler. Assignments translate into a

    >> > sequence of instructions, but that is of no interest here.  Compound

    >> > statements translate into the sequence of instructions produced by the

    >> > sequence of statements, also of no interest. But interestingly,

    >> conditionals

    >> > and loops are  translated into a FLAT sequence of instructions containing

    >> two

    >> > new instructions that are not in the source language: conditional and

    >> > unconditional JUMP instructions. We also have the notion of a program

    >> counter,

    >> > which is simply incremented by most instructions. Only the JUMP

    >> instructions

    >> > change the program counter explicitly.

    >> >

    > The problem is that machine language/assembler uses explicit offsets to

    > express jumps and branches, and those destroy referential transparency. In

    > effect, you can't split a valid program into two arbitrary parts and have

    > the two parts still be valid -- if you cut in the middle of a branch, the

    > branch will then lead off into nowhere.

    >

     Since the language had assignments, there was no referential transparency to

    start with. But take the purely functional subset of just about any language

    (Lisp Pascal C..), and translate the expression f(g(a),h(b)) into assembler.

    In the definitions of f(,) g() and (h() there will be some code ending with

    a return (which also restores the program counter from the run time stack).

    The corresponding calls all push the program counter. The entire expression

    assembles into something like the following five instructions: push(a),

    call(g), push(b), call(h), call(f). This is just postfix code, where each

    operation does something to various parts (stack, stack pointer, program

    counter,..) of the actual or virtual machine. And the concatenation of the

    five operations computes the composition of the five functions computed by

    the five parts. Concatenative according to my definition:

    If P is a program which computes a function F, and Q is a program which

    computes a function G, then the concatenation P Q of the two programs

    computes the composition F G of the two functions.

    But I suspect that it is not by your definition. (I got a similar impression

    some time much earlier). You mean (or you also mean, or you mean by ³flat²):

    If P is a program consisting of concatenated parts p1 p1 .., and P computes

    a function F, then each of the parts compute functions f1 f2 .., and F is

    their composition.

    This happens to be satisfied by my assembled expression, but it is not part

    of my definition of concatenative. It is true that cutting in the middle of

    a branch leads somewhere else, but where it leads is still dependent on what

    the cut inserts of deletes.

    Of course nobody expects cuts to be permissible inside an instruction. Thus

    call(h) does not have 3 parts: cal  l( h).

    - Manfred

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

## William Tanksley, Jr — 2007-03-14 14:43:51

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

     > Thanks for this, I had a vague suspicion that it might be so for

    > the Lisps.

    > Joy-in-Prolog interpreter and do something with it. Maybe something will

    > click in my mind eventually. I was lucky having (re-)stumbled upon Prolog so

    > early.

     It might help to look at the definition of Prolog in Lisp in the book

    "On Lisp", available free at http://www.paulgraham.com/onlisp.html. (I

    see it seems to be down -- there's a copy at

    http://www.scribd.com/doc/2659/On-Lisp-by-Paul-Graham-a-classic-every-hacker-should-read.)

    Lisp is an impressive language. Pity it's not concatenative (just kidding).

    -Billy

## William Tanksley, Jr — 2007-03-14 14:26:39

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

     > "William Tanksley, Jr" <wtanksleyjr@...> wrote:

    > > The problem is that machine language/assembler uses explicit offsets to

    > > express jumps and branches, and those destroy referential transparency. In

    > > effect, you can't split a valid program into two arbitrary parts and have

    > > the two parts still be valid -- if you cut in the middle of a branch, the

    > > branch will then lead off into nowhere.

    > Since the language had assignments, there was no referential transparency to

    > start with.

     Oops! I meant to type "destroy flatness", not "destroy referential

    transparency". Oops.

    Doggone it, one slip like that and my message makes no sense at all.

     > counter,..) of the actual or virtual machine. And the concatenation of the

    > five operations computes the composition of the five functions computed by

    > the five parts. Concatenative according to my definition:

    > If P is a program which computes a function F, and Q is a program which

    > computes a function G, then the concatenation P Q of the two programs

    > computes the composition F G of the two functions.

     That's concatenative by my definition as well.

     > But I suspect that it is not by your definition. (I got a similar impression

    > some time much earlier). You mean (or you also mean, or you mean by ³flat²):

     The latter -- I try to use the word "concatenative" in the same way

    you do; I try to use the word "flat" to mean:

     > If P is a program consisting of concatenated parts p1 p1 .., and P computes

    > a function F, then each of the parts compute functions f1 f2 .., and F is

    > their composition.

     ...approximately. Actually, I define it using the hand-waving but

    intuitive concept of "splitting" a function into two parts, each of

    which is a valid program for all possible splits. I can make this more

    rigorous by admitting that "all possible splits" includes some splits

    that don't make intuitive sense, such as a split between characters of

    a literal; thus I use the idea of the quantitative ratio "flatness",

    where you compare the number of possible places to perform a split

    with the number of splits that produce two valid programs. Our ik and

    ok languages are perfectly flat; there's no possible split that

    produces invalid programs, even if you get really pedantic and start

    splitting between odd bits.

    However, in general, similar languages will have similar possible

    splits, so when we're not comparing very different languages -- for

    example, the compare-and-branch versus the ik/ok languages -- we can

    ignore nitpicking splits that are equally impossible in both

    languages.

     > This happens to be satisfied by my assembled expression, but it is not part

    > of my definition of concatenative.

     Agreed. That's why I use the combined expression "flat concatenative"

    to describe my language.

     > It is true that cutting in the middle of

    > a branch leads somewhere else, but where it leads is still dependent on what

    > the cut inserts of deletes.

     Well, a cut doesn't insert; it only deletes.

     > Of course nobody expects cuts to be permissible inside an instruction. Thus

    > call(h) does not have 3 parts: cal  l( h).

     Right -- it's intuitively not reasonable to split inside an

    instruction. I don't count that against the language :-). On the other

    hand, if you can't cut inside the instruction, you have to count every

    bit, so one can't claim the compare-and-branch language has only one

    instruction; each instruction uses all /n/ bits of its encoding, so

    such a language has 2^n instructions.

     > - Manfred

     -Billy

## Christopher Diggins — 2007-03-15 16:29:12

    On 3/13/07, Manfred Von Thun <m.vonthun@...> wrote:

     > On 9/3/07 6:54 PM, "Christopher Diggins" <cdiggins@...> wrote:

    >

    > I did look at your paper and read it with great interest. I am not really

    > competent

    > to judge the details, so I cannot help you in any substantial way. I had

    > some

    > superficial acquaintance with natural deduction rules for typing, but have

    > never

    > used the them in earnest. But it is a formalism which I should study and

    > perhaps

    > use to describe typed Joy.

     A great book about the typing formalism which I think you may enjoy

    (to be honest I found it very hard to understand, but I am not

    formally educated) was Types and Programming Languages by Benjamin

    Pierce which sums up the state of the art of type systems.

    I hope to write an extended version of my paper which doesn't presume

    a previous knowledge of type theory.

     > Actually the type inference that I use for the

    > Joy-to-Prolog

    > compiler is so automatic when writing in Prolog that it is barely visible.

    > It is simply

    > this:

    >

    > IF a turns S into T1

    > AND b turns T2 into U1

    > AND c turns U2 into V

    > THEN [a b c] turns S into V

    >

    > where there have to be the unifications T1=T2 and U1=U2. All that is

    > automatic.

     Now I see! That is brilliant! in a previous version of the Cat

    compiler (which did type-inference) I ended up having to write a type

    unifier from scratch. In effect I wrote a mini-prolog. I am surprised

    that your technique of expresing types in a logic language (are there

    others besides Prolog?) isn't used more often. Perhaps it is one of

    those great ideas hiding in plain sight?

     > There are two compilers at present, both about 18 lines long. One produces

    > lengthy Prolog code which is still more efficient than the Joy source. The

    > other produces optimised Prolog code in which all the stack-and

    > list-shuffling

    > is done at compile time and leaves no trace in the Prolog code. All thanks

    > to

    > Prolog¹s unification.

     Very elegant!

     > I also had a look at your implementation in C#. It looks much cleaner than

    > my Joy implementation. Thanks in part perhaps to C#, but only in part.

    > You are also a better programmer than I am. Well done.

     Thank you, you make me blush. I am actually rewriting the parsing

    engine so that it is easier to modify and extend. Afterwards I will

    try to reimplement the type checking/inference engine (but first I

    need to extend the type system with recursive types ... a long story

    but I will say that they are neccessary to accurately express the type

    of certain combinators such as Y and M).

    Perhaps this may encourage others on the list to try their hand at

    implementing their own concatenative languages. Anyway, C# is a very

    pleasant and easy to use language. I find it is much easier to be

    productive using C# than C or C++.

    On other topic, for those interested I am now in the middle of

    implementing a version of Cat with optional named parameters. This

    will become the primary Cat variant (the one I plan on using in an

    upcoming introductory programming book). This version of Cat gets

    translated into the original point-free (i.e. no parameter names) Cat.

    I'm taking a cue from Postscript with its different levels. In the end

    the specification of Cat will likely have a half-dozen variants which

    are expressed in terms of each other.

     > - Manfred

     Cheers,

    Christopher

## Manfred Von Thun — 2007-03-22 05:23:30

    Here is a flat concatenative language which I shall call L.

    After a lot of discussions on this group I now have some intuitive

    understanding of what

    a flat language is. I shall discuss this language L in relation to Joy.

    The problem seems to be how to handle apparent non-flatness due to

    quotations/lists, which can be nested. I need to introduce the notion of a

    waiting room, or ante-room, or briefly, a foyer. This is where incoming

    items form a queue (perhaps similar to Stevan¹s Y queue in his XY language).

    At certain times a queue in a foyer gets sent elsewhere and the foyer is

    destroyed. A foyer is created by the special item ³[³, and destroyed by the

    special item ³]².  I also need a notation for describing foyers: a newly

    created empty foyer is written <>, an after a ³dup² item arrives the foyer

    is written <dup>, after a ³*² item arrives it is written <dup *>. But a

    foyer is not a list, in fact a foyer can contain lists. Foyers cannot be

    nested, but there is a stack of foyers: I shall write this stack with the

    topmost item on the right.  When a foyer is destroyed by ³]², the contained

    queue is sent to the foyer below as a list.

    Here is a contrived example to illustrate several nestings. Let the program

    be

    9999 [ [2 3] [dup *] map ] dip .    # should produce:  [4 9]  9999

    The program starts with a stack containing just one empty foyer. I shall now

    trace the execution of the program by writing each step on a separate line,

    followed by a picture of the stack of foyers, followed by a comment.

             <> # start with stack of just one empty foyer

    9999  <9999>  # put 999 at end of top foyer top foyer

    [        <9999> <>  # start a new foyer

    [        <9999> <>  <> # start a new foyer

    2        <9999> <> <2> # put 2 at end of top foyer

    3        <9999> <> <2 3> # put 3 at end of top foyer

    ]         <9999> <[2 3]>  # pop top foyer, put is content as list into foyer

    below

    [         <9999> <[2 3]> <>  # start a new foyer

    dup     <9999> <[2 3]> <dup> # put dup at end of top foyer

    *         <9999> <[2 3]> <dup *> # put * at end of top foyer

    ]          <9999> <[2 3] [dup *]> # pop top foyer, put content as list into

    foyer below

    map     <9999> <[2 3] [dup *] map]  # put map at end of top foyer

    ]          <9999 [[2 3] [dup *] map]> pop top foyer, put its content as list

    into foyer below

    dip       <9999 [[2 3] [dup *] map] dip> put dip at end of top foyer

    .           pop the top foyer, execute its contents as a Joy program

    The behaviour of any item such as * and dip always depends on what it finds

    on the stack: if it is a foyer, join the queue, otherwise multiply or dip as

    normal for Joy. There is not much one can do with a foyer: create and

    destroy with ³[³ and ³]², or accept items into the queue.

    This is the flat concatenative language L. But one could invent an extension

    L++ which allows other things to be done to foyers  writing them out,

    adding things to a queue by means other than a newly arriving item, or

    perhaps immediate action macros. But I do not want to explore this here.

    Is L flat enough? It is a language from stacks to stacks, using

    concatenative notation. The behaviour of a whole program up to its

    termination as a Joy program is to compute a function, and all parts compute

    functions, and function computed by the whole is the composition of the

    functions computed by the parts. And of course if any parts get snipped out,

    the remainder will compute a function which may well be the empty  (nowhere

    defined)

    composition of the functions computed by the remaining parts.

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

## Manfred Von Thun — 2007-03-22 05:34:17

    My apologies for the previous posting which I wrote ages ago but did not

    post then Now it is completely out of date. Somehow I slipped with the mouse

    just now. Sorry.

      - Manfred

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

## Manfred Von Thun — 2007-03-28 08:26:36

    Cancel the cancellation. The previous cancellation was for a very tentative

    pre-Prolog draft of something about typing Joy. My mailer claims it was

    sent to concatenative, and I did receive it back, but I did not see it when

    I

    looked at the group from Google. I really don¹t know what I have done

    wrong.

    Anyhow, here is the other posting that I did intend to send, which did

    get through, but which might have been mistaken as the cancelled one.

    I have made a few changes, mainly because I have seen how some of

    the concepts can be generalised to something possibly useful, but also

    because

    I noticed some really bad typos.

     On 22/3/07 4:23 PM, "Manfred Von Thun" <m.vonthun@...> wrote:

    >

    Here is a flat concatenative language which I shall call L. After a lot of

    discussions on this group I now have some intuitive understanding of what a

    flat language is. I shall discuss this language L in relation to Joy.

    The problem seems to be how to handle apparent non-flatness due to

    quotations/lists, which can be nested. I need to introduce the notion of a

    waiting room, or ante-room, or briefly, a foyer. This is where incoming

    items form a queue (perhaps similar to Stevan¹s Y queue in his XY language).

    At certain times a queue in a foyer gets sent elsewhere and the foyer is

    destroyed. A foyer is created by the special item ³[³, and destroyed by the

    special item ³]².  I also need a notation for describing foyers: a newly

    created empty foyer is written <>, an after a ³dup² item arrives the foyer

    is written <dup>, after a ³*² item arrives it is written <dup *>. But a

    foyer is not a list, in fact a foyer can contain lists. Foyers cannot be

    nested, but there is a stack of foyers: I shall write this stack with the

    topmost item on the right.  When a foyer is destroyed by ³]², the contained

    queue is sent to the foyer below as a list. Finally, a ³.² will use the

    contents

    of the top foyer as a program to execute by using foyer below as a stack.

    >

    Here is a contrived example to illustrate several nestings. Let the program

    be

    9999 [ [2 3] [dup *] map ] dip .             # should produce:  [4 9]  9999

    The program starts with a stack containing two empty foyers. I shall now

    trace the execution of the program by writing each step on a separate line,

    followed by a picture of the stack of foyers, followed by a comment.

             <> <>       # start with stack of just two empty foyers

    9999  <> <9999>  # put 999 at end of top foyer top foyer

    [        <> <9999> <>  # start a new foyer

    [        <> <9999> <>  <> # start a new foyer

    2        <> <9999> <> <2> # put 2 at end of top foyer

    3        <> <9999> <> <2 3>  # put 3 at end of top foyer

    ]        <>  <9999> <[2 3]>  # pop top foyer, put content into foyer below

    [         <> <9999> <[2 3]> <>  # start a new foyer

    dup     <> <9999> <[2 3]> <dup> # put dup at end of top foyer

    *         <> <9999> <[2 3]> <dup *> # put * at end of top foyer

    ]         <> <9999> <[2 3] [dup *]> # pop top foyer, put content into foyer

    below

    map     <> <9999> <[2 3] [dup *] map>  # put map at end of top foyer

    ]          <> <9999 [[2 3] [dup *] map]> pop top foyer, put content below

    dip       <> <9999 [[2 3] [dup *] map] dip> put dip at end of top foyer

    .           pop the top foyer, execute its contents as a Joy program, using

    the

                foyer below as a normal Joy stack for execution.

    finally:  <[4 9] 9999>  the stack contains  two items, a list and a number

    To recapitulate: everything gets appended to the top foyer, except for

    the three special commands ³[³  ³]² and ³.² ,  as follows:

    ³[³ starts a new foyer

    ³]² pops the top foyer and appends its contents as a list to the foyer

    below.

    ³.² pops top foyer and executes contents on foyer below.

    This is the flat concatenative language L. The foyers are just about

    invisible

    to the user of the language: they are created, filled, emptied and executed

    entirely behind the scenes.

    Is L flat enough? It is a language from stacks to stacks, using

    concatenative notation. The behaviour of a whole program up to its

    termination as a Joy program is to compute a function, and all parts compute

    functions, and function computed by the whole is the composition of the

    functions computed by the parts. And of course if any parts get snipped out,

    the remainder will compute a function which may well be the empty  (nowhere

    defined) composition of the functions computed by the remaining parts.

    Would anyone be tempted to implement a language such as L? Don¹t

    rush off to do it, because it is nothing new. I¹ll let the cat out of the

    bag now:

    Look again at the paragraph at the beginning of the original posting,

    the paragraph that started as ³Here is a flat ...². There are three

    sentences

    in that paragraph. From each sentence take the last word. The three words

    form a sentence. It is true. All that stuff about foyers actually occurs

    inside

    the function ³readterm()² inside my joy.c, which reads a term (a sequence

    of factors) and translates it into internal code.

    One consequence from all this is that Joy is or is not a flat language,

    depending on what one considers the language to be. Presumably the same

    could be said of just about any language which has nesting of one kind

    or another. To express it as a slogan: flatness is in the eye of the

    beholder.

    But one could invent an extension L++ which allows other things to be done

    to foyers. Go back again five paragraphs, to the explanation of what ³[³,

    ³]²

    and ³.² do. Nothing there says that ³[³ and ³]² have to be properly nested.

    Consider the curious looking program

    > [5 *] [ [dup] infra . i .

    Let us execute it in the same way as before, using ³[³ , ³]² and ³.² as

    explained.

                <> <> # two empty foyers

    [           <> <> <> # start new foyer

    5           <> <> <5> # append 5

    *           <> <> <5 *> # append *

    ]            <> <[5 *]> # append as list

    [            <> <[5 *]> <> # start new foyer

    [            <> <[5 *]> <> <> # start another foyer

    dup        <> <[5 *]> <> <dup> # append dup

    ]             <> <[5 *]> <[dup]> append as list

    infra        <> <[5 *]> <[dup] infra> # append infra

    .              <> <[5 *] [dup]]> <infra> # starting to execute

                    <> <[5 5 *]>   # finished executing

    i               <> <[5 5 *] i>  # append i

    .               <[5 5 *]> <i>  # start executing

                    <>  <5 5 *> # this is what i always does

                    <5> <5 *> # pushed first 5

    So the stack end up with a single 5. Not an exciting way to do it,

    but it points to possibilities: construct a partial program, use Joy

    itself to modify it, then finally execute the modified program. I have

    used something similar in some of the Joy papers, where I speak of

    executing ³constructed programs². But what all this shows is that

    the behaviour of foyers that occurs inside function ³readterm()²

    could be extended (even indefinitely) by just allowing ³.² to occur

    after a ³[³ without a closing ³]² first.

    Is it worth extending Joy in this way? It would take only a few very

    tiny changes inside ³readterm()². Before you hasten to make those

    changes, consider obtaining the identical effects from plain ol¹ Joy,

    completely ignoring what goes on inside ³readterm()². Here is

    the same program in plain Joy:

    > [5 *] [dup] infra i .

    >

    start with an empty stack:

                    ->          # empty stack

    [5 *]         ->   [5 *]    # push the quote

    [dup]        ->    [5 *] [dup]   # push second quote

    infra          ->    [5 5 *]  # execute the dup via infra

    i                ->    25   # execute the top quote via i

    Same behaviour, and probably a better notation.

    Conjecture -- 1: Joy can be seen as a flat language, and could be programmed

    that way if one really wanted to. But 2: But everything that can be done  by

    programming in the flat version can equally well be done with the plain

    version.

    I am sorry that this has been so long.

      - Manfred

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

## William Tanksley, Jr — 2007-03-28 17:05:28

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

     > Cancel the cancellation. The previous cancellation was for a very tentative

    > pre-Prolog draft of something about typing Joy. My mailer claims it was

    > sent to concatenative, and I did receive it back, but I did not see it when

    > I looked at the group from Google. I really don¹t know what I have done

    > wrong.

     I'm glad to hear it -- I thought your post was interesting, and I

    couldn't recall having seen it before.

    Thanks for taking the opportunity to clean it up.

     > The problem seems to be how to handle apparent non-flatness due to

    > quotations/lists, which can be nested. I need to introduce the notion of a

    > waiting room, or ante-room, or briefly, a foyer. This is where incoming

    > items form a queue (perhaps similar to Stevan's Y queue in his XY language).

     Well, by some definitions the Y queue makes a language

    non-concatenative (or more accurately, programs that manipulate the Y

    queue might not be concatenative).

    Such a language could indeed be flat and concatenative; but please

    consider that the semantics of the language would be more complex

    because words would have to consider their effect on the foyers, not

    merely on the stack.

    In one of my experiments with my 1-bit flat language I added two extra

    symbols (thus making a 4-bit language), and had the extra symbols

    serve to append an operator onto the list on the stack (I also

    redefined the 0 operator to place only an empty list on the stack).

    This works much like what you've described, except that foyers are the

    same as lists.

    So for example:

    0 == []

    [B] [A] 1 == A

    [A] 2 == [A k]

    [A] 3 == [A q]

    The resulting language wasn't really any shorter than the original

    1-bit language for the derivations I tried, so I set it aside. It is a

    bit simpler to understand at a low level, I think, but that advantage

    doesn't seem to extend to shorter code at a high level, so I'm not as

    happy with it as I hoped.

     > At certain times a queue in a foyer gets sent elsewhere and the foyer is

    > destroyed. A foyer is created by the special item ³[³, and destroyed by the

    > special item ³]².  I also need a notation for describing foyers: a newly

    > created empty foyer is written <>, an after a ³dup² item arrives the foyer

    > is written <dup>, after a ³*² item arrives it is written <dup *>. But a

    > foyer is not a list, in fact a foyer can contain lists. Foyers cannot be

    > nested, but there is a stack of foyers: I shall write this stack with the

    > topmost item on the right.  When a foyer is destroyed by ³]², the contained

    > queue is sent to the foyer below as a list. Finally, a ³.² will use the

    > contents of the top foyer as a program to execute by using foyer below

    > as a stack.

     A nice description. This language also changes the nature of the "."

    operator, so it's now a kind of an 'i' operator as well as a syntactic

    delimiter.

     > To recapitulate: everything gets appended to the top foyer, except for

    > the three special commands ³[³  ³]² and ³.² ,  as follows:

    > ³[³ starts a new foyer

    > ³]² pops the top foyer and appends its contents as a list to the foyer

    > below.

    > ³.² pops top foyer and executes contents on foyer below.

     Interesting... So a way to execute an anonymous function would be to

    begin it with "[" and end it with ".".

     > Is L flat enough? It is a language from stacks to stacks, using

    > concatenative notation.

     I don't know. You haven't specified the runtime semantics of foyers;

    you've only explained what happens inside the parser. Are the foyers

    preserved across definitions?

     > One consequence from all this is that Joy is or is not a flat language,

    > depending on what one considers the language to be. Presumably the same

    > could be said of just about any language which has nesting of one kind

    > or another. To express it as a slogan: flatness is in the eye of the

    > beholder.

     In spite of your interpretation, Joy (as it stands) is not flat; if

    you unbalance the foyers, the parser will barf. A language without

    that error message but with the interpretation otherwise the same

    would be flat -- but such a language would be different from Joy.

    How different? And would the difference be useful?

    I'm afraid that from what I can see the differences wouldn't be

    useful. The problem is that in Joy foyers aren't a first-class

    construct; you can't do anything with them at runtime. The only thing

    you can do is write functions of which parts will inevitably be

    ignored, without receiving a warning. You can't perform a "[" or "]"

    at runtime (for example, inside a loop).

    One thing I'm not clear on, though. Are these foyers available at

    runtime? In practical terms: if I split a Joy definition into two

    parts (cutting in the middle of a quotation), giving each part of the

    definition its own name, and then I define a function which contains

    the two parts one after the other, is the resulting definition

    equivalent to the original? For example:

    DEFINE

        Csucc   ==  [dup [i] dip] dip i.

    DEFINE

        CsuccA == [dup [i];

        CsuccB ==  dip] dip i;

        CsuccC == CsuccA CsuccB.

    Is CsuccC exactly the same as Csucc? Would it still be the same if

    CsuccC were defined in a DEFINE block apart from CsuccA or CsuccB?

    Any way you put this, flatness is not in the eye of the beholder.

    Flatness is a language feature which Joy does not currently possess.

    If you want to add it you clearly can; it looks like it would be

    simple for you to do. The cost for Joy would be a syntax that accepts

    many odd programs, which seems to me to be a high price to pay; to

    avoid this being a useless feature, you'd have to clearly define the

    runtime behavior of foyers, and provide functions to manipulate them.

     > But one could invent an extension L++ which allows other things to be done

    > to foyers.

     This would make the change possibly useful.

     > Conjecture -- 1: Joy can be seen as a flat language, and could be programmed

    > that way if one really wanted to.

     Not as it stands. But such a version could be constructed, yes.

     > But 2: But everything that can be done  by

    > programming in the flat version can equally well be done with the plain

    > version.

     That's just because foyers aren't first-class.

     >   - Manfred

     -Billy

## Manfred Von Thun — 2007-04-02 09:53:03

    On 29/3/07 3:05 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

     > Manfred Von Thun <m.vonthun@... <mailto:m.vonthun%40latrobe.edu.au>

    > > wrote:

    >

     [..]

    I could not comment on the lean flat language experiment

     > Such a language could indeed be flat and concatenative; but please

    > consider that the semantics of the language would be more complex

    > because words would have to consider their effect on the foyers, not

    > merely on the stack.

     to anticipate: the L that I am discussing has a stack of foyers, starting

    with

    a stack of two empty foyers. What a symbol does depends on the stack that

    it finds, and in many cases this means just the content of the top foyer.

     >

    >> > At certain times a queue in a foyer gets sent elsewhere and the foyer is

    >> > destroyed. A foyer is created by the special item ³[³, and destroyed by the

    >> > special item ³]².  I also need a notation for describing foyers: a newly

    >> > created empty foyer is written <>, an after a ³dup² item arrives the foyer

    >> > is written <dup>, after a ³*² item arrives it is written <dup *>. But a

    >> > foyer is not a list, in fact a foyer can contain lists. Foyers cannot be

    >> > nested, but there is a stack of foyers: I shall write this stack with the

    >> > topmost item on the right.  When a foyer is destroyed by ³]², the contained

    >> > queue is sent to the foyer below as a list. Finally, a ³.² will use the

    >> > contents of the top foyer as a program to execute by using foyer below

    >> > as a stack.

    >

    > A nice description. This language also changes the nature of the "."

    > operator, so it's now a kind of an 'i' operator as well as a syntactic

    > delimiter.

     ³.² is now a full blown operator, and indeed it resembles ³i² somewhat. But

    there

    is a difference: ³i² executes a quotation that it expects on top of a stack

    and

    executes it on the remainder of the stack. By contrast, ³.² executes the

    content

    of the current foyer using the foyer below as a stack. Perhaps ³.² is more

    like

    ³infra², but even that isn¹t quite right.

     >> > To recapitulate: everything gets appended to the top foyer, except for

    >> > the three special commands ³[³  ³]² and ³.² ,  as follows:

    >> > ³[³ starts a new foyer

    >> > ³]² pops the top foyer and appends its contents as a list to the foyer

    >> > below.

    >> > ³.² pops top foyer and executes contents on foyer below.

    >

    > Interesting... So a way to execute an anonymous function would be to

    > begin it with "[" and end it with ".".

    >

     Indeed. In fact, assuming that we have otherwise balanced parentheses inside

    ³- - -², the following should be equivalent:

     >> [ - - -  .

    >> [ - - - ] i .

    >>

    >> > Is L flat enough? It is a language from stacks to stacks, using

    >> > concatenative notation.

    >

    > I don't know. You haven't specified the runtime semantics of foyers;

    > you've only explained what happens inside the parser. Are the foyers

    > preserved across definitions?

    >

     There is no parser. There is a lexer/tokeniser. Then there is the runtime.

    At runtime a stack of foyers gets processed. How it is processed depends on

    what it receives from the lexer. The initial stack has two empty foyers. A

    conventional Joy program running L ends up with a foyer that is just like

    the stack that running that program under Joy would end up with.

     >> > One consequence from all this is that Joy is or is not a flat language,

    >> > depending on what one considers the language to be. Presumably the same

    >> > could be said of just about any language which has nesting of one kind

    >> > or another. To express it as a slogan: flatness is in the eye of the

    >> > beholder.

    >

    > In spite of your interpretation, Joy (as it stands) is not flat; if

    > you unbalance the foyers, the parser will barf.

    >

     I don¹t know what you mean by an unbalanced foyer. If you mean something

    like unbalanced parentheses, then you should get the warning in this L

    (whereas it

    would be an errorr in Joy):

    ³Incomplete program? more than one foyer remaining. See top foyer?²

     >  A language without

    > that error message but with the interpretation otherwise the same

    > would be flat -- but such a language would be different from Joy.

    >

    > How different? And would the difference be useful?

    >

    > I'm afraid that from what I can see the differences wouldn't be

    > useful. The problem is that in Joy foyers aren't a first-class

    > construct; you can't do anything with them at runtime.

     Normally ³first class² means ³can be passed as a parameter or can be

    returned as a value. Indeed, but how does this count against being

    concatenative

    or being flat? But you can do four things with foyers.

    1. fill then up with things like 42, +, map and so on.

    2. start a new one with ³[³.

    3. execute them on the foyer below, by ³.²

    4. append their contents as a list to the foyer below, by ³]².

     > The only thing

    > you can do is write functions of which parts will inevitably be

    > ignored, without receiving a warning. You can't perform a "[" or "]"

    > at runtime (for example, inside a loop).

    >

     There is no separate runtime as opposed to parsetime. ³[³ and ³]² never get

    inside a foyer. The fact that lists inside a foyer are written <111 [22 33]

    444> are written using ³[³ and ³]² does no mean they are in the foyer. This

    foyer just contains three elements: two numbers and between them a list of

    two numbers.

     >

    > One thing I'm not clear on, though. Are these foyers available at

    > runtime?

     Yes, in the L-definition of runtime. This is not your definition, I know.

    But

    L has a right to make its own definition. In L one would define your notion

    of runtime as: executing the content of the topmost foyer using the

    ONLY remaining foyer below as its stack. But the executions of topmost

    foyers would be exactly the same if there are further foyers below.

     >

    > In practical terms: if I split a Joy definition into two

    > parts (cutting in the middle of a quotation), giving each part of the

    > definition its own name, and then I define a function which contains

    > the two parts one after the other, is the resulting definition

    > equivalent to the original? For example:

    >

     Since when does being able to give names to the parts have anything to

    do with cuttability or flatness?

     >

    > DEFINE

    >  Csucc   ==  [dup [i] dip] dip i.

    >

    > DEFINE

    >  CsuccA == [dup [i];

    >  CsuccB ==  dip] dip i;

    >  CsuccC == CsuccA CsuccB.

    >

    > Is CsuccC exactly the same as Csucc? Would it still be the same if

    > CsuccC were defined in a DEFINE block apart from CsuccA or CsuccB?

    >

     I have not said anything about definitions in L, and your example does

    show that if L is to be of interest at all, then L needs to use a different

    style

    of definitions. Thank you.

     >

     For a while I thought that your example (just the cutting into three bits)

    even shows that

    concatenativity is ruined. But no, the three bits each compute functions

    from stacks of foyers to stacks of foyers, and the concatenation of the bits

    computes the composition of what the bits compute. So no worry here.

     >

    > Any way you put this, flatness is not in the eye of the beholder.

    > Flatness is a language feature which Joy does not currently possess.

    > If you want to add it you clearly can; it looks like it would be

    > simple for you to do. The cost for Joy would be a syntax that accepts

    > many odd programs, which seems to me to be a high price to pay; to

    > avoid this being a useless feature, you'd have to clearly define the

    > runtime behavior of foyers, and provide functions to manipulate them.

    >

     But the odd programs would be just those that leave more than one foyer

    below. That is no more odd than an ordinary Joy program which leaves

    one or more quotationson the stack, such as [11 22 +] or [cons 42 +],

    whether the are executable or not.

     >

     Repeat: the runtime is all there is. There are the four ways of manipulating

    foyers. But why does one need new functions?

     >

    >> > But one could invent an extension L++ which allows other things to be done

    >> > to foyers.

    >

    > This would make the change possibly useful.

    >

     The way to manipulate the contents of foyers should be obvious: apart from

    filling foyers (from the ³end², if you like), an incoming ³.² calls the

    content of the

    top foyer to be executed using the foyer below as a stack. That is always

    the same.

    The whole of Joy machinery is available to manipulate the contents of

    foyers.

     >

    >> > Conjecture -- 1: Joy can be seen as a flat language, and could be

    >> programmed

    >> > that way if one really wanted to.

    >

    > Not as it stands. But such a version could be constructed, yes.

    >

    >> > But 2: But everything that can be done  by

    >> > programming in the flat version can equally well be done with the plain

    >> > version.

    >

    > That's just because foyers aren't first-class.

    >

     See earlier comments

     >> >   - Manfred

    >

    > -Billy

     Thanks for the discussion, Billy. I hope I have cleared up a few things.

      - Manfred

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

## William Tanksley, Jr — 2007-04-02 23:12:01

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

    Thank you for the prompt and clear answers. To cut to the chase: I

    agree that the language "L" is both flat and concatenative, and that L

    is not enormously different from Joy.

    However...

    My first reaction was that although I confess that I have researched

    flatness for its own sake, I suspect that there are higher principles

    in language design than perfect flatness, and I believe that L's

    design compromises some of them. I don't think that's a bad thing --

    but I did believe that unless I point out the problems, the obvious

    conclusion would be that flatness was the cause of those problems,

    rather than the design choices that allowed flatness.

    I'm not certain that I was right... thanks to your explanations, I

    might see the benefit to L.

     > On 29/3/07 3:05 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

    > >> > Is L flat enough? It is a language from stacks to stacks, using

    > >> > concatenative notation.

    > > I don't know. You haven't specified the runtime semantics of foyers;

    > > you've only explained what happens inside the parser. Are the foyers

    > > preserved across definitions?

    > There is no parser. There is a lexer/tokeniser. Then there is the runtime.

    > At runtime a stack of foyers gets processed. How it is processed depends on

    > what it receives from the lexer. The initial stack has two empty foyers. A

    > conventional Joy program running L ends up with a foyer that is just like

    > the stack that running that program under Joy would end up with.

     An excellent answer. You later detail that the foyers exist at

    runtime, which means that your language provides the basic support

    needed to be flat.

    Good job; I now clearly see that L is flat.

     > >> > One consequence from all this is that Joy is or is not a flat language,

    > >> > depending on what one considers the language to be. Presumably the same

    > >> > could be said of just about any language which has nesting of one kind

    > >> > or another. To express it as a slogan: flatness is in the eye of the

    > >> > beholder.

    > > In spite of your interpretation, Joy (as it stands) is not flat; if

    > > you unbalance the foyers, the parser will barf.

    > I don¹t know what you mean by an unbalanced foyer. If you mean something

    > like unbalanced parentheses, then you should get the warning in this L

    > (whereas it

    > would be an errorr in Joy):

    > ³Incomplete program? more than one foyer remaining. See top foyer?²

     Again, I was talking about Joy. Joy is not flat; it doesn't depend on

    your perspective. L _is_ flat; again, it doesn't depend on your

    perspective.

    Why didn't I like L -- in spite of its very manifest cleverness?

    I think my shortest answer would be "Occam's razor". To quote:

    "entities should not be multiplied beyond necessity." L introduces a

    new entity, the "foyer", which serves no purpose but to allow the

    designer to claim flatness. If the foyer also allowed some terseness

    or expressiveness, or otherwise demonstrated a result in language

    design, I would be much more impressed.

    I'm going to try to think of one.

     > >  A language without

    > > that error message but with the interpretation otherwise the same

    > > would be flat -- but such a language would be different from Joy.

    > > How different? And would the difference be useful?

    > > I'm afraid that from what I can see the differences wouldn't be

    > > useful. The problem is that in Joy foyers aren't a first-class

    > > construct; you can't do anything with them at runtime.

    > Normally ³first class² means ³can be passed as a parameter or can be

    > returned as a value. Indeed, but how does this count against being

    > concatenative or being flat?

     I have to admit that foyers can be returned as values -- your answers

    have made that clear. The ability to pass them as parameters would be

    a nice addition, and I suspect would not be a difficult thing to add

    -- I imagine that just as Forth has words to preserve a value on the

    return stack, JoyL would have words to 'dip' into the foyers.

    My imagination suggests that your new language would have more

    expressive power than Joy alone. In fact, my imagination suggests that

    such a language might be as purely functional, concatenative, and

    perhaps even as fun to program in as Joy, while being flat as well.

    Exciting, if true. Is it?

    Clearly, "[" creates a new foyer on the foyer stack, and "]" converts

    the top foyer into a quotation nested into the next foyer. I see no

    need for any special operators to juggle entries on the foyer stack

    (am I wrong?). However, it would make sense to provide a function to

    append the item on top of the data stack into the current foyer, and a

    function to pop the top foyer onto the data stack and convert it to a

    quotation. Without those, foyers can't be manipulated at runtime.

    There's one thing that's nagging at me...

    GOT IT! As an old Forth hand, I remember the need for IMMEDIATE words:

    functions that execute when the compiler encounters them, rather than

    being compiled for later execution. The problem is that "[", "]", and

    "." are immediate words... They don't act like all the other functions

    in L.

    All the other functions in L get appended onto the topmost foyer on

    the f-stack as soon as the compiler encounters them. Not those! They

    do something else.

    Does this make your language non-flat? Definitely NOT. Those words are

    special, but they can be made to fit by describing the functions of

    all other words as "this function appends the operation denoted by its

    name onto the topmost foyer". (This is similar to the way we describe

    concatenative languages as denoting function composition -- in

    practical we don't think of it that way, we merely get the benefits.)

    I'm not going to suggest (at this point) that you do what Forth did,

    and make it possible to mark ANY word "immediate", so that it's

    possible to make your own IMMEDIATE words to extend the compiler. I

    actually think that wasn't a good thing, and even Chuck Moore doesn't

    think it should be used often.

    But... We should add non-special (runtime) words that perform the

    functions of "[", "]", and perhaps "." (the latter can be implemented

    in terms of previously explained words).

    So we have:

     + "[": syntax, new foyer.

     + "]": syntax, embed foyer.

     + ".": syntax, execute top foyer.

     + "foyer": runtime, new foyer.

     + "embed": runtime, append TOS on top foyer.

     + "quotation": runtime, convert top foyer to quotation on TOS.

    I'm not sure that "." is needed. Why was it in there again? Would "."

    be the same thing as "quotation i", with no need for special syntax

    treatment?

     > > One thing I'm not clear on, though. Are these foyers available at

    > > runtime?

    > Yes, in the L-definition of runtime. This is not your definition, I know.

     I think it is my definition as well -- what am I missing?

     > But

    > L has a right to make its own definition. In L one would define your notion

    > of runtime as: executing the content of the topmost foyer using the

    > ONLY remaining foyer below as its stack. But the executions of topmost

    > foyers would be exactly the same if there are further foyers below.

     Nope, that's runtime. We're good.

     > > In practical terms: if I split a Joy definition into two

    > > parts (cutting in the middle of a quotation), giving each part of the

    > > definition its own name, and then I define a function which contains

    > > the two parts one after the other, is the resulting definition

    > > equivalent to the original? For example:

    > Since when does being able to give names to the parts have anything to

    > do with cuttability or flatness?

     It doesn't -- names help clarify things. I assume syntax to assign

    names for the sake of clarity. If asked the same question about my 01

    language, I would assume the same thing.

     > >DEFINE

    > >  Csucc   ==  [dup [i] dip] dip i.

    > >DEFINE

    > >  CsuccA == [dup [i];

    > >  CsuccB ==  dip] dip i;

    > >  CsuccC == CsuccA CsuccB.

    > > Is CsuccC exactly the same as Csucc? Would it still be the same if

    > > CsuccC were defined in a DEFINE block apart from CsuccA or CsuccB?

    > I have not said anything about definitions in L, and your example does

    > show that if L is to be of interest at all, then L needs to use a different

    > style of definitions. Thank you.

     Interesting. How would they differ?

     > For a while I thought that your example (just the cutting into three bits)

    > even shows that

    > concatenativity is ruined. But no, the three bits each compute functions

    > from stacks of foyers to stacks of foyers, and the concatenation of the bits

    > computes the composition of what the bits compute. So no worry here.

     Great -- that (together with the other things you've explained) gives

    sufficient evidence to me that the result is both concatenative and

    flat.

     > Thanks for the discussion, Billy. I hope I have cleared up a few things.

     You certainly did! I hope I make more sense now that we're on the same page.

     >   - Manfred

     -Billy

## Manfred Von Thun — 2007-04-10 04:04:54

    On 3/4/07 9:12 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

    [..]

    Sorry Billy, I cannot respond right now. But I will clarify a few things

    when I have the time

      - Manfred

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

## Manfred Von Thun — 2007-04-18 06:18:59

    On 3/4/07 9:12 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

     >

    > Manfred Von Thun <m.vonthun@... <mailto:m.vonthun%40latrobe.edu.au>

    > > wrote:

    >

    > Thank you for the prompt and clear answers. To cut to the chase: I

    > agree that the language "L" is both flat and concatenative, and that L

    > is not enormously different from Joy.

     Indeed, not enormously. But see below.

    [..]

     > However...

    >

    > My first reaction was that although I confess that I have researched

    > flatness for its own sake, I suspect that there are higher principles

    > in language design than perfect flatness, and I believe that L's

    > design compromises some of them. I don't think that's a bad thing --

    > but I did believe that unless I point out the problems, the obvious

    >> > I don¹t know what you mean by an unbalanced foyer. If you mean something

    >> > like unbalanced parentheses, then you should get the warning in this L

    >> > (whereas it

    >> > would be an errorr in Joy):

    >> > ³Incomplete program? more than one foyer remaining. See top foyer?²

    >

    > Again, I was talking about Joy. Joy is not flat; it doesn't depend on

    > your perspective. L _is_ flat; again, it doesn't depend on your

    > perspective.

     See your own comment above. You agree that L is concatenative (and flat),

    and that Joy is concatenative (but not flat). I thought it was clear that

    they

    accept the same programs  more or less, perhaps. If so, then flatness is

    in the eye of the beholder.

    It seems we need a definition of identity between two programming languages.

    (And keep in mind that any single language might have several very different

    implementations.) Here is one attempt at a definition:

    L1 is a sublanguage of L2 if and only if

    For all programs P, if P is a correct program in L1, then P is a correct

    program in L2,

    and for all inputs I, program P with input I produces the same output in L1

    and in L2.

    L1 is identical with L2 if and only if they are sublanguages of each other.

    I claim that Joy and L are identical in this sense  apart from the trivial

    sense

    that an incomplete Joy program (as Joy is currently implemented) produces

    an error message (³end of input file, incomplete program²), whereas L

    would not consider it to be incomplete. But surely this is a trivial

    difference,

    and is easily removed,

    [..]

     >

    >>> > > One thing I'm not clear on, though. Are these foyers available at

    >>> > > runtime?

    >

    >> > Yes, in the L-definition of runtime. This is not your definition, I know.

    >

    > I think it is my definition as well -- what am I missing

    >

     In most languages there is scantime, parsetime and runtime. In L there

    are only scantime and runtime.

     >

    >

    >

    >> > But

    >> > L has a right to make its own definition. In L one would define your notion

    >> > of runtime as: executing the content of the topmost foyer using the

    >> > ONLY remaining foyer below as its stack. But the executions of topmost

    >> > foyers would be exactly the same if there are further foyers below.

    >

    > Nope, that's runtime. We're good.

    >

    >>> > > In practical terms: if I split a Joy definition into two

    >>> > > parts (cutting in the middle of a quotation), giving each part of the

    >>> > > definition its own name, and then I define a function which contains

    >>> > > the two parts one after the other, is the resulting definition

    >>> > > equivalent to the original? For example:

    >

    >> > Since when does being able to give names to the parts have anything to

    >> > do with cuttability or flatness?

    >

    > It doesn't -- names help clarify things. I assume syntax to assign

    > names for the sake of clarity. If asked the same question about my 01

    > language, I would assume the same thing.

    >

    >>> > >DEFINE

    >>> > >  Csucc   ==  [dup [i] dip] dip i.

    >>> > >DEFINE

    >>> > >  CsuccA == [dup [i];

    >>> > >  CsuccB ==  dip] dip i;

    >>> > >  CsuccC == CsuccA CsuccB.

    >

    >>> > > Is CsuccC exactly the same as Csucc? Would it still be the same if

    >>> > > CsuccC were defined in a DEFINE block apart from CsuccA or CsuccB?

    >

    >> > I have not said anything about definitions in L, and your example does

    >> > show that if L is to be of interest at all, then L needs to use a different

    >> > style of definitions. Thank you.

    >

    > Interesting. How would they differ?

     Note the ³.² at the end of these definitions. If ³.² is to be allowed inside

    a definition,

    then a different notation might be needed, something like:

    DEFINE a == ...; b == ...; c == ... END_DEF

     >

     [..]

     >

    >> > Thanks for the discussion, Billy. I hope I have cleared up a few things.

    >

    > You certainly did! I hope I make more sense now that we're on the same page.

    >

    >> >   - Manfred

    >

    > -Billy

    >

      - Manfred

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

## William Tanksley, Jr — 2007-04-18 14:40:17

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

     > "William Tanksley, Jr" <wtanksleyjr@...> wrote:

    > > Again, I was talking about Joy. Joy is not flat; it doesn't depend on

    > > your perspective. L _is_ flat; again, it doesn't depend on your

    > > perspective.

    > See your own comment above. You agree that L is concatenative (and flat),

    > and that Joy is concatenative (but not flat). I thought it was clear that

    > they accept the same programs  more or less, perhaps. If so, then

    > flatness is in the eye of the beholder.

     But they do not accept the same programs. L accepts many more programs

    than Joy does. L may even be more expressive than Joy (although I

    haven't examined it to see whether it actually is).

     > It seems we need a definition of identity between two programming languages.

    > (And keep in mind that any single language might have several very different

    > implementations.) Here is one attempt at a definition:

     In computation theory, one formal definition of a language is the set

    of all texts that are legal in the language.

     > L1 is a sublanguage of L2 if and only if

    > For all programs P, if P is a correct program in L1, then P is a correct

    > program in L2,

    > and for all inputs I, program P with input I produces the same output in L1

    > and in L2.

    > L1 is identical with L2 if and only if they are sublanguages of each other.

    > I claim that Joy and L are identical in this sense  apart from the trivial

    > sense that an incomplete Joy program (as Joy is currently

    > implemented) produces an error message (³end of input file, incomplete

    > program²), whereas L would not consider it to be incomplete. But surely

    > this is a trivial difference, and is easily removed,

     A text that produces a syntax error is by definition not a "correct

    program" (your words). Thus there exist correct programs in L which

    are not correct programs in Joy. This is your definition of

    sublanguage -- Joy is a sublanguage of L, and not the other way

    around.

     > >> > Yes, in the L-definition of runtime. This is not your definition, I know.

    > > I think it is my definition as well -- what am I missing?

    > In most languages there is scantime, parsetime and runtime. In L there

    > are only scantime and runtime.

     That's the case for Forth as well. I'm pretty sure that I'm okay with

    that; anyone must agree that runtime is runtime.

     > >> > I have not said anything about definitions in L, and your example does

    > >> > show that if L is to be of interest at all, then L needs to use a different

    > >> > style of definitions. Thank you.

    > > Interesting. How would they differ?

    > Note the ³.² at the end of these definitions. If ³.² is to be allowed inside

    > a definition,

    > then a different notation might be needed, something like:

    > DEFINE a == ...; b == ...; c == ... END_DEF

     Actually, I questioned before whether "." was truly needed as part of

    the flat language. It seems to me that everything "." is doing is

    semantic, not syntactic; therefore it can be a function rather than

    being syntax. I believe I suggested using the phrase "quotation i"

    instead of "." (using my definition of "quotation", feel free to use

    your own name for the function that takes the top lobby, converts it

    to a quotation, and places it on the stack).

     >  - Manfred

     -Billy

## Manfred Von Thun — 2007-04-26 07:58:36

    On 19/4/07 12:40 AM, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

     >

    > Manfred Von Thun <m.vonthun@... <mailto:m.vonthun%40latrobe.edu.au>

    > > wrote:

    >

    >> > "William Tanksley, Jr" <wtanksleyjr@...

    >> <mailto:wtanksleyjr%40gmail.com> > wrote:

    >>> > > Again, I was talking about Joy. Joy is not flat; it doesn't depend on

    >>> > > your perspective. L _is_ flat; again, it doesn't depend on your

    >>> > > perspective.

    >

    >> > See your own comment above. You agree that L is concatenative (and flat),

    >> > and that Joy is concatenative (but not flat). I thought it was clear that

    >> > they accept the same programs  more or less, perhaps. If so, then

    >> > flatness is in the eye of the beholder.

    >

    > But they do not accept the same programs. L accepts many more programs

    > than Joy does. L may even be more expressive than Joy (although I

    > haven't examined it to see whether it actually is).

    >

     You are exactly right about L++ (in the terminology of my original post),

    but not about L.

    Reminder: L and L++ both use a stack of foyers, but they differ in whether

    they allow

    unmatched ³[³ before ³.² In a nutshell, again for both L and L++ :

    ³[³ starts a new foyer,

    ³]² appends the current foyer as a list to the previous foyer, and

    ³.² executes the current foyer on the foyer below.

     >

     But there is a difference:

    L does not allow the sequence ³[³ ... ³.² because of unmatched brackets.

    L++ does allow this sequence, and as you rightly observe, it resembles Forth

    immediates.

    I still maintain that L = Joy, and agree that L++ is a superset. But I am

    not at all sure

    whether the extras that L++ can do cannot also be achieved (in a different

    way) by

    using existing list- (and hence program-) manipulators. I just don¹t know.

    I meant this posting to be more detailed, sorry Billy. But I got sidetracked

    by downloading

    the Factor tarfile and inspecting quite a lot of the files. A most

    impressive piece of work,

    congratulations to the author(s).

      - Manfred

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

## William Tanksley, Jr — 2007-04-26 16:59:22

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

     > "William Tanksley, Jr" <wtanksleyjr@...> wrote:

    > > But they do not accept the same programs. L accepts many more programs

    > > than Joy does. L may even be more expressive than Joy (although I

    > > haven't examined it to see whether it actually is).

    > You are exactly right about L++ (in the terminology of my original post),

    > but not about L.

    > Reminder: L and L++ both use a stack of foyers, but they differ in whether

    > they allow

    > unmatched ³[³ before ³.² In a nutshell, again for both L and L++ :

     I'm extremely confused. I thought you just said that L accepted

    unbalanced brackets -- you said, "an incomplete Joy program (as Joy is

    currently implemented) produces an error message..., whereas L would

    not consider it to be incomplete."

    How does this NOT mean that L accepts a superset of what Joy accepts?

    The only thing I can think of is that you consider producing "an error

    message" to be a way for a language to signify that it accepts the

    text as a valid program. My texts list that as the ONLY way a parser

    can reject a text as an invalid program.

     > ³[³ starts a new foyer,

    > ³]² appends the current foyer as a list to the previous foyer, and

    > ³.² executes the current foyer on the foyer below.

    > But there is a difference:

    > L does not allow the sequence ³[³ ... ³.² because of unmatched brackets.

    > L++ does allow this sequence, and as you rightly observe, it resembles Forth

    > immediates.

     I'm definitely completely lost on what L is. Your previous posts

    seemed to indicate that it did something different from Joy, which I

    interpreted as (in my own words) "it doesn't produce an error for

    unmatched brackets." Now you're telling me that it doesn't allow

    unmatched brackets.

     > I still maintain that L = Joy, and agree that L++ is a superset.

     They're your languages, so you have the right to define them as you

    wish. I'm still phenomenally confused, however, because I you

    previously defined L using language that (in your own words) implied

    "nothing there says that '[' and ']' have to be properly nested."

    Indeed, I assumed that was the case when reading your original post --

    after all, if you were to imply that [ and ] nested the text they

    contained, you wouldn't have been defining a flat language.

    But now, looking very carefully at what you say, here's my opinion:

     - Joy isn't flat; it will reject programs that were cut at arbitrary places.

     - If L is exactly Joy, L isn't flat either.

     - If L is Joy minus the rejection of unbalanced nesting, L is flat.

     - I don't know anything about L++. I thought you were only using it

    to mean "a language like L but with additional unspecified features."

    There's nothing wrong with *not* being flat. I would strongly

    recommend against making a language flat for any reason other than

    pure research.

     > But I am not at all sure

    > whether the extras that L++ can do cannot also be achieved (in a different

    > way) by using existing list- (and hence program-) manipulators. I just

    > don't know.

     Assuming that L++ is your name for a language that accepts any section

    of a valid Joy program as a valid L++ program... Yes, since it's

    Turing complete, Joy can do all the same things. But what Joy can't do

    is be refactored 100% validly by cut and paste. L++ can.

    Does that matter? A bit. A flatter language is easier to mentally

    parse than a less flat one, all other things being equal. BUT... Not

    all things are equal. Kerby's and my 01 languages are abominations

    from the pit of mathematical hell (hey, maybe I *like* it warm!); L

    and L++ add "foyers", a concept which is not needed to understand Joy

    (so Joy is simpler).

    So far nobody's been able to produce a flat language that's _actually_

    easier to work with in general than a non-flat language. Anyone who

    suspected that it's impossible would be in good company.

    I don't think it's reasonable to ask for a perfectly flat language;

    but I do think it might be possible to design a language that doesn't

    need quite as much nesting. A _flatter_ language. Such a language

    might (or might not) be like Joy, but using foyers _instead_ of

    quotations (to reduce the number of simultaneous concepts that people

    have to work with). I don't know. I'm taking a slightly different

    approach at the moment, with no results yet to report on.

     > I meant this posting to be more detailed, sorry Billy. But I got sidetracked

    > by downloading

    > the Factor tarfile and inspecting quite a lot of the files. A most

    > impressive piece of work, congratulations to the author(s).

     Indeed it is!

     >   - Manfred

     -Billy

## Manfred Von Thun — 2007-04-30 09:06:05

    From time to time I have considered various alternative notations for

    concatenative languages. In particular the syntax for combinators would seem

    to allow some variants the might be explored. In this note I only present

    some alternatives, I do not argue for or against one or the other.

    When writing Joy programs with combinators, in about 95% of cases I seem to

    push the quotation parameters just before the combinator. Using the ifte

    combinator, a piece of program would look like this:

    [if-part]  [then-part]  [else-part]  ifte

    The ifte combinator  immediately removes the three quotations, and all other

    combinators do the same. Could one have a different notation? Perhaps to

    avoid the needless pushes, perhaps for better intelligibility, perhaps for

    other reasons. Starting at one extreme of the possibilities we have several

    choices:

    (1)  Write instead something like this mixfix notation

    IF  if-part  THEN  then-part  ELSE  elsepart  ENDIF

    in analogy with some procedural languages. Make IF, THEN, ELSE, ENDIF

    reserved words, perhaps. Do something analogous for other combinators, but

    restrict the palette of combinators to a fixed useful minimum. This is what

    procedural languages tend to do with statements  sequencing, conditionals,

    various loops. Do not allow the user to define their own. (Something needs

    to be said here about procedures taking other procedures as parameters  but

    I¹ll skip that for the moment.) The Pascals and the Cs do this, and so does

    the FP language by Backus (if memory serves right). I don¹t know what a

    suitable minimal set for Joy or other concatenative languages would be.

    (2) Allow user defined combinators, but (probably) without the mixfix

    notation. Instead do functional notation:

    ifte(ifpart, then-part, else-part)

    Definitions for user declared combinators now look like this:

    DEFINE  foo(f1, f2, ..)  ==  ... .

    The extension to the parser is trivial, and checking for agreement of formal

    and actual parameters in calls is not difficult either.

    Both (1) and (2) introduce more structure into programs, and allow the

    language processor to check that the required structure is not violated.

    In each case the combinators take stack functions (such as dup * ) as

    parameters and the result behaves just like a simple stack function. Calls

    now look like this:

    IF ... THEN dup * ELSE  ...

    ifte(...,  dup *, ...)

    foo(..., dup *, ..., ...)

    In other words the parameters have to be literally the verbatim programs

    to be executed by the combinator, the program dup * in this case. Note also

    that as described so far there is no need for quotation brackets in the

    comma-separated list of actual parameters.

    (3) But in languages like the lisps there is another possibility. In most

    cases

    the combinators are given their function parameters literally, but at least

    for the apply combinator actual function parameter is an expression which

    has to be evaluated to give the function to be applied. Suppose we allow

    that for the concatenative language sketched so far. Assume we have defined

    a list of quotations, with the squaring quotation in third position:

    DEFINE quotelist ==  [ [..]  [..] [dup *] [..] ....]

    Now we could write things like these:

    ifte(..., quotelist third, ...)

    which will be equivalent to

    ifte(..., [dup *], ...)

    but now with quotation brackets. So there is more expressive power again,

    but still the parameters are in predetermined positions which can be

    enforced

    by the language processor.

    (4) Allow the quotation parameters to be constructed just before they are

    used by the

    combinator:

    ifte(..., quotelist third dup concat, ...)

    which is equivalent to

    ifte(..., [dup * dup *], ...)

    (5) Drop the restriction of predetermined positions of the parameters. Allow

    them to come from anywhere on the stack, but put them in the right position

    just before the combinator uses them. Examples in Joy:

    ...  rollup quotelist third swap ifte

    ...  rollup quotelist third dup concat swap ifte

    Just as in (4), even the concat example builds up a quotation from existing

    ones.

    (6) Allow quotation parameters to be built by taking other quotations apart:

    Examples:

    ifte( ..., quotelist third rest cons, ...)

    ... rollup 3 quotelist third rest cons swap ifte

    which are equivalent to

    ifte( ..., [3 *], ...)

    ... rollup [3 *] swap ifte

    As you the steps from 3 to 5 and 6 show, the ³spectrum² of possible

    notations is not quite linear, but never mind.

    We have started with a very inflexible version of combinators and allowed

    more and more freedom. There may be even more restrictive and more

    flexible notations than the two extremes outlined here.

    Question: which level is best? Safety bought by inflexible rigidity, or

    flexibility at the cost of obfuscation? I¹ll leave it at that. Pick your

    level

    and tell us about it.

     - Manfred

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

## William Tanksley, Jr — 2007-04-30 14:36:10

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

     > Question: which level is best? Safety bought by inflexible rigidity, or

    > flexibility at the cost of obfuscation? I¹ll leave it at that. Pick your

    > level and tell us about it.

     I think one of the great advances of Joy over Forth was its ability to

    pass code to combinators. Going back to a fixed syntax would be a

    pity. Safety can be acquired at less cost by adding some typechecking.

    However, some of Joy's combinators might be a little overdone. 'ifte'

    takes 3 quotations; that's a lot. I'd like to be able to express

    'else' without having to go so deep on the stack. What if the 'if'

    combinator left a conditional token on the stack, to be picked up by

    an 'else' combinator?

    [if-part] [conditional] if [else-part] else

    alternately, if you really like traditional syntax,

    [conditional] if [if-part] else [else-part] endif

    The same implementation would work for more complex conditionals:

    [action-choice] decisiontable

       [decision-part] decision

       [decision-part] decision

       [decision-part] decision ...

    endtable

    An 'if' would build a two-choice decision table. A full decision table

    could have any number of choices.

     >  - Manfred

     -Billy

## James Hague — 2007-05-01 14:23:04

    >When writing Joy programs with combinators, in about 95% of cases I seem to

    >push the quotation parameters just before the combinator. Using the ifte

    >combinator, a piece of program would look like this:

    >

    >[if-part] [then-part] [else-part] ifte

    >

    >The ifte combinator immediately removes the three quotations, and all other

    >combinators do the same. Could one have a different notation?

     The Forth-like notation you suggest is a step-backwards.  This is coming

    from someone who has written a lot of Forth :)

    I would like to see [if-part] replaced with a simple Boolean flag.  Is there

    a reason it needs to be a quotation?  I believe it's a Boolean in Factor.

    James

## John Cowan — 2007-05-01 15:38:29

    James Hague scripsit:

     > I would like to see [if-part] replaced with a simple Boolean flag.

    > Is there a reason it needs to be a quotation?  I believe it's a Boolean

    > in Factor.

     There are two separate two-armed conditional words in Joy, "ifte" and

    "choice".  The latter behaves as you suggest: it takes a boolean

    value and two quotations on the stack.  However, "ifte" works differently:

    after executing the [if-part], it gets the boolean value from the

    top of the stack and then restores the stack to its former state.

    Thus the program

    	20 [pop true] ["yes"] ["no"] ifte

    is equivalent to

    	20 "yes"

    because although the pop is executed, its effect is undone by the

    stack restoration.

    There are many other Joy combinators with similar behavior.  For example,

    "nullary" pops a combinator from the stack, preserves the stack, executes

    the combinator, saves the top value, restores the stack, and pushes the

    top value.  Thus it does not matter how many items are popped from the

    stack by the combinator.

    In the Joy interpreter, the stack is a linked list rather than a vector,

    and garbage collection is used to reclaim stack fragments.  Consequently,

    restoring the stack is a cheap operation.

    --

    Time alone is real                      John Cowan <cowan@...>

      the rest imaginary

    like a quaternion       --phma          http://www.ccil.org/~cowan

## Manfred Von Thun — 2007-05-04 08:15:33

    On 2/5/07 1:38 AM, "John Cowan" <cowan@...> wrote:

     >

    >

    >

    >

    > James Hague scripsit:

    >

    >> > I would like to see [if-part] replaced with a simple Boolean flag.

    >> > Is there a reason it needs to be a quotation?  I believe it's a Boolean

    >> > in Factor.

    >

    > There are two separate two-armed conditional words in Joy, "ifte" and

    > "choice".  The latter behaves as you suggest: it takes a boolean

    > value and two quotations on the stack.  However, "ifte" works differently:

    > after executing the [if-part], it gets the boolean value from the

    > top of the stack and then restores the stack to its former state.

    >

    > Thus the program

    >

    > 20 [pop true] ["yes"] ["no"] ifte

    >

    > is equivalent to

    >

    > 20 "yes"

    >

    > because although the pop is executed, its effect is undone by the

    > stack restoration.

    >

    > There are many other Joy combinators with similar behavior.  For example,

    > "nullary" pops a combinator from the stack, preserves the stack, executes

    > the combinator, saves the top value, restores the stack, and pushes the

    > top value.  Thus it does not matter how many items are popped from the

    > stack by the combinator.

    >

    > In the Joy interpreter, the stack is a linked list rather than a vector,

    > and garbage collection is used to reclaim stack fragments.  Consequently,

    > restoring the stack is a cheap operation.

     The two combinators ifte and choice are interdefinable:

    [thenpart] [elsepart] choice ==

    [] [thenpart] [elsepart] ifte ==

    [thenpart] [elsepart] [] rollup ifte

    and hence:

    choice == [] rollup ifte

    [ifpart] [thenpart] [elsepart] ifte ==

    [ifpart] nullary [thenpart][elepart] choice ==

    [ifpart] [nullary] i [thenpart] [elsepart] choice ==

    [ifpart] thenpart] [nullary] dip [elsepart] choice ==

    [ifpart] [thenpart] [elsepart] [[nullary]dip] dip choice

    And hence:

    ifte == [[nullary] dip] dip choice.

    So the ifte combinator can be defined in tems of nullary and dip. Presumably

    the nullary combinator will evoke the same wide variety of reactions from

    programmers as the ifte combinator. By way of contrast, the dip combinator

    has never evoked such a variety. But what is surprising is that nullary need

    not be a primitive combinator, it can be defined in terms of dip or in terms

    of infra. I cannot remember the two definitions right now. But I¹ll look

    them

    up at home and post them next week.

     - Manfred

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

## Manfred Von Thun — 2007-05-07 04:23:37

    On 4/5/07 6:15 PM, "Manfred Von Thun" <m.vonthun@...> wrote:

     > So the ifte combinator can be defined in tems of nullary and dip. Presumably

    > the nullary combinator will evoke the same wide variety of reactions from

    > programmers as the ifte combinator. By way of contrast, the dip combinator

    > has never evoked such a variety. But what is surprising is that nullary need

    > not be a primitive combinator, it can be defined in terms of dip or in terms

    > of infra. I cannot remember the two definitions right now. But I¹ll look

    > them up at home and post them next week.

    >

     Here we are:

    First, two older versions:

    nullary == [stack] dip infra first

    nullary == [stack] dip dip cons unstack

    My current favourites, using just one combinator (infra or dip):

    nullary == stack rest swap infra first

    nullary == stack rest swap dip cons unstack

    With the wisdom of hindsight this should not really be a surprise.

    Given any stack, the stack operator will produce essentially two

    identical lists: the original stack and a copy (in the form of a list).

    Put a quotation on top, and then the dip operator and the infra operator

    can use the quotation to change the original or the copy.

    So there exists some kind of symmetry between dip and infra.

    If I had understood this earlier, I might have chosen two more

    symmetric names for the two combinators.

    I have not succeeded to define dip in terms of infra, or to

    define infra in terms of dip. I don¹t know whether this is just

    failure of the imagination or whether this is just impossible.

    And this raises another question: Is there some technique by

    which one can show that it is impossible to define one thing

    in terms of a given set of others? I only have the vaguest

    recollection of seeing a proof that ³not² cannot be defined

    in terms of ³and² and ³or². Obvious, yes. But is there a

    general technique?

      - Manfred

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

## Manfred Von Thun — 2007-05-07 10:52:30

    On 2/5/07 12:23 AM, "James Hague" <jamesh@...> wrote:

     > [..]

    >> >The ifte combinator immediately removes the three quotations, and all other

    >> >combinators do the same. Could one have a different notation?

    >

    > The Forth-like notation you suggest is a step-backwards.  This is coming

    > from someone who has written a lot of Forth :)

     Firstly, I wasn¹t actually suggesting it, I was merely listing various

    alternatives.

    Is it a step backwards? Maybe, but that can be a a good thing if one has

    been led

    up the garden path. I was really looking for a cost/benefit analysis of the

    various

    possible alternative notations. Then, when one has settled on one notation,

    at

    least one knows why it was chosen in preference to others. My own little

    contribution

    to the analysis was my usage statistic: 95% of programs could be written

    with

    a less permissive notation and be clearer. Are the 5% using the various

    extras

    worth the risks? It is safe rigidity versus freedom (to shoot oneself in the

    foot).

    I have tried not to make my preferences shine through.

      - Manfred

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