Interop mini-series – Callbacks special! (Common Lisp special) (Part 2b)


This is a continuation of the previous post callbacks interlude. I decided to give the section pertaining to Common Lisp its own post as I think there is some good educational value in this part itself.

We carry on from where we left off last time. We continue with the same squaring number callback example.

As a quick refresher, the idea is to implement a synchronous callback scenario. The function client invokes another function squarify which squares the passed value and invokes a callback function callback.

How it’s done in Common Lisp

Let’s start off with our first attempt to implement the solution in Common Lisp.

;;;; Callback demo using the squarify example.

(defpackage :callback-demo-user
  (:use :cl))

(in-package :callback-demo-user)

(defun callback(n)
  (format t "Received: ~d~%" n))

(defun squarify(n cb)
  (funcall cb (* n n)))

(defun client ()
  (let ((n (progn
             (princ "Enter a number: ")
             (read))))
    (squarify n #'callback)))
CALLBACK-DEMO-USER> (client)
Enter a number: 19
Received: 361
NIL

That’s the direct equivalent of all the demos shown so far. However, since Common Lisp is a functional language (albeit not as pure as, say, Scheme or Haskell), we can certainly do better!

In most Functional Programming languages, higher order functions are usually deployed to do the job. So let’s see if we can cook up something nicely functional like function composition.
Here’s a first attempt:

(defun client()
  (funcall #'(lambda (n)
               (format t "Received: ~d~%" n))
           (funcall #'(lambda (n)
                        (* n n))
                    (funcall #'(lambda ()
                                 (princ "Enter number: ")
                                 (read))))))

Which produces:

CALLBACK-DEMO-USER> (client)
Enter number: 19
Received: 361
NIL

As expected! Now, as you may know, funcall simply takes a function and some arguments (optional), and applies the function to those arguments. In this case, we simply compose them in the proper order so that the types match up: read a number -> square it -> print message.

However, let’s work our way to a generic compose function that simulates the behaviour of Haskell’s composition operator. The previous function can be improved by defining a new version that composes the three functions in the mentioned order (so as to match types):

The compose function:

(defun compose (fn gn hn)
  #'(lambda (&rest args)
      (funcall fn (funcall gn (apply hn args)))))

And the client to test it:

(defun client ()
  (funcall (compose #'(lambda (x)
                        (format t "Received: ~d~%" x))
                    #'(lambda (x)
                        (* x x))
                    #'(lambda ()
                        (princ "Enter a number: ")
                        (read)))))

And the output is the same:

CALLBACK-DEMO-USER> (client)
Enter a number: 19
Received: 361
NIL

So what’s changed? Well, taking inspiration from the nested funcall function, we defined compose to invoke the functions in the proper order – first read the number, and then square it, and then finally print it! (Remember that the functions are composed in reverse order in which they are entered).

Note that the last function invocation is done using apply instead of funcall because &rest args produces a list of arguments, and funcall does not work with that (unless the function definition takes a list itself as a parameter, but that is not the general case, and apply works very well with lists and destructures them correctly.

How can we make this generic enough though? We notice the pattern – we invoke apply on the innermost function call, but we use funcall for the rest of the function call chain. This means that we must handle two cases – if there is a single function passed in, we should simply use apply on that, and if not, we should take care to chain them up as discussed. This lends itself to a nice recursive definition as shown next.

The updated compose function:

(defun compose (&rest funcs)
  (labels ((f (funcs args)
             (if (null (cdr funcs))
                 (apply (car funcs) args)
                 (funcall (car funcs) (f (cdr funcs) args)))))
    #'(lambda (&rest args)
        (f funcs args))))
)

And the test client for it:

(defun client ()
  (funcall (compose #'(lambda (x)
                        (format t "Received: ~d~%" x))
                    #'(lambda (x)
                        (* x x))
                    #'(lambda ()
                        (princ "Enter number: ")
                        (read)))))

And the output:

CALLBACK-DEMO-USER> (client)
Enter number: 19
Received: 361
NIL

Explanation: What we do is simply generalise the three-function version of compose into a generic function. For this we, define an internal function f that takes the supplied functions and the arguments as input.

f then recursively decomposes the function applications. The base condition (stopping condition) is when there is only one function left. The (if (null (cdr funcs)) bit then takes care to return the only apply call that we need, and that is of course, applied to the args argument.

As the recursion unwinds the call stack, successive funcallS are applied at each stage. This is exactly in line with the algorithm discussed at the end of the last section.

Now we are almost home and dry! Pay special attention to the order in which the lambda equivalents of the functions are entered in the client function. They are applied in the following order – callback, squarify, and then client.

We could stop here, but there’s one more change that we can make. The current version of compose works absolutely as expected, but the intuitive order of supplying functions is the opposite of what we could expect as a user. The expected order would be, in English, “read in the number, square it, and then print out a message indicating that the number was received”.

Let’s fix that last bit for out final version of compose.

Final version of compose:

;;; final version of compose
(defun compose(&rest funcs)
  (labels ((f (funcs args)
             (if (null (cdr funcs))
                 (apply (car funcs) args)
                 (funcall (car funcs) (f (cdr funcs) args)))))
    #'(lambda (&rest args)
        (f (reverse funcs) args)))))

And the corresponding test code:

;;; test out the final version of compose
(defun client ()
  (funcall (compose #'(lambda ()
                        (princ "Enter a number: ")
                        (read))
                    #'(lambda (x)
                        (* x x))
                    #'(lambda (x)
                        (format t "Received: ~d~%" x)))))

And now let’s test out and see if it works!

CALLBACK-DEMO-USER> (client)
Enter a number: 19
Received: 361
NIL

Success!

The only difference is this line: (f (reverse funcs) args). We simply reverse the order of the received functions while passing it to the recursive function f, and the rest of the code remains exactly the same!

And, of course, this is purely functional! Sweet, ain’t it?

The compose function could be optimised in multiple ways – converting it to an iterative version for instance, but conceptually, this works exactly as advertised.

Conclusion

This post illustrates why I love Common Lisp! Even as I make my journey through the world of Common Lisp, my admiration for it only grows. If there is some feature that we would like to incorporate into the language, it can be done in a just a few lines of code! No other language truly comes close in terms of expressiveness and extensibility.

Advertisements
Interop mini-series – Callbacks special! (Common Lisp special) (Part 2b)

Speak your mind!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s