# language hierarchy

## John Nowak — 2007-12-04 06:18:31

    Going along with the discussion trying to pin down a definition of

    concatenative and/or develop a new term, I propose this hierarchy with

    the hope that it might be partially correct and/or useful:

    A functional programming language is one that treats computation as

    the evaluation of mathematical functions and avoids state and mutable

    data.

    Examples: Scheme, ML, Haskell

    A function-level programming language is a variable-free functional

    programming language in which all functions are unary and new

    functions are created in terms of existing functions through the use

    of functional forms.

    Examples: FP, FL, APL (?), J (?)

    A compositional programming language is a function-level programming

    language in which composition is the only functional form.

    Examples: Joy, Cat, etc

    A concatenative programming language is a compositional programming

    language in which the concatenation of functions denotes composition.

    Examples: Joy, Cat, etc

    - - -

    Side note: Given that the term compositional programming is taken,

    what about calling them composable programming languages? You'd have

    the following definition (roughly):

    "A programming language is composable if it is a variable-free, all

    functions are unary, and new functions are created only by composing

    existing functions."

    In addition to it not yet having a meaning, I find the term

    "composable programming language" somewhat more playful and to-the-

    point. It also highlights the composable/factorable nature of such

    programs nicely.

    - John

## William Tanksley, Jr — 2007-12-04 16:17:40

    John Nowak <john@...> wrote:

     > Going along with the discussion trying to pin down a definition of

    > concatenative and/or develop a new term, I propose this hierarchy with

    > the hope that it might be partially correct and/or useful:

     Be careful about hierarchies that extend outside of this group's

    direct interest -- if we were to develop one, we really should try to

    develop it on a general-interest programming language group rather

    than one limited to our narrow interests.

    But I never could resist an argument over nit-picking semantics :-).

     > A functional programming language is one that treats computation as

    > the evaluation of mathematical functions and avoids state and mutable

    > data.

    > Examples: Scheme, ML, Haskell

     Hey, that works. It's a direct quote of Wikipedia, so I can't argue with it.

     > A function-level programming language is a variable-free functional

    > programming language in which all functions are unary and new

    > functions are created in terms of existing functions through the use

    > of functional forms.

    > Examples: FP, FL, APL (?), J (?)

     I don't know about FP and FL, but APL, J, and K are binary; and I'm

    not sure it's good to leave them out. How about we call this the

    "combinatory programming language", and rather than talking about

    "functional forms" (what are those? Google won't tell me), we refer to

    "combinators"? Or is that totally not what you meant?

    Another naming choice would be "dataflow language".

     > A compositional programming language is a function-level programming

    > language in which composition is the only functional form.

    > Examples: Joy, Cat, etc

     I don't know what a "functional form" is, so I can't reply.

     > A concatenative programming language is a compositional programming

    > language in which the concatenation of functions denotes composition.

    > Examples: Joy, Cat, etc

     I don't want to narrow us down enough to exclude Forth, Postscript,

    and possibly Factor. Forth has never attempted to be functional.

    "A concatenative programming language is a language in which the

    concatenation of any two valid programs is a valid program, and the

    entire language can be generated by the concatenation of a finite set

    of programs."

     > Side note: Given that the term compositional programming is taken,

    > what about calling them composable programming languages? You'd have

    > the following definition (roughly):

     I don't mind using either word. Neither one is heavily used.

     > "A programming language is composable if it is a variable-free, all

    > functions are unary, and new functions are created only by composing

    > existing functions."

     I'd just skip the first two requirements. Why exclude a language which

    includes variables?

     > In addition to it not yet having a meaning, I find the term

    > "composable programming language" somewhat more playful and to-the-

    > point. It also highlights the composable/factorable nature of such

    > programs nicely.

     It does look like it's available for our use. I see one random person

    on the web using it to mean "a language in which every statement

    returns a value." I'd translate that to mean "a language in which

    every statement is an expression," (and thus can optionally be

    textually included inside another, appropriately typed, statement). I

    think this definition has an advantage over your earlier one in that

    it's phrased in a positive way. It also happens to be a broader

    definition than "concatenative"; every concatenative language is

    my-definition-composable, but Scheme is my-definition-composable but

    not concatenative or combinatorial. FP is my-definition-composable and

    combinatorial, but not concatenative.

    Is it possible to be concatenative but not combinatory? It's

    definitely NOT possible to be concatenative but not composable (both

    by my definitions).

     > - John

     -Wm

## john@johnnowak.com — 2007-12-04 22:03:57

    > John Nowak <john@...> wrote:

    > I don't know about FP and FL, but APL, J, and K are binary; and I'm

    > not sure it's good to leave them out. How about we call this the

    > "combinatory programming language", and rather than talking about

    > "functional forms" (what are those? Google won't tell me), we refer to

    > "combinators"? Or is that totally not what you meant?

     This page might explain it a bit better:

    http://en.wikipedia.org/wiki/Function-level_programming

    This goes into more detail on functional forms (aka "functionals" on the

    wikipedia article):

    http://www.stanford.edu/class/cs242/readings/backus.pdf

    As for J and K, I've seen them called function-level, but this may simply

    be confusion because they're point-free. I'm not really sure.

     > I don't want to narrow us down enough to exclude Forth, Postscript,

    > and possibly Factor. Forth has never attempted to be functional.

     Is Forth really not functional? Can you not view every function as [stack,

    world] -> [stack, world]? I realize this doesn't really capture the spirit

    of the language, but I think it allows Forth to still be classified as

    functional (or function-based). It is possible that Forth violates this in

    ways I'm not aware of; for instance, a Forth with local variables (global

    is fine)

    might not apply. I'd be interested in hearing arguments as to why this

    view of Forth as a functional language isn't valid.

     > I'd just skip the first two requirements. Why exclude a language which

    > includes variables?

     It is necessary to exclude them if you're writing strictly in terms of

    function composition. Dealing with variables implies you're doing

    value-level programming, not function-level programming. If you don't

    consider concatenative languages to be function-level, then you'd not need

    to exclude them. Backus's paper goes into more detail on this.

    However, if you do allow variables, you lose the factorability of

    languages like Joy. I'm not sure I'd want to call anything with local

    bindings (module systems are okay) concatenative, because you can't create

    new functions simply by concatenating; you've got scopes, name clashes,

    and so on getting in the way. Modules don't violate this, because you can

    still compose functions easily within a module, modules exist to avoid

    name clashes, etc.

     > It does look like it's available for our use. I see one random person

    > on the web using it to mean "a language in which every statement

    > returns a value."

     He's a rogue and a drunkard anyway.

     > every concatenative language is

    > my-definition-composable, but Scheme is my-definition-composable but

    > not concatenative or combinatorial. FP is my-definition-composable and

    > combinatorial, but not concatenative.

     Perhaps the quick, precise definition is:

    "A language is composable if programs are written only by composing

    functions."

    This implies a few things that we can avoid stating outright:

    - There are no variables; if there are, you're not writing only in terms

    of function composition, are you!

    - All functions are unary (else they'd not be composable... assuming they

    all return single values anyway, which seems to be a sane assumption)

    - A concatenative syntax isn't required, but it is the most obvious choice

    Joy would fit in this category. FL would not, as functions can be

    manipulated in ways beyond composition. Forth should fit provided local

    variables are eschewed. Haskell wouldn't.

     > Is it possible to be concatenative but not combinatory?

     Heh, it really depends on the definition of concatenative. If you just

    mean a concatentive syntax, then yes. For example, look at unary messages

    in Smalltalk. You're composing messages which select functions, not

    functions themselves.

     > It's definitely NOT possible to be concatenative but not composable

     (both by my definitions).

    Again, depends on the definition. I would think the Smalltalk example

    above is concatenative and not composable, assuming you're talking about a

    concatenative *syntax*. If you consider concatenative languages as a

    subset of compositional/composable languages as I originally proposed (and

    as I would still stick with), then you're correct (by definition).

    - John

## William Tanksley, Jr — 2007-12-05 00:41:31

    <john@...> wrote:

     > > John Nowak <john@...> wrote:

    > > I don't know about FP and FL, but APL, J, and K are binary; and I'm

    > > not sure it's good to leave them out. How about we call this the

    > > "combinatory programming language", and rather than talking about

    > > "functional forms" (what are those? Google won't tell me), we refer to

    > > "combinators"? Or is that totally not what you meant?

    > This page might explain it a bit better:

    > http://en.wikipedia.org/wiki/Function-level_programming

     It does indeed! Thank you.

    And now I'm enlightened. You weren't merely making up your own

    hierarchy :-); you were citing well-established terms.

     > As for J and K, I've seen them called function-level, but this may simply

    > be confusion because they're point-free. I'm not really sure.

     Wikipedia lists them as examples, and doesn't list APL. I think it's

    right -- APL functions are not really manipulable.

     > > I'd just skip the first two requirements. Why exclude a language which

    > > includes variables?

    > It is necessary to exclude them if you're writing strictly in terms of

    > function composition. Dealing with variables implies you're doing

    > value-level programming, not function-level programming. If you don't

    > consider concatenative languages to be function-level, then you'd not need

    > to exclude them. Backus's paper goes into more detail on this.

     I see what you mean. I agree.

    And I guess one might say that concatenative languages would then be

    function-level languages such that the functional form 'unary

    composition' is denoted by the syntactic relationship of

    concatenation. I'm not sure that it's right to say that composition is

    the ONLY functional form; others may be permitted (for example, 'map'

    is a functional form). Perhaps the rule is that those functional forms

    not be expressed in syntax.

     > However, if you do allow variables, you lose the factorability of

    > languages like Joy. I'm not sure I'd want to call anything with local

    > bindings (module systems are okay) concatenative, because you can't create

    > new functions simply by concatenating; you've got scopes, name clashes,

    > and so on getting in the way. Modules don't violate this, because you can

    > still compose functions easily within a module, modules exist to avoid

    > name clashes, etc.

     I agree. It's also not destructive to have local non-concatenative

    syntax here and there, so long as there's some interesting subset of

    the language that IS concatenative.

     > > every concatenative language is

    > > my-definition-composable, but Scheme is my-definition-composable but

    > > not concatenative or combinatorial. FP is my-definition-composable and

    > > combinatorial, but not concatenative.

    > Perhaps the quick, precise definition is:

    > "A language is composable if programs are written only by composing

    > functions."

    > This implies a few things that we can avoid stating outright:

    > - There are no variables; if there are, you're not writing only in terms

    > of function composition, are you!

    > - All functions are unary (else they'd not be composable... assuming they

    > all return single values anyway, which seems to be a sane assumption)

    > - A concatenative syntax isn't required, but it is the most obvious choice

     Okay, I'll agree with that.

    What other syntax choices are available, aside from the trivial choice

    of using a symbol to represent the composition operator? Is that the

    only difference between this definition of 'composable' and

    'concatenative'?

     > Joy would fit in this category. FL would not, as functions can be

    > manipulated in ways beyond composition. Forth should fit provided local

    > variables are eschewed. Haskell wouldn't.

     ...yet well-defined and "interesting" subsets of all those languages

    would be composable. Haskell, to the best of my knowledge, doesn't

    have an interesting subset that's concatenative -- you have to use an

    explicit operator to denote composition.

    Correct?

     > > Is it possible to be concatenative but not combinatory?

    > > It's definitely NOT possible to be concatenative but not composable

    > > (both by my definitions).

    > Again, depends on the definition.

     Hence my caveat "by my definitions".

     > - John

     -Wm

