Lambda the Ultimate

inactiveTopic Point Free Style
started 6/19/2003; 6:32:43 AM - last post 6/22/2003; 9:17:38 AM
andrew cooke - Point Free Style  blueArrow
6/19/2003; 6:32:43 AM (reads: 2308, responses: 12)
Point Free Style
This style is particularly useful when deriving efficient programs by calculation, but it is good discipline in general. It helps the writer (and reader) think about composing functions (high level), rather than shuffling data (low level).

Condensed from a Haskell mailing list post, this also has a number of interesting-looking references.
Posted to theory by andrew cooke on 6/19/03; 6:38:41 AM

Frank Atanassow - Re: Point Free Style  blueArrow
6/19/2003; 10:17:16 AM (reads: 1281, responses: 0)
Well, I dunno if point-freeness is actually `higher-level' in any concrete sense, but it can be more concise (yet also sometimes more verbose) and makes it easier to see the relationship with categorical concepts.

Here is another reference, actually about the opposite topic, in the context of relations. Quite interesting:

O. de Moor and J. Gibbons. Pointwise relational programming. (invited paper) T. Rus (editor), Procs. of AMAST 2000, Springer Lecture Notes in Computer Science, Volume 1816, pages 371--390. (available here)

James Hague - Re: Point Free Style  blueArrow
6/19/2003; 12:11:14 PM (reads: 1241, responses: 1)
There's not a single mention of J on that page, the ultimate point free language:
   mean =: +/ % #
   mean 8 6 12

Tim Sweeney - Re: Point Free Style  blueArrow
6/19/2003; 4:08:19 PM (reads: 1197, responses: 0)
I've always found it very hard to read and write point-free code. I wonder if this is just a matter of practice. Anyone here feel comfortable with the point-free style?

sean - Re: Point Free Style  blueArrow
6/19/2003; 7:49:16 PM (reads: 1162, responses: 1)
I'll have to agree with Tim on this one. Trying to write a bit of code in an FP-like, variable-free language led me to conclude that Lambda (or Whomever is the bringer of names) makes things clearer. As it was, I ended up having to pass around lists of values, pull them out of the list with selectors, and lean on comments to remember which variables corresponded to which positions. For example, here's code for Euler's totient function, supposedly demonstrating how "clear" things are in FP:
  def totient = /+ . @((== . [1, `1] -> `1 ; `0) .
   (while (> . [2, `0]) (< -> reverse ; id) . [2, -]))
   . distl . [id, iota]

Darius Bacon - Re: Point Free Style  blueArrow
6/19/2003; 10:18:22 PM (reads: 1145, responses: 0)
I made up a variant of FP once with fewer funny symbols and where you say "f g" instead of "g . f" for function composition. I think this code is equivalent to yours, and clearer? You read from left to right, like a Unix pipeline:

to totient   [id, iota] distl  each coprime?  count
to coprime?  [gcd, #1] ==
to count     each (if id then #1 else #0)  insert +

to gcd // This and `count' ought to be library functions, really. while [2, #0] > do ( [2, -] if < then reverse else id )

So the real problem with that code is insufficient factoring, plus maybe excessively squiggly notation. OTOH I ended up adding local variables to the language eventually, because without them you do sometimes need to mentally follow values through a chain of manipulations, like stack gymnastics in Forth, and variables are a good way to automate that.

andrew cooke - Re: Point Free Style  blueArrow
6/20/2003; 4:15:43 AM (reads: 1146, responses: 0)
lean on comments

types really help here. i've not used J or whatever the example above is written in, but going from lisp to haskell one of the big things i noticed was that the types helped me follow what was happening, letting me manage higher order functions with less confusion (no particular criticism of lisp implied - i suspect once you're expert at this it's less of an issue, for example).

Dan Schmidt - Re: Point Free Style  blueArrow
6/20/2003; 7:57:51 AM (reads: 1073, responses: 0)
Having types does really help me a lot with this kind of stuff; if I can instantly see that a function is ('a -> 'b) -> 'a list -> 'b list or whatever, it doesn't matter so much that I don't see the 'a list explicitly mentioned in the code of the function itself.

In general I figure that I will not be a true functional programmer until I am completely comfortable reading and writing point-free code without mentally inserting extra parameters into the code such as the 'a list in the above example.

Ehud Lamm - Re: Point Free Style  blueArrow
6/22/2003; 1:35:20 AM (reads: 999, responses: 0)
Right. If you are interested in this sort of thing, go read on tacit definitions in J.

It is interesting to note the different approaches taken in FP (i.e., Haskell) and in J, in order to achieve "point free style." In Haskell for example, automatic currying is quite essential for this sort of programming style, where as in J the difference between unary and binary functions is quite fundamental.

Perhaps more itneresting is the work on phrasal forms in J. For example the meaning of a "fork" like (+/ % #) x is (+/ x) % (# x), which means sum elements of x and divide by the number of elements in x (give by the # operator). A lot of thought was given to assigning useful meaning to trains of operators (hooks, forks etc.)

Final thought: As J is an array programming language, there are interesting rule regarding rank ("dimensionality"), these apply to trains of operators in ways that vcan cause subtle bugs for those not in the know.

Neel Krishnaswami - Re: Point Free Style  blueArrow
6/22/2003; 6:27:22 AM (reads: 951, responses: 3)
I think that the combination of named arguments and currying, like Ocaml provides, is a huge aid in writing code in a combinatorial style. One of the big difficulties in writing a combinator library in SML or Haskell is the problem of ensuring that the most common partial applications are on the left. If you get the order wrong, you need to introduce all sorts of gratuitous anonymous functions to curry the correct arguments. For example, you can end up writing <tt>(fun x -> foo x 3)</tt> instead of something like <tt>(foo 3)</tt>.

Ehud Lamm - Re: Point Free Style  blueArrow
6/22/2003; 7:07:36 AM (reads: 981, responses: 2)
Sounds helpful. What do others think?

andrew cooke - Re: Point Free Style  blueArrow
6/22/2003; 8:05:25 AM (reads: 1010, responses: 1)
What do others think?

well i immediately thought: "ouch! so what other stupid assumptions have i made about the way languages work just because i read from left to right and write code in lines?"

Dan Shappir - Re: Point Free Style  blueArrow
6/22/2003; 9:17:38 AM (reads: 1048, responses: 0)
While I love the natural way Haskell does currying, I couldn't help but notice this issue. When we added currying to JavaScript in BeyondJS, we had to do this using an explicit method call:

function f(x,y) { ... }
var g = f.curry(1);

Given this, we leveraged this limitation to support named currying and most every other type of argument binding we could think of.

Moreover, we have an "extened" version of currying in the form of the using() method:

function h(x,y,z) { ... }
var g = f.using(h);

g now becomes a function with three arguments: x, y, z Invoking g as:

g(1, 2, 3);

translates to:

f(h(1, 2, 3), 2);

this is because the y argument is used both by g and h (x is also used by both, but for f it is bound to the value return by h).

using() also provides a mechanism for argument renaming.

Note: I've slightly modified this post to make it more correct and readable