# an exchange on flatness

## stevan apter — 2005-07-16 17:30:52

    the following is a (slightly edited) conversation which took place

    on #concatenative earlier this morning.

    comments?

    -------------

    <eiz> How is 'flatness' in any way desirable in the first place?

    <sa>  it permits factoring at finer granularity

    <eiz> Sorry, you have to do better than that =) Is this finer granularity

    actually useful?

    <sa>  it is theoretically smoother - punctuation symbols become functions

    <sa>  the only punctuation symbol is the blank

    <sa>  it obviates the need for a separate macro facility

    <sa>  i never know how to answer the question "is it useful?" that's a very

    deep question.

    <sa>  so there are three reasons ..

    <eiz> I don't know, it seems kind of goofy to me

    <sa>  "goofy" =abbrev "good for you"  :)

    <sa>  initially, i was skeptical. but the idea has grown on me.

    <eiz> There aren't any compelling examples

    <sa>  well, not yet

    <sa>  reason 2 seems to me to be the strongest. flat languages have some nice

    theoretical properties

    <sa>  e.g. a program is a sequence of tokens. all partitionings of the sequence

    are semantically equivalent

    <eiz> Well, you know my take on that... :P

    <sa>  no, i really don't

    <sa>  the parser for a flat language = tokenizer + typer

    <eiz> Theoretical properties only interest me if they improve real programs

    <sa>  theoretical simplicity -> conceptual simplicity -> improvement in

    productivity (other things being equal)

    <eiz> Only to a point

    <sa>  suppose you have five programs which begin with the sequence [ 2 + *

    <eiz> Unlambda and Brainfuck are certainly very conceptually simple, for example

    <sa>  then you can factor that out as : f [ 2 + *

    <sa>  unlambda isn't simple at all!

    <sa>  continuations, delays, promises ... side-effects!!

    <eiz> pfft, it's still simple

    <sa>  but what about my example -- : f [ 2 + ; -- you have five programs which

    begin with "make a list with 2 + as initial elements". you can factor that out

    and give it a name. (assume that it's not an accident that they begin with f -

    now you have just one place in the code you have to change)

    <eiz> Because I don't believe that kind of micro-factoring is useful

    <sa>  ah

    <eiz> [ 2 + is not a full thought, you're just applying compression to your

    program at that point

    <sa>  ah

    <sa>  so you think that "thoughts" align on boundaries defined syntactically by

    mated brackets

    <sa>  that's an interesting hypothesis

    <eiz> Not necessarily, but I don't think [ 2 + says much of anything

    <sa>  and you think that factoring is only useful when it's applied to "full

    thoughts"

    <sa>  [ 2 + means "(a program which) starts by adding 2 and continues ..."

    * eiz wonders what this word would be called

    <eiz> I think if you can't give it a good name, it's too small.

    <sa>  add2then

    <eiz> heheh

    <sa>  you could adopt the convention that initial sub-quotation definitions

    end in "then" and terminal subquotation words begin with "and"

    * sa admits that this doesn't seem entirely convincing

## William Tanksley, Jr — 2005-07-26 01:02:11

    stevan apter <sa@...> wrote:

     > <eiz> How is 'flatness' in any way desirable in the first place?

     I can say that SOME flatness is desirable -- it makes programming in

    Forth pleasant. The idea of a completely flat language is new and

    untested, so I can't say whether it's more desirable than all the

    things we'd be giving up in order to get it.

     > <sa>  theoretical simplicity -> conceptual simplicity -> improvement in

    > productivity (other things being equal)

    > <eiz> Only to a point

     Ah, but where exactly is that point? We don't know.

     > <eiz> Because I don't believe that kind of micro-factoring is useful

    > <eiz> [ 2 + is not a full thought, you're just applying compression to your

    > program at that point

     Again, nobody's tried. We just don't know -- few people have even

    thought about it. Realistically, it's quite probable that

    microfactoring IS useful in at least a few cases; the real question is

    whether it's generally useful. Macros are more useful than most

    programmers realise; just ask a Lisp programmer.

    -Billy

## Mackenzie Straight — 2005-07-26 07:19:48

    On 7/25/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > Ah, but where exactly is that point? We don't know.

     I don't see how adding extra modes, markers or other doodads

    'simplifies' anything in the first place. From a user perspective it

    seems fairly useless (pending examples to the contrary -- really, I

    want to be proven wrong here), and from an implementation perspective

    it's yet another thing to worry about optimizing, as the naive method

    is laughably inefficient, to say nothing of the fact that the tree

    structure of source code is highly useful for tools like

    pretty-printers, editors, etc...

    Really, what's simpler (I'll use the latest XY's notion of flatness,

    as that is what my original comments were based on):

    [ is a literal which, when present on the stack, causes the

    interpreter to go into a special mode in which all words -- except 3

    magic words -- are pushed onto the stack literally instead of being

    executed.

    vs.

    [ ... ] is a list of things.

    Or even the Factor definitions:

    : [ f ; parsing

    : ] reverse swons ; parsing

    I know which I prefer.

     > > <eiz> Because I don't believe that kind of micro-factoring is useful

    > > <eiz> [ 2 + is not a full thought, you're just applying compression to your

    > > program at that point

    >

    > Again, nobody's tried. We just don't know -- few people have even

    > thought about it. Realistically, it's quite probable that

    > microfactoring IS useful in at least a few cases; the real question is

    > whether it's generally useful. Macros are more useful than most

    > programmers realise; just ask a Lisp programmer.

     I haven't managed to convince myself that it's a good idea. I don't

    think about programs in terms of tokens. I don't want to.

     > -Billy

     --eiz

## stevan apter — 2005-07-26 10:58:05

    ----- Original Message -----

    From: "Mackenzie Straight" <eizneckam@...>

    To: <concatenative@yahoogroups.com>

    Sent: Tuesday, July 26, 2005 3:19 AM

    Subject: Re: [stack] an exchange on flatness

    > On 7/25/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

    > > Ah, but where exactly is that point? We don't know.

    >

    > I don't see how adding extra modes, markers or other doodads

    > 'simplifies' anything in the first place. From a user perspective it

    > seems fairly useless (pending examples to the contrary -- really, I

    > want to be proven wrong here), and from an implementation perspective

    > it's yet another thing to worry about optimizing, as the naive method

    > is laughably inefficient, to say nothing of the fact that the tree

    > structure of source code is highly useful for tools like

    > pretty-printers, editors, etc...

    >

    > Really, what's simpler (I'll use the latest XY's notion of flatness,

    > as that is what my original comments were based on):

    >

    > [ is a literal which, when present on the stack, causes the

    > interpreter to go into a special mode in which all words -- except 3

    > magic words -- are pushed onto the stack literally instead of being

    > executed.

    >

    > vs.

    >

    > [ ... ] is a list of things.

    >

    > Or even the Factor definitions:

    >

    > : [ f ; parsing

    > : ] reverse swons ; parsing

    >

    > I know which I prefer.

    but if you give up quotations for eager lists, which billy seems

    willing to do, then the rule is just:

        [ is a literal:

                            X [^Y -> X^[ Y]

        ] finds its [-mate, enlists, pushes onto the stack, i.e.

                            [X^[^Z ]^Y] -> [X^[Z] Y]

    there are no markers, modes, magic words, or other doo-dads.

    >

    > > > <eiz> Because I don't believe that kind of micro-factoring is useful

    > > > <eiz> [ 2 + is not a full thought, you're just applying compression to your

    > > > program at that point

    > >

    > > Again, nobody's tried. We just don't know -- few people have even

    > > thought about it. Realistically, it's quite probable that

    > > microfactoring IS useful in at least a few cases; the real question is

    > > whether it's generally useful. Macros are more useful than most

    > > programmers realise; just ask a Lisp programmer.

    >

    > I haven't managed to convince myself that it's a good idea. I don't

    > think about programs in terms of tokens. I don't want to.

    >

    > > -Billy

    >

    > --eiz

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

## William Tanksley, Jr — 2005-07-27 05:04:19

    Mackenzie Straight <eizneckam@...> wrote:

     > On 7/25/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

    > > Ah, but where exactly is that point? We don't know.

    > I don't see how adding extra modes, markers or other doodads

    > 'simplifies' anything in the first place.

     That's not the question -- the question is whether *removing* all of

    the modes, markers, and other doodads simplifies things too much.

    That's the purpose of flatness.

     > From a user perspective it

    > seems fairly useless (pending examples to the contrary -- really, I

    > want to be proven wrong here),

     Well, consider that one of the nicest practical features of

    concatenative languages, easy factoring, is easy only where the

    language is flat. Anywhere the language becomes non-flat -- near an IF

    in Forth, or near a [ in Joy -- factoring becomes nontrivial.

    This is a handwaving claim, however. I have no real proof or evidence

    -- in fact, I admit that Forth and Joy may already receive the best

    benefits of flatness, and anything more will have diminishing returns.

    But if so, this is an accident, because neither language was designed

    with the idea of flatness in mind. It's interesting that Chuck Moore

    has since invented, and now does all his work in, a flatter language

    than Forth.

    Rather than assuming that Forth and Joy are coincidentally already at

    the perfect level of flatness, I'd like to check.

     > and from an implementation perspective

    > it's yet another thing to worry about optimizing, as the naive method

    > is laughably inefficient,

     The naive method results immediately in a dataflow graph, which other

    languages have to perform multiple steps to produce. Every decent

    optimiser starts with a dataflow graph. And THIS graph expresses the

    explicit intentions of the programmer, not some odd combination of the

    assumptions of the language designer with the (implicit) intentions of

    the programmer.

     > to say nothing of the fact that the tree

    > structure of source code is highly useful for tools like

    > pretty-printers, editors, etc...

     All of those things are tools to help recover from the difficulties

    caused by overstructured languages. They're symptoms of a problem, not

    solutions. (I sound like Chuck Moore now... :-) And anyhow, they're

    mostly useless anyhow in most concatenative languages.

     > Really, what's simpler (I'll use the latest XY's notion of flatness,

    > as that is what my original comments were based on):

    > [ is a literal which, when present on the stack, causes the

    > interpreter to go into a special mode in which all words -- except 3

    > magic words -- are pushed onto the stack literally instead of being

    > executed.

     Well, I don't find that too useful -- it's modal. But keep in mind

    that the mode he's using here is the same thing that Factor hides

    behind : and ; -- it's the "compile these things" mode.

     > > > <eiz> Because I don't believe that kind of micro-factoring is useful

    > > > <eiz> [ 2 + is not a full thought, you're just applying compression to your

    > > > program at that point

    > > Again, nobody's tried. We just don't know -- few people have even

    > > thought about it. Realistically, it's quite probable that

    > > microfactoring IS useful in at least a few cases; the real question is

    > > whether it's generally useful. Macros are more useful than most

    > > programmers realise; just ask a Lisp programmer.

    > I haven't managed to convince myself that it's a good idea. I don't

    > think about programs in terms of tokens. I don't want to.

     Could you clarify? Do you mean that you don't see distinct words when

    you look at a program? What do you see?

     > --eiz

     -Billy

## Mackenzie Straight — 2005-07-27 06:40:17

    On 7/26/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > Mackenzie Straight <eizneckam@...> wrote:

    > > On 7/25/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

    > > > Ah, but where exactly is that point? We don't know.

    >

    > > I don't see how adding extra modes, markers or other doodads

    > > 'simplifies' anything in the first place.

    >

    > That's not the question -- the question is whether *removing* all of

    > the modes, markers, and other doodads simplifies things too much.

    > That's the purpose of flatness.

     Except all that this 'flatness' does, as far as I can tell anyway, is

    move things from parse time to runtime. The structures are still

    there, it's just a matter of when you construct them.

     > Well, consider that one of the nicest practical features of

    > concatenative languages, easy factoring, is easy only where the

    > language is flat. Anywhere the language becomes non-flat -- near an IF

    > in Forth, or near a [ in Joy -- factoring becomes nontrivial.

     How so? [ foo bar baz ] can be trivially replaced by [ foobar baz ]

    and : foobar foo bar ;. If that's not good enough, eager lists may

    also help: DEFINE eager == [] swap infra reverse. The problem you are

    describing is not one that I have ever encountered in practice.

     > > to say nothing of the fact that the tree

    > > structure of source code is highly useful for tools like

    > > pretty-printers, editors, etc...

    >

    > All of those things are tools to help recover from the difficulties

    > caused by overstructured languages. They're symptoms of a problem, not

    > solutions. (I sound like Chuck Moore now... :-) And anyhow, they're

    > mostly useless anyhow in most concatenative languages.

     I disagree completely, but if you don't like tools, that's fine. I do.

    Another example: S-expressions are often used in Lisp to marshal data.

    I utilize the syntax of my own concatenative language (a scripting

    language for OCaml programs) in a very similar manner. It's quite

    handy, although not nearly as powerful as the CL reader. Tree syntax

    is useful, and should not be thrown away lightly.

    Check this out: http://factor.modalwebserver.co.nz/responder/browser/

    This would be a lot less general and simple if the prettyprinter had

    to think about [ and ], to say nothing of [[, ]], {, }, {{, }}, << and

     >> as words rather than just seeing a list or other data structure.

    > > I haven't managed to convince myself that it's a good idea. I don't

    > > think about programs in terms of tokens. I don't want to.

    >

    > Could you clarify? Do you mean that you don't see distinct words when

    > you look at a program? What do you see?

     Of course I _see_ the individual tokens. I just don't necessarily

    think about them individually. Breaking up a list which is, in my

    mind, a single literal object rather than a sequence of words seems

    unnatural.

    We've been thinking of a Factor editor that directly edits trees in

    memory (like SEdit) for some time now. Not a token in sight. I don't

    know if that will actually materialize, but it would be nice...

     > -Billy

     --eiz

## William Tanksley, Jr — 2005-08-02 00:06:01

    Mackenzie Straight <eizneckam@...> wrote:

     > On 7/26/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

    > > Mackenzie Straight <eizneckam@...> wrote:

    > > > On 7/25/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

    > > > > Ah, but where exactly is that point? We don't know.

    > > > I don't see how adding extra modes, markers or other doodads

    > > > 'simplifies' anything in the first place.

    > > That's not the question -- the question is whether *removing* all of

    > > the modes, markers, and other doodads simplifies things too much.

    > > That's the purpose of flatness.

    > Except all that this 'flatness' does, as far as I can tell anyway, is

    > move things from parse time to runtime. The structures are still

    > there, it's just a matter of when you construct them.

     If the language is lazy such things can be accomplished by the

    optimizer quickly in most cases, and deferred in other cases (and

    avoided by programmers in the remaining cases). There are other lazy

    languages that operate that way.

     > > Well, consider that one of the nicest practical features of

    > > concatenative languages, easy factoring, is easy only where the

    > > language is flat. Anywhere the language becomes non-flat -- near an IF

    > > in Forth, or near a [ in Joy -- factoring becomes nontrivial.

    > How so? [ foo bar baz ] can be trivially replaced by [ foobar baz ]

    > and : foobar foo bar ;. If that's not good enough, eager lists may

    > also help: DEFINE eager == [] swap infra reverse. The problem you are

    > describing is not one that I have ever encountered in practice.

     You'll never encounter it as long as it's impossible to express in

    your native language. Imagine trying to explain the concept of zero to

    a person whose culture didn't use it... "Well, so you're trying to

    tell me I need this because it's good for NOTHING?"

    :-)

    I've mentioned that ColorForth is a bit flatter than Forth, since it

    has no compile/interpret mode, nor any special lookahead words like

    ":", and that added flatness is a convenience. It's the core of

    several regular idioms in the language.

    Unlike my extreme flatness, Chuck's colorForth doesn't attempt to take

    things too far, and his language is very fast as well as very flat.

     > > > to say nothing of the fact that the tree

    > > > structure of source code is highly useful for tools like

    > > > pretty-printers, editors, etc...

    > > All of those things are tools to help recover from the difficulties

    > > caused by overstructured languages. They're symptoms of a problem, not

    > > solutions. (I sound like Chuck Moore now... :-) And anyhow, they're

    > > mostly useless anyhow in most concatenative languages.

    > I disagree completely, but if you don't like tools, that's fine. I do.

     I didn't say I didn't like tools. I said that many of the tools you

    name are merely attempting to overcome the problems your "solutions"

    are causing you. If your code has a clear tree structure, your

    definitions are too long.

     > Another example: S-expressions are often used in Lisp to marshal data.

     And Forth code is often used in Forth to construct data. In

    colorForth, you'd actually write an editor widget to hold your data,

    so that it could be edited inline with the code in a format that's

    natural for the data. (I don't know of anyone that's done that aside

    from Chuck himself, but he told me that's the intended use of color

    Forth.)

    I'm not knocking a standard format for data. But if you're talking

    about code and data having the same format, well, might as well let

    the code do its job.

     > I utilize the syntax of my own concatenative language (a scripting

    > language for OCaml programs) in a very similar manner. It's quite

    > handy, although not nearly as powerful as the CL reader.

     You mean not nearly as consistent as the CL reader. CL reader macros

    can look like anything, but are a pain to implement; CL macros can

    only look like CL function calls, and are reasonably easy to

    implement. Concatenative macros can look like anything and are easy to

    implement. So I'd say that they're of equal power, but for the same

    power concatenative macros are easier. (Qualification: I give Lisp

    props for consistency; I can't knock S-exps for consistent data

    storage. But that doesn't grant you "power".)

     > Tree syntax is useful, and should not be thrown away lightly.

     I can see some benefit to throwing it away -- a flat language that

    didn't allow tree syntax would be a lot simpler and fast than one that

    did. But ignore that for the moment, because I've not proposed

    throwing away tree syntax here. I've explained how to be ABLE to do

    without it. Just because the language CAN express ideas without it

    doesn't mean that programmers should express ALL ideas without it.

     > Check this out: http://factor.modalwebserver.co.nz/responder/browser/

    > This would be a lot less general and simple if the prettyprinter had

    > to think about [ and ], to say nothing of [[, ]], {, }, {{, }}, << and >>

    > as words rather than just seeing a list or other data structure.

     Wait a sec. If all you want is list literals, my suggestion doesn't

    offer anything -- I only eliminate the need to put quotations in

    whenever you need conditionals. Lists and data structures are

    completely different. Even in my system, you'd still need to put

    quotes around strings, and something around lists.

     > > > I haven't managed to convince myself that it's a good idea. I don't

    > > > think about programs in terms of tokens. I don't want to.

    > > Could you clarify? Do you mean that you don't see distinct words when

    > > you look at a program? What do you see?

    > Of course I _see_ the individual tokens. I just don't necessarily

    > think about them individually. Breaking up a list which is, in my

    > mind, a single literal object rather than a sequence of words seems

    > unnatural.

     A list is a single object, of course, and should be expressed in code

    that way; its semantics are treelike. But the consequential of a

    conditional isn't a list; it's not any (particular) data structure.

    It's an action. Insisting that every programmer MUST write it as

    though it were a list is a bit overboard.

     > We've been thinking of a Factor editor that directly edits trees in

    > memory (like SEdit) for some time now. Not a token in sight. I don't

    > know if that will actually materialize, but it would be nice...

     Good to hear! Sounds fun and useful.

    colorForth's editor works essentially that way. Chris Cogan's paper on

    QP and Tree-P suggest the ideas as well -- in a completely different

    way than how you're planning to do it.

     > --eiz

     -Billy

## Mackenzie Straight — 2005-08-02 00:54:36

    On 8/1/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

     >

    > > > Well, consider that one of the nicest practical features of

    > > > concatenative languages, easy factoring, is easy only where the

    > > > language is flat. Anywhere the language becomes non-flat -- near an IF

    > > > in Forth, or near a [ in Joy -- factoring becomes nontrivial.

    >

    > > How so? [ foo bar baz ] can be trivially replaced by [ foobar baz ]

    > > and : foobar foo bar ;. If that's not good enough, eager lists may

    > > also help: DEFINE eager == [] swap infra reverse. The problem you are

    > > describing is not one that I have ever encountered in practice.

    >

    > You'll never encounter it as long as it's impossible to express in

    > your native language. Imagine trying to explain the concept of zero to

    > a person whose culture didn't use it... "Well, so you're trying to

    > tell me I need this because it's good for NOTHING?"

     Okay, show one example of where this sort of thing is actually useful.

    That's all I've asked for. I'm not going to just take your word for

    it.

     > A list is a single object, of course, and should be expressed in code

    > that way; its semantics are treelike. But the consequential of a

    > conditional isn't a list; it's not any (particular) data structure.

    > It's an action. Insisting that every programmer MUST write it as

    > though it were a list is a bit overboard.

     It's a quotation, which happens to be represented as a list. In the

    future, Factor is actually going to have a first class quotation type,

    and cons lists are going to have their role seriously reduced or

    eliminated, but that's beside the point. The point is that the code

    _is_ a data structure.

    As for the bit about the problems my "solutions" are causing, I'll

    keep them thanks. I don't care to discuss religion on the Internet. =)

     > -Billy

     --eiz

## William Tanksley, Jr — 2005-08-02 02:36:51

    Mackenzie Straight <eizneckam@...> wrote:

     > On 8/1/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

    > > You'll never encounter it as long as it's impossible to express in

    > > your native language. Imagine trying to explain the concept of zero to

    > > a person whose culture didn't use it... "Well, so you're trying to

    > > tell me I need this because it's good for NOTHING?"

    > Okay, show one example of where this sort of thing is actually useful.

    > That's all I've asked for. I'm not going to just take your word for

    > it.

     Okay.

    I can't give that to you. Sorry. There are no perfectly flat languages

    yet, and there may never be. I'm trying to figure out how to

    accomplish such a thing, and I think it can be done... But of course,

    that doesn't imply that it SHOULD be done.

    However, I don't think this means that it's useless to talk about it,

    even though I think that pure flatness probably will be unusable. I

    already know that partial flatness is useful, and languages with more

    flatness get more useful. I'm certain that there's a point of

    diminishing returns, but I want to find it.

    Oh, and I've given you examples of partially flat languages. Typical

    concatenative languages are inherently flatter than typical

    applicative ones; colorForth is flatter than Forth.

     > > A list is a single object, of course, and should be expressed in code

    > > that way; its semantics are treelike. But the consequential of a

    > > conditional isn't a list; it's not any (particular) data structure.

    > > It's an action. Insisting that every programmer MUST write it as

    > > though it were a list is a bit overboard.

    > It's a quotation, which happens to be represented as a list.

     No, it "is" not a quotation. Joy and Factor use quotations for it.

    Forth doesn't define any data structure. It's easy to define an

    improper subset of Forth, "flat Forth", that uses xts (which are

    atoms) for the consequentials of conditionals.

    Please don't confuse implementation with essence.

     > In the

    > future, Factor is actually going to have a first class quotation type,

    > and cons lists are going to have their role seriously reduced or

    > eliminated, but that's beside the point. The point is that the code

    > _is_ a data structure.

     The code is represented by a data structure. You use a compile-time

    list. A list is a great way to gather concatenative code together, but

    a very poor way to dissect and manipulate code -- you can do things

    with lists that aren't sensible with code.

    (You can also do things with my lazy flat language that aren't

    sensible with static native code -- this suggests to me that my lazy

    flat language isn't the best way to express programming ideas.)

     > As for the bit about the problems my "solutions" are causing, I'll

    > keep them thanks. I don't care to discuss religion on the Internet. =)

     And yet you just did. I didn't bring religion up, after all.

    I think your solutions are fair game -- you're the one bringing them

    in as a telling argument against flatness, after all. I repeat: the

    tools you use are only useful to overcome the problems of a different

    type of code. With flat code, different tools would be needed. I

    honestly don't know what they'd look like.

     > --eiz

     -Billy

## Daniel Ehrenberg — 2005-08-02 02:53:24

    > The code is represented by a data structure. You use a compile-time

    > list. A list is a great way to gather concatenative code together, but

    > a very poor way to dissect and manipulate code -- you can do things

    > with lists that aren't sensible with code.

     What are you saying? That a language needs to restrict how people

    manipulate code? I don't see why. It's possible to do things with cons

    cells that don't make sense to do with lists, but does that mean lists

    shouldn't be made with cons cells? It is very useful to have code be

    [represented by] an accessable data structure; Lisp macros are a

    testimate to that, and Factor sometimes does similar things, though

    not as often.

    Daniel Ehrenberg

## Mackenzie Straight — 2005-08-02 04:18:29

    On 8/1/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > No, it "is" not a quotation. Joy and Factor use quotations for it.

    > Forth doesn't define any data structure. It's easy to define an

    > improper subset of Forth, "flat Forth", that uses xts (which are

    > atoms) for the consequentials of conditionals.

    >

    > Please don't confuse implementation with essence.

     I am well aware that Forth does not have quotations. Ask yourself

    this, though: what is the fundamental difference between a quotation

    and an xt? The answer is simple: xts are opaque, and can't really be

    manipulated. But aside from that they're basically the same thing.

    (Would an xt-forth qualify as 'flat'?)

     >

    > > In the

    > > future, Factor is actually going to have a first class quotation type,

    > > and cons lists are going to have their role seriously reduced or

    > > eliminated, but that's beside the point. The point is that the code

    > > _is_ a data structure.

    >

    > The code is represented by a data structure. You use a compile-time

    > list. A list is a great way to gather concatenative code together, but

    > a very poor way to dissect and manipulate code -- you can do things

    > with lists that aren't sensible with code.

     A very poor way to manipulate code? Lists have been working quite well

    for manipulating source code for the last 42 years. I've grown

    somewhat attached to the notion, myself.

     > I think your solutions are fair game -- you're the one bringing them

    > in as a telling argument against flatness, after all. I repeat: the

    > tools you use are only useful to overcome the problems of a different

    > type of code. With flat code, different tools would be needed. I

    > honestly don't know what they'd look like.

     The "solutions" which I brought up are not necessities by any means. I

    don't need them. They're not solving problems; they just make my life

    a bit more pleasant. They're not necessitated by the fact that the

    code is too long or overstructured or any other so called problem

    (aka, matter of personal taste, or in the vernacular, "religion," much

    like vi vs. emacs).

    It's not an argument against flatness, either. I was simply pointing

    out some things that may rely on the tree representation of code, at

    least in their current form. Your response was that these tools are

    "symptoms of a problem" and "mostly useless anyway in most

    concatenative languages." If that's your opinion on the value of the

    sort of tools I mentioned, we really can't discuss how they would be

    adapted to a flat language. Oh well...

     > -Billy

     --eiz

## William Tanksley, Jr — 2005-08-02 22:18:30

    Daniel Ehrenberg <microdan@...> wrote:

     > > The code is represented by a data structure. You use a compile-time

    > > list. A list is a great way to gather concatenative code together, but

    > > a very poor way to dissect and manipulate code -- you can do things

    > > with lists that aren't sensible with code.

    > What are you saying? That a language needs to restrict how people

    > manipulate code?

     No. I'm saying that code isn't a data structure. Perhaps I'm

    misphrasing that; perhaps I should say something like "computations

    aren't data structures". I can see that my origiinal phrasing was

    misleading. The reason I say that is that every data structure we've

    used to represent computations implies that you can manipulate the

    data structure to determine things about the computation.

    And that's just not true. Turing proved it -- the only general way to

    know things about computations is to actually run them. Languages that

    allow you to know the data structure used to represent a computation

    automatically put limitations on the computation.

    For example, Joy's documentation mentions that identities such as "dup

    drop == nop" don't hold within quotations, because someone might use

    the length of the quotation (list).

     > It is very useful to have code be

    > [represented by] an accessable data structure;

     Agreed. When I said "code" I should have said "computations". When you

    say "code" you're referring to the stuff that the programmer

    manipulates in order to specify the computation.

     > Lisp macros are a

    > testimate to that, and Factor sometimes does similar things, though

    > not as often.

     Agreed. And Joy quotations as well -- very much so!

     > Daniel Ehrenberg

     -Billy

## William Tanksley, Jr — 2005-08-03 00:38:36

    Mackenzie Straight <eizneckam@...> wrote:

     > On 8/1/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

    > > No, it "is" not a quotation. Joy and Factor use quotations for it.

    > > Forth doesn't define any data structure. It's easy to define an

    > > improper subset of Forth, "flat Forth", that uses xts (which are

    > > atoms) for the consequentials of conditionals.

    > > Please don't confuse implementation with essence.

    > I am well aware that Forth does not have quotations. Ask yourself

    > this, though: what is the fundamental difference between a quotation

    > and an xt? The answer is simple: xts are opaque, and can't really be

    > manipulated. But aside from that they're basically the same thing.

    > (Would an xt-forth qualify as 'flat'?)

     Forth doesn't use xts for its conditionals, either. And yes, making it

    impossible to manipulate an unexecuted computation accurately

    represents the reality of a computation. The only operation that can

    be performed in general on a computation is to execute it -- and of

    course there's no guarantee that it'll halt.

     > > > In the

    > > > future, Factor is actually going to have a first class quotation type,

    > > > and cons lists are going to have their role seriously reduced or

    > > > eliminated, but that's beside the point. The point is that the code

    > > > _is_ a data structure.

    > > The code is represented by a data structure. You use a compile-time

    > > list. A list is a great way to gather concatenative code together, but

    > > a very poor way to dissect and manipulate code -- you can do things

    > > with lists that aren't sensible with code.

    > A very poor way to manipulate code? Lists have been working quite well

    > for manipulating source code for the last 42 years. I've grown

    > somewhat attached to the notion, myself.

     I apologise -- the miscommunication is my fault. I wasn't referring to

    source code; I was referring to computations. I'm not talking about

    the ability for a program to build another program from parts; I'm

    talking about the ability to pass a computation to an 'if' combinator

    that will either execute it or drop it, and to know that the optimizer

    will be able to optimize it the same as any other chunk of code in

    your system.

     > > I think your solutions are fair game -- you're the one bringing them

    > > in as a telling argument against flatness, after all. I repeat: the

    > > tools you use are only useful to overcome the problems of a different

    > > type of code. With flat code, different tools would be needed. I

    > > honestly don't know what they'd look like.

    > The "solutions" which I brought up are not necessities by any means. I

    > don't need them. They're not solving problems; they just make my life

    > a bit more pleasant.

     Enjoy, then. I guess that once flat programming takes the world by

    storm you can freely load old, legacy, no-longer-used code into your

    prettyprinters and so on and make your life as much more pleasant as

    you want. :-) ;-)

    I personally don't see any use to those things beyond dealing with the

    complexities of code; and I know that there are many other ways of

    dealing with the complexity. I'm not claiming, by the way, that my

    ways are better; I am claiming that there will be other ways of

    dealing with complexity, and they will work at least as well. So

    unless you truly enjoy prettyprinters and structured editors for their

    own sake, there's no need to bring them up in this discussion.

     > It's not an argument against flatness, either.

     My misunderstanding, then. I took it as such, since it was in a

    paragraph of arguments against flatness.

     > I was simply pointing

    > out some things that may rely on the tree representation of code, at

    > least in their current form.

     That's true. All I can say, then, is that if you want to express your

    code as a tree you still can. Flat languages are graphs, not trees;

    but if the programmer wishes, he can confine his work to the shape of

    a tree. I suspect that most of the time that'll give the best results,

    actually (for that reason I'm not sure that flatness is ideal).

     > Your response was that these tools are

    > "symptoms of a problem" and "mostly useless anyway in most

    > concatenative languages." If that's your opinion on the value of the

    > sort of tools I mentioned, we really can't discuss how they would be

    > adapted to a flat language. Oh well...

     No, I don't believe they could be. Entirely new tools would have to be produced.

    Prettyprinters are probably the smallest problem -- prettyprinters

    force code to match conventions, and don't conceptually depend on

    syntax. So all we have to do is decide what conventions we're going to

    use... :-)

    colorForth has no prettyprinters yet, and probably never will. I doubt

    any would be needed.

    I've seen Forth code that needed prettyprinting, and code that was

    effectively impossible to prettyprint. I prefer the second.

     > --eiz

     -Billy

## Daniel Ehrenberg — 2005-08-03 14:26:16

    On 8/2/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > Daniel Ehrenberg <microdan@...> wrote:

    > > > The code is represented by a data structure. You use a compile-time

    > > > list. A list is a great way to gather concatenative code together, but

    > > > a very poor way to dissect and manipulate code -- you can do things

    > > > with lists that aren't sensible with code.

    >

    > > What are you saying? That a language needs to restrict how people

    > > manipulate code?

    >

    > No. I'm saying that code isn't a data structure. Perhaps I'm

    > misphrasing that; perhaps I should say something like "computations

    > aren't data structures". I can see that my origiinal phrasing was

    > misleading. The reason I say that is that every data structure we've

    > used to represent computations implies that you can manipulate the

    > data structure to determine things about the computation.

    >

    > And that's just not true. Turing proved it -- the only general way to

    > know things about computations is to actually run them. Languages that

    > allow you to know the data structure used to represent a computation

    > automatically put limitations on the computation.

    >

    > For example, Joy's documentation mentions that identities such as "dup

    > drop == nop" don't hold within quotations, because someone might use

    > the length of the quotation (list).

    >

     ...ok, but I don't really see any place for 100% abstract computations

    in any programming language, and it's still extremely useful to have

    code be a data structure. The quotation *is* a list, and there's

    nothing you could say to make it not. It makes no sense to do length

    the way you're picturing on quotations, though their length might be

    needed to produce another quotation from them. Any optimizations that

    the compiler might do, such as removing dup drop, should be done in a

    way invisible to the user.

     > > It is very useful to have code be

    > > [represented by] an accessable data structure;

    >

    > Agreed. When I said "code" I should have said "computations". When you

    > say "code" you're referring to the stuff that the programmer

    > manipulates in order to specify the computation.

     There are no computations. Computations are just a way of thinking

    about what's actually happening, but they don't exist within the

    language, as you've said would be impossible. So it's pretty useless

    to talk about computations at all.

    Daniel Ehrenberg

## William Tanksley, Jr — 2005-08-04 00:39:25

    Daniel Ehrenberg <microdan@...> wrote:

     > ...ok, but I don't really see any place for 100% abstract computations

    > in any programming language,

     The only purpose for using a programming language is to express

    computations. I don't know what you mean by 100% abstract, though;

    perhaps there's something there.

     > and it's still extremely useful to have

    > code be a data structure.

     I believe I agreed with this -- it's useful when you explicitly want

    to be able to manipulate the code before the computation it implies

    needs to be run. The problem is that if this abilitity remains open to

    *all* computations,

     > The quotation *is* a list, and there's

    > nothing you could say to make it not.

     I wouldn't want to do something like that. Quotations are lists.

    But I'm not talking about quotations. I'm talking about computations

    -- the things you pass to an 'if', the things your source code

    represents when it's being executed. Those aren't lists. You might say

    they're sequences of machine-language operations, but that doesn't

    provide a useful connection to the language for most programmers. You

    could say that they're sequences of virtual operations, but that would

    cripple performance. You could say that they're sequences of

    characters, but that makes manipulating them hard and slow. And so

    on...

     > It makes no sense to do length

    > the way you're picturing on quotations,

     I thought you just said that they're lists. If so, it makes absolute

    sense to do length on them.

     > though their length might be

    > needed to produce another quotation from them. Any optimizations that

    > the compiler might do, such as removing dup drop, should be done in a

    > way invisible to the user.

     That's good to hope for. It's possible to come close if you've chosen

    your abstraction well. Tcl chose its abstraction very poorly, and it

    took them years to salvage their performance.

     > > > It is very useful to have code be

    > > > [represented by] an accessable data structure;

    > > Agreed. When I said "code" I should have said "computations". When you

    > > say "code" you're referring to the stuff that the programmer

    > > manipulates in order to specify the computation.

    > There are no computations. Computations are just a way of thinking

    > about what's actually happening, but they don't exist within the

    > language, as you've said would be impossible. So it's pretty useless

    > to talk about computations at all.

     I don't think both of us understand. (I'm not willing to promise that

    even one of us understands. :-)

    A computation is what you pass to 'if'. It's what the code that you

    type into your editor represents. Deciding what you can do with a

    computation is important. We both know that you can execute a

    computation and destroy a computation (this seems to preclude your

    claim that computations don't exist). I don't know what else you can

    do with a computation. I suppose concatenating them makes sense; if a

    computation is flat, splitting it makes sense too (but the definition

    for "flat" may be different for computations than it is for

    languages), but I don't know what you could do with the two halves.

    Do you know anything else you can do with a computation?

     > Daniel Ehrenberg

     -Billy

## Daniel Ehrenberg — 2005-08-04 02:49:44

    On 8/3/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > Daniel Ehrenberg <microdan@...> wrote:

    > > ...ok, but I don't really see any place for 100% abstract computations

    > > in any programming language,

    >

    > The only purpose for using a programming language is to express

    > computations. I don't know what you mean by 100% abstract, though;

    > perhaps there's something there.

    >

    > > and it's still extremely useful to have

    > > code be a data structure.

    >

    > I believe I agreed with this -- it's useful when you explicitly want

    > to be able to manipulate the code before the computation it implies

    > needs to be run. The problem is that if this abilitity remains open to

    > *all* computations,

    >

    > > The quotation *is* a list, and there's

    > > nothing you could say to make it not.

    >

    > I wouldn't want to do something like that. Quotations are lists.

    >

    > But I'm not talking about quotations. I'm talking about computations

    > -- the things you pass to an 'if', the things your source code

    > represents when it's being executed. Those aren't lists. You might say

    > they're sequences of machine-language operations, but that doesn't

    > provide a useful connection to the language for most programmers. You

    > could say that they're sequences of virtual operations, but that would

    > cripple performance. You could say that they're sequences of

    > characters, but that makes manipulating them hard and slow. And so

    > on...

    >

    > > It makes no sense to do length

    > > the way you're picturing on quotations,

    >

    > I thought you just said that they're lists. If so, it makes absolute

    > sense to do length on them.

    >

    > > though their length might be

    > > needed to produce another quotation from them. Any optimizations that

    > > the compiler might do, such as removing dup drop, should be done in a

    > > way invisible to the user.

    >

    > That's good to hope for. It's possible to come close if you've chosen

    > your abstraction well. Tcl chose its abstraction very poorly, and it

    > took them years to salvage their performance.

    >

    > > > > It is very useful to have code be

    > > > > [represented by] an accessable data structure;

    >

    > > > Agreed. When I said "code" I should have said "computations". When you

    > > > say "code" you're referring to the stuff that the programmer

    > > > manipulates in order to specify the computation.

    >

    > > There are no computations. Computations are just a way of thinking

    > > about what's actually happening, but they don't exist within the

    > > language, as you've said would be impossible. So it's pretty useless

    > > to talk about computations at all.

    >

    > I don't think both of us understand. (I'm not willing to promise that

    > even one of us understands. :-)

    >

    > A computation is what you pass to 'if'. It's what the code that you

    > type into your editor represents. Deciding what you can do with a

    > computation is important. We both know that you can execute a

    > computation and destroy a computation (this seems to preclude your

    > claim that computations don't exist). I don't know what else you can

    > do with a computation. I suppose concatenating them makes sense; if a

    > computation is flat, splitting it makes sense too (but the definition

    > for "flat" may be different for computations than it is for

    > languages), but I don't know what you could do with the two halves.

    >

    > Do you know anything else you can do with a computation?

    >

    > > Daniel Ehrenberg

    >

    > -Billy

     Overall, I really don't understand where this idea of computations is

    comming from. In some implementations, during runtime, it is still the

    quotation, never at all anything else. A computation, as I understand

    it, is a completely abstract concept. Could someone please define it

    better for me?

## William Tanksley, Jr — 2005-08-05 04:50:03

    Daniel Ehrenberg <microdan@...> wrote:

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

    > > A computation is what you pass to 'if'. It's what the code that you

    > > type into your editor represents. Deciding what you can do with a

    > > computation is important. We both know that you can execute a

    > Overall, I really don't understand where this idea of computations is

    > comming from. In some implementations, during runtime, it is still the

    > quotation, never at all anything else. A computation, as I understand

    > it, is a completely abstract concept. Could someone please define it

    > better for me?

     Joy has two ways to express a computation. One example is a quotation,

    the other is a function body. So it's not "never at all anything

    else".

    The concrete concept of "computation" is neccesary in order to compare

    Forth and Joy's conditionals on equal terms, and in order to think

    about the nature of a lazy concatenative language. If we only

    understand "quotations", we'll only be able to work with Joy and

    Factor, not Forth.

    -Billy

## Daniel Ehrenberg — 2005-08-05 14:59:23

    > Joy has two ways to express a computation. One example is a quotation,

    > the other is a function body. So it's not "never at all anything

    > else".

    >

    > The concrete concept of "computation" is neccesary in order to compare

    > Forth and Joy's conditionals on equal terms, and in order to think

    > about the nature of a lazy concatenative language. If we only

    > understand "quotations", we'll only be able to work with Joy and

    > Factor, not Forth.

    >

    > -Billy

     Hmm... ok, but what does that have to do with the abstract concept

    you're talking about where [ dup drop ] is equivalent to [ nop ] ?

## William Tanksley, Jr — 2005-08-06 01:57:15

    Daniel Ehrenberg <microdan@...> wrote:

     > > Joy has two ways to express a computation. One example is a quotation,

    > > the other is a function body. So it's not "never at all anything

    > > else".

    > > The concrete concept of "computation" is neccesary in order to compare

    > > Forth and Joy's conditionals on equal terms, and in order to think

    > > about the nature of a lazy concatenative language. If we only

    > > understand "quotations", we'll only be able to work with Joy and

    > > Factor, not Forth.

    > Hmm... ok, but what does that have to do with the abstract concept

    > you're talking about where [ dup drop ] is equivalent to [ nop ] ?

     As a compuation, the two are the same. As quoted lists, they're

    obviously not. So therefore, quoted lists are not the same as

    computations. This doesn't mean that they _can't_ be used to implement

    computations (although Forth in fact doesn't use them); it just means

    that you should be careful about "leaky abstractions" when lists allow

    you to do things that real computations don't allow.

    -Billy

## Daniel Ehrenberg — 2005-08-06 16:39:28

    On 8/5/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > Daniel Ehrenberg <microdan@...> wrote:

    > > > Joy has two ways to express a computation. One example is a quotation,

    > > > the other is a function body. So it's not "never at all anything

    > > > else".

    >

    > > > The concrete concept of "computation" is neccesary in order to compare

    > > > Forth and Joy's conditionals on equal terms, and in order to think

    > > > about the nature of a lazy concatenative language. If we only

    > > > understand "quotations", we'll only be able to work with Joy and

    > > > Factor, not Forth.

    >

    > > Hmm... ok, but what does that have to do with the abstract concept

    > > you're talking about where [ dup drop ] is equivalent to [ nop ] ?

    >

    > As a compuation, the two are the same. As quoted lists, they're

    > obviously not. So therefore, quoted lists are not the same as

    > computations. This doesn't mean that they _can't_ be used to implement

    > computations (although Forth in fact doesn't use them); it just means

    > that you should be careful about "leaky abstractions" when lists allow

    > you to do things that real computations don't allow.

    >

    > -Billy

     You're using two different meanings of "computation". One is a body of

    code, as you used for the Joy word/quotation thing, and another is the

    abstract meaning of code. Could you define computation in a way that's

    not just by example?

    Daniel Ehrenberg

## William Tanksley, Jr — 2005-08-06 19:34:01

    Daniel Ehrenberg <microdan@...> wrote:

     > You're using two different meanings of "computation". One is a body of

    > code, as you used for the Joy word/quotation thing, and another is the

    > abstract meaning of code. Could you define computation in a way that's

    > not just by example?

     I'm not aware of using two different meanings; I changed from my old

    and incorrect term "code" so that I could have a single meaning.

    Computation as an idea is defined by compexity theory; as an object, a

    computation should have an interface that allows you to do only the

    things that you could do to a computation in the theoretical sense.

     > Daniel Ehrenberg

     -Billy

## Daniel Ehrenberg — 2005-08-06 19:49:15

    > I'm not aware of using two different meanings; I changed from my old

    > and incorrect term "code" so that I could have a single meaning.

    > Computation as an idea is defined by compexity theory; as an object, a

    > computation should have an interface that allows you to do only the

    > things that you could do to a computation in the theoretical sense.

     So what does that have to do with the Joy thing you were talking about?

## William Tanksley, Jr — 2005-08-06 20:12:38

    Daniel Ehrenberg <microdan@...> wrote:

     > > I'm not aware of using two different meanings; I changed from my old

    > > and incorrect term "code" so that I could have a single meaning.

    > > Computation as an idea is defined by compexity theory; as an object, a

    > > computation should have an interface that allows you to do only the

    > > things that you could do to a computation in the theoretical sense.

    > So what does that have to do with the Joy thing you were talking about?

     What "Joy thing"? Sounds like a miscommunication. I wasn't addressing

    anything in Joy. I did use Joy quotations as an example of how Joy

    handles computations, and I explained a problem with that... But I

    wasn't adressing Joy other than as a minor example.

    What do you mean?

    -Billy

## Daniel Ehrenberg — 2005-08-06 21:40:40

    Never mind. I don't really see this conversation going anywhere so I'm

    going to end my part of it right here.

     On 8/6/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

    > Daniel Ehrenberg <microdan@...> wrote:

    > > > I'm not aware of using two different meanings; I changed from my old

    > > > and incorrect term "code" so that I could have a single meaning.

    > > > Computation as an idea is defined by compexity theory; as an object, a

    > > > computation should have an interface that allows you to do only the

    > > > things that you could do to a computation in the theoretical sense.

    >

    > > So what does that have to do with the Joy thing you were talking about?

    >

    > What "Joy thing"? Sounds like a miscommunication. I wasn't addressing

    > anything in Joy. I did use Joy quotations as an example of how Joy

    > handles computations, and I explained a problem with that... But I

    > wasn't adressing Joy other than as a minor example.

    >

    > What do you mean?

    >

    > -Billy

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

## William Tanksley, Jr — 2005-08-06 23:38:11

    Daniel Ehrenberg <microdan@...> wrote:

     > Never mind. I don't really see this conversation going anywhere so I'm

    > going to end my part of it right here.

     Okay. Thank you both for talking -- I apologize that I wasn't able to

    answer your questions.

    -Billy

## Narcoleptic Electron — 2005-08-07 02:31:23

    On 8/6/05, Daniel Ehrenberg <microdan@...> wrote:

     > Could you define computation in a way that's

    > not just by example?

     Sorry for carrying this on, but I am interested in knowing the

    definition of a computation.  This is fundamentally important.  Here's

    my stab at it...

    Lexicographically, "computing" is something that a "computer" does.  I

    think we can all agree on that.

    From here, I would define a computation as "a change from one internal

    machine state to another".  By this, it is possible for a computation

    to be comprised of simpler computations.

    Source code is a "description" of such a change of machine state, not

    the change itself.  It is used to generate the change it describes.

    It is like thoughts (...computations) vs. language (...source code).

    It is nonsensical to say that a thought can exist inside a language.

    To convey a thought to another person, one can only *describe* the

    thought using language, whereby the listening person will attempt to

    recreate the thought from the description provided.

    In this sense, I am programming all of you mailing list recipients

    right now, and the message that you are reading is the source code.  I

    have indicated the initial machine state (the problem statement, and

    what we can all agree on about this problem), and have provided a set

    of translations (logical arguments) to take you to a final machine

    state (the conclusion I have drawn).  If I have done this 100%

    correctly (which is nearly impossible, considering the complexity of

    the state in question), you will all have reached the same conclusion

    as me.

    How did I do?

## phimvt@lurac.latrobe.edu.au — 2005-08-08 03:01:50

    On Sat, 6 Aug 2005, Narcoleptic Electron wrote:

    I find myself in agreement with some but not all of the things you say.

    First, here is what I came up with before seeing your definition.

    The  I shall comment on yours.

    Computations happen at runtime. A computation begins at the start of a run

    of a program, and it ends when then the run finishes.  A computatation

    starts with an initial state of the computing machine and it ends with a

    final state. Even in the case where the program computes the identity

    function ("noop"), the initial and the final state are different - its the

    difference between "start" and "done".  In between the initial state and

    the final state a sequence of changes occurs.  So, one way to think of a

    computation is as a sequence of changes.  A change is what occurs between

    two successive states.  So another way is to think of a computation is as

    a sequence of states. The two views are entirely equivalent.

    What counts as the state of the machine depends entirely on the chosen

    level of description. The machine may be a virtual machine: the Joy

    interpreter, the "inner interpreter" of Forth, the SECD machine of Lisp

    the Pcode machine of Pascal, and so on. Or it may be the actual hardware,

    at various possible levels of description. In just about all cases a

    single step of a virtual machine is implemented as several steps of the

    underlying machine. Indeed, there may be a whole tower of more and more

    finegrained descriptions (virtual machines) down to the rock bottom.,

    perhaps at the quantum level.

    The sequence of changes and the sequence of states seem to bear an

    interesting relation to the program. This will be especially true if the

    program is written

    in a concatenative language, which to a large part consists of sequences

    of atomic programs. All three kinds of sequences can be concatenated

    to form larger sequences. So, what is the relation between on the one

    hand the program sequence and the changes/states sequences?

    Clearly the closest correspondence should be expected for the

    sequences of changes or states of the virtual machine.

    Only in exceptional cases will there be a 1-1 correspondence, that will

    only happen if the program has no conditionals, no loops, no calls of

    defined functions. In all other cases there will only be short stretches

    of correspondence between the program and the changes. The correspondence

    will occur precisely at those stretches of program that are flat. Any such

    stretch is of course mirrored by a stretch of correspondence between the

    program and the states.

    If concatenations of programs denote compositions of functions,

    then do concatenations of sequences of changes denote anything similar?

    Clearly not, they are not syntactic entities and hence do not

    denote anything. A single change is just a pair of before/after states,

    and a sequence of n changes is just a sequence of (n+1) states.

    Also, there is a many-to-one correspondence between the functions

    denoted by programs and the changes. For, consider the change of

    an internal variable from -3 to +3. This could be due to a program

    that takes the absolute value, or a program that adds 6, or a program

    that doubles negative numbers and then adds 9, or by ...

    But I must stop and discuss your contribution.

    > On 8/6/05, Daniel Ehrenberg <microdan@...> wrote:

    > > Could you define computation in a way that's

    > > not just by example?

    >

    > Sorry for carrying this on, but I am interested in knowing the

    > definition of a computation.  This is fundamentally important.  Here's

    > my stab at it...

    >

    > Lexicographically, "computing" is something that a "computer" does.  I

    > think we can all agree on that.

    That is taking "lexicographically" in the normal (not computerese)

    sense, yes.

    > From here, I would define a computation as "a change from one internal

    > machine state to another".  By this, it is possible for a computation

    > to be comprised of simpler computations.

    The tower of virtual machines, yes.

    > Source code is a "description" of such a change of machine state, not

    > the change itself.  It is used to generate the change it describes.

    Entirely agree so far.

    > It is like thoughts (...computations)

    Yes

    >                                       vs. language (...source code).

    I don't follow at all. But you really mean source code (written, of

    course, in some language).

    > It is nonsensical to say that a thought can exist inside a language.

    Nor can a thought exist inside an utterance in a language.

    > To convey a thought to another person, one can only *describe* the

    > thought using language, whereby the listening person will attempt to

    > recreate the thought from the description provided.

    And the description is an utterance (spoken of written) in a language.

    Different descriptions (programs in your analogy) can lead to the

    same thought (final state of the computation). Yes. For example

    writers of textbooks attempt to write better descriptions of

    thought processes than those written by the original authors.

    > In this sense, I am programming all of you mailing list recipients

    > right now, and the message that you are reading is the source code.  I

    > have indicated the initial machine state (the problem statement, and

    > what we can all agree on about this problem), and have provided a set

    > of translations (logical arguments) to take you to a final machine

    > state (the conclusion I have drawn).  If I have done this 100%

    > correctly (which is nearly impossible, considering the complexity of

    > the state in question), you will all have reached the same conclusion

    > as me.

    >

    > How did I do?

    Pretty well, I think. Some nice and interesting thoughts.

      - Manfred

## Narcoleptic Electron — 2005-08-08 04:51:31

    On 8/7/05, phimvt@... <phimvt@...> wrote:

     > Computations happen at runtime.

     Yes.  This includes "run time of a compiler".

    I agree with the rest of what you wrote.  Well said.

     > On Sat, 6 Aug 2005, Narcoleptic Electron wrote:

    > > It is like thoughts (...computations)

    >

    > Yes

    >

    > >                                       vs. language (...source code).

    >

    > I don't follow at all. But you really mean source code (written, of

    > course, in some language).

     My mistake.  I added the parenthetical translations as an afterthought

    and, as should be expected, they are incorrect.  The metaphor should

    be: human thought = machine computation, human language = programming

    language, utterance in human language = source code.

     > > It is nonsensical to say that a thought can exist inside a language.

    >

    > Nor can a thought exist inside an utterance in a language.

     Indeed.  This is what I meant to write...

     > Some nice and interesting thoughts.

     Thank you.  It looks like we are on the same track, minus my

    "programming errors".  Thanks for helping to debug my email message.

     >   - Manfred

     N. Electron

## Ivan Tomac — 2005-08-10 15:03:47

    I'm a bit late to join this discussion but I'm starting to like the

    idea of flat languages. If nothing else I think it's worth exploring

    them further until we can say for sure whether their advantages

    outweigh the disadvantages.

    I have a few questions though. They may have already been answered

    (I've tried to read all the posts on topic so far but there are just

    so many! I'm sure I missed some things) so I apologize in advance if

    that's the case.

    If I remember it right you mentioned in one of the posts (can't find

    it right now, otherwise I'd quote it) that the main (only?) things

    that prevent Joy from being flat are it's definitions and blocks. The

    problem with definitions is easy enough to solve which leaves only

    code blocks. How do you get around that problem? How do you flatten

    quotations?

    Do you simply treat them as atomic values so that no quotation can

    ever be split into smaller quotations? Or is there more to it then

    that? What else is neccesary in order for a language to be truly flat?

    --- In concatenative@yahoogroups.com, "William Tanksley, Jr"

    <wtanksleyjr@g...> wrote:

     > > I was simply pointing

    > > out some things that may rely on the tree representation of code,

     at

     > > least in their current form.

    >

    > That's true. All I can say, then, is that if you want to express

     your

     > code as a tree you still can. Flat languages are graphs, not trees;

    > but if the programmer wishes, he can confine his work to the shape

     of

     > a tree.

     This part confused me a bit - how is the code in a flat language a

    graph?

     > -Billy

     Ivan

## Narcoleptic Electron — 2005-08-10 15:55:18

    On 8/10/05, Ivan Tomac <e1_t@...> wrote:

     > How do you flatten quotations?

    > Do you simply treat them as atomic values so that no quotation can

    > ever be split into smaller quotations? Or is there more to it then

    > that? What else is neccesary in order for a language to be truly flat?

     A short answer:

    String literals.

    A long answer:

    In a flat language that I've been developing for a while now (no

    website yet... no time), the only literal in the language is a string,

    which is indicated by enclosing square brackets (i.e. [I'm a string

    literal.]).  Nesting is allowed (i.e. [[inner1] [inner2]] pushes the

    string "[inner1] [inner2]", not including the double quotes), and

    unbalanced brackets must be escaped.

    A string literal means "push the string value described herein onto

    the stack".  If the literal is followed by whitespace, this means

    "treat the string on the stack as a name, and replace it with its

    defined value".

    Thus:

    [2][#]  [3][#]  [+]

    -> Push string "2", push string "#", replace "#" with program and

    execute (replacing "2" on stack with numeric value for 2), etc.

    Results in only the numeric value 5 on the stack.

    There are no numeric or quotation literals; just string literals.  All

    data values start as string values on the stack, which then converted

    to various value types by different programs (such as "#", which

    converts a string to a number).

    (Even comments are handled this way: [This is a comment.][comment]

    puts the comment string on the stack, then drops it.)

    Note that a defined name can literally have any character, including

    spaces.  For example, the identity program is bound to an empty string

    (i.e. []), which allows the following:

    [string 1][]  [string 2][]

    -> Leaves "string 1" and "string 2" values on the stack.

    A quotation would be as follows:

    [[2][#] [3][#] [+]][code]

    -> Pushes the quotation string onto the stack, then calls "code" which

    converts the string to code and evaluates.  (I haven't settled on my

    names yet, but you get the idea.)

    When quotations are handled as strings, they can be split up any which way.

    (As far as my language syntax goes: that's all there is.  The only

    "special characters" used by the parser are "[", "]" and whitespace.)

    Sorry if I've taken this too far off-topic: I just wanted to

    illustrate what my solution to this has been.  I've been interested in

    flatness for quite some time.

## sa@dfa.com — 2005-08-10 16:01:26

    well that's certainly clever.

    i'd like to hear more details about '#' and 'code'.

    concatenative@yahoogroups.com wrote on 08/10/2005 11:55:18 AM:

     > On 8/10/05, Ivan Tomac <e1_t@...> wrote:

    > > How do you flatten quotations?

    > > Do you simply treat them as atomic values so that no quotation can

    > > ever be split into smaller quotations? Or is there more to it then

    > > that? What else is neccesary in order for a language to be truly flat?

    >

    > A short answer:

    >

    > String literals.

    >

    > A long answer:

    >

    > In a flat language that I've been developing for a while now (no

    > website yet... no time), the only literal in the language is a string,

    > which is indicated by enclosing square brackets (i.e. [I'm a string

    > literal.]).  Nesting is allowed (i.e. [[inner1] [inner2]] pushes the

    > string "[inner1] [inner2]", not including the double quotes), and

    > unbalanced brackets must be escaped.

    >

    > A string literal means "push the string value described herein onto

    > the stack".  If the literal is followed by whitespace, this means

    > "treat the string on the stack as a name, and replace it with its

    > defined value".

    >

    > Thus:

    >

    > [2][#]  [3][#]  [+]

    > -> Push string "2", push string "#", replace "#" with program and

    > execute (replacing "2" on stack with numeric value for 2), etc.

    > Results in only the numeric value 5 on the stack.

    >

    > There are no numeric or quotation literals; just string literals.  All

    > data values start as string values on the stack, which then converted

    > to various value types by different programs (such as "#", which

    > converts a string to a number).

    >

    > (Even comments are handled this way: [This is a comment.][comment]

    > puts the comment string on the stack, then drops it.)

    >

    > Note that a defined name can literally have any character, including

    > spaces.  For example, the identity program is bound to an empty string

    > (i.e. []), which allows the following:

    >

    > [string 1][]  [string 2][]

    > -> Leaves "string 1" and "string 2" values on the stack.

    >

    > A quotation would be as follows:

    >

    > [[2][#] [3][#] [+]][code]

    > -> Pushes the quotation string onto the stack, then calls "code" which

    > converts the string to code and evaluates.  (I haven't settled on my

    > names yet, but you get the idea.)

    >

    > When quotations are handled as strings, they can be split up any which

     way.

     >

    > (As far as my language syntax goes: that's all there is.  The only

    > "special characters" used by the parser are "[", "]" and whitespace.)

    >

    > Sorry if I've taken this too far off-topic: I just wanted to

    > illustrate what my solution to this has been.  I've been interested in

    > flatness for quite some time.

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

## Narcoleptic Electron — 2005-08-10 16:01:31

    I wrote:

     > On 8/10/05, Ivan Tomac <e1_t@...> wrote:

    > > How do you flatten quotations?

    > > Do you simply treat them as atomic values so that no quotation can

    > > ever be split into smaller quotations? Or is there more to it then

    > > that? What else is neccesary in order for a language to be truly flat?

    >

    > A short answer:

    >

    > String literals.

     PS: I realize that this isn't *absolutely* flat, because string

    enclosures must be balanced, but I think that this is as flat as we

    could get before sinking into a turing tarpit.

## John.Cowan — 2005-08-10 16:05:53

    Narcoleptic Electron scripsit:

     > > String literals.

    >

    > PS: I realize that this isn't *absolutely* flat, because string

    > enclosures must be balanced, but I think that this is as flat as we

    > could get before sinking into a turing tarpit.

     I think it's just as flat as Joy or Forth, no more, no less.

    --

    John Cowan  jcowan@...  www.reutershealth.com  www.ccil.org/~cowan

    Rather than making ill-conceived suggestions for improvement based on

    uninformed guesses about established conventions in a field of study with

    which familiarity is limited, it is sometimes better to stick to merely

    observing the usage and listening to the explanations offered, inserting

    only questions as needed to fill in gaps in understanding. --Peter Constable

## Narcoleptic Electron — 2005-08-10 16:14:45

    On 8/10/05, John.Cowan <cowan@...> wrote:

     > Narcoleptic Electron scripsit:

    >

    > > > String literals.

    > >

    > > PS: I realize that this isn't *absolutely* flat, because string

    > > enclosures must be balanced, but I think that this is as flat as we

    > > could get before sinking into a turing tarpit.

    >

    > I think it's just as flat as Joy or Forth, no more, no less.

     No: Joy has list literals and string literals.  My language removes

    list literals, making it a bit more flat.

## Narcoleptic Electron — 2005-08-10 16:24:59

    On 8/10/05, sa@... <sa@...> wrote:

     > well that's certainly clever.

     Thanks.  Your shoulders are two of many that I have been perched on in

    thinking it up...

     > i'd like to hear more details about '#' and 'code'.

     "#" and "code" are just names of programs.

    For the following code:

    [42][#]

    The following happens:

    - The string "42" is pushed onto the stack.

    - The string "#" is pushed onto the stack.

    - The string "#" is popped and looked up in the dictionary.  The value

    it is bound to is pushed onto the stack; in this case a program that

    converts text to numbers.

    - The program on the top of the stack is executed, which in this case

    pops the string "42" below it and pushes its numerical equivalent.

    "code" is the program that parses and evaluates code.

    I will try to get my act together and put up a website to explain

    further about how programs are defined, etc., as well as actually

    implementing some of this stuff in a fashion usable to others...

## John.Cowan — 2005-08-10 16:34:51

    Narcoleptic Electron scripsit:

     > No: Joy has list literals and string literals.  My language removes

    > list literals, making it a bit more flat.

     It would be trivial to write a string->list word in Joy making list literals

    unnecessary.

    --

    What asininity could I have uttered     John Cowan <jcowan@...>

    that they applaud me thus?              http://www.reutershealth.com

            --Phocion, Greek orator         http://www.ccil.org/~cowan

## Narcoleptic Electron — 2005-08-10 16:41:46

    Addendum:

     On 8/10/05, Narcoleptic Electron <narcoleptic.electron@...> wrote:

    > For the following code:

    >

    > [42][#]

    >

    > The following happens:

    > - The string "42" is pushed onto the stack.

    > - The string "#" is pushed onto the stack.

    > - The string "#" is popped and looked up in the dictionary.  The value

    > it is bound to is pushed onto the stack; in this case a program that

    > converts text to numbers.

    The above step happens because whitespace is reached.  When whitespace

    is encountered after a string literal, the string at the top of the

    stack (pushed there by the literal) is treated as a name and gets the

    "lookup and replace" treatment.

    [#][#] would try to convert the string "#" to a number, which would of

    course fail.

    [#][#][] would push two strings containing the character "#" onto the

    stack, and not do anything else with them.  (The [] program leaves the

    stack unchanged.)

    > - The program on the top of the stack is executed, which in this case

    > pops the string "42" below it and pushes its numerical equivalent.

## Narcoleptic Electron — 2005-08-10 16:54:22

    On 8/10/05, John.Cowan <cowan@...> wrote:

     > It would be trivial to write a string->list word in Joy making list literals

    > unnecessary.

     Yes.  I was attempting to illustrate the flattest possible non-tarpit

    language for the sake of discussion.  You're right: there is a

    flatter subset of Joy.

    However, not all non-flat parts of Joy can be removed this way.

    Definitions in Joy are not flat, whereas they are in my language

    (which I really should name).  Explaining the details might be a

    little much for this thread, but I can give more info if anyone wants

    it.

## Ivan Tomac — 2005-08-10 16:59:21

    --- In concatenative@yahoogroups.com, Narcoleptic Electron

    <narcoleptic.electron@g...> wrote:

     > On 8/10/05, John.Cowan <cowan@c...> wrote:

    > > Narcoleptic Electron scripsit:

    > >

    > > > > String literals.

    > > >

    > > > PS: I realize that this isn't *absolutely* flat, because string

    > > > enclosures must be balanced, but I think that this is as flat

     as we

     > > > could get before sinking into a turing tarpit.

    > >

    > > I think it's just as flat as Joy or Forth, no more, no less.

    >

    > No: Joy has list literals and string literals.  My language removes

    > list literals, making it a bit more flat.

     Why does that make the language more flat.

    I would think it would be more worthwhile to explore flatness from a

    slightly higher level and still have strings and lists and integers

    but add functions or code blocks or computations, whatever you want to

    call them, as atoms that cannot be decomposed. Only executed,

    concatenated or destroyed as Billy suggested.

    I'm not sure if I completely misunderstood the concept of flatness

    however. It's almost 3am here and my brain is shutting down :)

    I think I'll have to re-read the whole thread from the beginning some

    time this week..

    Ivan

## Narcoleptic Electron — 2005-08-10 17:17:09

    On 8/10/05, Ivan Tomac <e1_t@...> wrote:

     > --- In concatenative@yahoogroups.com, Narcoleptic Electron

    > <narcoleptic.electron@g...> wrote:

    > > No: Joy has list literals and string literals.  My language removes

    > > list literals, making it a bit more flat.

    >

    > Why does that make the language more flat.

    >

    > I would think it would be more worthwhile to explore flatness from a

    > slightly higher level and still have strings and lists and integers

    > but add functions or code blocks or computations, whatever you want to

    > call them, as atoms that cannot be decomposed. Only executed,

    > concatenated or destroyed as Billy suggested.

    > I'm not sure if I completely misunderstood the concept of flatness

    > however. It's almost 3am here and my brain is shutting down :)

     As I recall, the scenario that started this discussion was that of

    breaking up a quotation literal, binding each half to a different

    name, and reconstituting it later.  That's the type of flatness [I

    think] we're talking about.

    "Code blocks" and "computations" are very different things.  Code

    block = quotation; computation = internal machine state change.  The

    former can exist in source code; the latter can't.  A quotation

    describes a computation.

## Martin Young — 2005-08-10 20:22:18

    I've only been half following this discussion - apologies if I've

    got the wrong end of the stick.  I was just doing a little bit of on-

    paper doodling and came up with the following idea:

    The execution system has two stacks: a data stack, and a dip stack.

    These are initially empty.

    It also has a stack/queue of incoming symbols - the program.

    Initially the program queue contains the program as a series of

    atoms (symbols or numbers).  Symbols are removed from the program

    stack and "executed" the discarded.

    There are no lists, strings, tuples or suchlike in the language.

    I've described the dip stack in previous posts to this list

    concerning how a Joy-like language, MONKEY, operates.  In short, it

    moves the state storage associated with a dip out of the execution

    system and into the language's domain.  The atom "move" moves the

    top value from the data stack on the dip stack.  The atom "unmove"

    does the converse.  All the iterative and recursive conbinators can

    be constructed on top of the data/dip stack thus moving things like

    recursion state and mechanics into the langugage's domain.

    The addition of two new operators, snatch and unsnatch may make the

    language flat.

    "snatch" takes one integer value (N) from the data stack then

    arranges for the next N symbols from the program queue to be

    conbined into an opaque Lump and pushed onto the dip

    stack.  "unsnatch" pulls one Lump from the snatch stack and pushes

    its content onto the front of the program queue.  Their presence on

    the dip stack means that suitably polymorphic symbols such as swap

    and dip can maniplate Lumps but they, the Lumps, cannot be

    decomposed.

    The structure previously offered by quotations (i.e. the ability to

    manipulate pieces of program as entities) is replaced by the snatch

    functionality.  The key change is that the program's logical

    structure exists (and can be changed) at runtime, but not in the

    source code.  That is, it is flat.

    I've been trying to build an example.  I started with a program

    which prints the first N fibonaci numbers.  One way of writing it is

    as two words (in MONKEY syntax).

    fibstep ==

    {{

        dup

        { + } dip

        swap

        dup .

    }}

    nfib ==

    {{

        1 . 1 .

        { 1 1 { fibstep } } dip

        repeat

        drop drop

    }}

    I've started by converting fibstep into flat MONKEY:

    dup 1 snatch + move unsnatch swap dup .

    I think this works.  Sorry about the lack of formatting.  Not sure

    how to format source code that has no internal structure...

    I'm currently puzzling over how to write the "repeat" word, but I

    thought I'd post this before I discover that it's impossible...

    --- In concatenative@yahoogroups.com, Narcoleptic Electron

    <narcoleptic.electron@g...> wrote:

     > As I recall, the scenario that started this discussion was that of

    > breaking up a quotation literal, binding each half to a different

    > name, and reconstituting it later.  That's the type of flatness [I

    > think] we're talking about.

    >

    > "Code blocks" and "computations" are very different things.  Code

    > block = quotation; computation = internal machine state change.

     The

     > former can exist in source code; the latter can't.  A quotation

    > describes a computation.

## Ivan Tomac — 2005-08-11 01:33:06

    --- In concatenative@yahoogroups.com, Narcoleptic Electron

    <narcoleptic.electron@g...> wrote:

     > On 8/10/05, Ivan Tomac <e1_t@y...> wrote:

    > > --- In concatenative@yahoogroups.com, Narcoleptic Electron

    > > <narcoleptic.electron@g...> wrote:

    > > > No: Joy has list literals and string literals.  My language

     removes

     > > > list literals, making it a bit more flat.

    > >

    > > Why does that make the language more flat.

    > >

    > > I would think it would be more worthwhile to explore flatness

     from a

     > > slightly higher level and still have strings and lists and

     integers

     > > but add functions or code blocks or computations, whatever you

     want to

     > > call them, as atoms that cannot be decomposed. Only executed,

    > > concatenated or destroyed as Billy suggested.

    > > I'm not sure if I completely misunderstood the concept of flatness

    > > however. It's almost 3am here and my brain is shutting down :)

    >

    > As I recall, the scenario that started this discussion was that of

    > breaking up a quotation literal, binding each half to a different

    > name, and reconstituting it later.  That's the type of flatness [I

    > think] we're talking about.

    >

    > "Code blocks" and "computations" are very different things.  Code

    > block = quotation; computation = internal machine state change.  The

    > former can exist in source code; the latter can't.  A quotation

    > describes a computation.

     You missed my point. It doesn't matter what it's called as long as the

    language has functions you can pass around on stack and manipulate.

    But something that's more limited then quotations in Joy - rather then

    have quotations that are at the same time both lists and code, have 2

    different types, one for lists and one for code. The latter can only

    be executed, duplicated, concatenated, shuffled or destroyed. It

    cannot be split.

    What I'm asking is is this enough for a language to be flat?

    I've just re-read some of the early posts on the topic and the

    following definition (along with the posts about flatForth) got me

    thinking:

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

     >Flat: Flatness is the absence of all syntactic (compile-time)

    >nesting.

    >A test for flatness: a definition is flat if and only if it can

    >be cut apart into two valid definitions on any blank space. A

    >definition is partially flat to the extent that it can be so

    >cut. This could be expressed numericly, by dividing the number

    >of cuttable spaces by the total number of spaces.

     I think I understand now what Billy meant by saying that a flat

    language is a graph rather then a tree.

    I'm not sure whether it answers my question though. If you have a type

    of code blocks or functions and if each code block is an atom then

    doesn't that make the language flat regardless of whether a function

    in such a language has nesting or not? Why am I asking that? Because

    if each code block is an atom then [1 dup 2 * drop] and [1 dup drop]

    and [1] are all equivalent and if one of those is nested inside

    another code block it can be replaced by a reference to an existing

    code block so you can still get a graph structure as opposed to a

    tree.

## Narcoleptic Electron — 2005-08-11 18:04:07

    On 8/10/05, Ivan Tomac <e1_t@...> wrote:

     > If you have a type

    > of code blocks or functions and if each code block is an atom then

    > doesn't that make the language flat regardless of whether a function

    > in such a language has nesting or not? Why am I asking that? Because

    > if each code block is an atom then [1 dup 2 * drop] and [1 dup drop]

    > and [1] are all equivalent and if one of those is nested inside

    > another code block it can be replaced by a reference to an existing

    > code block so you can still get a graph structure as opposed to a

    > tree.

     This won't work because the only way to determine equivalence of two

    computations is to perform the computations.  So there is no way to do

    the pre-execution optimization you describe, wherein [1 dup drop] and

    [1] are replaced with references to the same computation object.

    (Maybe I'm misunderstanding you...)

## Narcoleptic Electron — 2005-08-11 18:06:58

    Oops...

     On 8/11/05, Narcoleptic Electron <narcoleptic.electron@...> wrote:

    > On 8/10/05, Ivan Tomac <e1_t@...> wrote:

    > > If you have a type

    > > of code blocks or functions and if each code block is an atom then

    > > doesn't that make the language flat regardless of whether a function

    > > in such a language has nesting or not? Why am I asking that? Because

    > > if each code block is an atom then [1 dup 2 * drop] and [1 dup drop]

    > > and [1] are all equivalent and if one of those is nested inside

    > > another code block it can be replaced by a reference to an existing

    > > code block so you can still get a graph structure as opposed to a

    > > tree.

    >

    > This won't work because the only way to determine equivalence of two

    > computations is to perform the computations.  So there is no way to do

    > the pre-execution optimization you describe, wherein [1 dup drop] and

    > [1] are replaced with references to the same computation object.

    Sorry: replace "computation object" above with "quotation".

    More explanation: because a computation is a change of machine state,

    the only way to determine if two pieces of code will result in the

    same computation (i.e. machine state delta) is to do each computation

    and compare the resulting machine state of each.

## Narcoleptic Electron — 2005-08-11 18:24:03

    On 8/10/05, Martin Young <martin@...> wrote:

     > The execution system has two stacks: a data stack, and a dip stack.

    > These are initially empty.

     I like the idea of making everything in the language explicit; eg.

    creating the dip stack to remove the magic of the "dip" program.  This

    is similar to XY, but taken a step further.

     > fibstep ==

    > {{

    >     dup

    >     { + } dip

    >     swap

    >     dup .

    > }}

    >

    > nfib ==

    > {{

    >     1 . 1 .

    >     { 1 1 { fibstep } } dip

    >     repeat

    >     drop drop

    > }}

    >

    > I've started by converting fibstep into flat MONKEY:

    >

    > dup 1 snatch + move unsnatch swap dup .

     This type of solution has been discussed before (instead of

    parentheses, specifying the number of programs to "read ahead" and

    stick into a quotation).  Sorry I can't find it at the moment.  You

    may be the first to have implemented this idea, though.  (Although XY

    might have something similar?)

    One question: is there an easy way to create a string in your language?

## Martin Young — 2005-08-11 21:10:38

    --- In concatenative@yahoogroups.com, Narcoleptic Electron

    <narcoleptic.electron@g...> wrote:

     > On 8/10/05, Martin Young <martin@e...> wrote:

    > > The execution system has two stacks: a data stack, and a dip

     stack.

     > > These are initially empty.

    >

    > I like the idea of making everything in the language explicit; eg.

    > creating the dip stack to remove the magic of the "dip" program.

     This

     > is similar to XY, but taken a step further.

     It also removes the magic of recursion and itteration - everything

    this is built from move and unmove primitives - it's analogous to

    explicit continuation manipulation.  For example, this post

    <http://groups.yahoo.com/group/concatenative/message/2122> shows an

    implementation of linrec.

     > This type of solution has been discussed before (instead of

    > parentheses, specifying the number of programs to "read ahead" and

    > stick into a quotation).  Sorry I can't find it at the moment.  You

    > may be the first to have implemented this idea, though.  (Although

     XY

     > might have something similar?)

     Ah, sorry, missed that.  As I said I haven't really been paying

    attention.  I saw some bits in a similar vein and assumed they were

    parse-time constructs.  Snatch and unsnatch are runtime (i.e. the

    program can construct new, parameterised length snatches on the fly).

     > One question: is there an easy way to create a string in your

     language?

    Normally MONKEY uses lists of integers as atrings.  The parser has

    syntactic sugar for strings whereby text inbetween double quotes is

    converted into a list.  E.g.  "abcde" in the source would be

    converted into the list literal [ 97 98 99 100 101 ] at parse time.

    Flat MONKEY could do he same but converting into e.g "5 snatch 97 98

    99 100 101" instead.  A string would thus be opaque until it's

    unsnatched whereupon its execution would cause its conponent

    characters to appear on the data stack.

    To be honest, I'm unconvinced that snatching (or read-ahead) is very

    useful.  ISTM, it makes programs even harder to write and optimise

    that normal.

## stevan apter — 2005-08-11 21:57:07

    ----- Original Message -----

    From: "Martin Young" <martin@...>

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, August 11, 2005 5:10 PM

    Subject: [stack] Re: an exchange on flatness

    --- In concatenative@yahoogroups.com, Narcoleptic Electron

    <narcoleptic.electron@g...> wrote:

    > On 8/10/05, Martin Young <martin@e...> wrote:

    > > The execution system has two stacks: a data stack, and a dip

    stack.

    > > These are initially empty.

    >

    > I like the idea of making everything in the language explicit; eg.

    > creating the dip stack to remove the magic of the "dip" program.

    This

    > is similar to XY, but taken a step further.

    It also removes the magic of recursion and itteration - everything

    this is built from move and unmove primitives - it's analogous to

    explicit continuation manipulation.  For example, this post

    <http://groups.yahoo.com/group/concatenative/message/2122> shows an

    implementation of linrec.

    --------------

    a few of joy's combinators in XY:

    ; i             / ;

    ; x             dup i ;

    ; b             { [p q] p i q i } ;

    ; y             [dup cons] swap , dup cons i ;

    ; cleave        { [x p q] x p i x q i } ;

    ; construct     { [p P] } ;

    ; slip          => / <= ;

    ; 2slip         => => / <= <= ;

    ; dip           swap slip ;

    ; 2dip          -rot 2slip ;

    ; ifte  { [c t e] [e t] _x c infra* true? @ i } ;

    ; if            pair swap zero? @ i ;

    ; branch        [] if ;

    ; cond          { [a] a #: 1 = [a *: i] [_x <- a cond.] if } ;

    ; cond.         { [[[b T] A]] b T [A cond] ifte } ;

    ; infra         { [a p] a @: [a p i] [S/ a <- p i S\] if } ;

    ; infra*        infra |: *: ;

    ; unary         { [n p] G\ n -: #. p map _x n -: _. swap , <- } ;

    ; map           [jump] [each* rot => map <= swons] [pop] ifte ;

    ; each*         => uncons <= tuck 2slip ;

    ; filter        { [a p] a p map &: a @. } ;

    ; split         { [a p] a p map dup ~: pair a swap [&: @] each/ i } ;

    ; some?         { [a p] a p map 1 swap _in } ;

    ; all?          { [a p] a p map 0 swap _in ~: } ;

    ; step          { [a p] a [a uncons p dip p _z] branch } ;

    ; fold          [swap] dip step ;

    ; fold!         { [a s p] S/ a s p fold!. S\ } ;

    ; fold!.        { [a s p] a [s 1 a _ s a *: p i p _z] [s] if } ;

    ; linrec        { [c t r s] c i c t r s _x linrec. } ;

    ; linrec.       { [b c t r s x] x <- b t [r i c t r s linrec s i] if } ;

    ; tailrec       [] linrec ;

    ; binrec        { [p t r s] p i p t r s _x binrec. } ;

    ; binrec.       { [b p t r s x] x <- b t [r i p t r s binrec.. s i] if } ;

    ; binrec..      { [a b p t r s] a p t r s binrec b p t r s binrec } ;

    ; genrec        { [p t r s] p i p t r s _x genrec. } ;

    ; genrec.       { [b p t r s x] x <- b t [r i p t r s genrec s i] if } ;

    ; primrec       { [n p c] p i 1 n 1 + c primrec. } ;

    ; primrec.      { [k n c] k n = [] [k c i k 1 + n c _z] if } ;

    ; primrec-      [zero?] -rot swap [pop] swap , swap [dup pred] swap linrec ;

    see http://www.nsl.com/k/xy/xy.htm for details

    > This type of solution has been discussed before (instead of

    > parentheses, specifying the number of programs to "read ahead" and

    > stick into a quotation).  Sorry I can't find it at the moment.  You

    > may be the first to have implemented this idea, though.  (Although

    XY

    > might have something similar?)

    Ah, sorry, missed that.  As I said I haven't really been paying

    attention.  I saw some bits in a similar vein and assumed they were

    parse-time constructs.  Snatch and unsnatch are runtime (i.e. the

    program can construct new, parameterised length snatches on the fly).

    > One question: is there an easy way to create a string in your

    language?

    Normally MONKEY uses lists of integers as atrings.  The parser has

    syntactic sugar for strings whereby text inbetween double quotes is

    converted into a list.  E.g.  "abcde" in the source would be

    converted into the list literal [ 97 98 99 100 101 ] at parse time.

    Flat MONKEY could do he same but converting into e.g "5 snatch 97 98

    99 100 101" instead.  A string would thus be opaque until it's

    unsnatched whereupon its execution would cause its conponent

    characters to appear on the data stack.

    To be honest, I'm unconvinced that snatching (or read-ahead) is very

    useful.  ISTM, it makes programs even harder to write and optimise

    that normal.

    Yahoo! Groups Links

## Martin Young — 2005-08-11 22:06:54

    Stevan,

    I notice that your recursive combinators are still explicitly

    recursive

    themselves.  E.g.

     > ; linrec        { [c t r s] c i c t r s _x linrec. } ;

    > ; linrec.       { [b c t r s x] x <- b t [r i c t r s linrec s i]

     if } ;

    With MONKEY I set out to remove all such explicit recursion from the

    base language.  That is, the only way to perform recursion is with

    the recursive combinations where are, in turn, built on non-

    recursive primitives.  This is what I meant about removing the magic

    of recursion (borrowing Narcoleptic's words).

    I had an idea that this would make the language more amenable to

    optimisation and compilation.  I don't have a good theoretical basis

    for this other than a very little experience.

    -Martin.

## stevan apter — 2005-08-11 23:30:20

    ----- Original Message -----

    From: "Martin Young" <martin@...>

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, August 11, 2005 6:06 PM

    Subject: [stack] Re: an exchange on flatness

    Stevan,

    I notice that your recursive combinators are still explicitly

    recursive

    themselves.  E.g.

    > ; linrec        { [c t r s] c i c t r s _x linrec. } ;

    > ; linrec.       { [b c t r s x] x <- b t [r i c t r s linrec s i] if } ;

    ---------

    the recursion is an illusion.  in XY, invocation of

    a defined word causes the definition to be pushed onto

    the queue.  is this very different from the use of

    the 'repeat' word in your definition of linrec?

    ---------

    With MONKEY I set out to remove all such explicit recursion from the

    base language.  That is, the only way to perform recursion is with

    the recursive combinations where are, in turn, built on non-

    recursive primitives.  This is what I meant about removing the magic

    of recursion (borrowing Narcoleptic's words).

    I had an idea that this would make the language more amenable to

    optimisation and compilation.  I don't have a good theoretical basis

    for this other than a very little experience.

    -Martin.

    Yahoo! Groups Links

## Martin Young — 2005-08-11 23:43:55

    --- In concatenative@yahoogroups.com, "stevan apter" <sa@n...> wrote:

     > the recursion is an illusion.  in XY, invocation of

    > a defined word causes the definition to be pushed onto

    > the queue.  is this very different from the use of

    > the 'repeat' word in your definition of linrec?

     In that sense, isn't all explicit recursion an illusion?  No sane

    execution system actually tries to expand explicit recursion prior

    to execution; the expansion of the recursive invocation is always

    lazy.  Not least because the expansion is non-computable.

    I think MONKEY is (slightly) different because "repeat" is also

    defined in terms of move and unmove.  All recursive and itterative

    combinators are built on top of the "pcon" word defined thusly:

    pcon ==

    {{

    { dip swapdup { swapif } dip unmove swap { dup unmove swap move swap

    move move 0 } if drop }

    cons cons

    dup move move

    }}

    Not pretty, I grant you, and not quick to execute.

    The upside is that it becomes possible to fully expand every

    definition in a program; something that can't be done with

    explicitly recursive definitions, as noted above.  I /think/ this is

    useful.

## stevan apter — 2005-08-12 00:48:40

    ----- Original Message -----

    From: "Martin Young" <martin@...>

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, August 11, 2005 7:43 PM

    Subject: [stack] Re: an exchange on flatness

    > --- In concatenative@yahoogroups.com, "stevan apter" <sa@n...> wrote:

    > > the recursion is an illusion.  in XY, invocation of

    > > a defined word causes the definition to be pushed onto

    > > the queue.  is this very different from the use of

    > > the 'repeat' word in your definition of linrec?

    >

    > In that sense, isn't all explicit recursion an illusion?  No sane

    > execution system actually tries to expand explicit recursion prior

    > to execution; the expansion of the recursive invocation is always

    > lazy.  Not least because the expansion is non-computable.

    >

    > I think MONKEY is (slightly) different because "repeat" is also

    > defined in terms of move and unmove.  All recursive and itterative

    > combinators are built on top of the "pcon" word defined thusly:

    >

    > pcon ==

    > {{

    > { dip swapdup { swapif } dip unmove swap { dup unmove swap move swap

    > move move 0 } if drop }

    > cons cons

    > dup move move

    > }}

    >

    > Not pretty, I grant you, and not quick to execute.

    but of course that's not important (the performance, i mean.)

    i'm wondering how monkey (the unflat version) maps to XY, which also

    uses a result stack X and an input queue Y and has the primitives:

            ->      queue           [X^z Y] -> [X z]

            <-      stack           [X^z Y] -> [z Y]

            =>      cache           [X^z Y] -> [X Y^z]

            <=      uncache         [X Y^z] -> [X^z Y]

            /       use             [X^z Y] -> [X z,Y]

            \       mention         [X z^Y] -> [X^z Y]

            (       stack*          [X Y] -> [X^[X] Y]

            )       queue*          [X Y] -> [X^[Y] Y]

    i'm thinking that move/unmove are similar to cache/uncache.  if so,

    then i should be able to write pcon in XY.  can you provide me with

    some sample input/output?

    apart from postings here, have you written anything up?

    >

    > The upside is that it becomes possible to fully expand every

    > definition in a program; something that can't be done with

    > explicitly recursive definitions, as noted above.  I /think/ this is

    > useful.

    >

    >

    >

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

## William Tanksley, Jr — 2005-08-12 00:58:22

    On 8/10/05, Ivan Tomac <e1_t@...> wrote:

     > But something that's more limited then quotations in Joy - rather then

    > have quotations that are at the same time both lists and code, have 2

    > different types, one for lists and one for code. The latter can only

    > be executed, duplicated, concatenated, shuffled or destroyed. It

    > cannot be split.

    > What I'm asking is is this enough for a language to be flat?

     No. A language with literal code blocks is not "purely" flat, at least

    not within those blocks. (I use the word "purely" to imply a

    similarity to the "pure" functional languages that seem to often take

    a good idea too far... I don't know whether pure flatness is as

    uncomfortable as pure functionality, but I'm willing to not quibble

    with anyone who fears it might be. As long as they let me explore it!)

     > I've just re-read some of the early posts on the topic and the

    > following definition (along with the posts about flatForth) got me

    > thinking:

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

    > >Flat: Flatness is the absence of all syntactic (compile-time)

    > >nesting.

     Yeah, I'll stand by that.

     > >A test for flatness: a definition is flat if and only if it can

    > >be cut apart into two valid definitions on any blank space. A

    > >definition is partially flat to the extent that it can be so

    > >cut. This could be expressed numericly, by dividing the number

    > >of cuttable spaces by the total number of spaces.

     BTW, I'm not sure anymore about the usefulness of this measure. It

    does measure cuttability, but I'm not sure if that's a practical thing

    to measure. I'm tempted to measure the lengths of the cuttable

    sequences, but that seems to imply that a Forth program consisting of

    short definitions would score lower than one consisting of long

    ones... An odd result. But perhaps appropriate, since Forth

    definitions aren't flat (you gotta pay somewhere for using a non-flat

    language!).

     > I think I understand now what Billy meant by saying that a flat

    > language is a graph rather then a tree.

     Actually, not quite. The lazy flat language I suggested can form

    graphs, not just trees; but flat languages in general aren't any

    different from non-flat ones. A lazy non-flat language could also form

    graphs.

     > I'm not sure whether it answers my question though. If you have a type

    > of code blocks or functions and if each code block is an atom then

    > doesn't that make the language flat regardless of whether a function

    > in such a language has nesting or not?

     Yes. HOWEVER, by saying that the "code blocks" are atoms and the

    language itself is flat, you are therefore implying that the "code

    blocks" are not part of the program, and in fact their structure is

    not specified by the language. If their structure is part of the

    language, then they are a part of the program, and the language is not

    flat.

     > Why am I asking that? Because

    > if each code block is an atom then [1 dup 2 * drop] and [1 dup drop]

    > and [1] are all equivalent and if one of those is nested inside

    > another code block it can be replaced by a reference to an existing

    > code block so you can still get a graph structure as opposed to a

    > tree.

     That's not what I meant by a graph structure. That's just an optimiser

    -- any language could have one (so long as the quotations aren't too

    visible to the program). The tree structure could arise if a program

    took its own lazy structure and performed operations on it -- in

    apter's language, you could swap bracket elements. You don't even have

    to do this at runtime; you could get a nasty graph at compile time

    with a little ingenuity.

    -Billy

## William Tanksley, Jr — 2005-08-12 05:24:52

    On 8/10/05, Martin Young <martin@...> wrote:

     > I've only been half following this discussion - apologies if I've

    > got the wrong end of the stick.  I was just doing a little bit of on-

    > paper doodling and came up with the following idea:

    > The execution system has two stacks: a data stack, and a dip stack.

    > These are initially empty.

     The dip operator is brilliant (thanks for introducing it to us,

    Manfred!), but fundamentally, the dip stack (or return stack, to use

    the Forth term) is more elemental.

     > It also has a stack/queue of incoming symbols - the program.

    > Initially the program queue contains the program as a series of

    > atoms (symbols or numbers).  Symbols are removed from the program

    > stack and "executed" the discarded.

     Like XY. Okay.

     > There are no lists, strings, tuples or suchlike in the language.

     That's fine, your call. Definitely flatter in syntax -- but it occurs

    to me that flatness doesn't have to be applied to data.

     > The addition of two new operators, snatch and unsnatch may make the

    > language flat.

    > "snatch" takes one integer value (N) from the data stack then

    > arranges for the next N symbols from the program queue to be

    > conbined into an opaque Lump and pushed onto the dip

    > stack.  "unsnatch" pulls one Lump from the snatch stack and pushes

    > its content onto the front of the program queue.  Their presence on

    > the dip stack means that suitably polymorphic symbols such as swap

    > and dip can maniplate Lumps but they, the Lumps, cannot be

    > decomposed.

     I don't think so. The acid test of a flat program is its cuttability.

    What happens if you "cut" the program right in the middle of a

    snatch-snippet? The problem with snatch is that it has to look ahead,

    and that means it imposes syntactic structure.

    Example:

    define "x" as "2 3 +"

    5 snatch 1 2 3 + *

    ==

    5 snatch x *

    The two are not equal -- the second is nonsense -- but all I did was

    apply a pair of cuts (to extract the program) and concatenated the

    results.

    Here's the above in colorForth:

    :x 2 3 + ;

    :y 1 2 3 + * ;

    :z x * ;

    The trick to notice here is that although I've put each "definition"

    on a line of its own, making it look like it starts with a :name and

    ends with a semicolon, they actually don't work that way. Semicolon is

    actually a normal library word -- it performs a return. It doesn't

    have any syntactic significance. Likewise, :name doesn't start a

    definition; it merely creates a name that, when used later, refers to

    that entry point in the code.

     > I've been trying to build an example.  I started with a program

    > which prints the first N fibonaci numbers.  One way of writing it is

    > as two words (in MONKEY syntax).

    > fibstep ==

    > {{

    >     dup

    >     { + } dip

    >     swap

    >     dup .

    > }}

    >

    > nfib ==

    > {{

    >     1 . 1 .

    >     { 1 1 { fibstep } } dip

    >     repeat

    >     drop drop

    > }}

    >

    > I've started by converting fibstep into flat MONKEY:

    >

    > dup 1 snatch + move unsnatch swap dup .

     Here's a similar solution in a flat colorForth variant (pop==move,

    push==unmove):

    :nfib  for 1 1  :fibstep dup . ab--bab +  'fibstep ?loop . push drop ;

    (The ab--bab is my style of stack manipulation. It does what it looks like.)

     > I think this works.  Sorry about the lack of formatting.  Not sure

    > how to format source code that has no internal structure...

     Straight lines are best, IMO -- but the programmer's discretion should

    not be ignored. When in doubt, stay with straight lines, and cut the

    program to make each line shorter and more elemental. (This is a Forth

    rule. I violate it every time.)

     > I'm currently puzzling over how to write the "repeat" word, but I

    > thought I'd post this before I discover that it's impossible...

     I implemented the for and ?loop words, but in the final analysis

    they'd be simpler to emit machine code for. Real simple... And

    frankly, the flat source code for the two weren't pretty, so I cut

    them out before I finished debugging them.

    -Billy

## Ivan Tomac — 2005-08-12 10:48:18

    Thanks. Your post and Manfred's original post where flat languages are

    first mentioned (and which I've just now managed to dig out - for

    others who were also late to the discussion, a link:

    http://groups.yahoo.com/group/concatenative/message/2471) have

    answered all my questions :)

    --- In concatenative@yahoogroups.com, "William Tanksley, Jr"

    <wtanksleyjr@g...> wrote:

     > On 8/10/05, Ivan Tomac <e1_t@y...> wrote:

    > > But something that's more limited then quotations in Joy - rather

     then

     > > have quotations that are at the same time both lists and code,

     have 2

     > > different types, one for lists and one for code. The latter can

     only

     > > be executed, duplicated, concatenated, shuffled or destroyed. It

    > > cannot be split.

    >

    > > What I'm asking is is this enough for a language to be flat?

    >

    > No. A language with literal code blocks is not "purely" flat, at

     least

     > not within those blocks. (I use the word "purely" to imply a

    > similarity to the "pure" functional languages that seem to often

     take

     > a good idea too far... I don't know whether pure flatness is as

    > uncomfortable as pure functionality, but I'm willing to not quibble

    > with anyone who fears it might be. As long as they let me explore

     it!)

     >

    > > I've just re-read some of the early posts on the topic and the

    > > following definition (along with the posts about flatForth) got me

    > > thinking:

    >

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

    > > >Flat: Flatness is the absence of all syntactic (compile-time)

    > > >nesting.

    >

    > Yeah, I'll stand by that.

    >

    > > >A test for flatness: a definition is flat if and only if it can

    > > >be cut apart into two valid definitions on any blank space. A

    > > >definition is partially flat to the extent that it can be so

    > > >cut. This could be expressed numericly, by dividing the number

    > > >of cuttable spaces by the total number of spaces.

    >

    > BTW, I'm not sure anymore about the usefulness of this measure. It

    > does measure cuttability, but I'm not sure if that's a practical

     thing

     > to measure. I'm tempted to measure the lengths of the cuttable

    > sequences, but that seems to imply that a Forth program consisting

     of

     > short definitions would score lower than one consisting of long

    > ones... An odd result. But perhaps appropriate, since Forth

    > definitions aren't flat (you gotta pay somewhere for using a

     non-flat

     > language!).

    >

    > > I think I understand now what Billy meant by saying that a flat

    > > language is a graph rather then a tree.

    >

    > Actually, not quite. The lazy flat language I suggested can form

    > graphs, not just trees; but flat languages in general aren't any

    > different from non-flat ones. A lazy non-flat language could also

     form

     > graphs.

    >

    > > I'm not sure whether it answers my question though. If you have a

     type

     > > of code blocks or functions and if each code block is an atom then

    > > doesn't that make the language flat regardless of whether a

     function

     > > in such a language has nesting or not?

    >

    > Yes. HOWEVER, by saying that the "code blocks" are atoms and the

    > language itself is flat, you are therefore implying that the "code

    > blocks" are not part of the program, and in fact their structure is

    > not specified by the language. If their structure is part of the

    > language, then they are a part of the program, and the language is

     not

     > flat.

    >

    > > Why am I asking that? Because

    > > if each code block is an atom then [1 dup 2 * drop] and [1 dup

     drop]

     > > and [1] are all equivalent and if one of those is nested inside

    > > another code block it can be replaced by a reference to an

     existing

     > > code block so you can still get a graph structure as opposed to a

    > > tree.

    >

    > That's not what I meant by a graph structure. That's just an

     optimiser

     > -- any language could have one (so long as the quotations aren't too

    > visible to the program). The tree structure could arise if a program

    > took its own lazy structure and performed operations on it -- in

    > apter's language, you could swap bracket elements. You don't even

     have

     > to do this at runtime; you could get a nasty graph at compile time

    > with a little ingenuity.

    >

    > -Billy

     Ivan

## Martin Young — 2005-08-12 11:14:06

    On Fri, 2005-08-12 at 06:24, William Tanksley, Jr wrote:

     > > The addition of two new operators, snatch and unsnatch may make the

    > > language flat.

    >

    > > "snatch" takes one integer value (N) from the data stack then

    > > arranges for the next N symbols from the program queue to be

    > > conbined into an opaque Lump and pushed onto the dip

    > > stack.  "unsnatch" pulls one Lump from the snatch stack and pushes

    > > its content onto the front of the program queue.  Their presence on

    > > the dip stack means that suitably polymorphic symbols such as swap

    > > and dip can maniplate Lumps but they, the Lumps, cannot be

    > > decomposed.

    >

    > I don't think so. The acid test of a flat program is its cuttability.

    > What happens if you "cut" the program right in the middle of a

    > snatch-snippet? The problem with snatch is that it has to look ahead,

    > and that means it imposes syntactic structure.

    >

    > Example:

    >

    > define "x" as "2 3 +"

    >

    > 5 snatch 1 2 3 + *

    > ==

    > 5 snatch x *

    >

    > The two are not equal -- the second is nonsense -- but all I did was

    > apply a pair of cuts (to extract the program) and concatenated the

    > results.

     Good point.

     > Here's the above in colorForth:

    >

    > :x 2 3 + ;

    > :y 1 2 3 + * ;

    > :z x * ;

    >

    > The trick to notice here is that although I've put each "definition"

    > on a line of its own, making it look like it starts with a :name and

    > ends with a semicolon, they actually don't work that way. Semicolon is

    > actually a normal library word -- it performs a return. It doesn't

    > have any syntactic significance. Likewise, :name doesn't start a

    > definition; it merely creates a name that, when used later, refers to

    > that entry point in the code.

     Whilst this is indeed flat from the point of view of the execution

    system, it's not really flat from the programmer's point of view.

    Whilst you can, I guess, build a program like this...

    :x 1 2

    :y 3 4 + ;

    ...where the execution of x falls through into y, it would, I'd

    suggest, be uncommon, confusing and not generally useful.  The

    majority of programs will retain the form where each has a start

    marker and an end marker.  (Or this there a school of programming

    where fall-through and suchlike is the norm?  I recall pulling many

    such tricks when developing apps for the Z80 but I'm uncertainly about

    it's continuing benefit.)

    One might say that the language is technically flat but not logically

    flat.  Does this matter?  At what level, for whom, or for what, is the

    flatness important?  Then again, one can write assembly language in a

    functional style so perhaps the distinction is meaningless?

    It seems to me colorForth has almost a direct mapping onto machine

    language.  I guess that's not accidental.  I wonder how close you're

    getting to building a smart macro assembler.

    I can't quite see how you build higher level constructs from it

    though.  How would you go about building an anonymous closure at

    runtime, for example?  Wouldn't it require the ability to construct

    new atoms of the form :X?  But how to build an anonymous one?  How

    would you, or rather the execution system, generate the entry address

    for a constructed program?

    Before first reading about Joy, I wrote an RPN expression compiler

    which had an operator ":" which droped the address of the next atom

    onto the stack (as opposed to creating a name/value pair).  With the

    addition of a conditional call operator it could run simple loops.

    This was even closer to machine language than colorForth.  But, of

    course, what it couldn't do was build higher level constructs - there

    was no way of deferring execution.  (The stack expressions were

    embedded in a simple imperative language so this wasn't an issue at

    the time.)

    -Martin.

## Martin Young — 2005-08-12 12:05:36

    Stevan,

    I think you're right.  Any such language that can manipulate its

    continuations can build an equivilent to pcon.

    I don't have any convenient input/output tests.  This is a failing of

    mine - once it does what I want I stop building test cases and

    pedagogical examples.  In any case, it's mostly dip stack manipulation

    which may well be different, in detail, for XY.

    It expects two programs on the stack.  The uppermost one is a test,

    the next one the body.

    pcon saves copies both of the test and body on the dip stack.  It then

    executes the test.  If boolean True is left on top of the stack, it

    executes the body then loops (i.e. it duplicates the body and the test

    from the dip stack and re-executes test, tests the boolean on top of

    the stack...).  When boolean False is left on the stack, pcon finishes.

    Here's the repeat word, implemented with pcon:

    repeat ==

    {{

    	{ dup 0 >= }

    	{ }

    	{

    	  { { dupmove i unmove } dip }

    	  { -1 + dup 0 <= }

    	  pcon

    	}

    	ifte

    	drop drop

    }}

    What I haven't done yet is figure out how best to eliminate arbitrary

    mutual recursion.

    I've not written up anything other than in posts here.

    -Martin.

     --- In concatenative@yahoogroups.com, "stevan apter" <sa@n...> wrote:

    >

    > ----- Original Message -----

    > From: "Martin Young" <martin@e...>

    > To: <concatenative@yahoogroups.com>

    > Sent: Thursday, August 11, 2005 7:43 PM

    > Subject: [stack] Re: an exchange on flatness

    >

    >

    > > --- In concatenative@yahoogroups.com, "stevan apter" <sa@n...> wrote:

    > > > the recursion is an illusion.  in XY, invocation of

    > > > a defined word causes the definition to be pushed onto

    > > > the queue.  is this very different from the use of

    > > > the 'repeat' word in your definition of linrec?

    > >

    > > In that sense, isn't all explicit recursion an illusion?  No sane

    > > execution system actually tries to expand explicit recursion prior

    > > to execution; the expansion of the recursive invocation is always

    > > lazy.  Not least because the expansion is non-computable.

    > >

    > > I think MONKEY is (slightly) different because "repeat" is also

    > > defined in terms of move and unmove.  All recursive and itterative

    > > combinators are built on top of the "pcon" word defined thusly:

    > >

    > > pcon ==

    > > {{

    > > { dip swapdup { swapif } dip unmove swap { dup unmove swap move swap

    > > move move 0 } if drop }

    > > cons cons

    > > dup move move

    > > }}

    > >

    > > Not pretty, I grant you, and not quick to execute.

    >

    > but of course that's not important (the performance, i mean.)

    >

    > i'm wondering how monkey (the unflat version) maps to XY, which also

    > uses a result stack X and an input queue Y and has the primitives:

    >

    >

    >         ->      queue           [X^z Y] -> [X z]

    >         <-      stack           [X^z Y] -> [z Y]

    >

    >         =>      cache           [X^z Y] -> [X Y^z]

    >         <=      uncache         [X Y^z] -> [X^z Y]

    >

    >         /       use             [X^z Y] -> [X z,Y]

    >         \       mention         [X z^Y] -> [X^z Y]

    >

    >         (       stack*          [X Y] -> [X^[X] Y]

    >         )       queue*          [X Y] -> [X^[Y] Y]

    >

    > i'm thinking that move/unmove are similar to cache/uncache.  if so,

    > then i should be able to write pcon in XY.  can you provide me with

    > some sample input/output?

    >

    > apart from postings here, have you written anything up?

    >

    > >

    > > The upside is that it becomes possible to fully expand every

    > > definition in a program; something that can't be done with

    > > explicitly recursive definitions, as noted above.  I /think/ this is

    > > useful.

    > >

    > >

    > >

    > >

    > >

    > >

    > >

    > > Yahoo! Groups Links

    > >

    > >

    > >

    > >

    > >

    > >

    > >

## William Tanksley, Jr — 2005-08-13 01:36:34

    Ivan Tomac <e1_t@...> wrote:

     > I'm a bit late to join this discussion but I'm starting to like the

    > idea of flat languages. If nothing else I think it's worth exploring

    > them further until we can say for sure whether their advantages

    > outweigh the disadvantages.

     That's what I think too.

     > If I remember it right you mentioned in one of the posts (can't find

    > it right now, otherwise I'd quote it) that the main (only?) things

    > that prevent Joy from being flat are it's definitions and blocks.

     Well, kinda. Joy has a whole syntax to provide scopes for its

    definitions. Other than that, yes.

     > The

    > problem with definitions is easy enough to solve which leaves only

    > code blocks. How do you get around that problem? How do you flatten

    > quotations?

    > Do you simply treat them as atomic values so that no quotation can

    > ever be split into smaller quotations? Or is there more to it then

    > that? What else is neccesary in order for a language to be truly flat?

     You'd have to make the quotations non-syntactic. I don't know how

    you'd want to do that; colorForth has a simple way, while my

    hypothetical flat lazy language uses a different one, and then there's

    the XY stack solution.

     > --- In concatenative@yahoogroups.com, "William Tanksley, Jr"

    > <wtanksleyjr@g...> wrote:

    > > > I was simply pointing

    > > > out some things that may rely on the tree representation of code,

    > > > at least in their current form.

    > > That's true. All I can say, then, is that if you want to express

    > > your

    > > code as a tree you still can. Flat languages are graphs, not trees;

    > > but if the programmer wishes, he can confine his work to the shape

    > of

    > > a tree.

    > This part confused me a bit - how is the code in a flat language a

    > graph?

     I just realised I badly misspoke by saying that ALL flat languages

    have graph structure. Code in my lazy flat language is a graph, as is

    code in flatXY. Code in colorForth isn't. A language (any language)

    can have graph-structured code if the structure of the program can be

    manipulated by dynamic code.

    This happens the same way that a program can have a graph-structured

    dataflow -- you just use the right combinators. Just as with dataflow,

    the resulting program can be staticly decidable (as with strongForth's

    type checking) or not.

     > Ivan

     -Billy

## stevan apter — 2005-08-13 12:57:12

    a nice example of a language, than which there can be no

    flatter, is chris barker's "jot":

    http://ling.ucsd.edu/~barker/Iota/

    in jot, every binary sequence is well-formed.  moreover,

    every expression e = e1^e2 in jot has the property that

        meaning(e) = meaning(apply(meaning(e1),meaning(e2)))

    i.e. you can cut an expression into an arbitrary number

    of parts, then repeatedly apply the meaning of the first

    to the meaning of the second, then apply that to the

    meaning of the third.

    now, that's flat.

     ----- Original Message -----

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

    To: <concatenative@yahoogroups.com>

    Sent: Friday, August 12, 2005 9:36 PM

    Subject: Re: [stack] Re: an exchange on flatness

    Ivan Tomac <e1_t@...> wrote:

    > I'm a bit late to join this discussion but I'm starting to like the

    > idea of flat languages. If nothing else I think it's worth exploring

    > them further until we can say for sure whether their advantages

    > outweigh the disadvantages.

    That's what I think too.

    > If I remember it right you mentioned in one of the posts (can't find

    > it right now, otherwise I'd quote it) that the main (only?) things

    > that prevent Joy from being flat are it's definitions and blocks.

    Well, kinda. Joy has a whole syntax to provide scopes for its

    definitions. Other than that, yes.

    > The

    > problem with definitions is easy enough to solve which leaves only

    > code blocks. How do you get around that problem? How do you flatten

    > quotations?

    > Do you simply treat them as atomic values so that no quotation can

    > ever be split into smaller quotations? Or is there more to it then

    > that? What else is neccesary in order for a language to be truly flat?

    You'd have to make the quotations non-syntactic. I don't know how

    you'd want to do that; colorForth has a simple way, while my

    hypothetical flat lazy language uses a different one, and then there's

    the XY stack solution.

    > --- In concatenative@yahoogroups.com, "William Tanksley, Jr"

    > <wtanksleyjr@g...> wrote:

    > > > I was simply pointing

    > > > out some things that may rely on the tree representation of code,

    > > > at least in their current form.

    > > That's true. All I can say, then, is that if you want to express

    > > your

    > > code as a tree you still can. Flat languages are graphs, not trees;

    > > but if the programmer wishes, he can confine his work to the shape

    > of

    > > a tree.

    > This part confused me a bit - how is the code in a flat language a

    > graph?

    I just realised I badly misspoke by saying that ALL flat languages

    have graph structure. Code in my lazy flat language is a graph, as is

    code in flatXY. Code in colorForth isn't. A language (any language)

    can have graph-structured code if the structure of the program can be

    manipulated by dynamic code.

    This happens the same way that a program can have a graph-structured

    dataflow -- you just use the right combinators. Just as with dataflow,

    the resulting program can be staticly decidable (as with strongForth's

    type checking) or not.

    > Ivan

    -Billy

    Yahoo! Groups Links

## stevan apter — 2005-08-13 20:41:32

    ----- Original Message -----

    From: "stevan apter" <sa@...>

    To: <concatenative@yahoogroups.com>

    Sent: Saturday, August 13, 2005 8:57 AM

    Subject: Re: [stack] Re: an exchange on flatness

    > a nice example of a language, than which there can be no

    > flatter, is chris barker's "jot":

    >

    > http://ling.ucsd.edu/~barker/Iota/

    >

    > in jot, every binary sequence is well-formed.  moreover,

    > every expression e = e1^e2 in jot has the property that

    >

    >     meaning(e) = meaning(apply(meaning(e1),meaning(e2)))

    >

    > i.e. you can cut an expression into an arbitrary number

    > of parts, then repeatedly apply the meaning of the first

    > to the meaning of the second, then apply that to the

    > meaning of the third.

    sorry - this is wrong.  what i should have said is this:

    you can cut an expression into an arbitrary number of parts.

    evaluate the first part on I (the identity combinator; in jot,

    the empty string); then evaluate the second part on that; &c.

    an example should make this clear.  (schemers can futz with

    chris barker's implementation to allow an initial point other

    than I.)

    / combinators:

    K:{y;x}

    S:{x[z]y[z]}

    I:{x}

    B:{x[y[z]]}

    / interpreter:

    j:{:[~#y;(x;y);.*y;(B[x];1_ y);(x[S][K];1_ y)]}

    jot:{*(j .)/(x;"",y)}

    / the S combinator:

      jot[I]"11111000"

    {x[z]y[z]}

    / so now, evaluate e.g. 1000 on the evaluation of 1111:

      jot[I]"1111"

    {x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x}]]]]

      jot[jot[I]"1111";"1000"]

    {x[z]y[z]}

    / in fact, evaluating the elements one bit at a time shows

    / how you progress from {x}, which is I, to {x[z]y[z]},

    / the final result:

      `0:$I jot\"11111000"

    {x}

    {x[y[z]]}[{x}]

    {x[y[z]]}[{x[y[z]]}[{x}]]

    {x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x}]]]

    {x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x}]]]]

    {x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x}]]]]]

    {x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x[y[z]]}[{x}]]]][{x[z]y[z]}[{y;x}]]

    {x[y[z]]}[{x[y[z]]}[{x}]][{y;x}]

    {x[z]y[z]}

    >

    > now, that's flat.

    >

    > ----- Original Message -----

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

    > To: <concatenative@yahoogroups.com>

    > Sent: Friday, August 12, 2005 9:36 PM

    > Subject: Re: [stack] Re: an exchange on flatness

    >

    >

    > Ivan Tomac <e1_t@...> wrote:

    > > I'm a bit late to join this discussion but I'm starting to like the

    > > idea of flat languages. If nothing else I think it's worth exploring

    > > them further until we can say for sure whether their advantages

    > > outweigh the disadvantages.

    >

    > That's what I think too.

    >

    > > If I remember it right you mentioned in one of the posts (can't find

    > > it right now, otherwise I'd quote it) that the main (only?) things

    > > that prevent Joy from being flat are it's definitions and blocks.

    >

    > Well, kinda. Joy has a whole syntax to provide scopes for its

    > definitions. Other than that, yes.

    >

    > > The

    > > problem with definitions is easy enough to solve which leaves only

    > > code blocks. How do you get around that problem? How do you flatten

    > > quotations?

    > > Do you simply treat them as atomic values so that no quotation can

    > > ever be split into smaller quotations? Or is there more to it then

    > > that? What else is neccesary in order for a language to be truly flat?

    >

    > You'd have to make the quotations non-syntactic. I don't know how

    > you'd want to do that; colorForth has a simple way, while my

    > hypothetical flat lazy language uses a different one, and then there's

    > the XY stack solution.

    >

    > > --- In concatenative@yahoogroups.com, "William Tanksley, Jr"

    > > <wtanksleyjr@g...> wrote:

    > > > > I was simply pointing

    > > > > out some things that may rely on the tree representation of code,

    > > > > at least in their current form.

    >

    > > > That's true. All I can say, then, is that if you want to express

    > > > your

    > > > code as a tree you still can. Flat languages are graphs, not trees;

    > > > but if the programmer wishes, he can confine his work to the shape

    > > of

    > > > a tree.

    >

    > > This part confused me a bit - how is the code in a flat language a

    > > graph?

    >

    > I just realised I badly misspoke by saying that ALL flat languages

    > have graph structure. Code in my lazy flat language is a graph, as is

    > code in flatXY. Code in colorForth isn't. A language (any language)

    > can have graph-structured code if the structure of the program can be

    > manipulated by dynamic code.

    >

    > This happens the same way that a program can have a graph-structured

    > dataflow -- you just use the right combinators. Just as with dataflow,

    > the resulting program can be staticly decidable (as with strongForth's

    > type checking) or not.

    >

    > > Ivan

    >

    > -Billy

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

## William Tanksley, Jr — 2005-08-14 15:24:38

    stevan apter <sa@...> wrote:

     > > a nice example of a language, than which there can be no

    > > flatter, is chris barker's "jot":

    > you can cut an expression into an arbitrary number of parts.

    > evaluate the first part on I (the identity combinator; in jot,

    > the empty string); then evaluate the second part on that; &c.

     Very interesting! There's one thing that makes this less flat than it

    could be -- the meaning of each string is determined by its prefix. So

    although you can chop a working program into parts, the resulting

    parts don't do anything definable on their own. And it's not

    concatenative either, even though any two valid programs form another

    valid program, because if the first program was complete, the second

    program won't do anything.

    Very cool language. It looks like someone'll have to use this to

    calculate Chaitin's Omega.

    -Billy

## stevan apter — 2005-08-14 18:54:28

    ----- Original Message -----

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

    To: <concatenative@yahoogroups.com>

    Sent: Sunday, August 14, 2005 11:24 AM

    Subject: Re: [stack] Re: an exchange on flatness

    > stevan apter <sa@...> wrote:

    > > > a nice example of a language, than which there can be no

    > > > flatter, is chris barker's "jot":

    > > you can cut an expression into an arbitrary number of parts.

    > > evaluate the first part on I (the identity combinator; in jot,

    > > the empty string); then evaluate the second part on that; &c.

    >

    > Very interesting! There's one thing that makes this less flat than it

    > could be -- the meaning of each string is determined by its prefix. So

    > although you can chop a working program into parts, the resulting

    > parts don't do anything definable on their own. And it's not

    > concatenative either, even though any two valid programs form another

    > valid program, because if the first program was complete, the second

    > program won't do anything.

    a language is flat if any program can be cut into parts which

    are programs, and the meaning of the concatenation of the parts

    is the same as the meaning of the whole.

    concatenation can denote function-composition or function-

    application.  the definition of "flat" doesn't specify any

    interpretation of this syntactic operation.  nor does it even

    require that the parts have meaning "on their own".  at least,

    that is how i've understood things up til now.

    the way i think of jot evaluation is that you start with an

    initial state and a program P.  at each step, you pop the

    next element of P and apply it to the state to get a new

    state.

    this is parallel to the way i think of joy evaluation:  you

    start with an initial stack and a program P.  at each step,

    you pop the next element of P and apply it to the stack to

    get a new stack.

    1 and 0 don't do anything on their own, but applied to the

    state, they give you a new state.

    + and - don't do anything on their own, but applied to the

    stack, they give you a new stack.

    in jot, the state is a function.  in joy, the state is a

    stack.

    it's true that the concatenation of two jot programs may

    do no more than one of the programs on its own, but that

    is also true in joy, is it not?  for example,

        2 3 + id id id

        ----- --------

          1      2

    1^2 does no more than 1.

    >

    > Very cool language. It looks like someone'll have to use this to

    > calculate Chaitin's Omega.

    i like it too.  here's an even shorter jot interpreter in k:

        jot:{*({(:[~#y;x;.*y;B[x];x[S][K]];1_ y)}.)/(x;"",y)}

    >

    > -Billy

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

## William Tanksley, Jr — 2005-08-14 22:05:34

    stevan apter <sa@...> wrote:

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

    > > stevan apter <sa@...> wrote:

    > > > > a nice example of a language, than which there can be no

    > > > > flatter, is chris barker's "jot":

    > > > you can cut an expression into an arbitrary number of parts.

    > > > evaluate the first part on I (the identity combinator; in jot,

    > > > the empty string); then evaluate the second part on that; &c.

    > > Very interesting! There's one thing that makes this less flat than it

    > > could be -- the meaning of each string is determined by its prefix. So

    > > although you can chop a working program into parts, the resulting

    > > parts don't do anything definable on their own. And it's not

    > > concatenative either, even though any two valid programs form another

    > > valid program, because if the first program was complete, the second

    > > program won't do anything.

    > a language is flat if any program can be cut into parts which

    > are programs, and the meaning of the concatenation of the parts

    > is the same as the meaning of the whole.

     Only the first half of that is in the definition of a flat language.

    The second half is the definition of a concatenative language. Why?

    Because it's trivially true-- it's just a neccesary consequence. Or so

    it seems to me.

    But your definition omitted a crucial word -- "valid". The parts must

    be valid programs, in distinction to parts which are not valid. Jot is

    not flat any more than it's concatenative, in spite of the fact that

    splitting and joining programs does produce programs -- because the

    language doesn't define validity or invalidity.

    Okay, I'm stretching. But it does seem important to me that Jot is at

    best "trivially" concatenative and flat, in much the same way that a

    Null language would be (i.e. the language that accepted only the empty

    string). Since Jot doesn't provide any definition for what makes a

    string a valid program, I could invent one -- for example, "a string

    is a valid program iff it describes a function, and no shorter string

    could be generated by chopping bits off the tail which describes the

    same function." (That's a nasty definition, and I didn't intend for it

    to get so Turing-complete, but a purely syntactic version is easy to

    produce.)

     > concatenation can denote function-composition or function-

    > application.

     In Jot's case, it doesn't represent either -- it provides more

    syntactic materiel for a program, or possibly does nothing at all.

     > the definition of "flat" doesn't specify any

    > interpretation of this syntactic operation.

     It's clear, then, that my definition of "flat" is unclear and

    insufficient. I think I'll have to downgrade my "definition" to the

    status of a "rule of thumb". Neccesary, but not sufficient.

    The primary definition of "concatenative language" isn't that the

    concatenation of any two valid programs is another valid program; the

    actual definition given was that it's a language in which function

    composition is represented by program concatenation.

    I defined flatness with that definition kind of sitting in the back of

    my head -- things would have been clearer if I'd explcitly built a

    similar definition.

     > nor does it even

    > require that the parts have meaning "on their own".  at least,

    > that is how i've understood things up til now.

     Well, I think it's fair to require a "meaning on their own". That

    meaning is a crucial part of what it means to be "valid", wouldn't you

    say?

     > the way i think of jot evaluation is that you start with an

    > initial state and a program P.  at each step, you pop the

    > next element of P and apply it to the state to get a new

    > state.

     Mmmm. I'm not sure I see that. I have a hard time reading it, but it

    looks to me like the only "state" that can be described that way is

    the compiler state, not the runtime state.

     > this is parallel to the way i think of joy evaluation:  you

    > start with an initial stack and a program P.  at each step,

    > you pop the next element of P and apply it to the stack to

    > get a new stack.

     Yes, but with a concatenative language, after you finish popping all

    the elements from the queue you're done. With Jot, I think you still

    have to evaluate the result.

     > 1 and 0 don't do anything on their own, but applied to the

    > state, they give you a new state.

     Exactly.

     > + and - don't do anything on their own, but applied to the

    > stack, they give you a new stack.

     But they DO something on their own. Or more precisely, regardless of

    the depth of the stack, they perform something that can be called an

    "operation" on the top two numbers on the stack. Every time.

     > in jot, the state is a function.  in joy, the state is a

    > stack.

     True.

    However, the function that's being built by Jot must then be executed.

    In Joy, the stack IS the entire result.

     > it's true that the concatenation of two jot programs may

    > do no more than one of the programs on its own, but that

    > is also true in joy, is it not?  for example,

    >     2 3 + id id id

    >     ----- --------

    >       1      2

    > 1^2 does no more than 1.

     I don't buy that. 2 is just the identity function; of course there are

    SOME functions that have any conceivable property. For example, just

    because + is comuatative doesn't make Joy Abelian!

    -Billy

## sa@dfa.com — 2005-08-15 12:36:57

    jot has two elements:  0 and 1.  0 denotes the function

          \x xSK

    1 denotes the function

          \x Bx

    and the empty string denotes I, where I, S, K, and B are

    the standard combinators.

    so 0 and 1 do mean something "on their own", viz. they

    each denote a specific function, just as + does in joy.

    in joy, 2 + denotes a particular composition, viz. the

    composition of the functions 2 and +.

    in jot, 01 denotes a particular composition, viz. the

    composition of the functions 0 and 1.

    a joy program is evaluated, a token at a time, on a

    stack, and returns a stack as its result.

    a jot program is evaluated, a token at a time, on a

    function, and returns a function as its result.

    you say that since the result is a function, we're

    not done yet, since "you still have to evaluate the

    result."  well, no.  just as in joy, everything in

    jot is a function.  2 3 + returns a stack containing

    5, and 5 is a function.

    bare jot is turing complete (we can simulate numbers,

    arithmetic, lists, and so on, using functions.)

    you can't get a syntax error in jot - ever sequence of

    0s and 1s is well-formed.  (some jot programs never

    terminate, but that doesn't stand in the way of their

    being "valid.")

    if you embed jot in a system which allows for the

    naming of jot programs, then your initial requirement

    for flatness is satisfied.  for example,

          11111000 -> S

          a:11111

          b:000

          ab -> S

    concatenative@yahoogroups.com wrote on 08/14/2005 06:05:34 PM:

     > stevan apter <sa@...> wrote:

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

    > > > stevan apter <sa@...> wrote:

    > > > > > a nice example of a language, than which there can be no

    > > > > > flatter, is chris barker's "jot":

    > > > > you can cut an expression into an arbitrary number of parts.

    > > > > evaluate the first part on I (the identity combinator; in jot,

    > > > > the empty string); then evaluate the second part on that; &c.

    >

    > > > Very interesting! There's one thing that makes this less flat than it

    > > > could be -- the meaning of each string is determined by its prefix.

     So

     > > > although you can chop a working program into parts, the resulting

    > > > parts don't do anything definable on their own. And it's not

    > > > concatenative either, even though any two valid programs form another

    > > > valid program, because if the first program was complete, the second

    > > > program won't do anything.

    >

    > > a language is flat if any program can be cut into parts which

    > > are programs, and the meaning of the concatenation of the parts

    > > is the same as the meaning of the whole.

    >

    > Only the first half of that is in the definition of a flat language.

    > The second half is the definition of a concatenative language. Why?

    > Because it's trivially true-- it's just a neccesary consequence. Or so

    > it seems to me.

    >

    > But your definition omitted a crucial word -- "valid". The parts must

    > be valid programs, in distinction to parts which are not valid. Jot is

    > not flat any more than it's concatenative, in spite of the fact that

    > splitting and joining programs does produce programs -- because the

    > language doesn't define validity or invalidity.

    >

    > Okay, I'm stretching. But it does seem important to me that Jot is at

    > best "trivially" concatenative and flat, in much the same way that a

    > Null language would be (i.e. the language that accepted only the empty

    > string). Since Jot doesn't provide any definition for what makes a

    > string a valid program, I could invent one -- for example, "a string

    > is a valid program iff it describes a function, and no shorter string

    > could be generated by chopping bits off the tail which describes the

    > same function." (That's a nasty definition, and I didn't intend for it

    > to get so Turing-complete, but a purely syntactic version is easy to

    > produce.)

    >

    > > concatenation can denote function-composition or function-

    > > application.

    >

    > In Jot's case, it doesn't represent either -- it provides more

    > syntactic materiel for a program, or possibly does nothing at all.

    >

    > > the definition of "flat" doesn't specify any

    > > interpretation of this syntactic operation.

    >

    > It's clear, then, that my definition of "flat" is unclear and

    > insufficient. I think I'll have to downgrade my "definition" to the

    > status of a "rule of thumb". Neccesary, but not sufficient.

    >

    > The primary definition of "concatenative language" isn't that the

    > concatenation of any two valid programs is another valid program; the

    > actual definition given was that it's a language in which function

    > composition is represented by program concatenation.

    >

    > I defined flatness with that definition kind of sitting in the back of

    > my head -- things would have been clearer if I'd explcitly built a

    > similar definition.

    >

    > > nor does it even

    > > require that the parts have meaning "on their own".  at least,

    > > that is how i've understood things up til now.

    >

    > Well, I think it's fair to require a "meaning on their own". That

    > meaning is a crucial part of what it means to be "valid", wouldn't you

    > say?

    >

    > > the way i think of jot evaluation is that you start with an

    > > initial state and a program P.  at each step, you pop the

    > > next element of P and apply it to the state to get a new

    > > state.

    >

    > Mmmm. I'm not sure I see that. I have a hard time reading it, but it

    > looks to me like the only "state" that can be described that way is

    > the compiler state, not the runtime state.

    >

    > > this is parallel to the way i think of joy evaluation:  you

    > > start with an initial stack and a program P.  at each step,

    > > you pop the next element of P and apply it to the stack to

    > > get a new stack.

    >

    > Yes, but with a concatenative language, after you finish popping all

    > the elements from the queue you're done. With Jot, I think you still

    > have to evaluate the result.

    >

    > > 1 and 0 don't do anything on their own, but applied to the

    > > state, they give you a new state.

    >

    > Exactly.

    >

    > > + and - don't do anything on their own, but applied to the

    > > stack, they give you a new stack.

    >

    > But they DO something on their own. Or more precisely, regardless of

    > the depth of the stack, they perform something that can be called an

    > "operation" on the top two numbers on the stack. Every time.

    >

    > > in jot, the state is a function.  in joy, the state is a

    > > stack.

    >

    > True.

    >

    > However, the function that's being built by Jot must then be executed.

    > In Joy, the stack IS the entire result.

    >

    > > it's true that the concatenation of two jot programs may

    > > do no more than one of the programs on its own, but that

    > > is also true in joy, is it not?  for example,

    >

    > >     2 3 + id id id

    > >     ----- --------

    > >       1      2

    >

    > > 1^2 does no more than 1.

    >

    > I don't buy that. 2 is just the identity function; of course there are

    > SOME functions that have any conceivable property. For example, just

    > because + is comuatative doesn't make Joy Abelian!

    >

    > -Billy

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

## Narcoleptic Electron — 2005-08-15 16:39:57

    On 8/15/05, sa@... <sa@...> wrote:

     > if you embed jot in a system which allows for the

    > naming of jot programs, then your initial requirement

    > for flatness is satisfied.  for example,

    >

    >       11111000 -> S

    >

    >       a:11111

    >       b:000

    >       ab -> S

     When I suggested that my quotations-as-text scheme was as flat as one

    could go before descending into a Turing Tarpit, Jot was the tarpit I

    was specifically thinking of...

    Jot is a very cool language, though.  See also:

    http://esoteric.voxelperfect.net/wiki/Binary_combinatory_logic

## phimvt@lurac.latrobe.edu.au — 2005-08-16 10:19:31

    On Sat, 13 Aug 2005, stevan apter wrote:

     > a nice example of a language, than which there can be no

    > flatter, is chris barker's "jot":

     Indeed, it is a language flatter than which cannot be conceived

    [with apologies to Aquinas(?)].

     > http://ling.ucsd.edu/~barker/Iota/

    >

    > in jot, every binary sequence is well-formed.  moreover,

    > every expression e = e1^e2 in jot has the property that

    >

    >     meaning(e) = meaning(apply(meaning(e1),meaning(e2)))

    >

    > i.e. you can cut an expression into an arbitrary number

    > of parts, then repeatedly apply the meaning of the first

    > to the meaning of the second, then apply that to the

    > meaning of the third.

     If I understand it correctly, it uses an idea which seems to be

    due to Quine. See my only too short reference in the Joy rationale

        http://www.latrobe.edu.au/philosophy/phimvt/joy/j00rat.html

    to Quine's introduction to Schoenfinkel's paper "On the building blocks of

    logic" in the J.van Heiyenoort collection _From Frege to Goedel_. Quine

    eliminates the parentheses of combinatory calculus by the standard device

    of prefix or postfix notation.  Rewrite x(yz) and (xy)z with an explicit

    binary infix operator o (his choice for an explicit application operator),

    to give xo(yoz) and (xoy)oz. Then use the parenthesis eliminating device

    to give either prefix oxoyz and ooxyz, or postfix xyzoo and xyozo.

    Maybe this can be adapted for concatenative notation.

    Start with 2 3 +, write the function composition explicitly using ^

    to give (2 ^ 3) ^ +, now use postix for ^ to give 2 3 ^ + ^.

    But that does not solve the problem for lists and quotations, which

    are needed for say [1 2 3] [dup *] map. But suppose we use $ for

    constructing these. How about this:

      1 2 3 ^ ^ $ $ $   dup * ^ $ $   ^ map ^

    where a string of N dollars means: "form a list from the N items

    on the stack and push it onto the stack. Sounds rather like

    a proposal we have seen on this group (Stevan?), which uses

    the integer N on the stack and a single operator which means

    the same.

    Note that with the explicit composition operator all the usual

    operators and combinators (dup, *, map) just get pushed onto the stack,

    and it is only by using composition that they get executed.

    Sorry, this has not been thought out properly. Is it concatenative?

    Is it flat? Maybe the postfix composition operator is just an

    unnecessary nuisance, but the list/quotation builder $ (or some

    more elegant alternative) is of some use?

    But here is yet another alternative:

    DEFINE

      NIL  ==  [];

      !    ==  NIL cons i

               (* execute the topmost single item on the stack *).

    Everything other than ! is a push. Then write

        1 2 3 NIL cons ! cons ! cons ! dup * NIL cons ! cons ! map !

    Here each NIL cons ! would behave rather like $ above.  Note the map !

    would have to supply its own implicit ! for each item in the quotation.

    Not so pretty.  The real test of course would involve nested lists and

    nested quotations...

    But not tonight.

      - Manfred

## Narcoleptic Electron — 2005-08-16 17:24:06

    On 8/16/05, phimvt@... <phimvt@...> wrote:

     > Maybe this can be adapted for concatenative notation.

    > Start with 2 3 +, write the function composition explicitly using ^

    > to give (2 ^ 3) ^ +, now use postix for ^ to give 2 3 ^ + ^.

    > But that does not solve the problem for lists and quotations, which

    > are needed for say [1 2 3] [dup *] map. But suppose we use $ for

    > constructing these. How about this:

    >

    >   1 2 3 ^ ^ $ $ $   dup * ^ $ $   ^ map ^

    >

    > where a string of N dollars means: "form a list from the N items

    > on the stack and push it onto the stack. Sounds rather like

    > a proposal we have seen on this group (Stevan?), which uses

    > the integer N on the stack and a single operator which means

    > the same.

    >

    > Note that with the explicit composition operator all the usual

    > operators and combinators (dup, *, map) just get pushed onto the stack,

    > and it is only by using composition that they get executed.

    >

    > Sorry, this has not been thought out properly. Is it concatenative?

    > Is it flat? Maybe the postfix composition operator is just an

    > unnecessary nuisance, but the list/quotation builder $ (or some

    > more elegant alternative) is of some use?

    >

    > But here is yet another alternative:

    >

    > DEFINE

    >   NIL  ==  [];

    >   !    ==  NIL cons i

    >            (* execute the topmost single item on the stack *).

    >

    > Everything other than ! is a push. Then write

    >

    >     1 2 3 NIL cons ! cons ! cons ! dup * NIL cons ! cons ! map !

    >

    > Here each NIL cons ! would behave rather like $ above.  Note the map !

    > would have to supply its own implicit ! for each item in the quotation.

    > Not so pretty.  The real test of course would involve nested lists and

    > nested quotations...

     This makes "!" a "special word" that doesn't just get pushed like all

    the other words.

    If I'm understanding correctly, this appears similar to my language,

    which uses whitespace instead of "!".  A quick translation of the

    original Joy example follows:

    [1 2 3][#s]

    [[dup] [*]][code]

    [map]

    The basics:

    - A square bracket enclosure means "push the enclosed text value onto

    the stack".

    - Whitespace (and end of code) means "(1) treat the text value at the

    TOS as a name, then (2) evaluate it, replacing it with its defined

    value."

    Programs used:

    - The program named "#s" replaces a text value with a list of numbers.

    - The program named "code" replaces a text value with a code value,

    which is a list wherein each item is either a string or an "evaluator

    flag" (indicating that the string preceding it is to be evaluated as a

    name) and corresponds exactly to the source code (string from

    [whatever], evaluator flag from whitespace).

    - The program named "map" pops a list and a code value, and applies

    the code to each item in the list.

    This could be considered flat as it doesn't use any nesting: inner

    brackets are just text (unbalanced ones must be escaped for parsing

    reasons), and text can be broken up any which way.  However, it could

    be rewritten so that instead of using text "quotations", the values

    get built up piece by piece, as you have done in your example above.

    Here is my stab at it:

    [1][#] [2][#] [3][#] [nil] [cons] [cons] [cons]

    [dup][!] [*][!] [nil] [cons] [cons] [cons] [cons]

    [map]

    Programs used:

    - The program named "#" replaces the text TOS value with its numeric equivalent.

    - The program named "!" pushes an evaluator flag.

    For readability, the identity program named "" can be used to make

    stack contents a little more clear:

    [1][#] [2][#] [3][#] [nil] [cons] [cons] [cons]

    [dup][] [!] [*][] [!] [nil] [cons] [cons] [cons] [cons]

    [map]

    Note that this is all quick-and-dirty (I haven't even implemented my

    language yet...)

## William Tanksley, Jr — 2005-08-20 03:44:38

    sa@... <sa@...> wrote:

     > so 0 and 1 do mean something "on their own", viz. they

    > each denote a specific function, just as + does in joy.

     Oops -- I was wrong. I got confused between Jot and Iota. You're

    definitely right; it's concatenative, and definitely belongs on this

    egroup :-).

    Facinating language; I don't understand a jot of it.

    -Billy

## William Tanksley, Jr — 2005-08-20 05:40:44

    Narcoleptic Electron <narcoleptic.electron@...> wrote:

     > On 8/16/05, phimvt@... <phimvt@...> wrote:

    > >     1 2 3 NIL cons ! cons ! cons ! dup * NIL cons ! cons ! map !

    > > Here each NIL cons ! would behave rather like $ above.  Note the map !

    > > would have to supply its own implicit ! for each item in the quotation.

    > > Not so pretty.  The real test of course would involve nested lists and

    > > nested quotations...

    > This makes "!" a "special word" that doesn't just get pushed like all

    > the other words.

     Yes, all of our suggestions seem to add a special syntactic element.

    My lazy language would require something like "!" to tell the compiler

    where the dataflow ends. Some people would use EOF, others would want

    something explicit.

     > If I'm understanding correctly, this appears similar to my language,

    > which uses whitespace instead of "!".  A quick translation of the

    > original Joy example follows:

    > [1 2 3][#s]

    > [[dup] [*]][code]

    > [map]

     I don't see the similarity -- your language seems to have the full

    syntactic structure of a typical Joylike language. Plus some more.

     > The basics:

    > - A square bracket enclosure means "push the enclosed text value onto

    > the stack".

    > - Whitespace (and end of code) means "(1) treat the text value at the

    > TOS as a name, then (2) evaluate it, replacing it with its defined

    > value."

     Ah. Yes, very complex syntax.

     > This could be considered flat as it doesn't use any nesting: inner

    > brackets are just text (unbalanced ones must be escaped for parsing

    > reasons), and text can be broken up any which way.  However, it could

    > be rewritten so that instead of using text "quotations", the values

    > get built up piece by piece, as you have done in your example above.

    > Here is my stab at it:

    > [1][#] [2][#] [3][#] [nil] [cons] [cons] [cons]

    > [dup][!] [*][!] [nil] [cons] [cons] [cons] [cons]

    > [map]

     That's flat.

    Try that with prefix, and all text ending at the first space:

    #1 #2 #3 nil cons cons cons !dup !* nil cons cons cons map

    That's essentially how colorForth works. Forth isn't too dissimilar,

    either (although it's more complex and less flat).

    -Billy

## Narcoleptic Electron — 2005-08-20 07:48:41

    On 8/20/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > Narcoleptic Electron <narcoleptic.electron@...> wrote:

    > > On 8/16/05, phimvt@... <phimvt@...> wrote:

    > > >     1 2 3 NIL cons ! cons ! cons ! dup * NIL cons ! cons ! map !

    >

    > > > Here each NIL cons ! would behave rather like $ above.  Note the map !

    > > > would have to supply its own implicit ! for each item in the quotation.

    > > > Not so pretty.  The real test of course would involve nested lists and

    > > > nested quotations...

    >

    > > This makes "!" a "special word" that doesn't just get pushed like all

    > > the other words.

    >

    > Yes, all of our suggestions seem to add a special syntactic element.

     By "special syntactic element", I assume you mean one that represents

    an exception to a rule (eg. a "special word").  This is not the case

    with my language.  Whitespace serves this single purpose only (to pop

    TOS string and push the program with that name).  This is why I'm

    bringing it up as a seemingly cleaner solution.

     > > If I'm understanding correctly, this appears similar to my language,

    > > which uses whitespace instead of "!".  A quick translation of the

    > > original Joy example follows:

    >

    > > [1 2 3][#s]

    > > [[dup] [*]][code]

    > > [map]

    >

    > I don't see the similarity -- your language seems to have the full

    > syntactic structure of a typical Joylike language.

     You're correct: there's not much similarity in this example.  The

    similarity comes below when I give the flat version in the same

    language.  The similarity there is that whitespace in mine does the

    job of the special "!" word in yours, more or less.

     > Plus some more.

     There is considerably less syntactic structure in my language than in Joy.

     > > The basics:

    > > - A square bracket enclosure means "push the enclosed text value onto

    > > the stack".

    > > - Whitespace (and end of code) means "(1) treat the text value at the

    > > TOS as a name, then (2) evaluate it, replacing it with its defined

    > > value."

    >

    > Ah. Yes, very complex syntax.

     You're kidding, right...?

     > > This could be considered flat as it doesn't use any nesting: inner

    > > brackets are just text (unbalanced ones must be escaped for parsing

    > > reasons), and text can be broken up any which way.  However, it could

    > > be rewritten so that instead of using text "quotations", the values

    > > get built up piece by piece, as you have done in your example above.

    > > Here is my stab at it:

    >

    > > [1][#] [2][#] [3][#] [nil] [cons] [cons] [cons]

    > > [dup][!] [*][!] [nil] [cons] [cons] [cons] [cons]

    > > [map]

    >

    > That's flat.

    >

    > Try that with prefix, and all text ending at the first space:

    >

    > #1 #2 #3 nil cons cons cons !dup !* nil cons cons cons map

     That's not as clean, because in my language, "#" and "!" are just

    regular programs, like "cons" and "nil".  There are absolutely no

    "special programs" or "tokens that have special parsing rules"; only

    whitespace and words (enclosed in []).  A word is either interpreted

    as a literal or a lexeme (to be looked up in the dictionary),

    depending on whether there is whitespace after it.

    I didn't intend to hijack this thread to talk about my language; just

    trying to demonstrate what I consider a simple and clean way to

    achieve flatness.

## phimvt@lurac.latrobe.edu.au — 2005-08-22 06:26:01

    On Fri, 19 Aug 2005, William Tanksley, Jr wrote:

     > Yes, all of our suggestions seem to add a special syntactic element.

     Indeed, there seems to be no way around it.  I keep on changing my mind

    about whether it is possible at all.  But then, after all the parser has

    as input a flat sequence, and manages to construct a possibly nested

    structure from that.  The way the Joy parser does it is this: when it sees

    [ , it starts an empty list. Subsequently, when it sees anything except ]

    , it APPENDs it to the most recently constructed list.  When it sees the

    closing ] , it APPENDs this list to the output stream (the program to be

    executed). Can we delay this construction so that it happens not at

    compile time but at run time? Yes, like this:

    Let A (pronounced "append") be a new unary operator which can only occur

    before atoms (literals, operators, combinators).  For any atom x, let "Ax"

    mean: append x to the list on top of the stack. Also, we need another

    ordinary operator E (pronounced "end", which means: append the list on top

    of the stack to the list which is second on the stack. Then

       [1 2 3]  [dup *]  map                # ==>  [1 4 9]

    would be rewritten as:

       [] A1 A2 A3 E  [] Adup A* E  map

    Similarly, the nested data and nested program

       [[1 2 [3]]  [[dup *] map]  map       # ==>  [[1 4][9]]

    would be rewritten as

       [] [] A1 A2 E [] A3 E E   [] Adup A* E  map

    The E operator is an ordinary Joy operator, it might have been defined by

       E  ==  [reverse] dip  cons  reverse

    But the A operator is something quite new, it cannot be defined in Joy,

    and it is the price we would have to pay for this particular version of

    flatness.  I do not at this stage know whether it would be useful to allow

    repetitions of the A operator, as in AAAx, which would append AAx to the

    end of the list on top of the stack.

    [Incidentally, when I wrote the implementation of Joy I had to decide

    whether to use normal linked lists or the slightly more complicated and

    more versatile circular lists. I used the first because it is more

    efficient, and because it seemed that the extra power of circular lists

    was not needed. But circular lists would be ideal for implementing the A

    operator - and quite a few other things.]

    Is this particular solution to the flatness problem really different from

    others? Not really, much of it is identical to Stevan's XY solution which

    uses a queue Y, together with some operators managing the traffic between

    the stack X and the queue Y. My solution essentially treats the list on

    top of the stack as a queue. Thanks, Stevan.

      - Manfred

## Narcoleptic Electron — 2005-08-22 15:12:17

    On 8/22/05, phimvt@... <phimvt@...> wrote:

     >

    > On Fri, 19 Aug 2005, William Tanksley, Jr wrote:

    >

    > > Yes, all of our suggestions seem to add a special syntactic element.

    >

    > Indeed, there seems to be no way around it.

     ?   I believe I just demonstrated one.  My language only has string

    literals (enclosed with "[]" rather than double quote) and whitespace.

     No other literals or syntactic constructs, and no special rules.

    This is a subset of the syntax of every other language being

    discussed, as I presume that they all have a means of specifying a

    string literal (probably enclosing it with double quotes).

     > But then, after all the parser has

    > as input a flat sequence, and manages to construct a possibly nested

    > structure from that.  The way the Joy parser does it is this: when it sees

    > [ , it starts an empty list. Subsequently, when it sees anything except ]

    > , it APPENDs it to the most recently constructed list.  When it sees the

    > closing ] , it APPENDs this list to the output stream (the program to be

    > executed). Can we delay this construction so that it happens not at

    > compile time but at run time? Yes, like this:

    >

    > Let A (pronounced "append") be a new unary operator which can only occur

    > before atoms (literals, operators, combinators).  For any atom x, let "Ax"

    > mean: append x to the list on top of the stack. Also, we need another

    > ordinary operator E (pronounced "end", which means: append the list on top

    > of the stack to the list which is second on the stack. Then

    >

    >    [1 2 3]  [dup *]  map                # ==>  [1 4 9]

    >

    > would be rewritten as:

    >

    >    [] A1 A2 A3 E  [] Adup A* E  map

    >

    > Similarly, the nested data and nested program

    >

    >    [[1 2 [3]]  [[dup *] map]  map       # ==>  [[1 4][9]]

    >

    > would be rewritten as

    >

    >    [] [] A1 A2 E [] A3 E E   [] Adup A* E  map

    >

    > The E operator is an ordinary Joy operator, it might have been defined by

    >

    >    E  ==  [reverse] dip  cons  reverse

    >

    > But the A operator is something quite new, it cannot be defined in Joy,

    > and it is the price we would have to pay for this particular version of

    > flatness.  I do not at this stage know whether it would be useful to allow

    > repetitions of the A operator, as in AAAx, which would append AAx to the

    > end of the list on top of the stack.

     As I see it, the only reason that "A" needs to be special is so that

    the word it prefixes isn't evaluated.  In other words, it quotes the

    word.

    Instead of doing this, what is wrong with my solution of using a

    string as a quoted word?  All tokens are strings to start off with,

    but some get evaluated as words and some remain strings, depending on

    whether they are followed by whitespace or not.

## William Tanksley, Jr — 2005-08-22 23:46:21

    Narcoleptic Electron <narcoleptic.electron@...> wrote:

     > On 8/22/05, phimvt@... <phimvt@...> wrote:

    > > On Fri, 19 Aug 2005, William Tanksley, Jr wrote:

    > > > Yes, all of our suggestions seem to add a special syntactic element.

    > > Indeed, there seems to be no way around it.

    > ?   I believe I just demonstrated one.  My language only has string

    > literals (enclosed with "[]" rather than double quote) and whitespace.

    >  No other literals or syntactic constructs, and no special rules.

     But your "string literals" are more than mere strings -- they're

    highly specified syntaxes, one of which (the "code" syntax) is the

    full language, including the possibility for arbitrarily nested

    literals.

     > This is a subset of the syntax of every other language being

    > discussed, as I presume that they all have a means of specifying a

    > string literal (probably enclosing it with double quotes).

     None of them require a complete nested syntax in the string literals.

     > As I see it, the only reason that "A" needs to be special is so that

    > the word it prefixes isn't evaluated.  In other words, it quotes the

    > word.

     Yes. Or in other words, it applies some other way of reading the word

    aside from the default "compile or interpret".

     > Instead of doing this, what is wrong with my solution of using a

    > string as a quoted word?  All tokens are strings to start off with,

    > but some get evaluated as words and some remain strings, depending on

    > whether they are followed by whitespace or not.

     Nothing's wrong with it -- your method uses postfixes, while the above

    method uses suffixes. The two can be transformed seamlessly into one

    another, but yours takes more characters to type, and I don't see any

    advantage to it. Yours requires every symbol to be quoted with open

    and close delimiters, while his requires only "extraordinary" symbols

    to be quoted.

    -Billy

## Narcoleptic Electron — 2005-08-23 04:16:39

    On 8/22/05, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > But your "string literals" are more than mere strings -- they're

    > highly specified syntaxes, one of which (the "code" syntax) is the

    > full language, including the possibility for arbitrarily nested

    > literals.

     That is incorrect.  The string literals are not more than mere

    strings, nor are they highly specified syntaxes.   They are just

    string literals.  There is no nesting -- the brackets within are

    characters.  Unbalanced brackets must be escaped only for parsing

    reasons.

    The "code" program is the one implicitly called when parsing text

    source code.  It can also be called explicitly on any string.

     > > This is a subset of the syntax of every other language being

    > > discussed, as I presume that they all have a means of specifying a

    > > string literal (probably enclosing it with double quotes).

    >

    > None of them require a complete nested syntax in the string literals.

     Neither does mine.  Programs can do with strings whatever they want,

    and calling the "code" program is only one possible approach.   I also

    demonstrated a flat approach in an earlier email.

     > Nothing's wrong with it -- your method uses postfixes, while the above

    > method uses suffixes. The two can be transformed seamlessly into one

    > another, but yours takes more characters to type, and I don't see any

    > advantage to it.

     Some advantages:

    - Any string can be used as a word (eg. [I am a descriptive name for a word.]).

    - Much simpler to parse: only string literals and whitespace.

    Contrast this with string literals, whitespace, prefix quotation

    operator (in Manfred's example), special "number literal" programs,

    etc...

    Don't get me wrong: I am not slamming Joy.  That language turned me

    around and helped me to see the light of concatenative programming,

    and Manfred's papers are brilliant.

     > Yours requires every symbol to be quoted with open

    > and close delimiters, while his requires only "extraordinary" symbols

    > to be quoted.

     That's exactly the point!  There are no "extraordinary" symbols in my

    language...

## phimvt@lurac.latrobe.edu.au — 2005-08-26 06:50:07

    On Mon, 22 Aug 2005 phimvt@... wrote:

     > On Fri, 19 Aug 2005, William Tanksley, Jr wrote:

    >

    > > Yes, all of our suggestions seem to add a special syntactic element.

     I now think that a new special syntactic element is not necessary

    as long as we relax the definition of flatness just a little bit.

    I proposed the following new syntactic element, which upon relaxation

    will not be necessary:

     > Let A (pronounced "append") be a new unary operator which can only occur

    > before atoms (literals, operators, combinators).  For any atom x, let "Ax"

    > mean: append x to the list on top of the stack. Also, we need another

    > ordinary operator E (pronounced "end", which means: append the list on top

    > of the stack to the list which is second on the stack. Then

    >

    >    [1 2 3]  [dup *]  map                # ==>  [1 4 9]

    >

    > would be rewritten as:

    >

    >    [] A1 A2 A3 E  [] Adup A* E  map

    >

    > Similarly, the nested data and nested program

    >

    >    [[1 2 [3]]  [[dup *] map]  map       # ==>  [[1 4][9]]

    >

    > would be rewritten as

    >

    >    [] [] A1 A2 E [] A3 E E   [] Adup A* E  map

    >

    > The E operator is an ordinary Joy operator, it might have been defined by

    >

    >    E  ==  [reverse] dip  cons  reverse

    >

    > But the A operator is something quite new, it cannot be defined in Joy,

    > and it is the price we would have to pay for this particular version of

    > flatness.

     Now relax the definition of flatness by allowing unitlists of atoms

    (literals, operators, combinators). Then the first program

     >    [1 2 3]  [dup *]  map                # ==>  [1 4 9]

     would be rewritten as

         [] [1] concat [2] concat [3] concat  [] [dup] concat [*] concat  map

    Or for the sake of more compact notation, DEFINE c == concat. :

         [] [1]c [2]c [3]c  [] [dup]c [*]c  map

     > Similarly, the nested data and nested program

    >

    >    [[1 2 [3]]  [[dup *] map]  map       # ==>  [[1 4][9]]

     would be rewritten as

         [] [] [1]c [2]c c [] [3]c c [] [] [dup]c [*]c  c [] [map]c  map

    Define Floy ("Flat Joy") to be that subset of Joy in which the only

    lists or quotations are [] and the unit lists of atoms.  Can we write

    a translator j2f (Joy to Floy) which takes a quoted Joy program J

    and produces a quoted Floy program F such that [J] i == [F] i ?

    (Note that even if F is a Floy program, its quotation [F] generally

    will not be.) Moreover, can the translator j2f be written in Joy?

    If so, then the translator can also be written in Floy, by passing

    it through itself. So there will be a j2f.joy and a j2f.floy. Compiler

    writers do that sort of thing all the time. I don't think that j2f.joy

    will be longer than five short lines, and j2f.floy will just have longer

    lines. I'll work on this, it looks like fun.

     > Is this particular solution to the flatness problem really different from

    > others? Not really, much of it is identical to Stevan's XY solution which

    > uses a queue Y, together with some operators managing the traffic between

    > the stack X and the queue Y. My solution essentially treats the list on

    > top of the stack as a queue. Thanks, Stevan.

     The debt to Stevan extends to Floy too. After all, for any atom a,

    the program [a]c does precisely an append of the atom a to the quotation

    on top of the stack. So the quotation is a queue on top of the stack.

      - Manfred

## phimvt@lurac.latrobe.edu.au — 2005-09-07 08:07:23

    On Fri, 26 Aug 2005 phimvt@... wrote:

    [..]

    > Define Floy ("Flat Joy") to be that subset of Joy in which the only

    > lists or quotations are [] and the unit lists of atoms.  Can we write

    > a translator j2f (Joy to Floy) which takes a quoted Joy program J

    > and produces a quoted Floy program F such that [J] i == [F] i ?

    That should have been [J] i == [F] i i

    > (Note that even if F is a Floy program, its quotation [F] generally

    > will not be.) Moreover, can the translator j2f be written in Joy?

    > If so, then the translator can also be written in Floy, by passing

    > it through itself. So there will be a j2f.joy and a j2f.floy. Compiler

    > writers do that sort of thing all the time. I don't think that j2f.joy

    > will be longer than five short lines, and j2f.floy will just have longer

    > lines. I'll work on this, it looks like fun.

    Well, it took much much longer than I anticipated - how embarrassing.

    But it was fun, and I think I'll write it up as a more detailed note.

    I haven't passed it through itself yet to get j2f.floy, but here is

    the simple version, j2f.joy :

    DEFINE

    	    c  ==  concat;

    	    HIDE

    	        h ==

    	            [ list ]

    		    [ [[[]] concat] dip [h] step [[] cons c] concat ]

    	            [ [] cons [c] cons concat ]

    	  	    ifte;

    	    IN

    	        j2f == [[]] swap [h] step

    	    END;

    	    P1 == [2 3 + dup *];

    	    P2 == [[1 2 3] [dup *] map];

    	    P3 == [ [[1 2][3 4][5] []] [[dup *] map] map ].

    The following tests show, for each of the three example programs P1 P2 P3:

      1: the original quoted Joy program,

      2: the translation as a quoted flat-Joy program

      3: the result of executing the translation (= the original)

      4: the result of executing this result (= executing the original)

    	P1 .

    [2 3 + dup *]

    	P1 j2f .

    [[] [2] c [3] c [+] c [dup] c [*] c]

    	P1 j2f i .

    [2 3 + dup *]

    	P1 j2f i i .

    25

    	P2 .

    [[1 2 3] [dup *] map]

    	P2 j2f .

    [[] [] [1] c [2] c [3] c [] cons c [] [dup] c [*] c [] cons c [map] c]

    	P2 j2f i .

    [[1 2 3] [dup *] map]

    	P2 j2f i i .

    [1 4 9]

    	P3 .

    [[[1 2] [3 4] [5] []] [[dup *] map] map]

    	P3 j2f .

    [[] [] [] [1] c [2] c [] cons c [] [3] c [4] c [] cons c [] [5] c [] cons c [] [] cons c [] cons c [] [] [dup] c [*] c [] cons c [map] c [] cons c [map] c]

    	P3 j2f i .

    [[[1 2] [3 4] [5] []] [[dup *] map] map]

    	P3 j2f i i .

    [[1 4] [9 16] [25] []]

    Note that j2f itself uses "concat" whereas the resultant flat Joy program

    uses "c" (defined as "concat"). That was to distinguish what the j2f

    translator does from the result that it produces. So both use a lot

    of concatenation, because they both operate on queues. But concatenation

    is always expensive.

    Could one replace the two levels of queue manipulation with two levels

    of stack manipulation which would be more efficient? Who cares, you say.

    OK, but similar problems might arise elsewhere, and it is an interesting

    challenge to know about general solutions. So I am now thinking about

    calling the above solution j2f-q, and writing another j2f-s. They should

    satisfy

        [J] j2f-q i  ==  [J]       and       [J] j2f-s i  ==  [J]

    or

            j2f-q i  ==  id        and           j2f-s i  ==  id

    Succinctly, the i combinator is the (post-)inverse of j2f-q and of j2f-s,

    but not conversely.

    More fun? more agony?

      - Manfred