## John Nowak — 2007-12-05 07:04:56

    On Dec 4, 2007, at 7:41 PM, William Tanksley, Jr wrote:

     >> This page might explain it a bit better:

    >> http://en.wikipedia.org/wiki/Function-level_programming

    >

    > It does indeed! Thank you.

    >

    > And now I'm enlightened. You weren't merely making up your own

    > hierarchy :-); you were citing well-established terms.

     Aye. I should've been more clear.

     >  I'm not sure that it's right to say that composition is

    > the ONLY functional form; others may be permitted (for example, 'map'

    > is a functional form).

     In Joy, map isn't a functional form; it's just a normal higher order

    function that operates on the value level. The fact that ones of the

    values is a function doesn't make map any less value-level.

    Composition in Joy isn't value-level; it's a function-level operation.

    (Of course, Joy also has a function named 'compose' that operates on

    values and is value-level.) FL had many of these functional forms; Joy

    has composition as the only functional form in terms of which programs

    are written. More on this later...

     > It's also not destructive to have local non-concatenative

    > syntax here and there, so long as there's some interesting subset of

    > the language that IS concatenative.

     Agreed. Like in the functional programming world where there are

    varying degrees of how functional something is -- Haskell is purely

    functional, ML is mostly functional, etc -- it would be the same here.

     >> - A concatenative syntax isn't required, but it is the most obvious

    >> choice

    >

    > What other syntax choices are available, aside from the trivial choice

    > of using a symbol to represent the composition operator? Is that the

    > only difference between this definition of 'composable' and

    > 'concatenative'?

     It's the only thing I see as distinguishing concatenative from

    composable if you consider concatenative languages a subset of

    composable languages. As for other syntactic choices, yes, an explicit

    operator is one way. This might be useful in a language that's not

    purely composable. Graphical syntaxes also could exist. I can imagine

    only ones that are fairly useless at the moment however.

     >> Joy would fit in this category. FL would not, as functions can be

    >> manipulated in ways beyond composition. Forth should fit provided

    >> local

    >> variables are eschewed. Haskell wouldn't.

    >

    > ...yet well-defined and "interesting" subsets of all those languages

    > would be composable.

     I don't think there's anything composable about Haskell, strictly

    speaking. The compose operator in Haskell is really just a function

    with infix syntax that operates on functions /as values/ via function

    application. This is something you can add to most any vaguely

    functional language:

    	(define (compose f g) (lambda args (f (apply g args))))

    To be more clear, in Joy, composition is the only functional form. In

    Haskell, /application/ is the primary functional form. In the program

    'f (g 5)', there's no apply function being called that deals with f or

    g as values. Again, you can have an 'apply' function that operates on

    the value level as in the above Scheme example, but that's something

    different. Interestingly, FL does not have a functional form for

    application as there are no arguments to be applying functions to.

    As I'd not consider Haskell composable, I'd not consider it

    concatenative either.

    - John

## John Nowak — 2007-12-05 07:11:33

    On Dec 5, 2007, at 2:04 AM, John Nowak wrote:

     > I don't think there's anything composable about Haskell

     Just to point out; I think this is the desirable outcome of a good

    definition for "composable". Haskell isn't any more composable than

    Joy is applicative, despite Haskell have a 'compose' function and Joy

    have an 'apply' function (called 'i').

    - John

## John Nowak — 2007-12-05 07:16:45

    On Dec 5, 2007, at 2:11 AM, John Nowak wrote:

     > Just to point out; I think this is the desirable outcome of a good

    > definition for "composable". Haskell isn't any more composable than

    > Joy is applicative, despite Haskell have a 'compose' function and Joy

    > have an 'apply' function (called 'i').

     Really not sure what I had against the present tense in this one...

    - John

## William Tanksley, Jr — 2007-12-05 15:13:38

    John Nowak <john@...> wrote:

     > William Tanksley, Jr wrote:

    > > It's also not destructive to have local non-concatenative

    > > syntax here and there, so long as there's some interesting subset of

    > > the language that IS concatenative.

    > Agreed. Like in the functional programming world where there are

    > varying degrees of how functional something is -- Haskell is purely

    > functional, ML is mostly functional, etc -- it would be the same here.

     Hmm... Right. And much the same, there are benefits and drawbacks to

    impurity... Perhaps one way of saying it is that impure programs can

    tersely express some things for which pure ones need more verbosity,

    while pure programs can be reasoned about using a simpler logic.

    That's just experience speaking, no hard theory.

    I do like your definitions now. Chris, any opinion?

     > >> - A concatenative syntax isn't required, but it is the most obvious

    > >> choice

    > > What other syntax choices are available, aside from the trivial choice

    > > of using a symbol to represent the composition operator? Is that the

    > > only difference between this definition of 'composable' and

    > > 'concatenative'?

    > It's the only thing I see as distinguishing concatenative from

    > composable if you consider concatenative languages a subset of

    > composable languages.

     Hmm. Okay, I think I get it. Review: composable means that function

    composition is available and capable of forming interesting programs.

    Concatenative means that function composition is the default operation

    (performed by merely concatenating functions).

     > >> Joy would fit in this category. FL would not, as functions can be

    > >> manipulated in ways beyond composition. Forth should fit provided

    > >> local variables are eschewed. Haskell wouldn't.

    > > ...yet well-defined and "interesting" subsets of all those languages

    > > would be composable.

    > I don't think there's anything composable about Haskell, strictly

    > speaking. The compose operator in Haskell is really just a function

    > with infix syntax that operates on functions /as values/ via function

    > application.

     Perhaps, but the language supports that composition on such a

    fundamental level that it's hard to identify it as NOT part of its

    syntax. A number of different subsets of Haskell can be constructed

    that form a composable language -- for example, consider a stack

    monad. At least if I'm reading your definition of 'composable'

    correctly.

    Of course, Haskell as a whole isn't composable, or at least isn't

    purely composed. It's just that it has all of the syntactic power

    needed to construct purely composed programs.

     > This is something you can add to most any vaguely

    > functional language:

    >         (define (compose f g) (lambda args (f (apply g args))))

     Sure; and if you can define that as infix, your language has

    superficial support for composability. If you can define it as the

    default operation for concatenation, your language has superficial

    support for concatenativity. Making that support more than superficial

    will require being able to define the datatype on which the functions

    are operating, and the basis set of functions themselves.

     > As I'd not consider Haskell composable, I'd not consider it

    > concatenative either.

     I'd consider it composable (if I understand the word correctly) -- it

    has sufficient expressive power to be warped that way -- but not

    purely composable. To the best of my understanding, it's not at all

    concatenative.

    I think your definition is adequate, so let's go forward with it.

     > - John

     -Wm

## John Nowak — 2007-12-06 05:31:20

    On Dec 5, 2007, at 10:13 AM, William Tanksley, Jr wrote:

     > Hmm. Okay, I think I get it. Review: composable means that function

    > composition is available and capable of forming interesting programs.

    > Concatenative means that function composition is the default operation

    > (performed by merely concatenating functions).

     No, not quite. Composable means composing functions is the only way to

    write programs. Joy works this way. Concatenative languages are

    composable languages with Joy-style syntax. I do not know of any

    language that is composable and not also concatenative; It's the

    obvious syntax to use. However, you can imagine such languages fairly

    easily.

     >> I don't think there's anything composable about Haskell, strictly

    >> speaking. The compose operator in Haskell is really just a function

    >> with infix syntax that operates on functions /as values/ via function

    >> application.

    >

    > Perhaps, but the language supports that composition on such a

    > fundamental level that it's hard to identify it as NOT part of its

    > syntax.

     It isn't any more part of the syntax than 'apply' is part of Cat's

    syntax.

     > A number of different subsets of Haskell can be constructed

    > that form a composable language -- for example, consider a stack

    > monad. At least if I'm reading your definition of 'composable'

    > correctly.

     No, I don't think you are. The compose function in haskell operates on

    values via application, not on functions directly as it does in Joy.

    Haskell is a functional language, not a function-level language like FL.

     >> This is something you can add to most any vaguely

    >> functional language:

    >>        (define (compose f g) (lambda args (f (apply g args))))

    >

    > Sure; and if you can define that as infix, your language has

    > superficial support for composability.

     Neither infixness, nor any other syntax-related feature, has nothing

    to do with my definition of 'composable'.

     >  think your definition is adequate, so let's go forward with it.

     Hm. Well, I will at least!

    - John

## John Nowak — 2007-12-06 05:33:41

    On Dec 6, 2007, at 12:31 AM, John Nowak wrote:

     > Neither infixness, nor any other syntax-related feature, has nothing

    > to do with my definition of 'composable'.

     s/nothing/anything

    Ugh. Apologies. I'm sick you see.

    - John

## John Nowak — 2007-12-06 05:39:38

    On Dec 6, 2007, at 12:33 AM, John Nowak wrote:

     > On Dec 6, 2007, at 12:31 AM, John Nowak wrote:

    >

    >> Neither infixness, nor any other syntax-related feature, has nothing

    >> to do with my definition of 'composable'.

    >

    > s/nothing/anything

     s/has/have

    Maybe I should take a break. Sorry for the noise.

## Christopher Diggins — 2007-12-06 14:36:23

    On Dec 5, 2007 2:04 AM, John Nowak <john@...> wrote:

     > Composition in Joy isn't value-level; it's a function-level operation.

    > (Of course, Joy also has a function named 'compose' that operates on

    > values and is value-level.) FL had many of these functional forms; Joy

    > has composition as the only functional form in terms of which programs

    > are written. More on this later...

     Terminology such as "value-level" and "function-level" are outdated

    and are very uncommon in modern literature on programming language

    theory. You seem to be saying that composition is part of the abstract

    syntax in Joy and application isn't, and that in a language like

    Haskell application is part of the abstract syntax and composition

    isn't. I think that would be a more effective way to communictate the

    same sentiment. FWIW I agree with what you are saying, just

    nit-picking how you are saying it.

    ....

     > As I'd not consider Haskell composable, I'd not consider it

    > concatenative either.

     So concatenation of terms in Haskell denotes application, but it isn't

    considered a concatenative language according to your definition. Try

    explaining that to a random group of programmer or computer scientists

    and see what their reaction is.

    - Christopher Diggins

## William Tanksley, Jr — 2007-12-06 17:55:50

    Christopher Diggins <cdiggins@...> wrote:

     > Terminology such as "value-level" and "function-level" are outdated

    > and are very uncommon in modern literature on programming language

    > theory. You seem to be saying that composition is part of the abstract

    > syntax in Joy and application isn't, and that in a language like

    > Haskell application is part of the abstract syntax and composition

    > isn't. I think that would be a more effective way to communicate the

    > same sentiment. FWIW I agree with what you are saying, just

    > nit-picking how you are saying it.

     I don't see that any terms here became outdated; they simply never

    were heavily used. Few of the languages allegedly inspired by FP and

    FL actually used their core ideas (especially this one).

     > > As I'd not consider Haskell composable, I'd not consider it

    > > concatenative either.

    > So concatenation of terms in Haskell denotes application, but it isn't

    > considered a concatenative language according to your definition. Try

    > explaining that to a random group of programmer or computer scientists

    > and see what their reaction is.

     But it doesn't, I think. Concatenation of terms in Haskell perhaps

    offers those terms for partial application; but the application only

    happens if the first term denotes a function with a free variable.

    Otherwise ... Well, I'm not sure; is it a syntax error? At any rate,

    it's not application.

    I don't think the path you're trying to walk will be fruitful. The

    problem is that any language written in plain text MUST do something

    when terms are concatenated (because that's the only thing you can DO

    with plain text); trying to call a language "concatenative" merely

    because it "does something" *in some cases* when terms are

    concatenated is so vague it describes ALL languages.

    A language that deserves the name "concatenative" should respond to

    concatenation in the same way every time.

     > - Christopher Diggins

     -Wm

