What does "concatenative" actually mean?

[spir]

Hello,

New to the list.
A long time ago, I was fascinated by Forth's ability to let one write programs/words by simply combining lower level words/programs. This was wonderfully illustrated by Logo's visual version of the feature.
I intuitively understand "concatenative" as meaning "constructive" in the sense of "brick programming". This is what I have always looked for, probably. Still, I do not really get why some languages may be so qualified; why most languages do not have this property.
I just discover that Forth (which I onlyused very few a long time ago) is supposed to be a concatenative language. I read the article on wikipedia, some more related texts and a few threads on this list. I do not know Joy (will read a bit while waiting for your replies ;-). Below my present ideas on the topic. I wish you would comment and criticize so that maybe... eurêka! (I am both an amateur and a non-english speaker: please be tolerant with my weird phrasing.)

I will use a notation where, for Forth like languages:
* Digits refer to literal data.
* An uppercase letters refers to a word/defined thing.
* A lowercase letter refers to any item inside a word definition, that may be a literal or another word



-1- referential transparency ================

In stack based langugages,
:W 1
actually means "push 1 (whatever it actually is) on top of the stack".
In a "real" OO language (based on messaged passing, such as usually done in prototypes languages like Io), a reference to a data slot actually calls a data accessor.
Is this analog to "pushing on the stack" ?

:X <do something with 2 values on top the stack>
:W 1 2 X

I intuitively think that this expression is analog to the following:

method X(a1,a2)
   <do something with a1 & a2>
method W
   x := 1 # literal value: call accessor
   y := 2 # idem
  X(x,y)

This leads me to wonder whether concatenation is related to referential transparency. Let us imagine a program which parse tree looks like this:
X
        x1
        x2
        x3
Y
        y1
        y2
        y3
Z
        z1
        z2
        z3
A
        a
        X
        Z
B
        b
        Y
        Z

I have the impression that the language is concatenative iff we can safely translate A & B to:
A
        a
        x1
        x2
        x3
        z1
        z2
        z3
B
        b
        y1
        y2
        y3
        z1
        z2
        z3

Id est replace words with their definitions. This means that a word's definition only relies on the definitions on the words it references. So what makes most languages "unsafe" in this aspect? What kind of element in a definition breaks the scheme? My hypethesis is: definitions may use outer things like environment, state, variables... In the tree above, this translates to the fact that several occurrences of, say, z1 do not perform exactly the same action. For instance, it may not push the same value a stack: then, if z2 uses this value, it will not have the same result.

What lets me uneasy with this point of view is that "concatenative" is not supposed to be a synonym of "purely functional". Or what? Are purely functional languages necessarily, logically, concatenative? But maybe there are other ways to achieve this property, meaning that concatenative is a superset of functional?
Or am I totally wrong?
Anyway, forth is not qualified as functional. Also, stack based languages can well use data external to a word definition (outside the stack). Are they then still concatenative?



-2- the self expression hypothesis ================

Another unusual feature of Forth is its ability to compile itself. This is related I guess to the property that new words are equally treated as builtin words. Io has a similar feature and, as I understand it, a consequence is that it has no keyword in the usual sense of the term.
To allow such a property, these languages' grammars map directly to a parse tree (like Lisp, too) without any structural transformation. This is related, if I understand it correctly, to the fact that the grammar itself does not hold semantics. Or not the same way as for other languages; rather it is basically formal.
Still, there must some primitives here or there, "under the hood", else such a language would really be a pure form and a program would execute without *doing* anything ;-) These primitives are not expressed in the language itself. There are operational primitives (such as IO), but also some minimal "meta-linguistic" ones such as in Forth:

* A number token means "push this number (value) on the stack"
* ':...;' means "parse and store this definition"
* A word token means "recall this word's definiton"
[Expressed with my own words that may not be accurate.]

Analog operational and meta-linguistic primitives can be found in Io or other languages. In Io's case, and I guess in Forth too, even those things can be redefined. [E.g. in Io one can give a new definition to '(...)' which default is close to the one in Lisp.]

Now, my question is: is there any relation between such self-defining properties and the notion of "concatenativity"?



-3- human expressiveness ======================

I wonder about the practical usefulness of the concatenative propertie(s). The ability of building a program by pure composition is great. But it seems to lead to great modelizing restrictions, too. I will illustrate my question with a simple example.

Lets take the "mystery number" game. [Guess a number between eg 1 & 100. The "game master" answers "more" or "less" until found.] As I see it:

* There are 2 actors.
* They communicate: the player "guesses", the master "answers".
* The master holds a "secret" data item; the player has current "lower" and "upper" bounds.

This example really well maps to OO semantics, sure, I didn't choose it randomly;-) But I really think, too, that it illustrates a kind of natural way to express most of non-scientific models. (I.e. models that are rather a system than a "problem" mapping to a (possibly tree-like) process.)

How would a model of this game expressed in a concatenative language look like? (I really ask: if ever some of you want to answer with source code...)

I guess that in a functional language it would lead to conceptual distortion. Slight, manageable distortion, because the game is so simple. What I mean is that such langugages are often unable to allow a direct mapping from a model to source code expression. In other words: for me, a program should look like (be analog to) what it pretends to express.
This statement may only reflect a personal bias. Prototype based languges are, imo, the best metaphor / paradigm as of know, to allow direct, "natural", expression (In the OO world, most class-based languages yield on the contrary incredible and highly abstract complication -- and extreme dependencies!).

