# Fwd: [stack] Concatenative Research

## John Carter — 2011-01-31 01:57:09

    On Mon, Jan 31, 2011 at 1:20 PM, Justin <zallambo@...> wrote:

     > Hello. Is this forum still alive? I haven't shown my head here for a couple

    > of years. I'm a MA/CS major with an ongoing interest in giving concatenative

    > languages a firmer mathematical foundation. I have a few partial results:

    > (i) an operational semantics, (ii) a concept of & application for

    > homomorphisms, (iii) a type system. Is anyone else around here interested in

    > this sort of research? Here's a link to my (ongoing) work,

    >

    > http://dl.dropbox.com/u/17328602/concat/index.html

    >

    >

     Some small comments...

     > There are no variables. I have the impression that variables are a

    > difficult concept to grasp. We spend years teaching students about variables

    > in math class, and even in college many students have difficulty

    > understanding that (lambda x. x) and (lambda y. y) are identical. This is

    > certainly a double-edged sword - variables are a powerful reasoning aid -

    > but I am nonetheless interested in glimpsing a world free of variables.

    >

     One major problem with variables is not variables themselves, but the

    existence of two entirely different concepts overloaded with the same name.

       - Half the time we mean "named storage location" and the other half the

       time we mean "named value". The "named storage location" notion of variables

       implies a stateful system and all the attendant difficulties in analysis.

       - The "named value" notion of variables is a convenience that allows us

       to remove the irrelevant computational fluff of stack manipulations from our

       expressions.

    "Concatenative" refers to the syntactic sugar (glucose?, alcohol?) of

    choosing a syntax in which function composition is represented by string

    concatenation.

    I invite you to contemplate what these languages are in the absence of a

    string representation. (For example, at one higher level of abstraction a

    concatenative language is one where functional composition is represented by

    the concatenation of two lists of tokens. But I'm sure we can abstract it

    well away from the representation.)

    The neatness of concatenative program fragments often arises from a

    carefully pre-chosen alignment of the output values of the previous function

    with the input requirements of the next.

    Where it doesn't align neatly, we need a bunch of stack manipulating "fluff"

    that adds nothing to computation.

    What may be interesting and useful would be to return to typed variables

    (named values variety) and something like a SQL "natural join".

    99% of the time which function result variable, needs to be bound which

    input variable, is obvious and can be automatically inferred from their type

    and name.

    By making the rules for doing this explicit, you should be able to create a

    concatenative language that doesn't involve the notion of a stack, nor are

    the program fragments cluttered with irrelavent variable name references or

    stack manipulation "fluff".

    I would argue that any language where the function definitions are cluttered

    with stack manipulations OR variable references has NOT yet met the full

    promise of concatenative languages.

    --

    John Carter                             Phone : (64)(3) 358 6639

    Tait Electronics                        Fax   : (64)(3) 359 4632

    PO Box 1645 Christchurch                Email : john.carter@...

    New Zealand

    =======================================================================

    This email, including any attachments, is only for the intended

    addressee.  It is subject to copyright, is confidential and may be

    the subject of legal or other privilege, none of which is waived or

    lost by reason of this transmission.

    If the receiver is not the intended addressee, please accept our

    apologies, notify us by return, delete all copies and perform no

    other act on the email.

    Unfortunately, we cannot warrant that the email has not been

    altered or corrupted during transmission.

    =======================================================================

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