## William Tanksley, Jr — 2007-12-06 18:09:00

    John Nowak <john@...> wrote:

     > William Tanksley, Jr wrote:

    > > Hmm. Okay, I think I get it. Review: composable means that function

    > > composition is available and capable of forming interesting programs.

    > > Concatenative means that function composition is the default operation

    > > (performed by merely concatenating functions).

    > No, not quite. Composable means composing functions is the only way to

    > write programs.

     Okay, sorry. You might want to choose a different word form then...

    the suffix "-able" means that the action is possible, not that it's

    mandatory. Perhaps "compository" or "compositional"?

    http://plato.stanford.edu/entries/compositionality/ (already taken,

    but not in programming).

     > Joy works this way. Concatenative languages are

    > composable languages with Joy-style syntax. I do not know of any

    > language that is composable and not also concatenative; It's the

    > obvious syntax to use. However, you can imagine such languages fairly

    > easily.

     So "concatenative" in your definition refers ONLY to the syntax of a

    composable language! Interesting. Perhaps Chris is right, and your

    definition of "concatenative" could apply to non-composable languages

    as well.

     > >> I don't think there's anything composable about Haskell, strictly

    > >> speaking. The compose operator in Haskell is really just a function

    > >> with infix syntax that operates on functions /as values/ via function

    > >> application.

    > > Perhaps, but the language supports that composition on such a

    > > fundamental level that it's hard to identify it as NOT part of its

    > > syntax.

    > It isn't any more part of the syntax than 'apply' is part of Cat's

    > syntax.

     Apply doesn't have special syntax support in Cat. The composition

    operator has special syntax support in Haskell.

     > > A number of different subsets of Haskell can be constructed

    > > that form a composable language -- for example, consider a stack

    > > monad. At least if I'm reading your definition of 'composable'

    > > correctly.

    > No, I don't think you are. The compose function in haskell operates on

    > values via application, not on functions directly as it does in Joy.

    > Haskell is a functional language, not a function-level language like FL.

     When you're looking at a Haskell program which uses composition

    exclusively, can you tell it's not actually "composable"? I would say

    that there are subsets of Haskell which are composable, just as there

    are subsets of Joy which are not (for example, function definition).

     > >> This is something you can add to most any vaguely

    > >> functional language:

    > >>        (define (compose f g) (lambda args (f (apply g args))))

    > > Sure; and if you can define that as infix, your language has

    > > superficial support for composability.

    > Neither infixness, nor any other syntax-related feature, has anything

    > to do with my definition of 'composable'.

     All features of a language are syntax-related.

     > - John

     -Wm

## Christopher Diggins — 2007-12-06 18:20:06

    > > So concatenation of terms in Haskell denotes application, but it isn't

    > > considered a concatenative language according to your definition. Try

    > > explaining that to a random group of programmer or computer scientists

    > > and see what their reaction is.

    >

    > But it doesn't, I think. Concatenation of terms in Haskell perhaps

    > offers those terms for partial application; but the application only

    > happens if the first term denotes a function with a free variable.

     That statement is simply false.

    See: http://www.haskell.org/onlinereport/exps.html

    "Function application is written e1 e2."

     > I don't think the path you're trying to walk will be fruitful. The

    > problem is that any language written in plain text MUST do something

    > when terms are concatenated (because that's the only thing you can DO

    > with plain text);

     False. The following is not simply invalid C:

    "12 13"

    Notice the concatenation of terms!

     > trying to call a language "concatenative" merely

    > because it "does something" *in some cases* when terms are

    > concatenated is so vague it describes ALL languages.

     That is not true. See: C, Java, C++, Pascal, Algol, etc. etc. etc.

     > A language that deserves the name "concatenative" should respond to

    > concatenation in the same way every time.

     Whatever response you require in your definition, be it application,

    composition, or some other operation, will be arbitrary: hence

    confusing.

    - Christopher

## John Nowak — 2007-12-06 19:02:06

    On Dec 6, 2007, at 1:09 PM, William Tanksley, Jr wrote:

     >> No, not quite. Composable means composing functions is the only way

    >> to

    >> write programs.

    >

    > Okay, sorry. You might want to choose a different word form then...

    > the suffix "-able" means that the action is possible, not that it's

    > mandatory. Perhaps "compository" or "compositional"?

    > http://plato.stanford.edu/entries/compositionality/ (already taken,

    > but not in programming).

     Well, perhaps you have "purely composable", "partially composable", et

    cetera. No different than "purely functional" really. Compositional is

    taken in programming, if you recall earlier discussion.

     > So "concatenative" in your definition refers ONLY to the syntax of a

    > composable language! Interesting. Perhaps Chris is right, and your

    > definition of "concatenative" could apply to non-composable languages

    > as well.

     I think that's reasonable. However, I also think it makes the term

    concatenative fairly useless, which I believe is what Chris was

    saying. Fair enough; I do agree.

     > Apply doesn't have special syntax support in Cat. The composition

    > operator has special syntax support in Haskell.

     No more special than any other infix operator (which are user-

    definable in Haskell).

     > When you're looking at a Haskell program which uses composition

    > exclusively, can you tell it's not actually "composable"?

     Perhaps dropping the requirement that composition be part of the

    abstract syntax (as Chris says) is sensible. Then, I suppose, Haskell

    would be partially composable. However, so would many other languages

    (Scheme, Python, etc).

    When explaining composable languages, it's difficult to make their

    benefits clear if Haskell is composable PLUS all the other stuff we're

    used to. We (as in people on this list) already essentially know what

    we're talking about and why Joy, Forth, Cat, Factor, etc, are related.

    It's conveying the idea to other people in a way that's clear and

    attractive that warrants a new term. For that, I'd prefer a definition

    that's possibly overly precise to one that's too vague so that the

    properties (and benefits) of such languages are not in question.

    - John

## John Nowak — 2007-12-06 19:28:07

    We might restrict the definition of composable to make it more useful

    by adding the requirement that all functions be unary (e.g. stack ->

    stack). Indeed, this is why we can write everything in terms of

    function composition in the first place.

    Not only does this narrow things down a bit (which is a good thing if

    you want to be able to talk about the properties of such languages),

    it also removes the need for silly explicit restrictions like

    "composition be part of the abstract syntax"; If you require that all

    functions be unary, then implicitly composition *must* be part of the

    abstract syntax as it's a binary operation.

    "A language is composable if new functions are created only by

    composing existing unary functions."

    Then again, if you require that functions be written *only* in terms

    of composition, then all functions *must* be unary anyway, and hence

    composition *must* be part of the abstract syntax. Hence, adding the

    unary restriction to the definition is unnecessary. For the purposes

    of making the definition useful, I think the "only" requirement is

    very reasonable. We can extend this definition to talk about

    "partially composable" languages when the time comes.

    - John

## William Tanksley, Jr — 2007-12-09 20:21:56

    Christopher Diggins <cdiggins@...> wrote:

     > > > So concatenation of terms in Haskell denotes application, but it isn't

    > > > considered a concatenative language according to your definition. Try

    > > > explaining that to a random group of programmer or computer scientists

    > > > and see what their reaction is.

    > > But it doesn't, I think. Concatenation of terms in Haskell perhaps

    > > offers those terms for partial application; but the application only

    > > happens if the first term denotes a function with a free variable.

    > That statement is simply false.

    > See: http://www.haskell.org/onlinereport/exps.html

    > "Function application is written e1 e2."

     I can't read that page, unfortunately (a lack of experience with the

    grammar); but from the look of it, the grammar is a LOT more complex

    than you're implying. It's true that function application is written

    e1 e2; but that doesn't mean that everything written as e1 e2 is a

    function application. Does it? And in fact, right above the informal

    discussion of e1 e2, there's a grammatical and precise note about

    "[fval] aval", which seems to imply a distinction between functions

    and things which can be applied to functions.

     > > I don't think the path you're trying to walk will be fruitful. The

    > > problem is that any language written in plain text MUST do something

    > > when terms are concatenated (because that's the only thing you can DO

    > > with plain text);

    > False. The following is not simply invalid C:

    > "12 13"

    > Notice the concatenation of terms!

     I don't get it. That looks to me like invalid C. Why do you say it's

    not invalid?

    Anyhow, my point was that there must be SOME use of concatenation for

    every text based language; but calling a language "concatenative" has

    to mean that concatenation _always_ means something.

     > > trying to call a language "concatenative" merely

    > > because it "does something" *in some cases* when terms are

    > > concatenated is so vague it describes ALL languages.

    > That is not true. See: C, Java, C++, Pascal, Algol, etc. etc. etc.

     Those are further examples of my point: languages in which

    concatenation does something some times. The simple *presence* of

    concatenation in the grammar isn't enough, any more than the simple

    presence of functions is enough to make a language "functional".

     > > A language that deserves the name "concatenative" should respond to

    > > concatenation in the same way every time.

    > Whatever response you require in your definition, be it application,

    > composition, or some other operation, will be arbitrary: hence

    > confusing.

     But my point is that I don't require anything in my definition.

    There's nothing arbitrary there. You can propose any operation you

    want; but so far, the only one that's proven to work consistently and

    "interestingly" is function composition.

    Now, I admit that my definition lacks boundaries; nobody knows for

    sure whether composition is the only possible operation. But in the

    same sense my definition also lacks arbitrariness.

     > - Christopher

     -Wm