Is there a way to accord concatenation and basic OO? Or are these approaches -- as I suspect -- definitely incompatible?


Denis
------
la vita e estrany

[John Nowak]

On Mar 2, 2009, at 3:19 PM, spir wrote:

> I intuitively understand "concatenative" as meaning "constructive"  
> in the sense of "brick programming". This is what I have always  
> looked for, probably. Still, I do not really get why some languages  
> may be so qualified; why most languages do not have this property.

The Wikipedia article was completely changed a few days ago and now  
gives a (mostly) good definition of what qualifies; I'd start there:
http://en.wikipedia.org/wiki/Concatenative_programming_language

> In stack based langugages,
> :W 1
> actually means "push 1 (whatever it actually is) on top of the stack".
> In a "real" OO language (based on messaged passing, such as usually  
> done in prototypes languages like Io), a reference to a data slot  
> actually calls a data accessor.
> Is this analog to "pushing on the stack" ?

I'm not sure what you mean exactly, but I think the answer is probably  
no. I don't think trying to understand concatenative languages in  
terms of message passing is likely to yield good results. The problem  
is that, unlike in Io, you don't really have a way of denoting the  
receiver of a given message. Especially in the higher order languages  
like Joy that have operations like 'dip', 'bi', etc, it's not clear  
how a message passing semantics would work. (That's not to say you  
couldn't make it work of course.)

The way to think about concatenative languages is in terms of function  
composition. Each term in the language represents a function that  
takes a stack as an argument and returns a new stack as a result. This  
is most clearly seen in Joy where stacks are first class and  
inexpensive to pass around freely. I'd try not to think about it in  
the Forth sort of mindset where there's a single stack (or pair of  
stacks) that all operations mutate.

> This leads me to wonder whether concatenation is related to  
> referential transparency.

In Joy, most functions are referentially transparent. Depending on how  
you look at it, you might even say that all functions are  
referentially transparent because the compositional nature of the code  
makes it possible to thread a single invisible state throughout the  
entire program. Some degree of hand-waving is required however.

> I have the impression that the language is concatenative iff we can  
> safely translate A & B to:
> ... Id est replace words with their definitions. This means that a  
> word's definition only relies on the definitions on the words it  
> references.

Correct.

> So what makes most languages "unsafe" in this aspect? What kind of  
> element in a definition breaks the scheme? My hypethesis is:  
> definitions may use outer things like environment, state, variables...

Correct; things like local variables make a language non-
concatenative. Factor offers locals but uses a compile-time transform  
to convert definitions that use them to purely concatenative code.

> What lets me uneasy with this point of view is that "concatenative"  
> is not supposed to be a synonym of "purely functional". Or what?

It depends on the language. For example, all data is persistent in  
Joy; only IO will cause a visible side effect. In a language like  
Factor, much data is not persistent.

> Are purely functional languages necessarily, logically, concatenative?

Not at all. Haskell is purely functional (i.e. there are *no* side  
effects), but not concatenative.

> Another unusual feature of Forth is its ability to compile itself.  
> This is related I guess to the property that new words are equally  
> treated as builtin words. Io has a similar feature and, as I  
> understand it, a consequence is that it has no keyword in the usual  
> sense of the term.

Many languages have the property that new words are treated equally to  
built-in words. What's unique about Io is that any function has access  
to the message sent to it before any expressions associated with that  
message are reduced. This is similar to the situation in Joy and XY  
where functions can manipulate the functions passed to them (called  
"quotations") as if they were lists. Factor offers a macro system that  
lets you do the same sort of things you do in Forth.

> Still, there must some primitives here or there, "under the hood",  
> else such a language would really be a pure form and a program would  
> execute without *doing* anything

You may want to look at this page; it shows how concatenative  
languages can be turing complete with a very minimal combinator  
selection:
http://tunes.org/~iepos/joy.html

> Now, my question is: is there any relation between such self-
> defining properties and the notion of "concatenativity"?

The simple grammar of concatenative languages makes it easy to do the  
sort of things you're talking about. It's not a property unique to  
concatenative languages however.

> I wonder about the practical usefulness of the concatenative  
> propertie(s).

They're useful. Tons of code is written in Forth. Factor has shown  
tremendous progress in a very short period of time. If you're  
interested in how such languages can be productive, I'd encourage you  
to download Factor and get to work.

Factor offers an OO system which may make you feel more at home,  
although it's based on multiple dispatch (I think) rather than message  
passing; the former makes more sense for a concatenative language. I  
don't know the system well enough to give you an example to your  
problem, although I'm sure asking on the #concatenative channel on  
Freenode would get you results; quite a few Factor programmers hang  
out there.

> Is there a way to accord concatenation and basic OO? Or are these  
> approaches -- as I suspect -- definitely incompatible?

They're not incompatible. Many Forths have objects, Factor has  
objects, and I believe there was talk of adding a prototype-based  
object system to Cat at one point as well. If you want to reimplement  
Io in Factor, you'd be more than able to. I'd encourage you to try the  
existing system first though and see what you think.

- John

[LittleDan]