## William Tanksley, Jr — 2011-01-31 03:40:19

    John Carter <john.carter@...> wrote:

     > Justin <zallambo@...> wrote:

    >> http://dl.dropbox.com/u/17328602/concat/index.html

    > "Concatenative" refers to the syntactic sugar (glucose?, alcohol?) of

     Definitely syntactic splicing factor U2AF.

     > choosing a syntax in which function composition is represented by string

    > concatenation.

     That's what I think of, yes -- minus the word "sugar". Not all syntax

    is "syntactic sugar". A language might be defined as "the mapping of

    syntax onto semantics"; thus, language design is concerned with

    defining syntax, semantics, and the mapping between them. Words like

    "syntax sugar" encourage a disregard for one of those crucial three

    components of language design.

     > The neatness of concatenative program fragments often arises from a

    > carefully pre-chosen alignment of the output values of the previous function

    > with the input requirements of the next.

    > Where it doesn't align neatly, we need a bunch of stack manipulating "fluff"

    > that adds nothing to computation.

    > What may be interesting and useful would be to return to typed variables

    > (named values variety) and something like a SQL "natural join".

     That is indeed an interesting thought.

    I should note that ANS Forth (for example) says that there may be an

    additional stack on which floating point numbers reside. Floating

    point operators access only the FP stack. Perhaps, therefore, part of

    the solution might involve defining multiple stacks for items with

    different types, and for items involved in different architectural

    purposes.

     > By making the rules for doing this explicit, you should be able to create a

    > concatenative language that doesn't involve the notion of a stack, nor are

    > the program fragments cluttered with irrelavent variable name references or

    > stack manipulation "fluff".

     Possibly true. I'd love to see this explored; it does seem that the

    "stack" is not _necessary_ to the idea of a concatenative language.

     > I would argue that any language where the function definitions are cluttered

    > with stack manipulations OR variable references has NOT yet met the full

    > promise of concatenative languages.

     I know what you mean. Forth, Joy, and Factor are all capable of being

    written without clutter; but it's widely admitted that it's easier to

    do in Factor than it is in Forth. Surely there's more progress to be

    made beyond what Factor's done already!

     > John Carter

     -Wm

## Justin — 2011-01-31 05:11:03

    --- In concatenative@yahoogroups.com, John Carter <john.carter@...> wrote:

     >

    > On Mon, Jan 31, 2011 at 1:20 PM, Justin <zallambo@...> wrote:

    >

    > > Hello. Is this forum still alive? I haven't shown my head here for a couple

    > > of years. I'm a MA/CS major with an ongoing interest in giving concatenative

    > > languages a firmer mathematical foundation. I have a few partial results:

    > > (i) an operational semantics, (ii) a concept of & application for

    > > homomorphisms, (iii) a type system. Is anyone else around here interested in

    > > this sort of research? Here's a link to my (ongoing) work,

    > >

    > > http://dl.dropbox.com/u/17328602/concat/index.html

    > >

    > >

    >

    > What may be interesting and useful would be to return to typed variables

    > (named values variety) and something like a SQL "natural join".

     I don't know what you mean. Could you give an example? (I don't have a good mental model of databases.)

     > 99% of the time which function result variable, needs to be bound which

    > input variable, is obvious and can be automatically inferred from their type

    > and name.

    >

    > By making the rules for doing this explicit, you should be able to create a

    > concatenative language that doesn't involve the notion of a stack, nor are

    > the program fragments cluttered with irrelavent variable name references or

    > stack manipulation "fluff".

    >

    > I would argue that any language where the function definitions are cluttered

    > with stack manipulations OR variable references has NOT yet met the full

    > promise of concatenative languages.

     I am aware of three methods of passing data around:

    1. stack manipulation

    2. variable references (the stateful kind)

    3. implicit state (think of the flags register in assembly)

    We can probably agree that (3) is usually a bad idea. Are there other methods? What else could a concatenative language do?

## Justin — 2011-01-31 05:10:59

    --- In concatenative@yahoogroups.com, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

     >

    > John Carter <john.carter@...> wrote:

    > > Justin <zallambo@...> wrote:

    >

    > That's what I think of, yes -- minus the word "sugar". Not all syntax

    > is "syntactic sugar". A language might be defined as "the mapping of

    > syntax onto semantics"; thus, language design is concerned with

    > defining syntax, semantics, and the mapping between them. Words like

    > "syntax sugar" encourage a disregard for one of those crucial three

    > components of language design.

     I don't understand what you mean. Syntactic sugar is syntax that can be easily explained in terms of other syntax. It says, "rather than give you a mapping from 'for loop' syntax to semantics, I'm going to give you a mapping from 'for loop' syntax to 'while loop' syntax, and then you can use the mapping from 'while loop' syntax to semantics". What's wrong with that?

     > Possibly true. I'd love to see this explored; it does seem that the

    > "stack" is not _necessary_ to the idea of a concatenative language.

     Indeed, my operational semantics does not involve a stack.

     > > I would argue that any language where the function definitions are cluttered

    > > with stack manipulations OR variable references has NOT yet met the full

    > > promise of concatenative languages.

    >

    > I know what you mean. Forth, Joy, and Factor are all capable of being

    > written without clutter; but it's widely admitted that it's easier to

    > do in Factor than it is in Forth.

     Why would you say that is? I know it allows both stack manipulation and variables; is this a potent combination, or is something else at work?