## Christopher Diggins — 2007-12-09 21:49:35

    On Dec 9, 2007 3:21 PM, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > Christopher Diggins <cdiggins@...> wrote:

    > > > > So concatenation of terms in Haskell denotes application, but it isn't

    > > > > considered a concatenative language according to your definition. Try

    > > > > explaining that to a random group of programmer or computer scientists

    > > > > and see what their reaction is.

    >

    > > > But it doesn't, I think. Concatenation of terms in Haskell perhaps

    > > > offers those terms for partial application; but the application only

    > > > happens if the first term denotes a function with a free variable.

    >

    > > That statement is simply false.

    > > See: http://www.haskell.org/onlinereport/exps.html

    > > "Function application is written e1 e2."

    >

    > I can't read that page, unfortunately (a lack of experience with the

    > grammar); but from the look of it, the grammar is a LOT more complex

    > than you're implying. It's true that function application is written

    > e1 e2; but that doesn't mean that everything written as e1 e2 is a

    > function application. Does it?

     Yes: where e1 and e2 are expressions. Haskell gets confusing because

    it has infix and prefix operations, but this is negotiated by the

    syntax parsing rules. Haskell is concatenative (by your *current*

    definition), interesting (e.g. turing complete and expressive), and

    based on application instead of composition.

    However, you may find it telling that while "f 5 2" might be valid (if

    f is a binary function). The terms "5 2" by themselves are not a valid

    expression, because "5" is not a function and can't be applied to 2.

    In Haskell you have to build left-associative parse-trees. This is

    very unpleasant from my point of view: I like concatenative languages

    precisely because I can generate a left-parse tree or right-parse

    tree, evaluate both of them and get the same result.

    You may then want to restrict the definition of concatenation to

    reject this anomaly. So perhaps in a concatenative language

    concatenation should have meaning and be associative. Application is

    not associative. So given that new reformation of concatenation, I

    would come right back to the fold, and embrace concatenative as a good

    description of Cat. See below for a new definition proposal.

     >  And in fact, right above the informal

    > discussion of e1 e2, there's a grammatical and precise note about

    > "[fval] aval", which seems to imply a distinction between functions

    > and things which can be applied to functions.

     There isn't any distinction. Application (a.k.a. "function

    application") is a higher-order operation that takes a function and a

    value (which can also be a function). Only functions can ever be

    "applied" to values.

     > > > I don't think the path you're trying to walk will be fruitful. The

    > > > problem is that any language written in plain text MUST do something

    > > > when terms are concatenated (because that's the only thing you can DO

    > > > with plain text);

    >

    > > False. The following is not simply invalid C:

    > > "12 13"

    > > Notice the concatenation of terms!

    >

    > I don't get it. That looks to me like invalid C. Why do you say it's

    > not invalid?

     Sorry, typo, I meant "simply not valid". It contradicts your claim

    that "any language written in plain text must do something when terms

    are concatenated".

     > Anyhow, my point was that there must be SOME use of concatenation for

    > every text based language;

     But there isn't a [semantic] use for concatenation in C: it is simply

    a token delimiter. I am overlooking that.

     > but calling a language "concatenative" has

    > to mean that concatenation _always_ means something.

     Which it does in Haskell. It always means application.

     > > > trying to call a language "concatenative" merely

    > > > because it "does something" *in some cases* when terms are

    > > > concatenated is so vague it describes ALL languages.

    >

    > > That is not true. See: C, Java, C++, Pascal, Algol, etc. etc. etc.

    >

    > Those are further examples of my point: languages in which

    > concatenation does something some times.

     What does concatenation do in these langauges other than as token delimiters?

     > The simple *presence* of

    > concatenation in the grammar isn't enough, any more than the simple

    > presence of functions is enough to make a language "functional".

     I agree concatenation of expressions has to have a specific semantic

    meaning: this implies a presence in the abstract syntax grammar (as

    opposed to the concrete or surface syntax grammar).

     > > > A language that deserves the name "concatenative" should respond to

    > > > concatenation in the same way every time.

    >

    > > Whatever response you require in your definition, be it application,

    > > composition, or some other operation, will be arbitrary: hence

    > > confusing.

    >

    > But my point is that I don't require anything in my definition.

     Yes, sorry that was aimed at other people intent on deciding that

    concatenation should imply composition.

     > There's nothing arbitrary there. You can propose any operation you

    > want; but so far, the only one that's proven to work consistently and

    > "interestingly" is function composition.

     Application has also been proven to be interesting. See: Combinatory

    Logic, ML, Haskell.

     > Now, I admit that my definition lacks boundaries; nobody knows for

    > sure whether composition is the only possible operation.

     I have already shown you several examples of langauges where

    concatenation implies application.

     > But in the

    > same sense my definition also lacks arbitrariness.

     Yes. I disagree that as it stands the definition rejects applicative

    languages. Here is a new suggestion for the definition of

    concatenative language:

    "A concatenative language is a programming language where the

    concatenation (i.e. the sequencing or juxtaposition) of terms

    corresponds to an associative operation on functions."

    The implication of this is that any sequence of terms will have both

    left-associative and right-associative abstract syntax trees that are

    equivalent in meaning.

    I know that this is a bit of an about-face from my earlier stance, but

    having been forced to think about things more deeply by William's

    comments it seems somehow intuitive that in a concatenative language

    (f * g) * h and f * (g * h) are equivalent, where * is the operation

    denoted by concatenation. It makes me very happy to be able to express

    this with some degree of formalism.

     > > - Christopher

    >

    > -Wm

     Thanks for hammering out these issues William,

    Christopher

## William Tanksley, Jr — 2007-12-10 18:17:17

    I'm going to do something that's VERY unusual for me. I'm going to

    say, "let's skip the arguments and cut straight to the agreement."

    We've got a LOT of misunderstandings going in this thread... But

    you've come up with a refinement of the "standard" definition which is

    IMO beautiful.

    So, let's skip the arguments and cut straight to the agreement. THEN

    we can start arguing again more efficiently.

    Christopher Diggins <cdiggins@...> wrote:

     > Here is a new suggestion for the definition of

    > concatenative language:

    > "A concatenative language is a programming language where the

    > concatenation (i.e. the sequencing or juxtaposition) of terms

    > corresponds to an associative operation on functions."

     I like it. It actually reveals something to me that our original

    standard definition failed to do; specifically, it explains how my

    idea of "flatness" is related to the standard idea of concatenativity.

    I think you've discovered something very important.

    Let me paste in my phrasing of the "standard definition": "A

    concatenative programming language is a language in which the

    concatenation of any two valid programs is a valid program."

    Your definition is superior in that it expressly requires

    associativity, which (come to think of it) was part of what I was

    assuming all along. Therefore, I like it and second your vote to make

    it the new standard definition.

    I do have a question, though. Does the old standard definition

    covertly imply associativity? It does rule out application (contrary

    to your earlier statement), since application doesn't work between

    "any two programs". I think there's a clear implication that the

    properties of concatenation should apply, but I think the old

    definition is incomplete and erroneous because it does NOT clearly

    state that all programs in a concatenative language can be built using

    only composition.

    I did, earlier in this thread, post a definition which included that

    requirement: "A concatenative programming language is a language in

    which the concatenation of any two valid programs is a valid program,

    and the entire language can be generated by the concatenation of a

    finite set of primitive programs." In other words, the language must

    be closed under concatenation (which rules out application as the

    meaning of concatenation) and must consist only of primitives and the

    concatenation of valid programs. This requirement in turn implies that

    the semantics of the language must follow the properties of

    concatenation, including associativity.

    I believe that this is exactly equivalent to your definition: HOWEVER,

    I believe that your definition is useful when discussing semantics,

    since it makes a direct semantic requirement which my definition

    leaves implied.

    Hmm. My definition still has a flaw: it demands a finite set of

    primitives, which ignores the fact that literals (such as quotations)

    may be infinite. How about this: "A concatenative programming language

    is a programming language which is identical to its own Kleene

    closure." I found that term on Wikipedia while trying to sort out the

    idea of closure. A Kleene closure of a language is the set containing

    all concatenations of all terms in the language. It's the meaning of

    the Regexp symbol "*".

    In other words, although Haskell isn't concatenative, Haskell* would

    be (by my definition). :-) This suggests (jokingly) that C* would be

    the new concatenative version of C, just as C++ is the object-oriented

    version. (No, I don't want to see C++*. I suspect C*++ would be less

    complex than C++ alone.)

    My definition, however, is now *very* specific to syntax. Perhaps I'd

    better phrase it as: "A language's syntax is concatenative if the

    language it accepts is its own Kleene closure." Then, your definition

    rephrased to be parallel to mine would be: "A language's semantics is

    concatenative if every term denotes a function, and every

    concatenation of terms denotes an associative operation on those

    functions." (Hmm, is the word "semantics" plural?)

    Now I *really* like your definition!!! This rephrase makes it VERY

    clear to me that even my new version is inadequate -- it was PURELY

    syntactic. I'm not sure whether your definition is sufficient by

    itself -- but it's clearly *necessary*.

    What do you think?

     > Thanks for hammering out these issues William,

     Hey, it's fun. Thanks for persisting.

     > Christopher

     -Wm