> They're useful. Tons of code is written in Forth. Factor has shown
> tremendous progress in a very short period of time. If you're
> interested in how such languages can be productive, I'd encourage you
> to download Factor and get to work.
>
> Factor offers an OO system which may make you feel more at home,
> although it's based on multiple dispatch (I think) rather than message
> passing; the former makes more sense for a concatenative language. I
> don't know the system well enough to give you an example to your
> problem, although I'm sure asking on the #concatenative channel on
> Freenode would get you results; quite a few Factor programmers hang
> out there.
>
>> Is there a way to accord concatenation and basic OO? Or are these
>> approaches -- as I suspect -- definitely incompatible?
>
> They're not incompatible. Many Forths have objects, Factor has
> objects, and I believe there was talk of adding a prototype-based
> object system to Cat at one point as well. If you want to reimplement
> Io in Factor, you'd be more than able to. I'd encourage you to try the
> existing system first though and see what you think.

Factor's OO system isn't based on message passing. Generic words are
words that can have methods defined on them for certain classes, like
Lisp. But multiple dispatch mostly isn't used (yet); there's a library
for multiple dispatch that's not in core.

Factor's object system used to be a unique hybrid between being
class-based and including delegation, but now it's more traditional.
There are things that are like structs, that can have single
inheritance among each other. Then, there are mixins, which are really
extensible union classes that take the place of declaring that a class
implements a certain interface. (It's not actually enforced that the
class does implement the interface.) There are also predicate classes,
singleton classes and a few other convenient things. The library
defines more (eg multimethods, delegation), since all the internals of
the object system are fully hackable.

I think Eduardo Cavazos wrote a prototype-based OO system in Factor,
but I'm not sure if it's still around. Generally, Factor is flexible
enough that you can implement whatever object system you want as a
library, and it can be made pretty efficient. Factor's object system
used to be just a library, but now it gets special help from the
compiler (type inference is used to reduce dispatch, etc), so it can't
really be considered that way now.

Dan

[Don Groves]

On Mar 2, 2009, at 12:19 PM, spir wrote:

> Hello,
>
> New to the list.
> A long time ago, I was fascinated by Forth's ability to let one  
> write programs/words by simply combining lower level words/programs.  
> This was wonderfully illustrated by Logo's visual version of the  
> feature.
> I intuitively understand "concatenative" as meaning "constructive"  
> in the sense of "brick programming". This is what I have always  
> looked for, probably. Still, I do not really get why some languages  
> may be so qualified; why most languages do not have this property.
> I just discover that Forth (which I onlyused very few a long time  
> ago) is supposed to be a concatenative language. I read the article  
> on wikipedia, some more related texts and a few threads on this  
> list. I do not know Joy (will read a bit while waiting for your  
> replies ;-).

Warning: if you were inspired by Forth, Joy will
change your life!

You will become hooked on its ideas, just as so
many here have before you ;-)
--
don

[spir]

Le Mon, 2 Mar 2009 16:23:15 -0500,
John Nowak <john@...> s'exprima ainsi:

> On Mar 2, 2009, at 3:19 PM, spir wrote:
>
> > I intuitively understand "concatenative" as meaning "constructive"  
> > in the sense of "brick programming". This is what I have always  
> > looked for, probably. Still, I do not really get why some languages  
> > may be so qualified; why most languages do not have this property.
>
> The Wikipedia article was completely changed a few days ago and now  
> gives a (mostly) good definition of what qualifies; I'd start there:
> http://en.wikipedia.org/wiki/Concatenative_programming_language

Thank you for your extensive reply.
I have read this page numerous times ;-)

> > In stack based langugages,
> > :W 1
> > actually means "push 1 (whatever it actually is) on top of the stack".
> > In a "real" OO language (based on messaged passing, such as usually  
> > done in prototypes languages like Io), a reference to a data slot  
> > actually calls a data accessor.
> > Is this analog to "pushing on the stack" ?
>
> I'm not sure what you mean exactly, but I think the answer is probably  
> no.

What I mean is (letting aside the notion of object to which a message are sent -- say that there a unique global object or talk of plain functions).

:plus <whatever> ;
:plus1 1 plus ;

Can we say that the code above is equivalent to:

func plus(a,b)
        <whatever>
func plus1(n)
        plus(n, 1)

or more explicitely:


:plus <whatever> push; # 'push' means push result on the stack
:plus1 1 push plus ; # result already on the stack

func plus(a,b)
        <whatever>
        resturn result
func plus1(n)
        # equivalent to pushing 'data'?
        x := n
        y := 1
        # then only call other func
        plus(x, y)

I wonder if the functional way and the stack way are equivalent manners of defining code snippets -- that use variables in the math sense of "unpredictable values" (at design time) -- that are secure; meaning that they will perform a fully defined action and/or are concatenatable as code bricks.

> > This leads me to wonder whether concatenation is related to  
> > referential transparency.
>
> In Joy, most functions are referentially transparent. Depending on how  
> you look at it, you might even say that all functions are  
> referentially transparent because the compositional nature of the code  
> makes it possible to thread a single invisible state throughout the  
> entire program. Some degree of hand-waving is required however.
[...]
> > What lets me uneasy with this point of view is that "concatenative"  
> > is not supposed to be a synonym of "purely functional". Or what?
>
> It depends on the language. For example, all data is persistent in  
> Joy; only IO will cause a visible side effect. In a language like  
> Factor, much data is not persistent.

