Lambda: the discontinuity

I like functional programming, especially in points-free style: it allows amazingly terse expression, with minimal attention to plumbing. But there is an annoyance that often trips me up: there's a discontinuity between combinator expressions and lambda-expressions.

Consider the commonplace task of iterating over a list and, say, printing out the elements. There is an obvious points-free way:

(mapc #'print numbers)

More complex functions can be handled with combinators...

(mapc (compose #'print #'round) numbers)

...and partial application:

(mapc (compose (op format t "  ~S~%" _) #'round) numbers)

But for more complicated functions, points-free style gets awkward quickly, especially if you don't have other combinators like s. As soon as we want to use some variable twice, it's usually easier to switch to lambda:

(mapc (lambda (x) (format t "~S (really ~S)~%" (round x) x))
      numbers)

And that switch requires rewriting the whole function in a completely different way.

Having more than one way to write functions is not in itself a problem, of course. The trouble is that I often want to transform between them, when a points-free expression grows to the point where it needs a lambda. At this point I have to stop thinking about what I want the code to do, and instead think about the trivia of combinators and variables. It's only a minor annoyance, but it's a very common one. And it's more common in more points-free code, so it probably discourages good programming style.

Is there an alternative to lambda/combinator calculus that can express simple functions as tersely as combinator style, but without the discontinuity when they grow? In particular, I want to be able to name variables without reorganizing the code that uses them. This is a hard problem and I don't expect to find any good solution, but I'm still looking. Lambda and combinator calculus are wonderful things, but they're not perfect, and even a small improvement in expressiveness of simple functions would be a big deal.

5 comments:

  1. Yes there is a solution for precisely that problem: Arrows. Popular in Haskell.

    ReplyDelete
  2. Do arrows help with this? AFAICT, they address a different problem: they generalize combinators (and λ and call, with the syntax) to types other than functions. This may be very handy, but I don't see how it eases the awkwardness of translating between combinators and lambda.

    ReplyDelete
  3. The most immediate solution that comes to mind is concatenative style (e.g. Factor, Forth). I'm not sure how to state the formatting operations, so I'll stub them, but here goes:

    define format-1 { something of one argument}
    define format-2 { something else of two arguments }

    (numbers) [print] map
    (numbers) [round print] map
    (numbers) [round format-1] map
    (numbers) [dup round format-2] map

    I'm still learning the stuff, so I may not have phrased it just right (and don't have a REPL at hand). The lack of unnecessary naming was one of the big draws of the concat style for me, and I think this problem shows it off well.

    ReplyDelete
  4. A nifty function, juxt, from Clojure's standard library is evocative of some combinators used by Factor, and even of the higher order functions you've used in your 'Optimizing samefringe' post from 2005.

    ((juxt f g ...) args...) == [(f args...) (g args...) ...]

    I believe this (along with partial application and composition) can handle many point-free definitions where the data flow somehow 'forks'. I wonder what its limits are... I have neither used nor contemplated juxt enough to tell.

    (defn round [x] (Math/round x))
    (def numbers [Math/PI Math/E (Math/sqrt 2)])

    (dorun
    (map (comp (partial apply printf "%s (really %s)\n") (juxt round identity))
    numbers))

    ReplyDelete
  5. Yeah, (juxt args...) is (h vector args...). I like h better, though, because I usually want to do something with the results other than make a vector, e.g. (h (fmt "~S (really ~S)~%" _ _) round i).

    (A comment on juxt from clojuredocs: "I kinda love this fn =)". Yeah, me too.)

    ReplyDelete

It's OK to comment on old posts.