## Don Groves — 2007-12-10 22:49:40

    On Dec 10, 2007, at 19:17 , William Tanksley, Jr wrote:

     > I'm going to do something that's VERY unusual for me. I'm going to

    > say, "let's skip the arguments and cut straight to the agreement."

    >

    > We've got a LOT of misunderstandings going in this thread... But

    > you've come up with a refinement of the "standard" definition which is

    > IMO beautiful.

    >

    > So, let's skip the arguments and cut straight to the agreement. THEN

    > we can start arguing again more efficiently.

    >

    > Christopher Diggins <cdiggins@...> wrote:

    >> Here is a new suggestion for the definition of

    >> concatenative language:

    >> "A concatenative language is a programming language where the

    >> concatenation (i.e. the sequencing or juxtaposition) of terms

    >> corresponds to an associative operation on functions."

    >

    > I like it. It actually reveals something to me that our original

    > standard definition failed to do; specifically, it explains how my

    > idea of "flatness" is related to the standard idea of concatenativity.

    > I think you've discovered something very important.

    >

    > Let me paste in my phrasing of the "standard definition": "A

    > concatenative programming language is a language in which the

    > concatenation of any two valid programs is a valid program."

    >

    > Your definition is superior in that it expressly requires

    > associativity, which (come to think of it) was part of what I was

    > assuming all along. Therefore, I like it and second your vote to make

    > it the new standard definition.

    >

    > I do have a question, though. Does the old standard definition

    > covertly imply associativity? It does rule out application (contrary

    > to your earlier statement), since application doesn't work between

    > "any two programs". I think there's a clear implication that the

    > properties of concatenation should apply, but I think the old

    > definition is incomplete and erroneous because it does NOT clearly

    > state that all programs in a concatenative language can be built using

    > only composition.

    >

    > I did, earlier in this thread, post a definition which included that

    > requirement: "A concatenative programming language is a language in

    > which the concatenation of any two valid programs is a valid program,

    > and the entire language can be generated by the concatenation of a

    > finite set of primitive programs." In other words, the language must

    > be closed under concatenation (which rules out application as the

    > meaning of concatenation) and must consist only of primitives and the

    > concatenation of valid programs. This requirement in turn implies that

    > the semantics of the language must follow the properties of

    > concatenation, including associativity.

    >

    > I believe that this is exactly equivalent to your definition: HOWEVER,

    > I believe that your definition is useful when discussing semantics,

    > since it makes a direct semantic requirement which my definition

    > leaves implied.

    >

    > Hmm. My definition still has a flaw: it demands a finite set of

    > primitives, which ignores the fact that literals (such as quotations)

    > may be infinite. How about this: "A concatenative programming language

    > is a programming language which is identical to its own Kleene

    > closure." I found that term on Wikipedia while trying to sort out the

    > idea of closure. A Kleene closure of a language is the set containing

    > all concatenations of all terms in the language. It's the meaning of

    > the Regexp symbol "*".

    >

    > In other words, although Haskell isn't concatenative, Haskell* would

    > be (by my definition). :-) This suggests (jokingly) that C* would be

    > the new concatenative version of C, just as C++ is the object-oriented

    > version. (No, I don't want to see C++*. I suspect C*++ would be less

    > complex than C++ alone.)

    >

    > My definition, however, is now *very* specific to syntax. Perhaps I'd

    > better phrase it as: "A language's syntax is concatenative if the

    > language it accepts is its own Kleene closure." Then, your definition

    > rephrased to be parallel to mine would be: "A language's semantics is

    > concatenative if every term denotes a function, and every

    > concatenation of terms denotes an associative operation on those

    > functions." (Hmm, is the word "semantics" plural?)

     Function composition is associative. The phasing "every concatenation

    of terms denotes an associative operation on those functions" begs the

    question of what associative operations on functions other than

    composition

    are we talking about?

    Is it sufficient to say, as Manfred defined it for Joy, that

    concatenation

    denotes function composition?

    --

    Don

     > Now I *really* like your definition!!! This rephrase makes it VERY

    > clear to me that even my new version is inadequate -- it was PURELY

    > syntactic. I'm not sure whether your definition is sufficient by

    > itself -- but it's clearly *necessary*.

    >

    > What do you think?

    >> Thanks for hammering out these issues William,

    >

    > Hey, it's fun. Thanks for persisting.

    >

    >> Christopher

    >

    > -Wm

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## Christopher Diggins — 2007-12-10 23:13:16

    On Dec 10, 2007 1:17 PM, William Tanksley, Jr <wtanksleyjr@...> wrote:

     > I'm going to do something that's VERY unusual for me. I'm going to

    > say, "let's skip the arguments and cut straight to the agreement."

    >

    > We've got a LOT of misunderstandings going in this thread... But

    > you've come up with a refinement of the "standard" definition which is

    > IMO beautiful.

     Thank you. This definition is only due to your help.

     > So, let's skip the arguments and cut straight to the agreement. THEN

    > we can start arguing again more efficiently.

    >

    >

    > Christopher Diggins <cdiggins@...> wrote:

    > > Here is a new suggestion for the definition of

    > > concatenative language:

    > > "A concatenative language is a programming language where the

    > > concatenation (i.e. the sequencing or juxtaposition) of terms

    > > corresponds to an associative operation on functions."

    >

    > I like it. It actually reveals something to me that our original

    > standard definition failed to do; specifically, it explains how my

    > idea of "flatness" is related to the standard idea of concatenativity.

    > I think you've discovered something very important.

    >

    > Let me paste in my phrasing of the "standard definition": "A

    >

    > concatenative programming language is a language in which the

    > concatenation of any two valid programs is a valid program."

     By saying program instead of expression or term, you are introducing a

    new restriction which IMO unneccesarily restricts the class of

    languages excluding a Cat language with namespaces. Program structure

    is generally not considered as interesting as term or expression

    structure.

     > Your definition is superior in that it expressly requires

    > associativity, which (come to think of it) was part of what I was

    > assuming all along. Therefore, I like it and second your vote to make

    > it the new standard definition.

    > I do have a question, though. Does the old standard definition

    > covertly imply associativity? It does rule out application (contrary

    > to your earlier statement), since application doesn't work between

    > "any two programs". I think there's a clear implication that the

    > properties of concatenation should apply, but I think the old

    > definition is incomplete and erroneous because it does NOT clearly

    > state that all programs in a concatenative language can be built using

    > only composition.

    >

    > I did, earlier in this thread, post a definition which included that

    > requirement: "A concatenative programming language is a language in

    >

    > which the concatenation of any two valid programs is a valid program,

    > and the entire language can be generated by the concatenation of a

    > finite set of primitive programs."

     Again, I disagree with the usage of "programs".

    You would have problems in Cat  because of the fact that you can't write:

    1 2 [define f { 3 4 }]

    Allow me to paraphrase:

    "A concatenative programming language is a language in

    which the concatenation of any two valid expression is a valid expression,

    and the entire language of expressions can be generated by the

    concatenation of a

    finite set of expressions."

    This rejects Joy:

    expr = primitive | expr expr | [expr]

    How do you construct [expr] from concatenation alone?

    And if you allow it somehow is still seems no different than the

    generative grammar for the abstract syntax of the S K calculus:

    expr = S | K | expr expr | (expr)

    Looks pretty much the same to me.

     > In other words, the language must

    > be closed under concatenation (which rules out application as the

    > meaning of concatenation)

     I don't see how you arose at that conclusion.

     > and must consist only of primitives and the

    > concatenation of valid programs. This requirement in turn implies that

    > the semantics of the language must follow the properties of

    > concatenation, including associativity.

    >

    > I believe that this is exactly equivalent to your definition: HOWEVER,

    > I believe that your definition is useful when discussing semantics,

    > since it makes a direct semantic requirement which my definition

    > leaves implied.

     Again, I don't see the semantic requirement implied.

     > Hmm. My definition still has a flaw: it demands a finite set of

    > primitives, which ignores the fact that literals (such as quotations)

    > may be infinite. How about this: "A concatenative programming language

    > is a programming language which is identical to its own Kleene

    > closure."  I found that term on Wikipedia while trying to sort out the

    > idea of closure. A Kleene closure of a language is the set containing

    > all concatenations of all terms in the language. It's the meaning of

    > the Regexp symbol "*".

    >

    > In other words, although Haskell isn't concatenative, Haskell* would

    > be (by my definition). :-) This suggests (jokingly) that C* would be

    > the new concatenative version of C, just as C++ is the object-oriented

    > version. (No, I don't want to see C++*. I suspect C*++ would be less

    > complex than C++ alone.)

    >

    > My definition, however, is now *very* specific to syntax. Perhaps I'd

    > better phrase it as: "A language's syntax is concatenative if the

    > language it accepts is its own Kleene closure." Then, your definition

    > rephrased to be parallel to mine would be: "A language's semantics is

    > concatenative if every term denotes a function, and every

    > concatenation of terms denotes an associative operation on those

    > functions." (Hmm, is the word "semantics" plural?)

    >

    > Now I *really* like your definition!!! This rephrase makes it VERY

    > clear to me that even my new version is inadequate -- it was PURELY

    > syntactic. I'm not sure whether your definition is sufficient by

    > itself -- but it's clearly *necessary*.

    >

    > What do you think?

     Well I don't think you need to say "semantics", it is implied. All

    common programming language classifications are based on semantics

    (functional, imperative, stack-based, declarative, logical,

    higher-order, first-order, array-oriented, concurrent, etc.). Computer

    scientists are concerned about classifying languages based on their

    semenatics, not their syntax. I would make a couple of other minor

    changes:

    "A language is concatenative if every term denotes a function, and the

    concatenation of terms denotes an associative operation on those

    functions."

    Though I think this is precisely my previously submitted definition.

    - Christopher

## William Tanksley, Jr — 2007-12-10 23:14:06

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

     > My definition, however, is now *very* specific to syntax. Perhaps I'd

    > better phrase it as: "A language's syntax is concatenative if the

    > language it accepts is its own Kleene closure." Then, your definition

    > rephrased to be parallel to mine would be: "A language's semantics is

    > concatenative if every term denotes a function, and every

    > concatenation of terms denotes an associative operation on those

    > functions." (Hmm, is the word "semantics" plural?)

     Okay, I just realized, thanks to

    http://en.wikipedia.org/wiki/Kleene_closure, that the Kleene closure

    of a language forms an associative monoid. If only I'd read

    http://www.latrobe.edu.au/philosophy/phimvt/joy/j02maf.html closely

    enough, I would have seen (in the first paragraph) that "The

    denotation of Joy programs maps a syntactic monoid of program

    concatenation to a semantic monoid of function composition."

    How about I condense (using the frigid temperatures of mathematical

    language) the two definitions I proposed above into a single one: "A

    concatenative language consists of a mapping from a syntactic monoid

    over program concatenation to a semantic monoid over an associative

    operation on functions."

    Now, the question is whether function composition is the only possible

    function operation that maintains concatenativity. I would claim it's

    not: the trivial counterexample would be the null operation, which

    discards both functions. I think 'nip' is also an associative

    operation (discard the result of the first function). Is there some

    reason why these -- admittedly uninteresting -- operations produce a

    non-concatenative language?

    -Wm

