Tacit programming in Lisp

Question

Is it possible to use/implement tacit programming (also known as point-free programming) in Lisp? And in case the answer is yes, has it been done?

Answer 1

This style of programming is possible in CL in principle, but, being a Lisp-2, one has to add several #'s and funcalls. Also, in contrast to Haskell for example, functions are not curried in CL, and there is no implicit partial application. In general, I think that such a style would not be very idiomatic CL.

For example, you could define partial application and composition like this:

(defun partial (function &rest args)
  (lambda (&rest args2) (apply function (append args args2))))

(defun comp (&rest functions)
  (flet ((step (f g) (lambda (x) (funcall f (funcall g x)))))
    (reduce #'step functions :initial-value #'identity)))

(Those are just quick examples I whipped up – they are not really tested or well thought-through for different use-cases.)

With those, something like map ((*2) . (+1)) xs in Haskell becomes:

CL-USER> (mapcar (comp (partial #'* 2) #'1+) '(1 2 3))
(4 6 8)

The sum example:

CL-USER> (defparameter *sum* (partial #'reduce #'+))
*SUM*
CL-USER> (funcall *sum* '(1 2 3))
6

(In this example, you could also set the function cell of a symbol instead of storing the function in the value cell, in order to get around the funcall.)

In Emacs Lisp, by the way, partial application is built-in as apply-partially.

In Qi/Shen, functions are curried, and implicit partial application (when functions are called with one argument) is supported:

(41-) (define comp F G -> (/. X (F (G X))))
comp

(42-) ((comp (* 2) (+ 1)) 1)
4

(43-) (map (comp (* 2) (+ 1)) [1 2 3])
[4 6 8]

There is also syntactic threading sugar in Clojure that gives a similar feeling of "pipelining":

user=> (-> 0 inc (* 2))
2

Answer 2

You could use something like (this is does a little more than -> in Clojure):

(defmacro -> (obj &rest forms)
  "Similar to the -> macro from clojure, but with a tweak: if there is
  a $ symbol somewhere in the form, the object is not added as the
  first argument to the form, but instead replaces the $ symbol."
  (if forms
      (if (consp (car forms))
          (let* ((first-form (first forms))
                 (other-forms (rest forms))
                 (pos (position '$ first-form)))
            (if pos
                `(-> ,(append (subseq first-form 0 pos)
                              (list obj)
                              (subseq first-form (1+ pos)))
                     ,@other-forms)
                `(-> ,(list* (first first-form) obj (rest first-form))
                     ,@other-forms)))
          `(-> ,(list (car forms) obj)
               ,@(cdr forms)))
      obj))

(you must be careful to also export the symbol $ from the package in which you place -> - let's call that package tacit - and put tacit in the use clause of any package where you plan to use ->, so -> and $ are inherited)

Examples of usage:

(-> "TEST"
    string-downcase
    reverse)

(-> "TEST"
    reverse
    (elt $ 1))

This is more like F#'s |> (and the shell pipe) than Haskell's ., but they are pretty much the same thing (I prefer |>, but this is a matter of personal taste).

To see what -> is doing, just macroexpand the last example three times (in SLIME, this is accomplished by putting the cursor on the first ( in the example and typing C-c RET three times).

Answer 3

YES, it's possible and @danlei already explained very well. I am going to add up some examples from the book ANSI Common Lisp by Paul Graham, chapter 6.6 on function builders:

you can define a function builder like this:

(defun compose (&rest fns)
  (destructuring-bind (fn1 . rest) (reverse fns)
    #'(lambda (&rest args)
        (reduce #'(lambda (v f) (funcall f v))
                rest
                :initial-value (apply fn1 args)))))

(defun curry (fn &rest args)
  #'(lambda (&rest args2)
      (apply fn (append args args2))))

and use it like this

(mapcar (compose #'list #'round #'sqrt)
        '(4 9 16 25))

returns

((2) (3) (4) (5))

The compose function call:

(compose #'a #'b #'c)

is equlvalent to

#'(lambda (&rest args) (a (b (apply #'c args))))

This means compose can take any number of arguments, yeah.

Make a function which add 3 to argument:

(curry #'+ 3)

See more in the book.

Answer 4

Yes, this is possible in general with the right functions. For example, here is an example in Racket implementing sum from the Wikipedia page:

#lang racket
(define sum (curry foldr + 0))

Since procedures are not curried by default, it helps to use curry or write your functions in an explicitly curried style. You could abstract over this with a new define macro that uses currying.