An observation

Go programs make a lot more sense if you pronounce if err != nil as “inshallah”.

You Are The Compiler

Consider a complex nested function call like

(foo (bar (baz x)) (quux y))

This is a tree of function calls. The outer call to foo has two arguments, the result of the inner call to bar and the result of the inner call to quux. The inner calls may themselves have nested calls.

One job of the compiler is to linearize this call tree into a sequential series of calls. So the compiler would generate some temporaries to hold the results of the inner calls, make each inner call in turn, and then make the outer call.

  temp1 = baz(x)
  temp2 = bar(temp1)
  temp3 = quux(y)
  return foo (temp2, temp3)

Another job of the compiler is to arrange for each call to follow the calling conventions that define where the arguments are placed and where the results are returned. There may be additional tasks done at function call boundaries, for example, the system might insert interrupt checks after each call. These checks are abstracted away at the source code level. The compiler takes care of them automatically.

Sometimes, however, you want to want modify the calling conventions. For example, you might want to write in continuation passing style. Each CPS function will take an additional argument which is the continuation. The compiler won't know about this convention, so it will be incumbent on the programmer to write the code in a particular way.

If possible, a macro can help with this. The macro will ensure that the modified calling convention is followed. This will be less error prone than expecting the programmer to remember to write the code in a particular way.

The Go language has two glaring omissions in the standard calling conventions: no dynamic (thread local) variables and no error handling. Users are expected to impose their own calling conventions of passing an additional context argument between functions and returning error objects upon failures. The programmer is expected to write code at the call site to check the error object and handle the failure.

This is such a common pattern of usage that we can consider it to be the de facto calling convention of the language. Unfortunately, the compiler is unaware of this convention. It is up to the programmer to explicitly write code to assign the possible error object and check its value.

This calling convention breaks nested function calls. The user has to explicitly linearize the calls.

temp1, err1 := baz(ctx, x)
  if err1 != nil {
    return nil, err1
  }
  temp2, err2 := bar(ctx, temp1)
  if err2 != nil {
    return nil, err2
  }
  temp3, err3 := quux(ctx, y)
  if err2 != nil {
    return nil, err2
  }
  result, err4 := foo(ctx, temp2, temp3)
  if err4 != nil {
    return nil, err4
  }
  return result, nil

Golang completely drops the ball here. The convention of returning an error object and checking it is ubiquitous in the language, but there is no support for it in the compiler. The user ends up doing what is normally considered the compiler's job of linearizing nested calls and checking for errors. Of course users are less disciplined than the compiler, so unconventional call sequences and forgetting to handle errors are common.

No Error Handling For You

According to the official Go blog, there are no plans to fix the (lack of) error handling in Go. Typical. Of course they recognize the problem, and many people have suggested solutions, but no one solution seems to be obviously better than the others, so they are going to do nothing. But although no one solution appears obviously better than the others, it's pretty clear that the status quo is worse than any of the proposed solutions.

But the fundamental problem isn't error handling. The fundamental problem is that the language cannot be extended and modified by the user. Error handling requires a syntactic change to the language, and changes to the language have to go through official channels.

If Go had a macro system, people could write their own error handling system. Different groups could put forward their proposals independently as libraries, and you could choose the error handling library that best suited your needs. No doubt a popular one would eventually become the de facto standard.

But Go doesn't have macros, either. So you are stuck with limitations that are baked into the language. Naturally, there will be plenty of people who will argue that this is a good thing. At least the LLMs will have a lot of training data for if err != nil.

Continuation-passing-style in Golang

I had a requirement change come in the other day. It was for a golang program that made some REST calls to an API. The change was that if a user did not supply credentials, the program should still be able to call those parts of the REST API that could handle anonymous requests. If the user supplied credentials, then all calls should use them. If the user did not supply credentials, but attempted to call a part of the API that required them, the program would panic with missing credentials and exit.

In Lisp, this is good use case for continuation-passing-style. The routine that fetches the credentials could take two continuations, one to call with the user-supplied credentials and one to call if no credentials are found. The second continuation could take a condition object that indicates why the credentials were not found.

A caller requesting credentials could call this routine with two continuations. The first would be a lexical closure that accepted the credentials as an argument and invoked the relevant API call. The second could either be a first-class function that accepted the condition and signalled it (and so the credentials would be required) or it could be a lexical closure that just invoked the API without credentials (and so make an anonymous request).