## William Tanksley, Jr — 2007-12-11 00:30:41

    Christopher Diggins <cdiggins@...> wrote:

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

    > > Christopher Diggins <cdiggins@...> wrote:

    > > > Here is a new suggestion for the definition of

    > > > concatenative language:

    > > > "A concatenative language is a programming language where the

    > > > concatenation (i.e. the sequencing or juxtaposition) of terms

    > > > corresponds to an associative operation on functions."

    > > I like it. It actually reveals something to me that our original

    > > standard definition failed to do; specifically, it explains how my

    > > idea of "flatness" is related to the standard idea of concatenativity.

    > > I think you've discovered something very important.

    > > Let me paste in my phrasing of the "standard definition": "A

    > > concatenative programming language is a language in which the

    > > concatenation of any two valid programs is a valid program."

    > By saying program instead of expression or term, you are introducing a

    > new restriction which IMO unneccesarily restricts the class of

    > languages excluding a Cat language with namespaces. Program structure

    > is generally not considered as interesting as term or expression

    > structure.

     Okay.

     > > I do have a question, though. Does the old standard definition

    > > covertly imply associativity? It does rule out application (contrary

    > > to your earlier statement), since application doesn't work between

    > > "any two programs". I think there's a clear implication that the

    > > properties of concatenation should apply, but I think the old

    > > definition is incomplete and erroneous because it does NOT clearly

    > > state that all programs in a concatenative language can be built using

    > > only composition.

    > > I did, earlier in this thread, post a definition which included that

    > > requirement: "A concatenative programming language is a language in

    > > which the concatenation of any two valid programs is a valid program,

    > > and the entire language can be generated by the concatenation of a

    > > finite set of primitive programs."

    > Again, I disagree with the usage of "programs".

     Your change is accepted.

     > You would have problems in Cat  because of the fact that you can't write:

    > 1 2 [define f { 3 4 }]

     Clearly, the 'define' part of Cat is not itself concatenative. That's

    okay; Joy has a non-concatenative superset. So does every other

    practical concatenative language. The only way around that is to use

    dynamically scoped definitions.

     > Allow me to paraphrase:

    > "A concatenative programming language is a language in

    > which the concatenation of any two valid expressions is a valid expression,

    > and the entire language of expressions can be generated by the

    > concatenation of a finite set of expressions."

    > This rejects Joy:

    > expr = primitive | expr expr | [expr]

    > How do you construct [expr] from concatenation alone?

     Right. This is why I threw away the "finite set of expressions" rule,

    and instead used the term "Kleene closure".

     > And if you allow it somehow is still seems no different than the

    > generative grammar for the abstract syntax of the S K calculus:

    > expr = S | K | expr expr | (expr)

    > Looks pretty much the same to me.

     I'm very much not good at reading these things... But is this grammar

    actually complete? That is, does it accept an expression if and only

    if it denotes a valid SK expression? From just looking at it, it

    appears that it will accept things which are not single SK

    expressions. To the best of my knowledge, an SK parse tree must have a

    single root. I'm not familiar with how to interpret a dual-rooted SK

    parse tree.

    And I can't seem to find any description of SK's grammar online. I

    found Iota and Jot, which are similar...

    http://barker.linguistics.fas.nyu.edu/Stuff/Iota/, in one of the first

    paragraphs, says that the language includes 'i', but not 'ii', so they

    fail my definition.

     > > In other words, the language must

    > > be closed under concatenation (which rules out application as the

    > > meaning of concatenation)

    > I don't see how you arose at that conclusion.

     Because application isn't closed under concatenation -- you can

    concatenate two valid terms together and not get a valid application

    (if the first term isn't a function with at least one free variable).

    If the programmer does this, the language has to choose some semantics

    OTHER than application, which isn't permitted by either of our

    definitions (that there be only one operation).

     > > and must consist only of primitives and the

    > > concatenation of valid programs. This requirement in turn implies that

    > > the semantics of the language must follow the properties of

    > > concatenation, including associativity.

    > > I believe that this is exactly equivalent to your definition: HOWEVER,

    > > I believe that your definition is useful when discussing semantics,

    > > since it makes a direct semantic requirement which my definition

    > > leaves implied.

    > Again, I don't see the semantic requirement implied.

     Concatenation is associative. Any operation which is bidirectionally

    implied by it must also be associative.

     > Well I don't think you need to say "semantics", it is implied. All

    > common programming language classifications are based on semantics

    > (functional, imperative, stack-based, declarative, logical,

    > higher-order, first-order, array-oriented, concurrent, etc.). Computer

    > scientists are concerned about classifying languages based on their

    > semanatics, not their syntax.

     Not true. Regular expressions are a language that is syntactically

    different from other languages; then you have LL languages, then LALR,

    then LR. The classifications you're listing are not "language

    classifications" in a language-theoretical sense; they're different

    styles of programming, and any of them can be done in a single

    language. Many computer scientists study them, and many programming

    languages are specialized to use one exclusively; but most of those

    languages are a subset of LALR, so a pure language researcher will

    yawn and look elsewhere.

    Another way of looking at things is to point out that those

    programming styles cannot be languages, because there's no way to

    distinguish between them using a terminating grammar. (Hmm, that

    statement smells suspicious to me... But I think it's close enough to

    true.)

    My point: when studying languages, syntax is important. See

    http://en.wikipedia.org/wiki/Formal_language: "In formal language

    theory, a language is nothing more than its syntax; questions of

    semantics are not addressed in this specialty."

    So how would you tell a formal language theorist how to tell when he's

    looking at a concatenative language? This guy's going to be looking

    only at a grammar -- he won't look at the generated source code. I can

    tell him to look for a language which is identical to its own Kleene

    closure, and he'll know what to look for.

    Now, if I tell that to a programmer, he'd be stumped. Even a language

    implementer won't know what to do -- although he'd be able to write a

    parser, he couldn't write an interpreter. So I like your definition,

    as it provides additional clarity.

    Keep in mind that your definition isn't any more precise, or at least

    I hope not. If it's more precise, I'm ruling out languages which

    should be considered concatenative, and that would be a pity. Nor is

    your definition the easiest to implement; for example, if I weren't

    curious about whether there were other interesting operations, I could

    define concatenative languages to require composition; or to go even

    further, I could define them to require a stack of lists, symbols, and

    numbers plus a global dictionary as the parameter which is passed

    between the functions.

    Those definitions would be more clear, but in at least the latter

    case, destructively more narrow, since the last definition would

    exclude Forth and Factor (which use two stacks and the contents of

    memory) -- and I suppose would make Joy programs that perform output

    technically non-concatenative.

     > I would make a couple of other minor changes:

    > "A language is concatenative if every term denotes a function, and the

    > concatenation of terms denotes an associative operation on those

    > functions."

    > Though I think this is precisely my previously submitted definition.

     Yes, but now you're trying to define a language in terms of its

    semantics. Semantics rests on a foundation of syntax.

     > - Christopher

     -Wm

## William Tanksley, Jr — 2007-12-11 00:44:52

    Don Groves <dgroves@...> wrote:

     > William Tanksley, Jr wrote:

    > > My definition, however, is now *very* specific to syntax. Perhaps I'd

    > > better phrase it as: "A language's syntax is concatenative if the

    > > language it accepts is its own Kleene closure." Then, your definition

    > > rephrased to be parallel to mine would be: "A language's semantics is

    > > concatenative if every term denotes a function, and every

    > > concatenation of terms denotes an associative operation on those

    > > functions." (Hmm, is the word "semantics" plural?)

    > Function composition is associative. The phasing "every concatenation

    > of terms denotes an associative operation on those functions" begs the

    > question of what associative operations on functions other than

    > composition are we talking about?

     It's intended to raise the question rather than begging it.

     > Is it sufficient to say, as Manfred defined it for Joy, that

    > concatenation denotes function composition?

     That would be begging the question: assuming the answer which we seek to prove.

    I'm not certain you're wrong, though. It may be that my definition

    could be satisfied by a language which we would all reject as entirely

    non-concatenative. I've attempted to test that by inventing a language

    which uses a different operation; for example, the language which

    looks like Joy syntactically but which uses 'null' as its

    concatenation operator (i.e. all programs do nothing). Although this

    language is extremely uninteresting, it seems to me that it remains

    concatenative... Just in a very boring way.

    There are tons of nontrivial associative operators on functions. For

    example, let "+" be the operation which, given a pair of functions,

    produces the function defined by the sum of the values of the

    functions evaluated at a single, fixed value (which must be a number).

    The resulting language is, of course, commutative, and less

    interesting than Joy... But it seems like a real language to me,

    perhaps slightly useful, and -- from the results of Manfred's work --

    I'd even say it's concatenative, although there are many additional

    transformations possible to it, since it's commutative.

    Perhaps I'm starting to get a grasp on some way to prove my idea

    false... I need to come up with a associative operator which produces

    a language that I can't accept as concatenative. If I can do this I'll

    be very happy; of course, if I can't I won't have proven you wrong.

    I'm going to try doing this with a non-commutative operator... Let me

    think about this.

     > Don

     -Wm

## John Nowak — 2007-12-11 01:09:28

    On Dec 10, 2007, at 7:30 PM, William Tanksley, Jr wrote:

     >> You would have problems in Cat  because of the fact that you can't

    >> write:

    >> 1 2 [define f { 3 4 }]

    >

    > Clearly, the 'define' part of Cat is not itself concatenative. That's

    > okay; Joy has a non-concatenative superset. So does every other

    > practical concatenative language. The only way around that is to use

    > dynamically scoped definitions.

     The language I'm working on has define (spelled 'def') as a normal

    function with type "A (B -> C) sym -> A". This allows one to define

    new functions without special syntax:

    	(sqr swap sqr + sqrt) :hypot def

    This has the downside that functions cannot make use of explicit

    recursion (as hypot isn't defined until def is called, and hence the

    quote can't make use of it), but this restriction is in place anyway

    due to the type system.

    - John

## Don Groves — 2007-12-11 01:13:18

    On Dec 10, 2007, at 19:44 , William Tanksley, Jr wrote:

     > Don Groves <dgroves@...> wrote:

    >> William Tanksley, Jr wrote:

    >>> My definition, however, is now *very* specific to syntax. Perhaps

    >>> I'd

    >>> better phrase it as: "A language's syntax is concatenative if the

    >>> language it accepts is its own Kleene closure." Then, your

    >>> definition

    >>> rephrased to be parallel to mine would be: "A language's

    >>> semantics is

    >>> concatenative if every term denotes a function, and every

    >>> concatenation of terms denotes an associative operation on those

    >>> functions." (Hmm, is the word "semantics" plural?)

    >

    >> Function composition is associative. The phasing "every concatenation

    >> of terms denotes an associative operation on those functions" begs

    >> the

    >> question of what associative operations on functions other than

    >> composition are we talking about?

    >

    > It's intended to raise the question rather than begging it.

    >

    >> Is it sufficient to say, as Manfred defined it for Joy, that

    >> concatenation denotes function composition?

    >

    > That would be begging the question: assuming the answer which we

    > seek to prove.

     Yes, I misused my terms quite well, didn't I?

     > I'm not certain you're wrong, though. It may be that my definition

    > could be satisfied by a language which we would all reject as entirely

    > non-concatenative. I've attempted to test that by inventing a language

    > which uses a different operation; for example, the language which

    > looks like Joy syntactically but which uses 'null' as its

    > concatenation operator (i.e. all programs do nothing). Although this

    > language is extremely uninteresting, it seems to me that it remains

    > concatenative... Just in a very boring way.

     I was in no way trying to prove you wrong William -- note that mine

    are questions, not statements. I'm completely in favor of the term

    "concatenative" so long as we can pin it down with reasonable rigor.

    I think you, Christopher, and the others have done quite well so far

    in working toward that conclusion.

    --

    Don

     > There are tons of nontrivial associative operators on functions. For

    > example, let "+" be the operation which, given a pair of functions,

    > produces the function defined by the sum of the values of the

    > functions evaluated at a single, fixed value (which must be a number).

    > The resulting language is, of course, commutative, and less

    > interesting than Joy... But it seems like a real language to me,

    > perhaps slightly useful, and -- from the results of Manfred's work --

    > I'd even say it's concatenative, although there are many additional

    > transformations possible to it, since it's commutative.

    >

    > Perhaps I'm starting to get a grasp on some way to prove my idea

    > false... I need to come up with a associative operator which produces

    > a language that I can't accept as concatenative. If I can do this I'll

    > be very happy; of course, if I can't I won't have proven you wrong.

    > I'm going to try doing this with a non-commutative operator... Let me

    > think about this.

    >

    >> Don

    >

    > -Wm

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## Don Groves — 2007-12-11 02:25:13

    On Dec 10, 2007, at 19:09 , John Nowak wrote:

     >

    > On Dec 10, 2007, at 7:30 PM, William Tanksley, Jr wrote:

    >

    >>> You would have problems in Cat  because of the fact that you can't

    >>> write:

    >>> 1 2 [define f { 3 4 }]

    >>

    >> Clearly, the 'define' part of Cat is not itself concatenative. That's

    >> okay; Joy has a non-concatenative superset. So does every other

    >> practical concatenative language. The only way around that is to use

    >> dynamically scoped definitions.

    >

    > The language I'm working on has define (spelled 'def') as a normal

    > function with type "A (B -> C) sym -> A". This allows one to define

    > new functions without special syntax:

    >

    > 	(sqr swap sqr + sqrt) :hypot def

    >

    > This has the downside that functions cannot make use of explicit

    > recursion (as hypot isn't defined until def is called, and hence the

    > quote can't make use of it), but this restriction is in place anyway

    > due to the type system.

     How about "self" as a call to its enclosing context?

    --

    Don

     >

    > - John

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## William Tanksley, Jr — 2007-12-11 15:38:44

    Don Groves <dgroves@...> wrote:

     > John Nowak wrote:

    > > This has the downside that functions cannot make use of explicit

    > > recursion (as hypot isn't defined until def is called, and hence the

    > > quote can't make use of it), but this restriction is in place anyway

    > > due to the type system.

    > How about "self" as a call to its enclosing context?

     It won't work for dynamic definitions, because there's no distinct

    concept of "enclosing context". All you know is that you're inside a

    quotation that's inside another quotation; you can't look ahead to see

    which enclosure is the one being defined and/or executed. There are

    several solutions:

    1. Provide special syntax for quoted definitions (perhaps make them compiled).

    2. Provide recursion primitives like linrec, genrec, etc.

    3. Provide partial continuations.

    #3 is especially interesting, since PCs can implement recursion or

    backtracking equally easily. In a typefree language, it's very simple

    to implement; in a typechecked language, of course, one additionally

    has to ensure that the word which begins the partial continuation is

    exposed to the same stack as the words which call it.

     > Don

     -Wm

## John Cowan — 2007-12-11 15:44:39

    William Tanksley, Jr scripsit:

     > > How about "self" as a call to its enclosing context?

    >

    > It won't work for dynamic definitions, because there's no distinct

    > concept of "enclosing context". All you know is that you're inside a

    > quotation that's inside another quotation; you can't look ahead to see

    > which enclosure is the one being defined and/or executed. There are

    > several solutions:

     [snippage]

    4.  Fall back on the Y combinator, or its eager equivalent Z.

    --

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

    Objective consideration of contemporary phenomena compel the conclusion

    that optimum or inadequate performance in the trend of competitive

    activities exhibits no tendency to be commensurate with innate capacity,

    but that a considerable element of the unpredictable must invariably be

    taken into account. --Ecclesiastes 9:11, Orwell/Brown version

## Christopher Diggins — 2007-12-11 16:59:54

    On Dec 11, 2007 10:44 AM, John Cowan <cowan@...> wrote:

     >

    > William Tanksley, Jr scripsit:

    > > > How about "self" as a call to its enclosing context?

    > >

    > > It won't work for dynamic definitions, because there's no distinct

    > > concept of "enclosing context". All you know is that you're inside a

    > > quotation that's inside another quotation; you can't look ahead to see

    > > which enclosure is the one being defined and/or executed. There are

    > > several solutions:

    >

    > [snippage]

    >

    > 4. Fall back on the Y combinator, or its eager equivalent Z.

     I am familiar with Y but not Z. How is Z defined?

    - Christopher

## John Cowan — 2007-12-11 17:28:52

    Christopher Diggins scripsit:

     > I am familiar with Y but not Z. How is Z defined?

     http://en.wikipedia.org/wiki/Anonymous_recursion tells the tale.

    --

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

    Consider the matter of Analytic Philosophy.  Dennett and Bennett are well-known.

    Dennett rarely or never cites Bennett, so Bennett rarely or never cites Dennett.

    There is also one Dummett.  By their works shall ye know them.  However, just as

    no trinities have fourth persons (Zeppo Marx notwithstanding), Bummett is hardly

    known by his works.  Indeed, Bummett does not exist.  It is part of the function

    of this and other e-mail messages, therefore, to do what they can to create him.

## Christopher Diggins — 2007-12-11 17:40:53

    On Dec 11, 2007 12:28 PM, John Cowan <cowan@...> wrote:

     > Christopher Diggins scripsit:

    >

    > > I am familiar with Y but not Z. How is Z defined?

    >

    > http://en.wikipedia.org/wiki/Anonymous_recursion tells the tale.

     Ah, "\x.(xx)" or "dup apply". It seems though that they are simply

    assigning an arbitary name to that combinator than specifically saying

    it is the "Z" combinator.

    AFAICT Z is not a commonly used name for the combinator. I have seen

    many references to it as the "m" combinator, or the mockingbird

    combinator.

    (http://www.angelfire.com/tx4/cus/combinator/birds.html)

    - Christopher

## Don Groves — 2007-12-11 20:48:40

    On Dec 11, 2007, at 19:38 , William Tanksley, Jr wrote:

     > Don Groves <dgroves@...> wrote:

    >> John Nowak wrote:

    >>> This has the downside that functions cannot make use of explicit

    >>> recursion (as hypot isn't defined until def is called, and hence the

    >>> quote can't make use of it), but this restriction is in place anyway

    >>> due to the type system.

    >

    >> How about "self" as a call to its enclosing context?

    >

    > It won't work for dynamic definitions, because there's no distinct

    > concept of "enclosing context". All you know is that you're inside a

    > quotation that's inside another quotation; you can't look ahead to see

    > which enclosure is the one being defined and/or executed. There are

    > several solutions:

    >

    > 1. Provide special syntax for quoted definitions (perhaps make them

    > compiled).

    > 2. Provide recursion primitives like linrec, genrec, etc.

    > 3. Provide partial continuations.

    >

    > #3 is especially interesting, since PCs can implement recursion or

    > backtracking equally easily. In a typefree language, it's very simple

    > to implement; in a typechecked language, of course, one additionally

    > has to ensure that the word which begins the partial continuation is

    > exposed to the same stack as the words which call it.

     You're probably right on this but I'm not entirely convinced.  John said

    "explicit recursion" which I take to mean calling a function from within

    itself. This would seem to leave leave out 1. and 2.

    Maintaining a pointer to the current enclosure should be sufficient for

    self invocation. That would require another stack, of course, which may

    be worse than having a simple solution to the problem. And using the

    already existing recursive methods is more in line with concatenative

    theory anyway, ..., so I'll forget about it ;-)

    --

    Don

     >

    >> Don

    >

    > -Wm

## William Tanksley, Jr — 2007-12-11 21:04:55

    Don Groves <dgroves@...> wrote:

     > William Tanksley, Jr wrote:

    > >> How about "self" as a call to its enclosing context?

    > > It won't work for dynamic definitions, because there's no distinct

    > > concept of "enclosing context". All you know is that you're inside a

    > > quotation that's inside another quotation; you can't look ahead to see

    > > which enclosure is the one being defined and/or executed. There are

    > > several solutions:

    > > 1. Provide special syntax for quoted definitions (perhaps make them

    > > compiled).

    > > 2. Provide recursion primitives like linrec, genrec, etc.

    > > 3. Provide partial continuations.

    > You're probably right on this but I'm not entirely convinced.  John said

    > "explicit recursion" which I take to mean calling a function from within

    > itself. This would seem to leave leave out 1. and 2.

     #1 actually is the definition of explicit recursion -- at least for

    any definition which allows using a pseudokeyword rather than naming

    the invoked function directly.

     > Maintaining a pointer to the current enclosure should be sufficient for

    > self invocation. That would require another stack, of course, which may

    > be worse than having a simple solution to the problem.

     Hmm, in effect most concatenative languages keep something

    functionally equivalent to a second stack -- the return addresses of

    all calls. Along with each return address you'd be able to keep a

    recursion address; both would be pushed at CALL time, and RET would

    use the return address while RECURSE uses the recursion address.

    That's not bad semantics... I'm almost tempted to play with it and see

    what else can be done (can one of those fields be used for other

    purposes?).

    Of course, the stack usage is doubled or worse, but such, it seems, is life.

     > And using the

    > already existing recursive methods is more in line with concatenative

    > theory anyway, ..., so I'll forget about it ;-)

     Is that true? Are the *rec functions especially good with

    concatenative languages? (I don't know.) I'm sure they work with any

    functional language...

     > Don

     -Wm

## Don Groves — 2007-12-11 21:28:10

    On Dec 11, 2007, at 19:04 , William Tanksley, Jr wrote:

     > Don Groves <dgroves@...> wrote:

    >> William Tanksley, Jr wrote:

    >>>> How about "self" as a call to its enclosing context?

    >

    >>> It won't work for dynamic definitions, because there's no distinct

    >>> concept of "enclosing context". All you know is that you're inside a

    >>> quotation that's inside another quotation; you can't look ahead

    >>> to see

    >>> which enclosure is the one being defined and/or executed. There are

    >>> several solutions:

    >

    >>> 1. Provide special syntax for quoted definitions (perhaps make them

    >>> compiled).

    >>> 2. Provide recursion primitives like linrec, genrec, etc.

    >>> 3. Provide partial continuations.

    >

    >> You're probably right on this but I'm not entirely convinced.

    >> John said

    >> "explicit recursion" which I take to mean calling a function from

    >> within

    >> itself. This would seem to leave leave out 1. and 2.

    >

    > #1 actually is the definition of explicit recursion -- at least for

    > any definition which allows using a pseudokeyword rather than naming

    > the invoked function directly.

    >

    >> Maintaining a pointer to the current enclosure should be

    >> sufficient for

    >> self invocation. That would require another stack, of course,

    >> which may

    >> be worse than having a simple solution to the problem.

    >

    > Hmm, in effect most concatenative languages keep something

    > functionally equivalent to a second stack -- the return addresses of

    > all calls. Along with each return address you'd be able to keep a

    > recursion address; both would be pushed at CALL time, and RET would

    > use the return address while RECURSE uses the recursion address.

    > That's not bad semantics... I'm almost tempted to play with it and see

    > what else can be done (can one of those fields be used for other

    > purposes?).

    >

    > Of course, the stack usage is doubled or worse, but such, it seems,

    > is life.

     I was considering playing with it in ACL, so maybe I should reconsider.

    If you do try it, please keep us posted on your results.

     >> And using the

    >> already existing recursive methods is more in line with concatenative

    >> theory anyway, ..., so I'll forget about it ;-)

    >

    > Is that true? Are the *rec functions especially good with

    > concatenative languages? (I don't know.) I'm sure they work with any

    > functional language...

     Well, they seem to be especially good in Joy, the prototypical

    concatenative

    language. As to whether or not something else might work better, at

    this point

    I'm not qualified to say.

    Thanks,

    Don

     >

    >> Don

    >

    > -Wm

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## William Tanksley, Jr — 2007-12-11 22:16:49

    Don Groves <dgroves@...> wrote:

     > William Tanksley, Jr wrote:

    > I was considering playing with it in ACL, so maybe I should reconsider.

     Please don't let me stop you :-). I've got nothing but curiosity time

    left right now.

     > If you do try it, please keep us posted on your results.

     Nope, not gonna do it... I've got too much else to do.

     > > Is that true? Are the *rec functions especially good with

    > > concatenative languages? (I don't know.) I'm sure they work with any

    > > functional language...

    > Well, they seem to be especially good in Joy, the prototypical

    > concatenative

    > language. As to whether or not something else might work better, at

    > this point I'm not qualified to say.

     Yup, me neither.

     > Don

     -Wm

## Don Groves — 2007-12-11 22:37:01

    On Dec 11, 2007, at 19:16 , William Tanksley, Jr wrote:

     > Don Groves <dgroves@...> wrote:

    >> William Tanksley, Jr wrote:

    >> I was considering playing with it in ACL, so maybe I should

    >> reconsider.

    >

    > Please don't let me stop you :-). I've got nothing but curiosity time

    > left right now.

    >

    >> If you do try it, please keep us posted on your results.

    >

    > Nope, not gonna do it... I've got too much else to do.

     Me too -- it's a common problem these days. It's on my to-do list.

    --

    Don

     >>> Is that true? Are the *rec functions especially good with

    >>> concatenative languages? (I don't know.) I'm sure they work with any

    >>> functional language...

    >

    >> Well, they seem to be especially good in Joy, the prototypical

    >> concatenative

    >> language. As to whether or not something else might work better, at

    >> this point I'm not qualified to say.

    >

    > Yup, me neither.

    >

    >> Don

    >

    > -Wm

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

## Stevan Apter — 2007-12-11 22:58:28

    >> And using the

    >> already existing recursive methods is more in line with concatenative

    >> theory anyway, ..., so I'll forget about it ;-)

    >

    > Is that true? Are the *rec functions especially good with

    > concatenative languages? (I don't know.) I'm sure they work with any

    > functional language...

     i've wondered about this for years.  at first glance, it seems like

    eliminating recursion in favor of *rec combinators would be as fruitful

    as eliminating iteration in APL, J, K.

    my last project involved some extremely hairy recursive processing

    on complex, inter-related tree-like structures.  over an interval

    of several years, i became quite fluent in deploying a handful of

    techniques for operating on these structures, and it occurred to me

    more than once to try to map these patterns to manfred's joy

    recursion abstractions.  but i never did succeed in that effort.

    while recursion seems simple enough if you concentrate on the

    standard handful of examples (fibonacci, factorial, &c.), things

    get complicated real fast.  perhaps more to the point, the problem-

    set for which recursion is a natural technique seems to thin out

    rather quickly.

    APLers may be familiar with a parallel phenomenon.  you've got

    about 20 or 30 first-order primitives in most languages:  plus, minus,

    times, &c., count, reverse, rotate, &c., and a few others.  out of

    those, you construct lots of programs (also first order:  applied to

    data, they return data.)  and then you've got (at least in the APLs)

    a handful of second-order primitives:  reduce, scan, &c.  and those

    are useful because they abstract from common iteration patterns.  so

    back in the 80s, the APL2 folks at IBM implemented the machinery

    for "defined operators".  the programmer could now define programs

    ("functions") which took first order functions as arguments ("operands")

    and return first order functions.  so now you could write reduce, scan,

    &c.  the problem was, no one could really find problems which lent

    themselves naturally to defined operators.  in theory, these were

    quite powerful, but practically, they just didn't mesh with the

    problems people were actually trying to solve.

    i recall a conversation with some of the APL guys at one of the

    minnowbrook conferences in which i asked if anyone had ever found a

    use for a third-order function.  of course, it was possible to add

    the machinery for defined functions of any order, but could anyone

    think of a use for this?

     >

    >> Don

    >

    > -Wm

    >

## Christopher Diggins — 2007-12-11 23:18:01

    > i recall a conversation with some of the APL guys at one of the

    > minnowbrook conferences in which i asked if anyone had ever found a

    > use for a third-order function. of course, it was possible to add

    > the machinery for defined functions of any order, but could anyone

    > think of a use for this?

     Parsers?

    http://journals.cambridge.org/action/displayAbstract?aid=44161

    - Christopher

## Stevan Apter — 2007-12-11 23:39:11

    you know, that article crossed my mind as i hit enter.

    further evidence that the quickest route to knowledge

    is to deny some proposition before a large, argumentative

    audience.

    (i'm sure some of you have heard the following sidney

    morgenbesser story:  at a colloquium on the philosophy

    of language, the speaker observed that one often finds

    double-negation signifying the affirmative, but never

    double-affirmation signifying the negative, to which

    morgenbesser replied, "yeah yeah.")

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

    From: "Christopher Diggins" <cdiggins@...>

    To: <concatenative@yahoogroups.com>

    Sent: Tuesday, December 11, 2007 6:18 PM

    Subject: Re: [stack] language hierarchy

    >> i recall a conversation with some of the APL guys at one of the

    >> minnowbrook conferences in which i asked if anyone had ever found a

    >> use for a third-order function. of course, it was possible to add

    >> the machinery for defined functions of any order, but could anyone

    >> think of a use for this?

    >

    > Parsers?

    >

    > http://journals.cambridge.org/action/displayAbstract?aid=44161

    >

    > - Christopher

    >

## John Nowak — 2007-12-12 05:25:57

    On Dec 11, 2007, at 3:48 PM, Don Groves wrote:

     > You're probably right on this but I'm not entirely convinced.  John

    > said

    > "explicit recursion" which I take to mean calling a function from

    > within

    > itself. This would seem to leave leave out 1. and 2.

     To clarify, recursion is done with recursive combinators. Perhaps

    "explicit recursion" is the wrong word, but what I meant is that

    functions do not explicitly call themselves recursively; some

    combinator (linrec, binrec, etc) does it.

     > Maintaining a pointer to the current enclosure should be sufficient

    > for

    > self invocation.

     This would hinder factoring. Below, both 'foo1' and 'foo2' should

    behave identically, but having things depend on their context as such

    would break that:

    	(a b c d) :foo1 def

    	(b c) :e def (a e d) :foo2 def

    - John

## John Nowak — 2007-12-12 05:48:21

    On Dec 11, 2007, at 5:58 PM, Stevan Apter wrote:

     >> Is that true? Are the *rec functions especially good with

    >> concatenative languages? (I don't know.) I'm sure they work with any

    >> functional language...

    >

    > i've wondered about this for years.  at first glance, it seems like

    > eliminating recursion in favor of *rec combinators would be as

    > fruitful

    > as eliminating iteration in APL, J, K.

     This is possible. At the moment, the plan is to see how well we can

    get on without them. The same goes for high-level programming in a

    linear language; it has nice benefits, including implementation

    simplicity and O(1) data structures without losing purity, but not

    having shared data might prove painful too often.

     > it occurred to me more than once to try to map these patterns

    > to manfred's joy recursion abstractions.  but i never did succeed in

    > that effort.

     I find that having types to guide you through the process makes it

    much easier. It can be quite tricky without them and often the result

    is tedious debugging. Then again, I personally think this extends to

    many aspects of programming in a stack-based language.

    - John

## Manfred Von Thun — 2008-01-16 07:03:37

    On 12/12/07 2:44 AM, "John Cowan" <cowan@...> wrote: William Tanksley,

    Jr scripsit How about "self" as a call to its enclosing context?

     >> > It won't work for dynamic definitions, because there's no distinct concept

    >> of

    >> > "enclosing context". All you know is that you're inside a quotation that's

    >> > inside another quotation; you can't look ahead to see which enclosure is

    >> the

    >> > one being defined and/or executed. There are several solutions: [snippage]

    >> 4.

    >> > Fall back on the Y combinator, or its eager equivalent Z.

    >> >

     Two things:

    First, the Z combinator is actually pretty much the same as the

    x combinator in Joy, definable as: x == dup i, which can do

    everything that the y combinator can (and it is also more efficient).

    Second, the problem of using a defined function before it has been

    defined also occurs in quite conventional  definitions when there

    is mutual recursion of functions. Most languages use the format

    A definition consists of a head followed(!) by a body

    A head consists of a name and the names and types of

    the parameters and the type of the value returned.

    The body consists of a statement (for procedures) or an expression

    (for functions) or a combination of these.

    Since the head precedes the body, there is no problem about

    recursive calls in the body, not even in a single pass compiler.

    If the order were reversed, as in the style currently being

    discussed, then a single pass compiler would have to do some

    backpatching, and it all gets messy.

    But even if the head always precedes the body, there will be a

    problem about mutual recursion. In Pascal (parsing-) functions

    can be nested, so the usual mutual recursion of

    expression -> term -> factor -> expression

    can be handled by nesting. But that will not work in some cases,

    most famously for

    factor -> function-call -> actual parameters -> expression

    The problem arises because some statements are procedure

    calls which also need actual parameters.

    The (very simple) solution is to give a so-called forward

    declaration. In C there is no nesting of definitions, so all

    cases of mutual recursion need one (or more) forward

    declarations, called prototypes in C.

    The same trick of using forward declarations could also be used

    if one really wants to have definitions to have first the body

    and then the name (presumably no explicit parameters in

    a concatenative language). Then a simply recursive definition

    would look like this:

    [] def foo (* the forward declaration with dummy body*)

    [.. foo.. foo..] def foo (* the full definition with recursive calls *)

    But I still do not see any advantage in reversing the normal

    <name body> order for ordinary and self-recursive definitions.

    I think that for languages with explicit parameters (most

    languages) it makes sense to give forward/prototypes for all

    functions, as one is encouraged to do in large C programs.

    But that is another matter.

      - Manfred

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

## Manfred Von Thun — 2008-01-29 08:21:19

    On 16/1/08 6:03 PM, "Manfred Von Thun" <m.vonthun@...> wrote:

    [.. stuff about use before definition..]

    > The same trick of using forward declarations could also be used if one

    > really wants to have definitions to have first the body and then the name

    > (presumably no explicit parameters in a concatenative language). Then a

    > simply recursive definition would look like this:

    >

    > [] def foo (* the forward declaration with dummy body*)

    >

    > [.. foo.. foo..] def foo (* the full definition with recursive calls *)

    I must have had a senior moment (that is what some of my retired colleagues

    call the phenomenon) when I wrote this. To some extent I was thinking of a

    compiled

    implementation with compile time type checking, but even that does not work

    out.

    In an interpreted implementation where all the type checking is done

    at run time, the following is possible: when a symbol is first encountered,

    enter it into the symbol table. Whenever a body of a definition is given,

    enter that body in the table for the symbol. Some symbols might never get

    a definition because they are not intended to be executed. This happens

    for example in lists: [peter paul mary]. But it could also happen

    accidentally

    when an attempt is made to execute the body of an undefined symbol.

    At any rate it is possible to use a symbol (say: bar) in the body of a

    definition of another symbol (say: foo). This is how it looks in Joy

    DEFINE foo == 42 bar.

    At this point bar is not yet defined, so it cannot be executed. Hence foo

    cannot be executed although it is defined.

    DEFINE bar == 2 *.

    Now both foo and bar are defined and can be executed.

    If there is self-recursion.as in the following, then there is not problem:

    DEFINE baz == ... baz ... .

    The first baz enters the symbol into the table, the second finds its

    position in the table, and the final period attaches the body to the

    position in the table.

    Finally, mutual recursion:

    DEFINE zot == ... zot ... wow ... .

    DEFINE wow == ... wow ... zot ... .

    In the definition of zot, the wow is entered and will be found subsequently,

    as on the two occasions in the second definition. So this is just like

    the earlier case of foo and bar. In the definition of wow, the zot of

    course finds its position in the table, and the wow finds a different one,

    just as for self-recursion.

    All the above definitions could be written in the reverse style, with body

    first and head second. Just the last two:

    [... zot ... wow ...] def zot

    [... wow ... zot ...] def wow

    So the idea of entering a symbol into the table as soon as the symbol

    is first encountered makes it possible to have self-recursion and even

    mutual recursion without any forward or prototype declarations.

    HOWEVER: This is fine if type checking is done at run time, but what

    about type checking at compile time? In Pascal the forward declarations

    and in  C the prototypes give the user not just the names of the

    procedures or functions, but also the types of the parameters and the

    the type of the result. In a stack language there will only be one

    parameter, a stack, and the result will also be a stack. Both stacks

    will have to be typed, and a notation is needed for that. My proposal

    would be to borrow some ideas from Prolog. For example, the notation

    [  N:num X | R ]

    would describe a stack of at least two elements, topmost a number N,

    second something of any type,followed by a possibly empty

    rest-of-stack R. Similarly the notation

    [ M:num N:num | R ]

    would desribe a stack of at least two elements, two numbers, not

    necessarily distinct. Then the definition

    DEFINE f == swap pop dup 10 *

    defines f to take as input stack one as described by the first description

    above, an yield as output one as described by the second description.

    Thus the type of f is given by

    f  :  [ N:num X | R] -> [M:num N:num | R]

    Note that N and R occur on both sides of the arrow, and this indicates

    that the input and result stacks are the same in both positions.

    A complete definition of f should then combine the typing and the code:

    DEFINE f : [N:num X| R] -> [M:num N:num | R] == swap pop dup 10 *

    Similar typing could be given for all definitions, and forward/prototypes

    would merely give the typing.

    Incidentally, the example also illustrates something else: that pattern

    matching can describe arbitrarily complex stack shuffling by swap,

    pop, dup and friends (and also list shuffling by cons, first, rest and

    friends.

    But the implications of that are outside this note.

      - Manfred

    >

    >

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