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]