It's no secret that I'm an aficionado of Lisp. It's my go to language, especially when I don't know what I'm doing. I call it research and prototyping, but it's really just playing around until something works.
We had a need for some auditing of some of our databases at work. They ought to agree with each other and with what GitHub and CircleCI think. It took a couple of weeks part time to prototype a solution in Common Lisp. It showed that the databases were in 99% agreement and found the few points of disagreement and anomalies that we ought to fix or look out for.
I want to integrate this information into a dashboard on one of our tools. I prototyped this by spinning up a Common Lisp microservice that returns the information in JSON format.
But management prefers that new services are written in golang. It would be easier for me to rewrite the service in golang than to try to persuade others to use Common Lisp. It also gives me the opportunity to compare the two languages head to head on a real world problem.
No, this is not a fair comparison. When I wrote the Lisp code I was exploring the problem space and prototyping. I'm much more experienced with Lisp than with golang. The golang version has the advantage that I know what I want to do and how to do it. In theory, I can just translate the Common Lisp code into golang. But then again, this is a “second system” which is not a prototype and has slightly larger scope and fuller requirements. So this cannot be a true head to head comparison.
The first point of comparison is macros (or lack thereof). I
generally don't use a lot of macros in Common Lisp, but they come in
handy when I do use them. One macro I wrote is
called audit-step, which you can wrap around any
expresion and it prints out a message before and after the
expression is evaluated. The steps are numbered in sequence, and
nested steps get nested numbers (like step 2.3.1). If you wrap the
major function bodies with this macro, you get a nice trace of the
call sequence in the log.
Golang doesn't have macros, but it has first class functions. It's easy enough to write a function that takes a function as an argument and wraps it to output the trace messages. In fact, the macro version in Common Lisp just rewrites the form into such a function call. But the macro version hides a level of indentation and a lambda. In golang, my major functions all start with
func MajorFunction (args) int {
return AuditStep("MajorFunction", "aux message", func() int {
// body of MajorFunction
// Actual code goes here.
})
}
The bodies of all my major functions are indented by 16 spaces, which is a little much.
I like higher order functions. I can write one higher order
function and parameterize it with functions that handle the specific
cases. In my auditing code, one such workhorse function is
called collate. It takes a list of objects and creates
a table that maps values to all objects in the list that contain
that value. To give an example, imaging you have a list of objects
that all have a field called foo. The foo
field is a string. The collate function can return a
table that maps strings to all objects that have that string in the
foo field.
collate is very general. It takes a list of objects
and four keyword arguments. The :key argument is a
function that extracts the value to collate on.
The :test argument is a function that compares two keys
(it defaults to eql if not specified).
The :merger
argument is a function to add the mapped object to its appropriate
collection in the table (it defaults to adjoin). The :default argument
specifies the initial value of a collection in the table (it
defaults to nil).
The :merger function is the most interesting. It takes the key and
the object and the current value of the table at that key. It
returns the new value of the table at that key. The default merger
function is adjoin, which adds the object to the
collection at the key if it is not already there. But you can
specify a different merger function. For example, if you want to
count the number of objects at each key, you can specify a merger
function that increments a counter.
The functional arguments to the collate function are often the
results of other higher order functions. For example,
the :key argument is often the result of composing
selector functions. The :merger argument is often the
result of composing a binary merge function with a unary transformer
function. The transformer function is often the result of composing
a number of primitive selectors and transformers.
In Common Lisp, it is quite easy to write these higher order
functions. We can compose two unary functions with
the compose2 function:
(defun compose2 (f g) (lambda (x) (funcall f (funcall g x)))
and then compose as many functions as we like
by fold-left of compose2 starting with
the identity function:
(defun compose (&rest fs) (fold-left #'compose2 #'identity fs))
We can compose a binary function with a unary function in three ways: we can pipe the output of the binary function into the unary function, or we can pipe the output of the unary function into one or the other of the inputs of the binary function.
(defun binary-compose-output (f g) (lambda (x y) (funcall f (funcall g x y)))) (defun binary-compose-left (f g) (lambda (x y) (funcall f (funcall g x) y))) (defun binary-compose-right (f g) (lambda (x y) (funcall f x (funcall g y))))
The collate function can now assume that a lot of the
work is done by the :key and :merger
functions that are passed in. It simply builds a hash table and
fills it:
(defun collate (item &key (key #'identity) (test #'eql) (merger (merge-adjoin #'eql)) (default nil))
(let ((table (make-hash-table :test test)))
(dolist (item items table)
(let ((k (funcall key item)))
(setf (gethash k table) (funcall merger (gethash k table default) item))))))
(defun merge-adjoin (test)
(lambda (collection item)
(adjoin item collection :test test)))
So suppose, for example, that we have a list of records. Each
record is a three element list. The third element is a struct that
contains a string. We want a table mapping strings to the two
element lists you get when you strip out the struct. This is easily
done with collate:
(collate records :key (compose #'get-string #'third) :test #'equal ; or #'string= if you prefer :merger (binary-compose-right (merge-adjoin #'equal) #'butlast))
The audit code reads lists of records from the database and from GitHub
and from CircleCI and uses collate to build hash tables
we can use to quickly walk and validate the data.
Translating this into golang isn't quite so easy. Golang has first
class function, true, but golang is a statically typed language.
This causes two problems. First, the signature of the higher order
functions includes the types of the arguments and the return value.
This means you cannot just slap on the lambda symbol,
you have to annotate each argument and the return value. This is
far more verbose. Second, higher order functions map onto
parameterized (generic) types. Generic type systems come with their
own little constraint language so that the computer can figure out
what concrete types can correctly match the generic types. This
makes higher order functions fairly unweildy.
Consider compose2. The functions f
and g each have an input and output type, but the
output type of g is the input type of f
so only three types are involved
func Compose2[T any, U any, V any](f func(U) V, g func(T) U) func(T) V {
return func(x T) V {
return f(g(x))
}
}
If want to compose three functions, we can write this:
func Compose3[T any, U any, V any, W any](f func(V) W, g func(U) V, h func(T) U) func(T) W {
return func(x T) W {
return f(g(h(x)))
}
}
The generic type specifiers take up as much space as the code
itself.
I don't see a way to write an n-ary compose function. It would have to be dynamically parameterized by the intermediate types of all the functions it was composing.
For the collate function, we can write this:
func Collate[R any, K comparable, V any](
list *Cons[R],
keyfunc func(R) K,
merger func(V, R) V,
defaultValue V) map[K]V {
answer := make(map[K]V)
for list != nil {
key := keyfunc(list.Car)
probe, ok := answer[key]
if !ok {
probe = defaultValue
}
answer[key] = merger(probe, list.Car)
list = list.Cdr
}
return answer
}
We have three types to parameterize over: the type of the
list elements (i.e. the record type) R, the type of
the key K, and the type of the value V.
The key type is needs to be constrained to be a valid key in a map,
so we use the comparable constraint. Now that we have
the types, we can annotate the arguments and return value. The list
we are collating is a list of R elements. The key
function takes an R and returns a K. The
merger takes an existing value of type V and the record
of type R and returns a new value of
type V.
The magic of type inference means that I do not have to annotate all the variables in the body of the function, but the compiler cannot read my mind and infer the types of the arguments and return value. Golang forces you to think about the types of arguments and return values at every step of the way. Yes, one should be aware of what types are being passed around, but it is a burden to have to formally specify them at every step. I could write the Common Lisp code without worrying too much about types. Of couse the types would have to be consistent at runtime, but I could write the code just by considering what was connected to what. In golang, the types are in your face at every function definition. You not only have to think about what is connected to what, you have to think about what sort of thing is passed through the connection.
I'm sure that many would argue that type safety is worth the trouble of annotation. I don't want to argue that it isn't. But the type system is cumbersome, awkward, and unweildy, especially when you are trying to write higher order functions.
It is taking me longer to write the golang version of the audit service than it did to write the Common Lisp version. There are several reasons. First, I am more experienced with Common Lisp than golang, so the right Common Lisp idioms just come to mind. I have to look up many of the golang idioms. Second, the golang code is trying to do more than the Common Lisp code. But third, golang itself introduces more friction than Common Lisp. Programs have to do more than express the algorithm, they have to satisfy the type system.
There are more points of comparison between the two languages. When I get frustrated enough, I'll probably write another post.