> > Are purely functional languages necessarily, logically, concatenative?
>
> Not at all. Haskell is purely functional (i.e. there are *no* side  
> effects), but not concatenative.

Still unclear for me. (good, I have unknown worlds to explore ;-)

> > I wonder about the practical usefulness of the concatenative  
> > propertie(s).
>
> They're useful. Tons of code is written in Forth.
[...]
I expressed myself unclearly.

> > Is there a way to accord concatenation and basic OO? Or are these  
> > approaches -- as I suspect -- definitely incompatible?
>
> They're not incompatible. Many Forths have objects, Factor has  
> objects, and I believe there was talk of adding a prototype-based  
> object system to Cat at one point as well. If you want to reimplement  
> Io in Factor, you'd be more than able to. I'd encourage you to try the  
> existing system first though and see what you think.

This is something I really do not understand. In many OO languages, especially prototype-based ones, objects are simple map/dict like variables. They can be refered to from inside any word/func/'action'; so as I understand the point they act, at least can act, as global state, environment, variables that will necessarily break the (referential) "safety" of the function. Meaning that they have unpredictable effect/result. How can one then simply combine such functions as code bricks -- which is how I understand concatenativity?
There must be something my brain is unable to catch...

> - John

Thank you again,
Denis
------
la vita e estrany

[John Nowak]

On Mar 3, 2009, at 4:56 AM, spir wrote:

> :plus <whatever> ;
> :plus1 1 plus ;
>
> Can we say that the code above is equivalent to:
>
> func plus(a,b)
> <whatever>
> func plus1(n)
> plus(n, 1)

I'm not sure this'll help, but I'll try.

In a stack-based concatenative language, every function takes a stack  
as input and returns a new stack as a result. Accordingly, we might  
implement the 'plus' function of a concatenative language in Scheme as  
such:

    (lambda (s) (cons (+ (car s) (cadr s)) (cddr s)))

Another example would be 'dup':

    (lambda (s) (cons (car s) s))

And 'dip':

    (lambda (s) (cons (cadr s) ((car s) (cddr s))))

Of course, if you're not familiar with Lisp, I've just confused you  
even more.

>> Not at all. Haskell is purely functional (i.e. there are *no* side
>> effects), but not concatenative.
>
> Still unclear for me. (good, I have unknown worlds to explore ;-)

In Haskell, not all terms denote functions. In concatenative  
languages, all terms denote functions. In Haskell, juxtaposition  
denotes application. In concatenative languages, juxtaposition denotes  
composition.

> This is something I really do not understand. In many OO languages,  
> especially prototype-based ones, objects are simple map/dict like  
> variables. They can be refered to from inside any word/
> func/'action'; so as I understand the point they act, at least can  
> act, as global state, environment, variables that will necessarily  
> break the (referential) "safety" of the function.

The object systems in Factor and Forth do break referential  
transparency. If this means that are not "purely concatenative"  
depends on who you ask.

- John

[William Tanksley, Jr]

John Nowak wrote:
> The object systems in Factor and Forth do break referential  
> transparency. If this means that are not "purely concatenative"  
> depends on who you ask.

Thanks for taking the time to explain; I agree with most of what you've
said, but this is false.

Forth doesn't have any "the object system"; some of the open-source
alternatives available do destroy local concatenativity, but most of
them don't.

Factor's official object system is definitely fully concatenative. It
won't matter who you ask; if they disagree with me, they're wrong. ;-)

Technical point: Referential Transparency in a concatenative language is
different from the same concept in an applicative language. In one
sense, it's harder to use, since you can't simply move words from one
place to another (without rearranging the stack); in another sense it's
easier to use, since you can "factor out" a word without having to do
any work at all (cut and paste is sufficient). Unlike applicative
languages, you do NOT have to worry about functional state; the fact
that the stack acts as a monad means that the state is already
preserved; even I/O can be modelled properly.

> - John

-Wm

[William Tanksley, Jr]

spir wrote:
> John Nowak <john@...> s'exprima ainsi:
> Can we say that the code above is equivalent to:
> I wonder if the functional way and the stack way are equivalent
> manners of defining code snippets -- that use variables in the math
> sense of "unpredictable values" (at design time) -- that are secure;
> meaning that they will perform a fully defined action and/or are
> concatenatable as code bricks.

The best way to say that kind of thing -- assuming that I understand
what you're asking for -- is to provide a constructive method to
transform one representation into another. Nowak pointed you at Kerby's
web page earlier; that includes an algorithm to convert lambda notation
into stack notation, thus proving that the two are equivalent (assuming
that you have a complete basis in both).

> > > This leads me to wonder whether concatenation is related to  
> > > referential transparency.
> > > What lets me uneasy with this point of view is that
> "concatenative"  
> > > is not supposed to be a synonym of "purely functional". Or what?

It's not. Joy attempts to be a partially pure functional language that's
purely concatenative; Cat and 5th try much harder to be functionally
pure. My little toy language achieves complete functional purity by the
expedient mechanism of being completely useless for any practical
purpose.