This separates the concerns nicely. The code that fetches the credentials doesn't have to know whether the credentials are ultimately required or optional. The code that uses the credentials doesn't have to know how they were fetched or where they are fetched from.

But I was working in Golang, not Lisp. Nevertheless, you can write a limited form of continuation-passing-style in Golang. Golang supports first-class functions and lexical closures, so you can pass these down as a continuations. But there are a couple of problems.

First, there is no tail recursion in Golang. This means that a stack frame is pushed on each call regardless of whether it is a continuation or not. You will run out of stack space if you call several continuation-passing-style routines in a row, especially if they end up looping. Each subroutine call pushes an "identity" stack frame that just returns what is returned to it, and these pile up. When you write continuation-passing-style code in Golang, you have to be careful to return to direct style often enough to pop these accumulating identity frames off the stack.

Second, Golang distinguishes between expressions that return a value and statements that do not. The function definition syntax is used for both, the difference being whether you declare a return type or not. A continuation-passing-style function returns a value of the same type as the continuation returns. For this we use a generic function that takes a type parameter for the return type:

func foo[T any](cont func(int) T) T {
        ... do something ...
        return cont(...some integer value...)
}

But what if the continuation is a statement that does not return a value? In this case, we don't want a return type at all.

func fooVoid (cont func(int)) {
        ... do something ...
        cont(...some integer value...)
        return
}

The problem here is that we now need two versions of every continuation-passing-style routine, one that returns a value and one that does not, and we have to manually choose which version to use at each call site. This is tedious and error-prone. It would be nice to have a "void" type that acts as a placeholder to indicate that no actual return value is expected.

Dynamic Variables in Go

Dynamic binding is an evaluation rule for free variables. The rule is that the value of a free variable in a lambda expression is the value bound in the nearest dynamically enlosing scope. This is in contrast to static binding, where the value is the value bound in the nearest lexically enclosing scope. A naive interpreter that saves variable bindings in a stack frame will usually end up implementing dynamic binding.

In general, static binding is preferred because it is easier to reason about. However, dynamic binding is sometimes very useful in handling context. Lisp provides both static and dynamic binding, with the default being static binding.

Golang provides lexical binding, but not dynamic binding. But you can mimic the effect of dynamic binding by saving the variable's value, assigning it a new value, then restoring the old value in a defer statement. But this trick won't work in a multi-threaded environment. Each thread has to manage its own value of the variable that is separate from the values in other threads.

But what if the implementation doesn't tightly bind continuations to threads? What if the implementation uses a thread pool, and the same thread is used for different goroutines at different times? In that case, the trick of saving and restoring the value of a variable won't work. The value of the variable will be shared among different goroutines, and the value will be unpredictable. To make things work, your dynamic variables should be continuation-local.

But golang doesn't provide continuation-local variables, and it seems to go out of its way to keep code from inspecting the current continuation. There is a trick that you can use.

We need a way to allocate synthetic continuation IDs and bind them to the chain of pending calls. We also need a way that a subroutine can inspect the current chain of pending calls and determine the synthetic continuation ID.

Allocating a synthetic continuation ID is easy enough by maintaining a bitmap of free continuation IDs. When we need a continuation ID, we grab a mutex and search the bitmap for an unused continuation ID. We set the bit to allocate the ID and free the mutex. To free the continuation ID, we reset the bit. Any time you want to use dynamic variables, you need to allocate a synthetic continuation ID early on. This will be used as an index into a value table for each dynamic variable.

var (
	continuationIdInUse [MaxContinuations]bool = [MaxContinuations]bool{}
	continuationIdMutex sync.Mutex       = sync.Mutex{}
)

func AllocateContinuationId[T any](receiver func(tid uint8) T) T {
	continuationIdMutex.Lock()

	for tid, inUse := range continuationIdInUse {
		if (tid > 0) && !inUse {
			continuationIdInUse[tid] = true
			continuationIdMutex.Unlock()
			return DeallocatingContinuationId(uint8(tid), receiver)
		}
	}

	panic("No available continuation ids")
}

func DeallocateContinuationId(tid uint8) {
	continuationIdInUse[tid] = false
}

