Why is point-free form so interesting?
Christopher Diggins — 2007-06-16 19:02:18
I have been struggling to formalize/rationalize my intuition that
point-free form is somehow better than a form with names from the
standpoint of tools (e.g. analyzers, compilers, translators,
optimizers, etc.). Note: this is completely separate from any
statements about the usability of point-free form for programmers.
That is a controversial idea that I would rather avoid debating (I
have nothing useful to add to that debate anyway)
Here are some bullet points that describe what I percieve to be the
main advantages of point-free form:
- less ambiguity (is foo a parameter or definition?)
- fewer evaluation rules (no alpha-conversion, no beta-conversion)
- flat structure versus tree
- maps more nicely to imperative programs: semi-colon (or in some
languages newline, and sometimes comma) is essentially a composition
operator
- syntactic analysis can be performed on tokens rather than parse tree
- fewer parantheses: all interesting computations are compositions,
rather than applications.
- ease of transformation
- rewriting rules are fundamentally easier (linear as opposed to trees)
Any other additions to this list, corrections, or clarifications would
be much appreciated!
One question is: can we reasonably claim with any formality that a
linear form is somehow easier to work with than a tree?
Cheers,
Christopher
http://cdiggins.com
William Tanksley, Jr — 2007-06-18 17:08:38
Christopher Diggins <
cdiggins@...> wrote:
> I have been struggling to formalize/rationalize my intuition that
> point-free form is somehow better than a form with names from the
> standpoint of tools (e.g. analyzers, compilers, translators,
> optimizers, etc.). Note: this is completely separate from any
Most of your points are good, but a few are specific to concatenative languages.
> - fewer evaluation rules (no alpha-conversion, no beta-conversion)
Just a side note: I think this one's the root of the coolness for
point-free languages. Because there are no parameter names, there's no
need for an approximate mathematical model of how the data gets from
the call site to where it's used in the function's body.
Digression: One of the few depressing things about reading SICP was,
to me, how hard a time they had explaining exactly how parameters
worked. If you haven't read SICP and you're interested in computer
science and languages, the best time to start reading it is a year
ago; the second best time is right now.
http://mitpress.mit.edu/sicp/
(free online)
Anyhow, another result of point-free notation (implied by your point
about beta-conversion) is that because data isn't ever given different
names, there's no name change required when you inline or extract a
function. Your code is truly referentially transparent.
A positive result of dataflow notation (which I'm almost convinced is
the same thing as point-free notation -- I could be wrong) is that the
complexity of the dataflow is directly reflected in the complexity of
the code. Named data, on the other hand, can hide almost arbitrarily
complex dataflow. And dataflow directly impacts performance, if
nothing else by using resources like registers, cache lines, physical
memory, and paging. So clean-looking dataflow code is fast code.
> - flat structure versus tree
> - syntactic analysis can be performed on tokens rather than parse tree
> - fewer parantheses: all interesting computations are compositions,
> rather than applications.
> - rewriting rules are fundamentally easier (linear as opposed to trees)
These are all specific to concatenative languages (well, only *flat*
languages have them perfectly, but close enough).
> One question is: can we reasonably claim with any formality that a
> linear form is somehow easier to work with than a tree?
I don't see why not. It's a simpler data structure. It seems certain
that it should be "somehow" easier to work with. (Make that claim
stronger and I'll have to work harder proving it. ;-)
> Christopher
-Billy
John Carter — 2007-07-10 04:26:49
On Sat, 16 Jun 2007, Christopher Diggins wrote:
> I have been struggling to formalize/rationalize my intuition that
> point-free form is somehow better than a form with names from the
> standpoint of tools (e.g. analyzers, compilers, translators,
> optimizers, etc.).
Probably because the pros and cons are symmetrical...
ie.
The Good thing about point free form is the mechanism for getting from
parameters to using them in expressions is explicit.
ie. You know exactly how the magic happens.
The Bad thing about point free form is the mechanism for getting from
parameters to using them in expressions is explicit.
ie. You know exactly how the magic happens....but you're almost sure
you don't care as any other mechanism should still give the same
answer and it's presence is just noise not signal.
As usual Christopher is asking a valuable question...
...perhaps we can rephrase it...
Is there a representation of a program where the mechanism of moving
parameters to values in expressions is...
* Explicit (ie. Can be reasoned about / transparent on inlining)
* Trivial (Adds almost nothing to the code / vanishes in this representation)?
John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email :
john.carter@...
New Zealand
William Tanksley, Jr — 2007-07-10 14:18:33
John Carter <
john.carter@...> wrote:
> Christopher Diggins wrote:
> Is there a representation of a program where the mechanism of moving
> parameters to values in expressions is...
> * Explicit (ie. Can be reasoned about / transparent on inlining)
> * Trivial (Adds almost nothing to the code / vanishes in
> this representation)?
Not in general. If the data transport mechanism is explicit, then the
written data transport will vanish only when the data transport needs
are simple in the given notation.
Stack notation is NOT the simplest possible data transfer notation; it
imposes a total ordering on data, when often a partial ordering is
sufficient. Adding support for arrays helps a lot; Ripple's support
for simultaneous return values is another interesting experiment in
this area.
So there's plenty of research to be done on this topic.
I will add that although in general explicit data transfer can't
vanish, it's sometimes (often?) the case that it can be made simpler.
> John Carter Phone : (64)(3) 358 6639
-Billy
stevan apter — 2007-07-10 15:37:42
for clarity, nothing beats a 2-d notation with peirce's "lines
of identity" connecting input and output. for example, consider
some set of functions f ... each having n arguments and returning
m results, and suppose that the f's are arranged in some call
tree. so f calls g with two arguments, which returns three,
two of which go to h and one to i, each of which returns a
single result, both of which go to j, which returns two results.
in a k-like syntax for lambdas, something like
f:{
[a;b;c]:g[x;y]
[d;e]:j[h[a;c];i[b]]
}
now on a sheet of paper, write down g, h, i, and j in any
orientation with slots for arguments and results:
_ _ _ g _ _
h _ _ i _
_ _ j _ _
now draw lines connecting inputs and outputs (i won't attempt
that here!)
if any of the functions have "internal structure", replace the
name of the function with a similar graph. (extra credit:
how do you diagram recursion?)
death to linear notation -- long live the diagram!
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Tuesday, July 10, 2007 9:18 AM
Subject: Re: [stack] Why is point-free form so interesting?
> John Carter <john.carter@...> wrote:
> > Christopher Diggins wrote:
> > Is there a representation of a program where the mechanism of moving
> > parameters to values in expressions is...
> > * Explicit (ie. Can be reasoned about / transparent on inlining)
> > * Trivial (Adds almost nothing to the code / vanishes in
> > this representation)?
>
> Not in general. If the data transport mechanism is explicit, then the
> written data transport will vanish only when the data transport needs
> are simple in the given notation.
>
> Stack notation is NOT the simplest possible data transfer notation; it
> imposes a total ordering on data, when often a partial ordering is
> sufficient. Adding support for arrays helps a lot; Ripple's support
> for simultaneous return values is another interesting experiment in
> this area.
>
> So there's plenty of research to be done on this topic.
>
> I will add that although in general explicit data transfer can't
> vanish, it's sometimes (often?) the case that it can be made simpler.
>
> > John Carter Phone : (64)(3) 358 6639
>
> -Billy
>
John Carter — 2007-07-12 01:23:18
On Tue, 10 Jul 2007, William Tanksley, Jr wrote:
> John Carter <john.carter@...> wrote:
>> Christopher Diggins wrote:
>> Is there a representation of a program where the mechanism of moving
>> parameters to values in expressions is...
>> * Explicit (ie. Can be reasoned about / transparent on inlining)
>> * Trivial (Adds almost nothing to the code / vanishes in
>> this representation)?
> Stack notation is NOT the simplest possible data transfer notation; it
> imposes a total ordering on data, when often a partial ordering is
> sufficient.
Any pointers to candidates for the "simplest possible data transfer notation"?
John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email :
john.carter@...
New Zealand
William Tanksley, Jr — 2007-07-13 14:30:36
John Carter <
john.carter@...> wrote:
> William Tanksley, Jr wrote:
> > Stack notation is NOT the simplest possible data transfer notation; it
> > imposes a total ordering on data, when often a partial ordering is
> > sufficient.
> Any pointers to candidates for the "simplest possible data
> transfer notation"?
None aside from the clue I just gave. I don't think it exists ... yet
..., and I don't know how to build it.
I have a vague suspicion that it'll involve a combination of stack and
array notation: the stack notation provides the ordering, and the
array notation allows you to align elements of equal importance at
identical level. Oh, I'm also impressed by Ripple's ability to handle
multiple return values by essentially splitting control flow.
> John Carter
-Billy
Christopher Diggins — 2007-07-13 17:04:18
On 7/10/07, William Tanksley, Jr <
wtanksleyjr@...> wrote:
> John Carter <john.carter@...> wrote:
> > Christopher Diggins wrote:
> > Is there a representation of a program where the mechanism of moving
> > parameters to values in expressions is...
> > * Explicit (ie. Can be reasoned about / transparent on inlining)
> > * Trivial (Adds almost nothing to the code / vanishes in
> > this representation)?
>
> Not in general. If the data transport mechanism is explicit, then the
> written data transport will vanish only when the data transport needs
> are simple in the given notation.
>
> Stack notation is NOT the simplest possible data transfer notation; it
> imposes a total ordering on data, when often a partial ordering is
> sufficient.
This is an interesting point. Specifying an ordering where non is
intended, I believe can be considered to be simpler than
differentiating between the two. Many programming languages don't even
bother allowing people to specify unordered data because it would
introduce new constructs, operations, or representations into their
language, thus increasing complexity.
- Christopher
Christopher Diggins — 2007-07-13 16:59:55
This is an approach which I am unfamiliar with, and it does appear to be
very powerful.
Thanks for sharing it!
On 7/10/07, stevan apter <sa@...> wrote:
>
> for clarity, nothing beats a 2-d notation with peirce's "lines
> of identity" connecting input and output. for example, consider
> some set of functions f ... each having n arguments and returning
> m results, and suppose that the f's are arranged in some call
> tree. so f calls g with two arguments, which returns three,
> two of which go to h and one to i, each of which returns a
> single result, both of which go to j, which returns two results.
> in a k-like syntax for lambdas, something like
>
> f:{
> [a;b;c]:g[x;y]
> [d;e]:j[h[a;c];i[b]]
> }
>
> now on a sheet of paper, write down g, h, i, and j in any
> orientation with slots for arguments and results:
>
> _ _ _ g _ _
>
> h _ _ i _
>
> _ _ j _ _
>
> now draw lines connecting inputs and outputs (i won't attempt
> that here!)
>
> if any of the functions have "internal structure", replace the
> name of the function with a similar graph. (extra credit:
> how do you diagram recursion?)
>
> death to linear notation -- long live the diagram!
>
>
> ----- Original Message -----
> From: "William Tanksley, Jr" <wtanksleyjr@...<wtanksleyjr%40gmail.com>
> >
> To: <concatenative@yahoogroups.com <concatenative%40yahoogroups.com>>
> Sent: Tuesday, July 10, 2007 9:18 AM
> Subject: Re: [stack] Why is point-free form so interesting?
>
> > John Carter <john.carter@... <john.carter%40tait.co.nz>> wrote:
> > > Christopher Diggins wrote:
> > > Is there a representation of a program where the mechanism of moving
> > > parameters to values in expressions is...
> > > * Explicit (ie. Can be reasoned about / transparent on inlining)
> > > * Trivial (Adds almost nothing to the code / vanishes in
> > > this representation)?
> >
> > Not in general. If the data transport mechanism is explicit, then the
> > written data transport will vanish only when the data transport needs
> > are simple in the given notation.
> >
> > Stack notation is NOT the simplest possible data transfer notation; it
> > imposes a total ordering on data, when often a partial ordering is
> > sufficient. Adding support for arrays helps a lot; Ripple's support
> > for simultaneous return values is another interesting experiment in
> > this area.
> >
> > So there's plenty of research to be done on this topic.
> >
> > I will add that although in general explicit data transfer can't
> > vanish, it's sometimes (often?) the case that it can be made simpler.
> >
> > > John Carter Phone : (64)(3) 358 6639
> >
> > -Billy
> >
>
>
>
[Non-text portions of this message have been removed]
Christopher Diggins — 2007-07-13 17:20:04
On 7/9/07, John Carter <
john.carter@...> wrote:
> On Sat, 16 Jun 2007, Christopher Diggins wrote:
>
> > I have been struggling to formalize/rationalize my intuition that
> > point-free form is somehow better than a form with names from the
> > standpoint of tools (e.g. analyzers, compilers, translators,
> > optimizers, etc.).
>
> Probably because the pros and cons are symmetrical...
>
> ie.
>
> The Good thing about point free form is the mechanism for getting from
> parameters to using them in expressions is explicit.
>
> ie. You know exactly how the magic happens.
>
> The Bad thing about point free form is the mechanism for getting from
> parameters to using them in expressions is explicit.
>
> ie. You know exactly how the magic happens....but you're almost sure
> you don't care as any other mechanism should still give the same
> answer and it's presence is just noise not signal.
>
> As usual Christopher is asking a valuable question...
Thank you.
> ...perhaps we can rephrase it...
>
> Is there a representation of a program where the mechanism of moving
> parameters to values in expressions is...
> * Explicit (ie. Can be reasoned about / transparent on inlining)
> * Trivial (Adds almost nothing to the code / vanishes in this representation)?
I like this a lot. This does a good job of summing up what I like
about point-free form very elegantly. One point though, is "explicit"
the correct term? I would normally consider argument passing in a
stack-language to be implicit, rather than explicit. However I agree
that it is obvious and unambiguous.
Some other bullet points concerning what I like about point-free form
(I've just brainstormed these and expect that they can be refined):
- data transfer is obvious
- data transfer is automatic
- function forms are uniform (stack -> stack)
- order of evaluation is simple and unambiguous: left to right (no
precedence rules)
- subterms can be evaluated concurrently
Cheers,
Christopher
William Tanksley, Jr — 2007-07-13 17:32:04
Christopher Diggins <
cdiggins@...> wrote:
> William Tanksley, Jr <wtanksleyjr@...> wrote:
> > Stack notation is NOT the simplest possible data transfer notation; it
> > imposes a total ordering on data, when often a partial ordering is
> > sufficient.
> This is an interesting point. Specifying an ordering where non is
> intended, I believe can be considered to be simpler than
> differentiating between the two. Many programming languages don't even
> bother allowing people to specify unordered data because it would
> introduce new constructs, operations, or representations into their
> language, thus increasing complexity.
You're right that it would increase grammar complexity (although
perhaps it would coincidentally remove some other aspect of the
grammar; I don't know). But such a thing should decrease program
complexity; some stack rearrangements would definitely go away.
> - Christopher
-Billy
William Tanksley, Jr — 2007-07-13 17:37:04
Christopher Diggins <
cdiggins@...> wrote:
> John Carter <john.carter@...> wrote:
> > Is there a representation of a program where the mechanism of moving
> > parameters to values in expressions is...
> > * Explicit (ie. Can be reasoned about / transparent on inlining)
> I like this a lot. This does a good job of summing up what I like
> about point-free form very elegantly. One point though, is "explicit"
> the correct term? I would normally consider argument passing in a
> stack-language to be implicit, rather than explicit. However I agree
> that it is obvious and unambiguous.
Actually, I think John made a mistake in another word: the mechanism
for moving _values_ from source to consumption is explicit. You're not
moving "parameters", nor are they being moved to "values". But yes,
the mechanism is explicit.
And also, yes, you're right that parameter passing is (in some sense) implicit.
> - order of evaluation is simple and unambiguous: left to right (no
> precedence rules)
> - subterms can be evaluated concurrently
Aren't these contradictory?
> Christopher
-Billy
John Carter — 2007-07-16 01:34:36
On Fri, 13 Jul 2007, Christopher Diggins wrote:
> On 7/10/07, William Tanksley, Jr <wtanksleyjr@...> wrote:
>> John Carter <john.carter@...> wrote:
>>> Christopher Diggins wrote:
>>> Is there a representation of a program where the mechanism of moving
>>> parameters to values in expressions is...
>>> * Explicit (ie. Can be reasoned about / transparent on inlining)
>>> * Trivial (Adds almost nothing to the code / vanishes in
>>> this representation)?
>> >snip<
>> Stack notation is NOT the simplest possible data transfer notation; it
>> imposes a total ordering on data, when often a partial ordering is
>> sufficient.
>
> This is an interesting point. Specifying an ordering where non is
> intended.
>snip<
> Many programming languages don't even bother allowing people to
> specify unordered data because it would introduce new constructs,
> operations, or representations into their language, thus increasing
> complexity.
Aha! Here we have the meat of it.
Yes, having an unorder data type is implementationwise more complex,
but semantically simpler.
I suspect "unordered set" needs to be a (or the) primitive.
Arrays and lists are a premature optimization that make reasoning
about the langauge harder as they add spurious information that has to
be dealt with.
Parameters probably should be a set, and a binding should be a map (an
unordered set of pairs).
John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email :
john.carter@...
New Zealand
Manfred Von Thun — 2007-07-16 08:26:24
On 16/7/07 11:34 AM, "John Carter" <
john.carter@...> wrote
> On Fri, 13 Jul 2007, Christopher Diggins wrote:
>
>> > snip< Many programming languages don't even bother allowing people to
>> specify
>> > unordered data because it would introduce new constructs, operations, or
>> > representations into their language, thus increasing complexity.
>> >
> Aha! Here we have the meat of it.
>
> Yes, having an unorder data type is implementationwise more complex, but
> semantically simpler.
>
> I suspect "unordered set" needs to be a (or the) primitive.
>
> Arrays and lists are a premature optimization that make reasoning about the
> langauge harder as they add spurious information that has to be dealt with.
>
> Parameters probably should be a set, and a binding should be a map (an
> unordered set of pairs).
>
One criticism of Joy has been that because there are no names for formal
parameters inside the definitions of functions, there has to be an arbitrary
ordering of the actual parameters which the definition of the function has
to know about. If the formal parameters are named, as in f(x,y,z) = ... then
the body ... of the definition does not have to know the order of the
formals. My response was that the caller of the function needs to know the
order (x,y,z) of the formals in the head of the definition so that the
actual parameters, say (a+b, c, d*e) are given in the appropriate order. In
Joy at least the actual parameters in a call and the formal parameters in
the definition are in exactly the same order.
I one wanted a language in which there is no arbitrary order, with names for
the formals in the definition, then these names should also be used in the
calls. So instead of writing f(a+b,c,d*e), one could write any of the
following: f(x=a+b,y=c,z=d*e), or f(z=d*e),x=a+b,y=c) or f(y=b,z=d*e,x=a+b)
or ... a total of 6 entirely equivalent ways. The same freedom already holds
for the formals in the head of the definition.
I believe Ada and Common Lisp allow such a notation. Another example are the
unix shells sh, csh and their variants. Here the parameters for the
utilities have useful and obvious default values. So beginners can use the
defaults for a long time without even knowing that this is what they are
doing. Only later they learn that one can override the default values by
explicitly giving alternative values. If one wants to give explicit values
to
all parameter, then one can do that in any order.
So we seem to have two extremes: The languages of the previous paragraph,
and the concatenative languages. In the middle are those notations used by
most programming languages.
- Manfred
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2007-07-16 15:06:39
John Carter <
john.carter@...> wrote:
> Christopher Diggins wrote:
> > William Tanksley, Jr <wtanksleyjr@...> wrote:
> >> Stack notation is NOT the simplest possible data transfer notation; it
> >> imposes a total ordering on data, when often a partial ordering is
> >> sufficient.
> > Many programming languages don't even bother allowing people to
> > specify unordered data because it would introduce new constructs,
> > operations, or representations into their language, thus increasing
> > complexity.
> Yes, having an unorder data type is implementationwise more complex,
> but semantically simpler.
Actually, an ordered data *type* is simpler in every way. But we
weren't talking about data types; we were talking about the ability to
specify dataflow. Stack-based concatenative languages completely order
their dataflow. Applicative functional languages leave their dataflow
entirely implicit. Explicit dataflow is good, but for most programs
there really isn't a total ordering of dataflows; inventing one in
order to manipulate a parameter stack is unpleasant and unnecessary.
I don't have a solution, although I can see several possible partial
solutions. (I don't know.) Array languages allow you to perform
dataflow over several chunks of data at identical stack level; Ripple
allows you to return several results at the same stack level. Both are
promising approaches.
> I suspect "unordered set" needs to be a (or the) primitive.
The problem with that is that you have to develop a concept of
identity before you can build a set. An ordered list doesn't require
identity.
But there are interesting results to be gained from a multiset. Hmm,
let me check Zotero...
http://web.maths.unsw.edu.au/~norman/papers.htm has (at the end) an
interesting paper on recasting set theory in terms of multisets and
arrays. IMO worth checking out.
There are some other papers on the same site on the author's
rebuilding of trigonometry along purely algebraic lines (i.e. without
sin, cos, or tan). Very interesting results. Some of the more
technical papers are on that page; another page elsewhere has a few
chapters excerpted from his book.
But I digress.
> Parameters probably should be a set, and a binding should be a map (an
> unordered set of pairs).
You're in the wrong discussion group -- concatenative languages don't
have parameters as such :-).
> John Carter Phone : (64)(3) 358 6639
-Billy
Christopher Diggins — 2007-07-16 16:30:17
On 7/13/07, William Tanksley, Jr <
wtanksleyjr@...> wrote:
> Christopher Diggins <cdiggins@...> wrote:
> > John Carter < john.carter@...> wrote:
> > > Is there a representation of a program where the mechanism of moving
> > > parameters to values in expressions is...
> > > * Explicit (ie. Can be reasoned about / transparent on inlining)
>
> > I like this a lot. This does a good job of summing up what I like
> > about point-free form very elegantly. One point though, is "explicit"
> > the correct term? I would normally consider argument passing in a
> > stack-language to be implicit, rather than explicit. However I agree
> > that it is obvious and unambiguous.
>
> Actually, I think John made a mistake in another word: the mechanism
> for moving _values_ from source to consumption is explicit. You're not
> moving "parameters", nor are they being moved to "values". But yes,
> the mechanism is explicit.
>
> And also, yes, you're right that parameter passing is (in some sense) implicit.
>
> > - order of evaluation is simple and unambiguous: left to right (no
> > precedence rules)
> > - subterms can be evaluated concurrently
>
> Aren't these contradictory?
I'm simply doing a poor job of saying what I mean.
What I was trying to say is that composition is always left-right, but
that subterms could be evaluated separately and in any order. IOW:
t = a b c d
== ((a b) (c d))
== ((a b) c) d)
- Christopher
William Tanksley, Jr — 2007-07-16 17:46:18
Christopher Diggins <
cdiggins@...> wrote:
> What I was trying to say is that composition is always left-right, but
> that subterms could be evaluated separately and in any order. IOW:
> t = a b c d
> == ((a b) (c d))
> == ((a b) c) d)
Yes, you're right. The missing definition is what a "subterm" is.
Unlike most languages, a subterm is not a grammatical concept; it's
defined semantically, based on which (grammatically) adjacent words
depend on each other.
> - Christopher
-Billy
John Carter — 2007-07-16 22:52:57
There is a lot else in your response worth reading and perhaps
commenting on...
But I couldn't resist a quickie...
On Mon, 16 Jul 2007, William Tanksley, Jr wrote:
>> Parameters probably should be a set, and a binding should be a map (an
>> unordered set of pairs).
>
> You're in the wrong discussion group -- concatenative languages don't
> have parameters as such :-).
The essence of the point under discussion is that this _is_ the Right Group....
Concatenative languages represent function composition by string
concatenation resulting in a great simplification in terms of
algebraic rewriting of programs.
We want to retain and if at all possible, enhance that advantage.
The point under discussion is representing parameter passing as stack
operations creates a burden that seems superfluous.
The implementation is getting in the way of reasoning about the semantics.
The question is can we retain functional composition is represented by
string concatenation whilst choosing a logically simpler (but
implementationwise more complex) representation of parameter passing?
John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email : john.carter@...
New Zealand
William Tanksley, Jr — 2007-07-17 14:57:23
John Carter <
john.carter@...> wrote:
> William Tanksley, Jr wrote:
> >> Parameters probably should be a set, and a binding should be a map (an
> >> unordered set of pairs).
> > You're in the wrong discussion group -- concatenative languages don't
> > have parameters as such :-).
> The essence of the point under discussion is that this _is_ the
> Right Group....
Yes, and furthermore, I meant that as a light toss-off joke. I also
intended to discuss the issue further, and forgot to. My mistake; I
made it look like I was dismissing your point. In fact, I did -- and
that wasn't my intention.
> The point under discussion is representing parameter passing as stack
> operations creates a burden that seems superfluous.
Correct.
> The question is can we retain functional composition is represented by
> string concatenation whilst choosing a logically simpler (but
> implementationwise more complex) representation of parameter passing?
Stevan's method (classical visual programming) works... But is rarely used.
http://en.wikipedia.org/wiki/Visual_programming_language
Named parameters lose dataflow -- or at least they CAN. Maybe there
are rules to prevent that?
Array dataflow languages are perhaps our best bet. But not any of the
existing ones, I think. I speculate that we want a stack language with
a very powerful array-building (or multiset-building) sublanguage, so
that independent dataflows can be elegantly gathered together into a
single stack element.
Okay, that's wild speculation. I really don't know. Some experiments
are taking shape in my head... I'll have to write these things down
and see what comes of them.
> John Carter Phone : (64)(3) 358 6639
-Billy
John Carter — 2007-07-17 21:14:30
On Tue, 17 Jul 2007, William Tanksley, Jr wrote:
> Array dataflow languages are perhaps our best bet. But not any of the
> existing ones, I think. I speculate that we want a stack language with
> a very powerful array-building (or multiset-building) sublanguage, so
> that independent dataflows can be elegantly gathered together into a
> single stack element.
Do you have some URL's for those languages? I can't seem to lay my
Googly fingers on them.
> Okay, that's wild speculation. I really don't know. Some experiments
> are taking shape in my head... I'll have to write these things down
> and see what comes of them.
I'm also brewing something that is looking fun.
I love these languages they are so simple, you can do profound changes
to the semantics and still make progress in short order.
John Carter Phone : (64)(3) 358 6639
Tait Electronics Fax : (64)(3) 359 4632
PO Box 1645 Christchurch Email :
john.carter@...
New Zealand
William Tanksley, Jr — 2007-07-17 22:24:16
John Carter <
john.carter@...> wrote:
> William Tanksley, Jr wrote:
> > Array dataflow languages are perhaps our best bet. But not any of the
> > existing ones, I think. I speculate that we want a stack language with
> > a very powerful array-building (or multiset-building) sublanguage, so
> > that independent dataflows can be elegantly gathered together into a
> > single stack element.
> Do you have some URL's for those languages? I can't seem to lay my
> Googly fingers on them.
NIAL is the open source one; APL, J, and K are to one extent or
another proprietary. I think K and NIAL are the best bets; J is good,
but K is more flexible with nested arrays.
http://www.nial.com/OpenSource.html
The manual is reasonably informative, although not as good as all the
J documentation.
None of them have multisets, which I'm starting to think may be
semantically important for true out-of-order dataflow. It's fine to
imagine that an array iteration is order-independent, but arrays are
actually ordered.
> I'm also brewing something that is looking fun.
You'll certainly beat me to the punch -- I'm about to start working on
earning a Master's degree for which my company surprised me with a
full scholarship (!).
But that's my excuse today. I didn't have that excuse a year ago, and
I've still managed to produce nothing :-(. :-)
> I love these languages they are so simple, you can do profound changes
> to the semantics and still make progress in short order.
Yes! It's also nice to be working in an almost untouched field (almost
every discovery is new), yet still with geniuses on whose shoulders to
stand.
> John Carter Phone : (64)(3) 358 6639
-Billy
stevan apter — 2007-07-18 14:56:05
i'm not following this.
a list has an order but you can ignore it.
in k at least, you can build a "map", e.g.
v:`x`y`z!10 20 10
so v.x = 10, v.y=20, &c. of course the components of v
are stored in *some* order, but the important point for
this discussion is that v is passed around as a unitary
whole and values are accessed by name. i believe that
linda behaves this way as well -- all functions are unary
taking and returning tuples. any language that has
association lists (symbol-value pairs) should give you
the same facility (lisp, &c.)
what am i missing?
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Tuesday, July 17, 2007 5:24 PM
Subject: Re: [stack] Why is point-free form so interesting?
> John Carter <john.carter@...> wrote:
> > William Tanksley, Jr wrote:
> > > Array dataflow languages are perhaps our best bet. But not any of the
> > > existing ones, I think. I speculate that we want a stack language with
> > > a very powerful array-building (or multiset-building) sublanguage, so
> > > that independent dataflows can be elegantly gathered together into a
> > > single stack element.
>
> > Do you have some URL's for those languages? I can't seem to lay my
> > Googly fingers on them.
>
> NIAL is the open source one; APL, J, and K are to one extent or
> another proprietary. I think K and NIAL are the best bets; J is good,
> but K is more flexible with nested arrays.
>
> http://www.nial.com/OpenSource.html
>
> The manual is reasonably informative, although not as good as all the
> J documentation.
>
> None of them have multisets, which I'm starting to think may be
> semantically important for true out-of-order dataflow. It's fine to
> imagine that an array iteration is order-independent, but arrays are
> actually ordered.
>
> > I'm also brewing something that is looking fun.
>
> You'll certainly beat me to the punch -- I'm about to start working on
> earning a Master's degree for which my company surprised me with a
> full scholarship (!).
>
> But that's my excuse today. I didn't have that excuse a year ago, and
> I've still managed to produce nothing :-(. :-)
>
> > I love these languages they are so simple, you can do profound changes
> > to the semantics and still make progress in short order.
>
> Yes! It's also nice to be working in an almost untouched field (almost
> every discovery is new), yet still with geniuses on whose shoulders to
> stand.
>
> > John Carter Phone : (64)(3) 358 6639
>
> -Billy
>
William Tanksley, Jr — 2007-07-18 14:45:06
stevan apter <
sa@...> wrote:
> William Tanksley, Jr wrote:
> > None of them have multisets, which I'm starting to think may be
> > semantically important for true out-of-order dataflow. It's fine to
> > imagine that an array iteration is order-independent, but arrays are
> > actually ordered.
> i'm not following this.
> a list has an order but you can ignore it.
Yes, but iteration over a list is ordered. That's the sort of minor
distinction that can wind up making a difference in a heavy
computation; especially since we're talking about a notation that's
supposed to clearly express the idea of unordered dataflows.
Perhaps I could define implicit iteration to be unordered; thus,
although the programmer is free (indeed, is required) to order arrays,
the runtime won't promise anything about how the arrays get unpacked
automatically.
There's a lot of possible implementations.
Of course, I'm not sure if my idea is a solution _at all_, so I'm a
little leery of getting too much into the details.
-Billy
stevan apter — 2007-07-18 16:26:31
----- Original Message -----
From: "William Tanksley, Jr" <wtanksleyjr@...>
To: <concatenative@yahoogroups.com>
Sent: Wednesday, July 18, 2007 9:45 AM
Subject: Re: [stack] Why is point-free form so interesting?
> stevan apter <sa@...> wrote:
> > William Tanksley, Jr wrote:
> > > None of them have multisets, which I'm starting to think may be
> > > semantically important for true out-of-order dataflow. It's fine to
> > > imagine that an array iteration is order-independent, but arrays are
> > > actually ordered.
> > i'm not following this.
> > a list has an order but you can ignore it.
>
> Yes, but iteration over a list is ordered. That's the sort of minor
> distinction that can wind up making a difference in a heavy
> computation; especially since we're talking about a notation that's
> supposed to clearly express the idea of unordered dataflows.
so then use association arrays or the equivalent, which cannot
be accessed by position, only by name or the equivalent. (of
course any implementation will order the symbol-value pairs in
some way, but who cares?)
>
> Perhaps I could define implicit iteration to be unordered; thus,
> although the programmer is free (indeed, is required) to order arrays,
> the runtime won't promise anything about how the arrays get unpacked
> automatically.
>
> There's a lot of possible implementations.
>
> Of course, I'm not sure if my idea is a solution _at all_, so I'm a
> little leery of getting too much into the details.
i've been wondering whether, instead of having 'set' and 'multiset'
datatypes, you have two types of characteristic function. a set cf
is a function f s.t. f x -> 1 iff x is in the set represented by
f, and f x -> n iff x occurs in the multiset n times. then implement
set-algebra with h.o.f.'s 'union', 'diff', etc. manfred?
>
> -Billy
>
William Tanksley, Jr — 2007-07-18 16:13:21
stevan apter <
sa@...> wrote:
> From: "William Tanksley, Jr" <wtanksleyjr@...>
> > stevan apter <sa@...> wrote:
> > > a list has an order but you can ignore it.
> > Yes, but iteration over a list is ordered. That's the sort of minor
> > distinction that can wind up making a difference in a heavy
> > computation; especially since we're talking about a notation that's
> > supposed to clearly express the idea of unordered dataflows.
> so then use association arrays or the equivalent, which cannot
> be accessed by position, only by name or the equivalent. (of
> course any implementation will order the symbol-value pairs in
> some way, but who cares?)
I suspect that this enters the realm of implementation details, about
which I don't think I'm concerned at the moment. I believe that I'm
actually worried about semantics.
And an idea has finally broken through to me. I'm going to stop
talking about multisets or data structures and just talk about
semantics.
What I actually want is the ability to declare that a number of data
items should appear as one for all stack shuffling and data processing
purposes -- yet they should both be processed. Let's consider the
simplest case, where we have two items. This implies that
semantically, the program behaves as though a new process was spawned
with the same stack as the parent EXCEPT the second-to-top item, while
the parent stack is missing the top item.
Practically, one probably wouldn't want to implement things that way
(I hope that most of the time the stack duplication and the thread
creation would be optimized away); but as a semantic model or a
quick-and-dirty implementation, I think it might work. It's kind of
like a classical generator (akin to Python's 'yield' statement),
except without any effect on control flow.
Now, back to talking about multisets. Another way to implement this
behavior would be to define a data structure which could contain any
number of items, and which, when accessed, would fork execution and
yield all the items in it, one per thread. Of course, alternately the
data structure could simply iterate over the items. The point is that
the code receiving the data structure in question is written to
receive a single item of the appropriate type -- there's no provision
for looping or parallelism; it's all implied by the data.
The reason I mentioned the classical array languages APL/J/K/NIAL is
that their implicit iteration is very much what I want. By the way,
Stevan, do you have an opinion on NIAL?
> > Of course, I'm not sure if my idea is a solution _at all_, so I'm a
> > little leery of getting too much into the details.
Still not sure. Won't get any gut feeling until I code something in
it. At least I'm now being more specific than I was.
> i've been wondering whether, instead of having 'set' and 'multiset'
> datatypes, you have two types of characteristic function. a set cf
> is a function f s.t. f x -> 1 iff x is in the set represented by
> f, and f x -> n iff x occurs in the multiset n times. then implement
> set-algebra with h.o.f.'s 'union', 'diff', etc. manfred?
The multiset paper I posted in my previous email here gave some very
interesting points on this matter.
-Billy
Manfred Von Thun — 2007-07-30 05:05:28
On 18/7/07 8:24 AM, "William Tanksley, Jr" <
wtanksleyjr@...> wrote:
> [..]
>
> You'll certainly beat me to the punch -- I'm about to start working on
> earning a Master's degree for which my company surprised me with a
> full scholarship (!).
Congratulations on the scholarship. Will that be full-time or part-time?
By thesis or by coursework, or both? What area are you planning to
investigate? Will you have time and energy left for the concatenative
group? I hope these questions are not too personal.
- Manfred
[Non-text portions of this message have been removed]
William Tanksley, Jr — 2007-07-30 15:15:34
Manfred Von Thun <
m.vonthun@...> wrote:
> "William Tanksley, Jr" <wtanksleyjr@...> wrote:
> > You'll certainly beat me to the punch -- I'm about to start working on
> > earning a Master's degree for which my company surprised me with a
> > full scholarship (!).
> Congratulations on the scholarship. Will that be full-time or part-time?
Thanks :-). It's going to be part-time, so it'll take a good 3 years.
> By thesis or by coursework, or both?
Coursework.
> What area are you planning to investigate?
The degree will be in 'Systems Engineering', which is basically
broad-scale, interdisciplinary engineering.
http://en.wikipedia.org/wiki/Systems_engineering
> Will you have time and energy left for the concatenative
> group?
Almost certainly. I'll probably want to talk about specific technical things.
> - Manfred
-Billy