But Forth and Postscript are (reasonably) concatenative, and are not
functionally pure at all.

"Concatenative" and "functional" are two completely different adjectives
that can be applied completely independently. The only thing they share
in common is that both allow you to make mathematical statements about
your code -- and if your language is "pure" enough, those statements
help you reason about your code.

> > > I wonder about the practical usefulness of the concatenative  
> > > propertie(s).
> > They're useful. Tons of code is written in Forth.
> I expressed myself unclearly.

To me, the most useful property is that concatenative code is fully
associative. This implies that you can group concatenative code in any
way that's convenient for you. If you're reading the code, you can "give
up" on a complex section of code and skip ahead to try to make sense of
a later section; what you discover will be correct no matter what the
earlier section actually meant. If you're writing or refactoring the
code, it means that you can "physically" group the code any way you
want: just cut any section out, replace it with a new function name, and
paste the old section into the definition of the new function.

One mathematical property, two uses.

> This is something I really do not understand. In many OO languages,
> especially prototype-based ones, objects are simple map/dict like
> variables. They can be refered to from inside any word/func/'action';
> so as I understand the point they act, at least can act, as global
> state, environment, variables that will necessarily break the
> (referential) "safety" of the function. Meaning that they have
> unpredictable effect/result. How can one then simply combine such
> functions as code bricks -- which is how I understand concatenativity?
> There must be something my brain is unable to catch...

The truly pure functional languages, like Haskell, have a mathematical
model for state-changing effects, like objects and I/O. The problem is
that purely functional languages don't express what order their
operations will occur in; they just tell the computer what operations to
do, and let the compiler figure out the best order. So Haskell provides
a mathematical construct called a "monad". Monads can mathematically
only be evaluated in order, so the compiler receives enough information
to know what order to execute your code in.

Concatenative languages use a stack (or something like that), and as a
result they already have a monad built into them. If you do something
that's functionally unsafe (stateful) you're still concatenatively safe,
so your associative property still applies.

(However, state-free concatenative languages DO have some nice
additional properties.)

> Denis

-Wm

[John Cowan]

William Tanksley scripsit:

> The truly pure functional languages, like Haskell, have a mathematical
> model for state-changing effects, like objects and I/O. The problem is
> that purely functional languages don't express what order their
> operations will occur in; they just tell the computer what operations to
> do, and let the compiler figure out the best order. So Haskell provides
> a mathematical construct called a "monad". Monads can mathematically
> only be evaluated in order, so the compiler receives enough information
> to know what order to execute your code in.

You don't really need monads: they are just a convenience, because
it would be painful to thread state through every function in
your program just in case a callee wants to use some of it; see
http://lambda-the-ultimate.org/node/1155#comment-12726 for details.
In Joy, the equivalent of the I/O monad is the simple fact that "read"
has a stack shape of F -> F O, preserving the F object on the stack.

--
One Word to write them all,             John Cowan <cowan@...>
  One Access to find them,              http://www.ccil.org/~cowan
One Excel to count them all,
  And thus to Windows bind them.                --Mike Champion

[Rodney D Price]

Haskell *does* need a monad to do I/O.  The essential
difference between "read" having a stack shape of
F -> F O, and Haskell's IO monad, is that the Haskell
IO monad is guaranteed to confine any side effects to
the IO monad; that is, the result of an IO operation will
always have a type of the form IO <something>.  And
there's no way any result depending on an I/O operation
can avoid having type IO <something>.  There's no
escape from the IO monad in Haskell.  Lacking a static
type system, Joy offers no such guarantee.

Cat, OTOH, has a Hindley-Milner static type system.
Perhaps Cat could do monads.

-Rod








William Tanksley scripsit:

> The truly pure functional languages, like Haskell, have a mathematical
> model for state-changing effects, like objects and I/O. The problem is
> that purely functional languages don't express what order their
> operations will occur in; they just tell the computer what operations to
> do, and let the compiler figure out the best order. So Haskell provides
> a mathematical construct called a "monad". Monads can mathematically
> only be evaluated in order, so the compiler receives enough information
> to know what order to execute your code in.

You don't really need monads: they are just a convenience, because
it would be painful to thread state through every function in
your program just in case a callee wants to use some of it; see
http://lambda-the-ultimate.org/node/1155#comment-12726 for details.
In Joy, the equivalent of the I/O monad is the simple fact that "read"
has a stack shape of F -> F O, preserving the F object on the stack.

--
One Word to write them all, John Cowan <cowan@...>
One Access to find them, http://www.ccil.org/~cowan
One Excel to count them all,
And thus to Windows bind them. --Mike Champion





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

[John Nowak]

On Mar 3, 2009, at 10:11 AM, William Tanksley wrote:

> Factor's official object system is definitely fully concatenative. It
> won't matter who you ask; if they disagree with me, they're wrong. ;-)
>
> Technical point: Referential Transparency in a concatenative  
> language is
> different from the same concept in an applicative language. In one
> sense, it's harder to use, since you can't simply move words from one
> place to another (without rearranging the stack); in another sense  
> it's
> easier to use, since you can "factor out" a word without having to do
> any work at all (cut and paste is sufficient). Unlike applicative
> languages, you do NOT have to worry about functional state; the fact
> that the stack acts as a monad means that the state is already
> preserved; even I/O can be modelled properly.

