# 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