func DeallocatingContinuationId[T any](tid uint8, receiver func(tid uint8) T) T {
	defer DeallocateContinuationId(tid)
	return receiver(tid)
}

Golang doesn’t offer much in the way of stack introspection or manipulation, but you can easily get a backtrace of the names of the pending function calls. So we’ll encode the synthetic continuation ID as a nested set of function calls. When we need to read the current continuation ID, we get a backtrace of the stack and look for the special nested set of function calls and decode them.

func Mark0[T any](count int, value uint8, thunk func() T) T {
	if count == 0 {
		return thunk()
	} else if value%2 == 0 {
		return Mark0(count-1, value/2, thunk)
	} else {
		return Mark1(count-1, (value-1)/2, thunk)
	}
}

func Mark1[T any](count int, value uint8, thunk func() T) T {
	if count == 0 {
		return thunk()
	} else if value%2 == 0 {
		return Mark0(count-1, value/2, thunk)
	} else {
		return Mark1(count-1, (value-1)/2, thunk)
	}
}

func MarkByte[T any](value uint8, thunk func() T) T {
	if value%2 == 0 {
		return Mark0(7, value/2, thunk)
	} else {
		return Mark1(7, (value-1)/2, thunk)
	}
}

When we call MarkByte on a byte, we’ll make a series of eight nested function calls to Mark0 or Mark1 depending on the bits in the byte. We can use the golang backtrace mechanism to find the nested function calls and determine what the byte was:

func ReadMark() int {
	pc := make([]uintptr, 256)
	n := runtime.Callers(0, pc)

	frames := runtime.CallersFrames(pc[:n])
	value := 0
	for {
		frame, more := frames.Next()
		if !more {
			break
		}

		if strings.Contains(frame.Function, "Mark0") {
			value *= 2
		} else if strings.Contains(frame.Function, "Mark1") {
			value = value*2 + 1
		}
	}
	return value
}

Now when we spin off a goroutine that will use dynamic variables, we must be careful to call WithThread some time early on in the goroutine:

func MakeMyGoroutineEntry () func () {
        return func () {
                _ = WithThread(func () int {
                        // There are 8 pending calls to Mark[0,1]
                        // And we can use ReadMark() to get the
                        // represented value
                        
                        // ... body of callback ...
                   })
         }
}

  // ... some code somewhere ...
  myGoroutine := MakeMyGoroutineEntry()
  go myGoroutine()

Now we can use the continuation ID to index into a table of values:

type GlVal[T any] struct {
	values [MaxThreads]T
}

func NewGlVal[T any]() *GlVal[T] {
	return &GlVal[T]{}
}

We read the goroutine local variable by indexing into the table:

func GlValGet[T any](g *GlVal[T]) T {
	return g.values[ReadMark()]
}

We write the golang local variable by writing to the table. We return the old value so that we can restore it later. Note, no mutex is needed because the value is thread-local:

func GlValSet[T any](g *GlVal[T], value T) T {
	mark := ReadMark()
	oldValue := g.values[mark]
	g.values[mark] = value
	return oldValue
}

When we want to dynamically bind the variable, we save the old value to a frame local variable, set the new value, and defer a function to restore the old value:

func GlValBind[T, U any](g *GlVal[T], value T, thunk func() U) U {
	oldValue := GlValSet(g, value)
	defer GlValSet(g, oldValue)
	return thunk()
}

This technique seems reasonably robust despite using the debugging support for its implementation. It will fail if they ever make golang tail-recursive, but I doubt that will happen any time soon.

Lisp vs. golang

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.

Continuation passing style resource management

One good use of continuation passing style is to manage dynamic resources. The resource allocation function is written in continuation passing style and it takes a callback that it invokes once it has allocated and initialized the resource. When the callback exits, the resource is uninitialized and deallocated.

(defun call-with-resource (receiver)
  (let ((resource nil))
    (unwind-protect
        (progn
          (setq resource (allocate-resource))
          (funcall receiver resource))
      (when resource
        (deallocate-resource resource)))))

  ;; example usage:
  (call-with-resource
    (lambda (res)
      (do-something-with res)))

;;; In Lisp, we would provide a convenient WITH- macro
(defmacro with-resource ((resource) &body body)
  ‘(CALL-WITH-RESOURCE (LAMBDA (,resource) ,@body)))

  ;; example usage:
  (with-resource (res)
    (do-something-with res))