Not everyone agrees on this point. Take a look at this thread:

    http://lambda-the-ultimate.org/node/3050

Many would say Joy is not purely functional and that the "monadic  
stack" argument essentially amounts to hand-waving. If you take this  
view, then the question of Joy or Factor being "purely concatenative"  
depends on if you require concatenative languages to be "purely  
functional".

Joy isn't "pure enough" to allow evaluation via postfix term rewriting  
in an arbitrary order. If you had a type system that could enforce  
something similar to the I/O monad in Haskell, it would be. I  
definitely think there's some use in distinguishing between the  
relative purity of both approaches.

I feel that being able to evaluate in any order without worrying about  
side effects is somehow "more concatenative" than having to evaluate  
left to right. Rather than make a claim here, I tried to sidestep the  
issue to avoid contention. I see I failed once again! :)

- John

[William Tanksley, Jr]

Rodney D Price wrote:
> can avoid having type IO <something>.  There's no
> escape from the IO monad in Haskell.  Lacking a static
> type system, Joy offers no such guarantee.

Actually, Joy has a dynamic type system that DOES make that guarantee.
That "F" type on the output of 'read' means that it truly is a file, and
the only way to muck with it is through the file itself.

> Cat, OTOH, has a Hindley-Milner static type system.
> Perhaps Cat could do monads.

My claim was that the stack is already a monad, so that nothing further
was needed. John pointed out correctly that it was also important to
return the thing whose state was being modified (thank you, you're
absolutely correct).

I'd now add that you have to have some assurance that there aren't
references to the same state being manipulated "at the same time". That
must be provided by the language's copy and reference semantics, as well
as the semantics of the library responsible for state mutation (in this
example, the I/O library).

I think this means -- in general -- that you have to have custom code
run when duplication and/or destruction happens. In specific, the
optimizer has to either know about your mutable types, or be completely
naive.

And here's another difference between pure functional languages and
concatenative languages, as a class: a naive implementation of a
concatenative language (i.e. without any optimizer whatsoever) will run
code reasonably quickly. Forth is a prime example; Joy is somewhat of an
example, although its extensive use of functional abilities slows it
down a bit.

> -Rod

-Wm

[John Nowak]

On Mar 3, 2009, at 2:00 PM, Rodney D Price wrote:

> Haskell *does* need a monad to do I/O.

Haskell doesn't need a monad to do I/O. The alternative would be ugly  
as Mr. Cowan said, but it's not a requirement.

The easiest way to do it would be to pass a "world value" into the  
program and then use uniqueness types to ensure no I/O actions are  
performed when there exists more than one reference to the world  
value. In this approach, you'd have to manually plumb the world state  
around instead of using monads.

- John

[William Tanksley, Jr]

spir wrote:
> This leads me to wonder whether concatenation is related to
> referential transparency. Let us imagine a program which parse tree
> looks like this:
> I have the impression that the language is concatenative iff we can
> safely translate A & B to:

(Examples snipped.)

> Id est replace words with their definitions.

"A language is concatenative iff one can replace words with their
definitions." I think that's at least CLOSE. You might also have to be
able to replace a definition with the word as well -- it has to run both
ways. You also have to be "persnickety" that you're not allowed to
rename anything during the replacement (i.e. you're not allowed to do
beta reduction or alpha conversion).

Of course, this is not a complete way to evaluate a language; it doesn't
allow for recursion.

> This means that a word's definition only relies on the definitions on
> the words it references. So what makes most languages "unsafe" in this
> aspect? What kind of element in a definition breaks the scheme? My
> hypethesis is: definitions may use outer things like environment,
> state, variables... In the tree above, this translates to the fact
> that several occurrences of, say, z1 do not perform exactly the same
> action. For instance, it may not push the same value a stack: then, if
> z2 uses this value, it will not have the same result.

Not really. The problem with most languages is that the functions are
defined using local variables, so when you attempt to replace their name
with their definition, you have to FIRST change the definition by
replacing all the instances of each local variable with the value of the
actual parameter.

The fact that some things have state is a problem for lambda expansion,
but it's not even a question when you don't attempt to replace formal
parameters with actual parameters.

> What lets me uneasy with this point of view is that "concatenative" is
> not supposed to be a synonym of "purely functional". Or what? Are
> purely functional languages necessarily, logically, concatenative? But
> maybe there are other ways to achieve this property, meaning that
> concatenative is a superset of functional?

Nope, they're completely different properties.

A concatenative language is completely associative: you can group words
within it anyhow you'd like, and maintain the same semantics. A pure
functional language is referentially transparent: if two complete
expressions have the same semantics, they can be interchanged without
changing the program semantics. The functional language, however,
requires "complete expressions"; the concatenative language doesn't.

> Or am I totally wrong?
> Anyway, forth is not qualified as functional. Also, stack based
> languages can well use data external to a word definition (outside the
> stack). Are they then still concatenative?

Yes. But they're not functional languages -- just concatenative.

> -2- the self expression hypothesis ================
> Another unusual feature of Forth is its ability to compile itself.
> This is related I guess to the property that new words are equally
> treated as builtin words. Io has a similar feature and, as I
> understand it, a consequence is that it has no keyword in the usual
> sense of the term.
> To allow such a property, these languages' grammars map directly to a
> parse tree (like Lisp, too) without any structural transformation.