## William Tanksley, Jr — 2011-01-31 16:34:06

    Justin <zallambo@...> wrote:

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

    >> John Carter <john.carter@...> wrote:

    >> > Justin <zallambo@...> wrote:

    >> That's what I think of, yes -- minus the word "sugar". Not all syntax

    >> is "syntactic sugar". A language might be defined as "the mapping of

    >> syntax onto semantics"; thus, language design is concerned with

    >> defining syntax, semantics, and the mapping between them. Words like

    >> "syntax sugar" encourage a disregard for one of those crucial three

    >> components of language design.

    > I don't understand what you mean. Syntactic sugar is syntax that can be easily explained in terms of other syntax. [...] What's wrong with that?

     I didn't mean to imply that "syntactic sugar" should never be used,

    sorry. I meant that it's entirely inappropriate in the use to which I

    was replying. A concatenative language is, by definition, a language

    in which syntactic concatenation is the primary means of expressing

    composition. If there are other means (and there need not be), they

    are the syntactic sugar;concatenation is not.

     >> Possibly true. I'd love to see this explored; it does seem that the

    >> "stack" is not _necessary_ to the idea of a concatenative language.

    > Indeed, my operational semantics does not involve a stack.

     There's no profound reason why it needs to; my friend wrote a very

    simple code generator that used registers for the top stack items.

    However, using something other than a stack means that the behavior of

    the language is different; your operational semantics would be

    different.

     >> I know what you mean. Forth, Joy, and Factor are all capable of being

    >> written without clutter; but it's widely admitted that it's easier to

    >> do in Factor than it is in Forth.

    > Why would you say that is? I know it allows both stack manipulation and variables; is this a potent combination, or is something else at work?

     Something else. (Forth also has both.)

    Factor also has the cleave/spread combinators. From

    http://factor-language.blogspot.com/2008/03/inheritance-tuple-reshaping-cleavers.html:

    "These combinators help structure your data flow by grouping parts of

    computations into one-to-many, many-to-many and many-to-one designs."

    ... "For example, I recently converted our serialization library to

    use these combinators. The result is extremely straightforward: there

    is almost no stack manipulation, except for the occasional dup and

    drop, but it doesn't use named locals either. Thanks to the cleave

    combinators, all values just happen to be in the right place at the

    right time, and everything composes together very nicely, like lego

    bricks."

    -Wm

## William Tanksley, Jr — 2011-01-31 20:08:26

    Justin <zallambo@...> wrote:

     >John Carter <john.carter@...> wrote:

    >> What may be interesting and useful would be to return to typed variables

    >> (named values variety) and something like a SQL "natural join".

    > I don't know what you mean. Could you give an example? (I don't have a

    > good mental model of databases.)

     I'm not certain, but I assumed he was implying that the compiler would

    somehow just figure things out. It's hand-waving, but he admits it

    hasn't been done yet.

     > I am aware of three methods of passing data around:

    > 1. stack manipulation

    > 2. variable references (the stateful kind)

    > 3. implicit state (think of the flags register in assembly)

    > We can probably agree that (3) is usually a bad idea. Are there other methods? What else could a concatenative language do?

     One can also pass data around in data structures; explicit ones, as

    with Joy's lists; semi-implicit ones, as in Joy's 'dip' combinator;

    and implicit ones, as in Forth's global dictionary. XY (one of Apter's

    languages) adds a queue structure to represent source evaluation. It's

    conceivable that some other structure could replace the stack, rather

    than simply augmenting it.

    A "language" which did nothing but join strings into one big string

    would be concatenative in syntax and compositional in semantics,

    although very boring in behavior -- and would replace the stack with a

    string.

    -Wm