This pattern of usage separates and abstracts the resource usage from the resource management. Notice how the unwind-protect is hidden inside call-with-resource so that the user of the resource doesn’t have to remember to deallocate the resource.

The with-resource macro is idiomatic to Lisp. You obviously can’t provide such a macro in a language without macros, but you can still provide the call-with-resource function.

Continuation passing style for resource management can be used in other languages, but it often requires some hairier syntax. Because call-with-resource takes a callback argument, it is actually a higher-order function. The syntax for passing higher-order functions in many languages is quite cumbersome. The return value of the callback becomes the return value of call-with-resource, so the return type of the callback must be compatible with the return type of the function. (Hence the type of call-with-resource is actually parameterized on the return value of the callback.) Languages without sophisticated type inference may balk at this.

Another advantage of the functional call-with-resource pattern is that you can dynamically select the resource allocator. Here is an example. I want to resolve git hashes against a git repository. The git repository is large, so I don’t want to clone it unless I have to. So I write two resource allocators: CallCloningGitRepository, which takes the URL of the repository to clone, and CallOpeningGitRepository which takes the pathname of an already cloned repository. The "cloning" allocator will clone the repository to a temporary directory and delete the repository when it is done. The "opening" allocator will open the repository and close it when it is done. The callback that will be invoked won’t care which allocator was used.

Here is what this looks like in golang:

// Invoke receiver with a temporary directory, removing the directory when receiver returns.
func CallWithTemporaryDirectory(dir string, pattern string, receiver func(dir string) any) any {
	dir, err := os.MkdirTemp(dir, pattern)
	CheckErr(err)
	defer os.RemoveAll(dir)

	return receiver(dir)
}

// Invoke receiver with open git repository.
func CallOpeningGitRepository(repodir string, receiver func(string, *git.Repository) any) any {
	repo, err := git.PlainOpen(repodir)
	if err != nil {
		log.Fatal(err)
	}
	return receiver(repodir, repo)
}

// Invoke receiver with a cloned git repository, removing the repository when receiver returns.
func CallCloningGitRepository(dir string, pattern string, url string, receiver func(tmpdir string, repo *git.Repository) any) any {
	if url == "" {
		return nil
	}
	return CallWithTemporaryDirectory(
		dir,
		pattern,
		func(tempdir string) any {
			log.Print("Cloning " + url + " into " + tempdir)
			repo, err := git.PlainClone(tempdir, true, &git.CloneOptions{
				Auth: &gitHttp.BasicAuth{
					Username: username,
					Password: password,
				},
				URL:      url,
				Progress: os.Stdout,
			})
			CheckErr(err)
			log.Print("Cloned.")
			return receiver(tempdir, repo)
		})
}

You specify a repository either with a URL or a pathname. We select the appropriate resource allocator based on whether the specifier begins with "https".

func RepositoryGetter (specifier string) func (receiver func(_ string, repo *git.Repository) any) any {
	if strings.EqualFold(specifier[0:5], "https") {
                return GetRemoteGitRepository (specifier)
	} else {
                return GetLocalGitRepository (specifier)
	}
}

func GetRemoteGitRepository(url string) func(receiver func(_ string, repo *git.Repository) any) any {
	return func(receiver func(_ string, repo *git.Repository) any) any {
		return CallCloningGitRepository("", "git", url, receiver)
	}
}

func GetLocalGitRepository(repodir string) func(receiver func(_ string, repo *git.Repository) any) any {
	return func(receiver func(_ string, repo *git.Repository) any) any {
		return CallOpeningGitRepository(repodir, receiver)
	}
}

To open a repository, we call RepositoryGetter(specifier) to get a getRepository function. Then we invoke the computed getRepository function on a receiver callback that accepts the local pathname and the repository:

  getRepository := RepositoryGetter(specifier)

  return getRepository(
         func (_ string, repo *git.Repository) any {
                 // resolve git hashes against the repository
                 ....
                 return nil
         })

If given a URL, this code will clone the repo into a temporary directory and open the cloned repo. If given a pathname, it will just open the repo at the pathname. It runs the callback and does the necessary cleanup when the callback returns.

The biggest point of confusion in this code (at least to me) are the type specifiers of the functions that manipulate the resource allocators. Static types don’t seem to mix well with continuation passing style.