Io and Forth work for entirely different reasons. For Io, it has a
textual grammar that's a simple tree, and every message has full access
to the data-structure representation of that tree.

For Forth, the grammar is a flat list (not a tree), and because the
source code is already a flat list, giving functions access to their own
source is sufficient to allow them full access to the data-structure.

Most concatenative languages don't allow that, and even in Forth it's
discouraged. I don't have a good theory to account for what happens when
you let a word freely read and/or modify the source in which it appears;
you can do fun things, but you also lose all guarantees of concatenative
behavior. It makes more sense to me for a language to provide at most a
formal macro facility, so that source rewriting will follow clear rules
and be clearly delimited.

> Still, there must some primitives here or there, "under the hood",
> else such a language would really be a pure form and a program would
> execute without *doing* anything ;-) These primitives are not
> expressed in the language itself. There are operational primitives
> (such as IO), but also some minimal "meta-linguistic" ones such as in
> Forth:

Correct; a language consists of both syntax and semantics. The syntax of
a concatenative language consists only of a flat list; the semantics
says that the members of that list may be selected from a set of
functions called "basis functions".

Forth -- and any practical language -- has a huge set of basis
functions, and allows you to define your own functions that are used
just like basis functions.

See Kerby's paper for more mathematical detail.
http://tunes.org/~iepos/joy.html

IF YOU DARE. :)

> * A number token means "push this number (value) on the stack"
> * ':...;' means "parse and store this definition"
> * A word token means "recall this word's definiton"
> [Expressed with my own words that may not be accurate.]

Right -- Forth has an additional syntax (not purely concatenative) to
allow you to do real work. :-)

> Now, my question is: is there any relation between such self-defining
> properties and the notion of "concatenativity"?

Yes. Concatenative languages have fully listlike grammar, so every
element of a program can be defined in terms of what it should be
replaced with; in a language with more complex syntax some elements have
to serve syntactic function (the parens in Lisp and Io, the spaces in
Io).

> -3- human expressiveness ======================
> I wonder about the practical usefulness of the concatenative
> propertie(s). The ability of building a program by pure composition is
> great. But it seems to lead to great modelizing restrictions, too. I
> will illustrate my question with a simple example.
> Lets take the "mystery number" game. [Guess a number between eg 1 &
> 100. The "game master" answers "more" or "less" until found.] As I see
> it:
> * There are 2 actors.
> * They communicate: the player "guesses", the master "answers".
> * The master holds a "secret" data item; the player has current
> "lower" and "upper" bounds.
> This example really well maps to OO semantics, sure, I didn't choose
> it randomly;-) But I really think, too, that it illustrates a kind of
> natural way to express most of non-scientific models. (I.e. models
> that are rather a system than a "problem" mapping to a (possibly
> tree-like) process.)

There's no reason NOT to use OO modeling in a concatenative language.
The only language type that's incompatible with that is immutable
functional languages.

> How would a model of this game expressed in a concatenative language
> look like? (I really ask: if ever some of you want to answer with
> source code...)

If we're restricted to the same model, it'd look the same way. If we can
choose a different model, it'd look different.

> I guess that in a functional language it would lead to conceptual
> distortion. Slight, manageable distortion, because the game is so
> simple. What I mean is that such langugages are often unable to allow
> a direct mapping from a model to source code expression. In other
> words: for me, a program should look like (be analog to) what it
> pretends to express.

That's only true if the model is OO. Not all models are OO. Don't forget
that OO modeling is also incompatible with relational modeling!

> This statement may only reflect a personal bias. Prototype based
> languges are, imo, the best metaphor / paradigm as of know, to allow
> direct, "natural", expression (In the OO world, most class-based
> languages yield on the contrary incredible and highly abstract
> complication -- and extreme dependencies!).

I know -- I really like Io for that.

> Is there a way to accord concatenation and basic OO? Or are these
> approaches -- as I suspect -- definitely incompatible?

Absolutely not incompatible. Factor has a complete OO system; it even
used to be based on prototypes (that was changed because the Factor
maintainers understood class based systems better and didn't want to
maintain a system they didn't understand; in particular they had buggy
delegation). It still has its prototype object system in a side library
(no longer in the core); perhaps a person knowledgeable in delegation
could fix it.

At any rate, there's no reason whatsoever for concatenative languages to
have any problem with object oriented modeling and/or programming.

> Denis

-Wm

[John Nowak]

On Mar 3, 2009, at 3:00 PM, William Tanksley wrote:

>> Id est replace words with their definitions.
>
> "A language is concatenative iff one can replace words with their
> definitions." I think that's at least CLOSE. You might also have to be
> able to replace a definition with the word as well -- it has to run  
> both
> ways. You also have to be "persnickety" that you're not allowed to
> rename anything during the replacement (i.e. you're not allowed to do
> beta reduction or alpha conversion).

You make it sound like Haskell might qualify. You can certainly  
replace words with their definitions in Haskell. Replacing expressions  
with the word that names them is possible as well for any "valid sub-
program". For example, I can take '(\x -> foo x 10) y' and convert it  
to 'bar y' if 'bar' is defined as '\x -> foo x 10'. I could not,  
however, do something like replace 'foo x 10' with something because  
it is not a valid sub-program (as 'x' is not introduced anywhere).

