Fwd: [stack] Concatenative Research
John Carter — 2011-01-31 01:57:09
On Mon, Jan 31, 2011 at 1:20 PM, Justin <
zallambo@...> wrote:
> Hello. Is this forum still alive? I haven't shown my head here for a couple
> of years. I'm a MA/CS major with an ongoing interest in giving concatenative
> languages a firmer mathematical foundation. I have a few partial results:
> (i) an operational semantics, (ii) a concept of & application for
> homomorphisms, (iii) a type system. Is anyone else around here interested in
> this sort of research? Here's a link to my (ongoing) work,
>
> http://dl.dropbox.com/u/17328602/concat/index.html
>
>
Some small comments...
> There are no variables. I have the impression that variables are a
> difficult concept to grasp. We spend years teaching students about variables
> in math class, and even in college many students have difficulty
> understanding that (lambda x. x) and (lambda y. y) are identical. This is
> certainly a double-edged sword - variables are a powerful reasoning aid -
> but I am nonetheless interested in glimpsing a world free of variables.
>
One major problem with variables is not variables themselves, but the
existence of two entirely different concepts overloaded with the same name.
- Half the time we mean "named storage location" and the other half the
time we mean "named value". The "named storage location" notion of variables
implies a stateful system and all the attendant difficulties in analysis.
- The "named value" notion of variables is a convenience that allows us
to remove the irrelevant computational fluff of stack manipulations from our
expressions.
"Concatenative" refers to the syntactic sugar (glucose?, alcohol?) of
choosing a syntax in which function composition is represented by string
concatenation.
I invite you to contemplate what these languages are in the absence of a
string representation. (For example, at one higher level of abstraction a
concatenative language is one where functional composition is represented by
the concatenation of two lists of tokens. But I'm sure we can abstract it
well away from the representation.)
The neatness of concatenative program fragments often arises from a
carefully pre-chosen alignment of the output values of the previous function
with the input requirements of the next.
Where it doesn't align neatly, we need a bunch of stack manipulating "fluff"
that adds nothing to computation.
What may be interesting and useful would be to return to typed variables
(named values variety) and something like a SQL "natural join".
99% of the time which function result variable, needs to be bound which
input variable, is obvious and can be automatically inferred from their type
and name.
By making the rules for doing this explicit, you should be able to create a
concatenative language that doesn't involve the notion of a stack, nor are
the program fragments cluttered with irrelavent variable name references or
stack manipulation "fluff".
I would argue that any language where the function definitions are cluttered
with stack manipulations OR variable references has NOT yet met the full
promise of concatenative languages.
--
John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email :
john.carter@...
New Zealand
=======================================================================
This email, including any attachments, is only for the intended
addressee. It is subject to copyright, is confidential and may be
the subject of legal or other privilege, none of which is waived or
lost by reason of this transmission.
If the receiver is not the intended addressee, please accept our
apologies, notify us by return, delete all copies and perform no
other act on the email.
Unfortunately, we cannot warrant that the email has not been
altered or corrupted during transmission.
=======================================================================
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2011-01-31 03:40:19
John Carter <
john.carter@...> wrote:
> Justin <zallambo@...> wrote:
>> http://dl.dropbox.com/u/17328602/concat/index.html
> "Concatenative" refers to the syntactic sugar (glucose?, alcohol?) of
Definitely syntactic splicing factor U2AF.
> choosing a syntax in which function composition is represented by string
> concatenation.
That's what I think of, yes -- minus the word "sugar". Not all syntax
is "syntactic sugar". A language might be defined as "the mapping of
syntax onto semantics"; thus, language design is concerned with
defining syntax, semantics, and the mapping between them. Words like
"syntax sugar" encourage a disregard for one of those crucial three
components of language design.
> The neatness of concatenative program fragments often arises from a
> carefully pre-chosen alignment of the output values of the previous function
> with the input requirements of the next.
> Where it doesn't align neatly, we need a bunch of stack manipulating "fluff"
> that adds nothing to computation.
> What may be interesting and useful would be to return to typed variables
> (named values variety) and something like a SQL "natural join".
That is indeed an interesting thought.
I should note that ANS Forth (for example) says that there may be an
additional stack on which floating point numbers reside. Floating
point operators access only the FP stack. Perhaps, therefore, part of
the solution might involve defining multiple stacks for items with
different types, and for items involved in different architectural
purposes.
> By making the rules for doing this explicit, you should be able to create a
> concatenative language that doesn't involve the notion of a stack, nor are
> the program fragments cluttered with irrelavent variable name references or
> stack manipulation "fluff".
Possibly true. I'd love to see this explored; it does seem that the
"stack" is not _necessary_ to the idea of a concatenative language.
> I would argue that any language where the function definitions are cluttered
> with stack manipulations OR variable references has NOT yet met the full
> promise of concatenative languages.
I know what you mean. Forth, Joy, and Factor are all capable of being
written without clutter; but it's widely admitted that it's easier to
do in Factor than it is in Forth. Surely there's more progress to be
made beyond what Factor's done already!
> John Carter
-Wm
Justin — 2011-01-31 05:11:03
--- In
concatenative@yahoogroups.com, John Carter <john.carter@...> wrote:
>
> On Mon, Jan 31, 2011 at 1:20 PM, Justin <zallambo@...> wrote:
>
> > Hello. Is this forum still alive? I haven't shown my head here for a couple
> > of years. I'm a MA/CS major with an ongoing interest in giving concatenative
> > languages a firmer mathematical foundation. I have a few partial results:
> > (i) an operational semantics, (ii) a concept of & application for
> > homomorphisms, (iii) a type system. Is anyone else around here interested in
> > this sort of research? Here's a link to my (ongoing) work,
> >
> > http://dl.dropbox.com/u/17328602/concat/index.html
> >
> >
>
> What may be interesting and useful would be to return to typed variables
> (named values variety) and something like a SQL "natural join".
I don't know what you mean. Could you give an example? (I don't have a good mental model of databases.)
> 99% of the time which function result variable, needs to be bound which
> input variable, is obvious and can be automatically inferred from their type
> and name.
>
> By making the rules for doing this explicit, you should be able to create a
> concatenative language that doesn't involve the notion of a stack, nor are
> the program fragments cluttered with irrelavent variable name references or
> stack manipulation "fluff".
>
> I would argue that any language where the function definitions are cluttered
> with stack manipulations OR variable references has NOT yet met the full
> promise of concatenative languages.
I am aware of three methods of passing data around:
1. stack manipulation
2. variable references (the stateful kind)
3. implicit state (think of the flags register in assembly)
We can probably agree that (3) is usually a bad idea. Are there other methods? What else could a concatenative language do?
Justin — 2011-01-31 05:10:59
--- In
concatenative@yahoogroups.com, "William Tanksley, Jr" <wtanksleyjr@...> wrote:
>
> John Carter <john.carter@...> wrote:
> > Justin <zallambo@...> wrote:
>
> That's what I think of, yes -- minus the word "sugar". Not all syntax
> is "syntactic sugar". A language might be defined as "the mapping of
> syntax onto semantics"; thus, language design is concerned with
> defining syntax, semantics, and the mapping between them. Words like
> "syntax sugar" encourage a disregard for one of those crucial three
> components of language design.
I don't understand what you mean. Syntactic sugar is syntax that can be easily explained in terms of other syntax. It says, "rather than give you a mapping from 'for loop' syntax to semantics, I'm going to give you a mapping from 'for loop' syntax to 'while loop' syntax, and then you can use the mapping from 'while loop' syntax to semantics". What's wrong with that?
> Possibly true. I'd love to see this explored; it does seem that the
> "stack" is not _necessary_ to the idea of a concatenative language.
Indeed, my operational semantics does not involve a stack.
> > I would argue that any language where the function definitions are cluttered
> > with stack manipulations OR variable references has NOT yet met the full
> > promise of concatenative languages.
>
> I know what you mean. Forth, Joy, and Factor are all capable of being
> written without clutter; but it's widely admitted that it's easier to
> do in Factor than it is in Forth.
Why would you say that is? I know it allows both stack manipulation and variables; is this a potent combination, or is something else at work?
William Tanksley, Jr — 2011-01-31 16:34:06
Justin <
zallambo@...> wrote:
>"William Tanksley, Jr" <wtanksleyjr@...> wrote:
>> John Carter <john.carter@...> wrote:
>> > Justin <zallambo@...> wrote:
>> That's what I think of, yes -- minus the word "sugar". Not all syntax
>> is "syntactic sugar". A language might be defined as "the mapping of
>> syntax onto semantics"; thus, language design is concerned with
>> defining syntax, semantics, and the mapping between them. Words like
>> "syntax sugar" encourage a disregard for one of those crucial three
>> components of language design.
> I don't understand what you mean. Syntactic sugar is syntax that can be easily explained in terms of other syntax. [...] What's wrong with that?
I didn't mean to imply that "syntactic sugar" should never be used,
sorry. I meant that it's entirely inappropriate in the use to which I
was replying. A concatenative language is, by definition, a language
in which syntactic concatenation is the primary means of expressing
composition. If there are other means (and there need not be), they
are the syntactic sugar;concatenation is not.
>> Possibly true. I'd love to see this explored; it does seem that the
>> "stack" is not _necessary_ to the idea of a concatenative language.
> Indeed, my operational semantics does not involve a stack.
There's no profound reason why it needs to; my friend wrote a very
simple code generator that used registers for the top stack items.
However, using something other than a stack means that the behavior of
the language is different; your operational semantics would be
different.
>> I know what you mean. Forth, Joy, and Factor are all capable of being
>> written without clutter; but it's widely admitted that it's easier to
>> do in Factor than it is in Forth.
> Why would you say that is? I know it allows both stack manipulation and variables; is this a potent combination, or is something else at work?
Something else. (Forth also has both.)
Factor also has the cleave/spread combinators. From
http://factor-language.blogspot.com/2008/03/inheritance-tuple-reshaping-cleavers.html:
"These combinators help structure your data flow by grouping parts of
computations into one-to-many, many-to-many and many-to-one designs."
... "For example, I recently converted our serialization library to
use these combinators. The result is extremely straightforward: there
is almost no stack manipulation, except for the occasional dup and
drop, but it doesn't use named locals either. Thanks to the cleave
combinators, all values just happen to be in the right place at the
right time, and everything composes together very nicely, like lego
bricks."
-Wm
William Tanksley, Jr — 2011-01-31 20:08:26
Justin <
zallambo@...> wrote:
>John Carter <john.carter@...> wrote:
>> What may be interesting and useful would be to return to typed variables
>> (named values variety) and something like a SQL "natural join".
> I don't know what you mean. Could you give an example? (I don't have a
> good mental model of databases.)
I'm not certain, but I assumed he was implying that the compiler would
somehow just figure things out. It's hand-waving, but he admits it
hasn't been done yet.
> I am aware of three methods of passing data around:
> 1. stack manipulation
> 2. variable references (the stateful kind)
> 3. implicit state (think of the flags register in assembly)
> We can probably agree that (3) is usually a bad idea. Are there other methods? What else could a concatenative language do?
One can also pass data around in data structures; explicit ones, as
with Joy's lists; semi-implicit ones, as in Joy's 'dip' combinator;
and implicit ones, as in Forth's global dictionary. XY (one of Apter's
languages) adds a queue structure to represent source evaluation. It's
conceivable that some other structure could replace the stack, rather
than simply augmenting it.
A "language" which did nothing but join strings into one big string
would be concatenative in syntax and compositional in semantics,
although very boring in behavior -- and would replace the stack with a
string.
-Wm
Justin — 2011-01-31 23:36:11
--- In
concatenative@yahoogroups.com, "William Tanksley, Jr" <wtanksleyjr@...> wrote:
>
> Justin <zallambo@...> wrote:
> >"William Tanksley, Jr" <wtanksleyjr@> wrote:
> I didn't mean to imply that "syntactic sugar" should never be used,
> sorry. I meant that it's entirely inappropriate in the use to which I
> was replying. A concatenative language is, by definition, a language
> in which syntactic concatenation is the primary means of expressing
> composition. If there are other means (and there need not be), they
> are the syntactic sugar;concatenation is not.
I see now; you are certainly right.
> >> Possibly true. I'd love to see this explored; it does seem that the
> >> "stack" is not _necessary_ to the idea of a concatenative language.
> > Indeed, my operational semantics does not involve a stack.
>
> There's no profound reason why it needs to; my friend wrote a very
> simple code generator that used registers for the top stack items.
> However, using something other than a stack means that the behavior of
> the language is different; your operational semantics would be
> different.
All I mean to say is that my operational semantics is general enough that it's completely ambivalent as to what kind of states a language's programs act on. There is no mention of stacks -- only states, which could be anything.
http://dl.dropbox.com/u/17328602/concat/theory/concat.pdf
> >> I know what you mean. Forth, Joy, and Factor are all capable of being
> >> written without clutter; but it's widely admitted that it's easier to
> >> do in Factor than it is in Forth.
> > Why would you say that is? I know it allows both stack manipulation and variables; is this a potent combination, or is something else at work?
>
> Something else. (Forth also has both.)
>
> Factor also has the cleave/spread combinators. From
> http://factor-language.blogspot.com/2008/03/inheritance-tuple-reshaping-cleavers.html:
>
> "These combinators help structure your data flow by grouping parts of
> computations into one-to-many, many-to-many and many-to-one designs."
> ... "For example, I recently converted our serialization library to
> use these combinators. The result is extremely straightforward: there
> is almost no stack manipulation, except for the occasional dup and
> drop, but it doesn't use named locals either. Thanks to the cleave
> combinators, all values just happen to be in the right place at the
> right time, and everything composes together very nicely, like lego
> bricks."
I remember seeing references to 'cleave' and 'spread' but never knew what they were. They seem to be elegant tools; thanks for pointing them out.
William Tanksley, Jr — 2011-02-01 00:31:11
Justin <
zallambo@...> wrote:
> "William Tanksley, Jr" <wtanksleyjr@...> wrote:
>> Justin <zallambo@...> wrote:
>> >> Possibly true. I'd love to see this explored; it does seem that the
>> >> "stack" is not _necessary_ to the idea of a concatenative language.
>> > Indeed, my operational semantics does not involve a stack.
>> There's no profound reason why it needs to; my friend wrote a very
>> simple code generator that used registers for the top stack items.
>> However, using something other than a stack means that the behavior of
>> the language is different; your operational semantics would be
>> different.
> All I mean to say is that my operational semantics is general enough that it's
> completely ambivalent as to what kind of states a language's programs act
> on. There is no mention of stacks -- only states, which could be anything.
Yes, you're right. I don't know whether your study makes any
stack-oriented assumptions later, but it doesn't make them in its
opening sections.
It may be that there's something special about a stack when it comes
to the primary data transfer mechanism for a Turing-complete
concatenative model. I don't know, and I'd like to.
>> Factor also has the cleave/spread combinators. From
>> http://factor-language.blogspot.com/2008/03/inheritance-tuple-reshaping-cleavers.html:
>> "These combinators help structure your data flow by grouping parts of
>> computations into one-to-many, many-to-many and many-to-one designs."
> I remember seeing references to 'cleave' and 'spread' but never knew what they were. They seem to be elegant tools; thanks for pointing them out.
Indeed, and like all elegant tools, they are from a more civilized
age. They were invented by Backus for FP and FL, the languages that
gave us the term "functional languages", although none of their
immediate successors met their definition of being functional
languages.
-Wm
Justin — 2011-02-02 02:25:16
--- In
concatenative@yahoogroups.com, "William Tanksley, Jr" <wtanksleyjr@...> wrote:
> Indeed, and like all elegant tools, they are from a more civilized
> age. They were invented by Backus for FP and FL, the languages that
> gave us the term "functional languages", although none of their
> immediate successors met their definition of being functional
> languages.
I never fail to be surprised by how much computer science theory was developed before I was born.
Don Groves — 2011-02-02 04:17:23
"It's been a long, strange trip" applies to both The Grateful Dead and Computer Science theory.
--
don
On 1 Feb 2011, at 18:25, Justin wrote:
>
> --- In concatenative@yahoogroups.com, "William Tanksley, Jr" <wtanksleyjr@...> wrote:
> > Indeed, and like all elegant tools, they are from a more civilized
> > age. They were invented by Backus for FP and FL, the languages that
> > gave us the term "functional languages", although none of their
> > immediate successors met their definition of being functional
> > languages.
>
> I never fail to be surprised by how much computer science theory was developed before I was born.
>
>
[Non-text portions of this message have been removed]