## Justin — 2011-01-31 23:36:11

    --- In concatenative@yahoogroups.com, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

     >

    > Justin <zallambo@...> wrote:

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

    > I didn't mean to imply that "syntactic sugar" should never be used,

    > sorry. I meant that it's entirely inappropriate in the use to which I

    > was replying. A concatenative language is, by definition, a language

    > in which syntactic concatenation is the primary means of expressing

    > composition. If there are other means (and there need not be), they

    > are the syntactic sugar;concatenation is not.

     I see now; you are certainly right.

     > >> Possibly true. I'd love to see this explored; it does seem that the

    > >> "stack" is not _necessary_ to the idea of a concatenative language.

    > > Indeed, my operational semantics does not involve a stack.

    >

    > There's no profound reason why it needs to; my friend wrote a very

    > simple code generator that used registers for the top stack items.

    > However, using something other than a stack means that the behavior of

    > the language is different; your operational semantics would be

    > different.

     All I mean to say is that my operational semantics is general enough that it's completely ambivalent as to what kind of states a language's programs act on. There is no mention of stacks -- only states, which could be anything.

    http://dl.dropbox.com/u/17328602/concat/theory/concat.pdf

     > >> I know what you mean. Forth, Joy, and Factor are all capable of being

    > >> written without clutter; but it's widely admitted that it's easier to

    > >> do in Factor than it is in Forth.

    > > Why would you say that is? I know it allows both stack manipulation and variables; is this a potent combination, or is something else at work?

    >

    > Something else. (Forth also has both.)

    >

    > Factor also has the cleave/spread combinators. From

    > http://factor-language.blogspot.com/2008/03/inheritance-tuple-reshaping-cleavers.html:

    >

    > "These combinators help structure your data flow by grouping parts of

    > computations into one-to-many, many-to-many and many-to-one designs."

    > ... "For example, I recently converted our serialization library to

    > use these combinators. The result is extremely straightforward: there

    > is almost no stack manipulation, except for the occasional dup and

    > drop, but it doesn't use named locals either. Thanks to the cleave

    > combinators, all values just happen to be in the right place at the

    > right time, and everything composes together very nicely, like lego

    > bricks."

     I remember seeing references to 'cleave' and 'spread' but never knew what they were. They seem to be elegant tools; thanks for pointing them out.

## William Tanksley, Jr — 2011-02-01 00:31:11

    Justin <zallambo@...> wrote:

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

    >> Justin <zallambo@...> wrote:

    >> >> Possibly true. I'd love to see this explored; it does seem that the

    >> >> "stack" is not _necessary_ to the idea of a concatenative language.

    >> > Indeed, my operational semantics does not involve a stack.

    >> There's no profound reason why it needs to; my friend wrote a very

    >> simple code generator that used registers for the top stack items.

    >> However, using something other than a stack means that the behavior of

    >> the language is different; your operational semantics would be

    >> different.

    > All I mean to say is that my operational semantics is general enough that it's

    > completely ambivalent as to what kind of states a language's programs act

    > on. There is no mention of stacks -- only states, which could be anything.

     Yes, you're right. I don't know whether your study makes any

    stack-oriented assumptions later, but it doesn't make them in its

    opening sections.

    It may be that there's something special about a stack when it comes

    to the primary data transfer mechanism for a Turing-complete

    concatenative model. I don't know, and I'd like to.

     >> Factor also has the cleave/spread combinators. From

    >> http://factor-language.blogspot.com/2008/03/inheritance-tuple-reshaping-cleavers.html:

    >> "These combinators help structure your data flow by grouping parts of

    >> computations into one-to-many, many-to-many and many-to-one designs."

    > I remember seeing references to 'cleave' and 'spread' but never knew what they were. They seem to be elegant tools; thanks for pointing them out.

     Indeed, and like all elegant tools, they are from a more civilized

    age. They were invented by Backus for FP and FL, the languages that

    gave us the term "functional languages", although none of their

    immediate successors met their definition of being functional

    languages.

    -Wm

## Justin — 2011-02-02 02:25:16

    --- In concatenative@yahoogroups.com, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

     > Indeed, and like all elegant tools, they are from a more civilized

    > age. They were invented by Backus for FP and FL, the languages that

    > gave us the term "functional languages", although none of their

    > immediate successors met their definition of being functional

    > languages.

     I never fail to be surprised by how much computer science theory was developed before I was born.

## Don Groves — 2011-02-02 04:17:23

    "It's been a long, strange trip" applies to both The Grateful Dead and Computer Science theory.

    --

    don

     On 1 Feb 2011, at 18:25, Justin wrote:

    >

    > --- In concatenative@yahoogroups.com, "William Tanksley, Jr" <wtanksleyjr@...> wrote:

    > > Indeed, and like all elegant tools, they are from a more civilized

    > > age. They were invented by Backus for FP and FL, the languages that

    > > gave us the term "functional languages", although none of their

    > > immediate successors met their definition of being functional

    > > languages.

    >

    > I never fail to be surprised by how much computer science theory was developed before I was born.

    >

    >

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