I think the best definition of a concatenative language is as follows:

"All terms denote functions and their juxtaposition denotes  
composition."

Everything else follows from this. It also makes it clear why Haskell  
doesn't qualify.

- John

[John Cowan]

John Nowak scripsit:

> The easiest way to do it would be to pass a "world value" into the  
> program and then use uniqueness types to ensure no I/O actions are  
> performed when there exists more than one reference to the world  
> value. In this approach, you'd have to manually plumb the world state  
> around instead of using monads.

That's what Clean does, correct?

--
Unless it was by accident that I had            John Cowan
offended someone, I never apologized.           cowan@...
        --Quentin Crisp                         http://www.ccil.org/~cowan

[John Nowak]

On Mar 3, 2009, at 3:57 PM, John Cowan wrote:

> John Nowak scripsit:
>
>> The easiest way to do it would be to pass a "world value" into the
>> program and then use uniqueness types to ensure no I/O actions are
>> performed when there exists more than one reference to the world
>> value. In this approach, you'd have to manually plumb the world state
>> around instead of using monads.
>
> That's what Clean does, correct?

Yes. The 'Start' function in your program makes this clear on the type  
level:

    Start :: *World -> *World
    Start world = startIO NDI Void initialise [] world

In my personal opinion, the monadic approach in Haskell is much  
cleaner. I'd still like to see uniqueness types added to Haskell  
though for things like destructive array update; I find uniqueness  
types preferable to monads in such cases. (Well, really, I just want  
to see Disciple Haskell become usable.)

In a concatenative language, one thing you can do as add the 'world'  
to the top of the stack and have all operations work below it except  
those that perform IO. This does let you sort of hand-wave and claim  
the language is purely functional. The problem is that *everything*  
now has a forced evaluation order, not just those things that perform  
IO. In other words, even though your language is purely functional,  
you're still essentially stuck with having to use eager evaluation.  
This is why I claim this approach is mostly hand-waving; it doesn't  
let you do anything different than you otherwise would.

Ideally, you'd handle the world value explicitly; this would make it  
clear which things can be reduced in an arbitrary order and which  
things cannot. You'd need to add a type system to ensure you don't  
violate assumptions about how the world value is used however. If you  
were allowed to duplicate the world value (or put it in an aggregate  
and then duplicate the aggregate), bad things would happen.

- John

[Robbert van Dalen-2]

>

> And here's another difference between pure functional languages and
> concatenative languages, as a class: a naive implementation of a
> concatenative language (i.e. without any optimizer whatsoever) will  
> run
> code reasonably quickly. Forth is a prime example; Joy is somewhat  
> of an
> example, although its extensive use of functional abilities slows it
> down a bit.
>
>

enchilada is purely functional *by design*.... without using monads or  
uniqueness types.
enchilada also happens to be 'concatenative' - whatever that means :)

i believe that marrying the two traits, purely functional and  
concatenative, will give us the nice properties we want, i.e.

you can factor out any valid (sub)expression and replace that with  
a ...word.... (denoting the factored expression).

i believe this property also holds for joy, if it is stripped from  
it's file manipulation primitives.

> > -Rod
>
> -Wm
>
>
- robbert.

>



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

Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/concatenative/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/concatenative/join
    (Yahoo! ID required)

<*> To change settings via email:
    mailto:concatenative-digest@...
    mailto:concatenative-fullfeatured@...

<*> To unsubscribe from this group, send an email to:
    concatenative-unsubscribe@...

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/

[John Cowan]

John Nowak scripsit:

> In a concatenative language, one thing you can do as add the 'world'  
> to the top of the stack and have all operations work below it except  
> those that perform IO. This does let you sort of hand-wave and claim  
> the language is purely functional. The problem is that *everything*  
> now has a forced evaluation order, not just those things that perform  
> IO. In other words, even though your language is purely functional,  
> you're still essentially stuck with having to use eager evaluation.  
> This is why I claim this approach is mostly hand-waving; it doesn't  
> let you do anything different than you otherwise would.

Nobody ever claimed that Joy was lazy; "pure functional" does not mean
"pure, functional, and lazy".  Lazy languages have their virtues, but
so do eager ones.

Similarly, it has a type system, just not a static type system.  Those too
have their disadvantages: I find it useful that languages like Scheme
and Joy can have fully heterogeneous lists.

--
May the hair on your toes never fall out!       John Cowan
        --Thorin Oakenshield (to Bilbo)         cowan@...

[John Nowak]

On Mar 3, 2009, at 4:17 PM, Robbert Dalen wrote:

> enchilada is purely functional *by design*.... without using monads or
> uniqueness types.

I don't believe you! Can you demonstrate how a "hello world" program  
would work?

> you can factor out any valid (sub)expression and replace that with
> a ...word.... (denoting the factored expression). i believe this
> property also holds for joy, if it is stripped from it's file
> manipulation primitives.

This property holds for Joy in all cases; the impure IO doesn't make  
any difference. What you can't do is replace an expression with the  
result of evaluating it, e.g., you can't replace '1 2 print' with '1'.  
This is another reason why I think it is not useful to say Joy is  
referentially transparent.

- John