LLM failures

I recently tried to get an LLM to solve two problems that I thought were well within its capabilities. I was suprised to find them unable to solve them.

Problem 1: Given a library of functions, re-order the function definitions in alphabetical order.

It can be useful to have the functions in alphabetical order so you can find them easily (assuming you are not constrained by any other ordering). The LLM was given a file of function definitions and was asked to put them in alphabetical order. It refused to do so, claiming that it was unable to determine the function boundaries because it had no model of the language syntax.

Fair enough, but a model of the language syntax isn't strictly necessary. Function definitions in most programming languages are easily identified: they are separated by blank lines, they start at the left margin, the body of the function is indented, the delimiters are balanced, etc. This is source code that was written by the LLM, so it is able to generate syntactically correct functions. It surprised me that it gave up so easily on the much simpler task of re-arranging the blocks of generated text.

Problem 2: Given the extended BNF grammar of the Go programming language, a) generate a series of small Go programs that illustrate the various grammar productions, b) generate a parser for the grammar.

This is a problem that I would have thought would be right up the LLM's alley. Although it easily generated twenty Go programs of varying complexity, it utterly failed to generate a parser that could handle them.

Converting a grammar to a parser is a common task, and I cannot believe that a parser for the Go language does not have several on-line examples. Furthemore taking a grammar as an input and producing a parser is a well-solved problem. The LLM made a quick attempt at generating a simple recursive descent parser (which is probably the easiest way to turn a grammar into a parser short of using a special tool), but the resultant parser could only handle the most trivial programs. When I asked the LLM to extend the parser to handle the more complex examples it had generated, it started hallucinating and getting lost in the weeds. I spent several hours redirecting the LLM and refining my prompts to help it along, but it never was able to make much progress beyond the simple parsing.

(I tried both Cursor with Claude Sonnet 4 and Gemini CLI with Gemini-2.5)

Both these problems uncovered surprising limitations to using LLMs to generate code. Both problems seem to me to be in the realm of problems that one would task to an LLM.

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.

Generating Images

“A Lisp Jedi wielding parentheses-shaped light sabers.”

It was suprisingly hard to persuade the image generator to generate a female Common Lisp alien. Asking for a female Lisp alien just produced some truly disturbing images. Evertually I uploaded the original alien and told it to add a pink bow and eyelashes, but it kept adding an extra arm to hold the flag. I had to switch to a different LLM model that eventually got it.

Avoiding Management

You can probably guess from prior blog posts that I am not a manager. I have made it clear in my last several gigs that I have no interest in management and that I only wish to be an individual contributor. I've managed before and I don't like it. The perqs - more control over the project, more money, a bigger office - don't even come close to the disadvantages - more meetings, less contact with the code, dealing with people problems, and so on.

The worst part of managing is dealing with people. In any group of people, there is some median level of performance, and by definition of the median, half the people are below that level. And one is at the bottom. He's the one who is always late, always had the bad luck, never checks in code, and so on. He struggles. Perhaps the right thing to do is to let him go, but I've been there. I've had jobs where the fit wasn't right and I wasn't performing at my best. I empathize. The last thing you need when you're in that position is the sword of Damocles hanging over your head. It's a horrible position to be in and I don't want to exacerbate it. I'll gladly forego the perqs of management to avoid being in the situation where I have to fire someone or even threaten to fire them.

But I do like to help people. I like to mentor and coach. I can usually keep the big picture in my head and I can help people find the places where they can be most effective. I'm pretty comfortable being a senior engineer, a technical lead, or an architect.

Scheduling is hard. I've got a rule of thumb for estimating how long a project will take. I take the best estimate I can get from the team, and then I triple it. If I think it will take two weeks, I tell upper management it will take six. It is almost always a realistic estimate - I'm not padding or sandbagging. When I get the time I ask for, I almost always deliver on time. But manegement rarely likes to hear the word "six" when they were hoping for "two".

There is always overhead that is hard to account for. You come in some day and find that your infrastructure is down and you have to spend a whole day fixing it. Or you need to coordinate with another team and it takes two days to get everyone on the same page. Or you discover that the API you were depending on hasn't really been implemented yet, and you have to spend a day or two writing a workaroud. These add up. As a contributor, I'm 100% busy developing and putting out fires, but managers only want to count the time spent developing.

The best managers I had didn't manage. They didn't assign work, or try to tell me what to do or try to direct the project. Instead, they acted as my off-board memory. I could rathole on some problem and when I solved it and came up for air, they would be there to remind me what I was in the middle of to begin with. They would keep track of the ultimate goals of the project and how we were progressing towards them, but they would not try to direct the activity. They trusted that I knew how to do my job. They acted as facilitators and enablers, not as managers. They would interface with upper management. They would handle the politics. They would justify the six weeks I asked for.

So I prefer to be an individual contributor and I avoid management like the plague. Programming makes me happy, and I don't need the stress of management.

Vibe Coding, A Kind of Success

Yeah, these posts about vibe coding are a bit tedious, but I got an interesting result. My hypothesis about vibe coding in Common Lisp was that there is simply not enough training data. But the most popular lisp is not Common Lisp but Emacs Lisp. It should have enough training data. So I tried vibe coding an application in Emacs Lisp. Again I used minesweeper as the example.

The model was Claude 3.7 Sonnet and I used VSCode in "Agent" mode. It generated a "minesweeper.el" file with 455 lines of code. There were some errors when I tried to run it, so I simply copied the error message into the AI prompt and let the VSCode agent fix it. After a couple of iterations, the code seems to work. It isn't the most polished minsweeper clone, but it is sort of a serviceable game.

So I guess the conclusion is that vibe coding works in Emacs Lisp. The result isn't all that slick, but what do expect from an Emacs game? This tends to support the hypothesis that you need ample training data.

Here is the code:

;;; minesweeper.el --- A Minesweeper game for Emacs -*- lexical-binding: t -*-

;; Author: AI Assistant
;; Keywords: games
;; Version: 1.0
;; Package-Requires: ((emacs "24.3"))

;;; Commentary:

;; This package implements the classic Minesweeper game for Emacs.
;; Use M-x minesweeper to start the game.

;;; Code:

(require 'cl-lib)

;;; Constants and Variables

(defvar minesweeper-mode-map
  (let ((map (make-sparse-keymap)))
    (define-key map (kbd "<down>") 'minesweeper-move-down)
    (define-key map (kbd "<up>") 'minesweeper-move-up)
    (define-key map (kbd "<left>") 'minesweeper-move-left)
    (define-key map (kbd "<right>") 'minesweeper-move-right)
    (define-key map (kbd "RET") 'minesweeper-reveal)
    (define-key map (kbd "SPC") 'minesweeper-flag)
    (define-key map (kbd "r") 'minesweeper-restart)
    (define-key map (kbd "q") 'minesweeper-quit)
    map)
  "Keymap for ‘minesweeper-mode'.")

(defgroup minesweeper nil
  "Minesweeper game for Emacs."
  :group 'games)

(defcustom minesweeper-board-width 10
  "Width of the Minesweeper game board."
  :type 'integer
  :group 'minesweeper)

(defcustom minesweeper-board-height 10
  "Height of the Minesweeper game board."
  :type 'integer
  :group 'minesweeper)

(defcustom minesweeper-mine-count 15
  "Number of mines on the Minesweeper board."
  :type 'integer
  :group 'minesweeper)

(defface minesweeper-hidden-face
  '((t :background "gray80" :box (:line-width -1 :color "gray50")))
  "Face for hidden cells."
  :group 'minesweeper)

(defface minesweeper-flag-face
  '((t :background "gray80" :foreground "red" :weight bold :box (:line-width -1 :color "gray50")))
  "Face for flagged cells."
  :group 'minesweeper)

(defface minesweeper-mine-face
  '((t :background "red" :foreground "black" :weight bold :box (:line-width -1 :color "gray50")))
  "Face for mine cells."
  :group 'minesweeper)

(defface minesweeper-empty-face
  '((t :background "gray95" :box (:line-width -1 :color "gray50")))
  "Face for empty revealed cells."
  :group 'minesweeper)

(defface minesweeper-number-1-face
  '((t :background "gray95" :foreground "blue" :weight bold :box (:line-width -1 :color "gray50")))
  "Face for cells with 1 adjacent mine."
  :group 'minesweeper)

(defface minesweeper-number-2-face
  '((t :background "gray95" :foreground "green" :weight bold :box (:line-width -1 :color "gray50")))
  "Face for cells with 2 adjacent mines."
  :group 'minesweeper)

(defface minesweeper-number-3-face
  '((t :background "gray95" :foreground "red" :weight bold :box (:line-width -1 :color "gray50")))
  "Face for cells with 3 adjacent mines."
  :group 'minesweeper)

(defface minesweeper-number-4-face
  '((t :background "gray95" :foreground "purple" :weight bold :box (:line-width -1 :color "gray50")))
  "Face for cells with 4 adjacent mines."
  :group 'minesweeper)

(defface minesweeper-number-5-face
  '((t :background "gray95" :foreground "maroon" :weight bold :box (:line-width -1 :color "gray50")))
  "Face for cells with 5 adjacent mines."
  :group 'minesweeper)

(defface minesweeper-number-6-face
  '((t :background "gray95" :foreground "turquoise" :weight bold :box (:line-width -1 :color "gray50")))
  "Face for cells with 6 adjacent mines."
  :group 'minesweeper)

(defface minesweeper-number-7-face
  '((t :background "gray95" :foreground "black" :weight bold :box (:line-width -1 :color "gray50")))
  "Face for cells with 7 adjacent mines."
  :group 'minesweeper)

(defface minesweeper-number-8-face
  '((t :background "gray95" :foreground "gray50" :weight bold :box (:line-width -1 :color "gray50")))
  "Face for cells with 8 adjacent mines."
  :group 'minesweeper)

(defvar minesweeper-buffer-name "*Minesweeper*"
  "Name of the Minesweeper game buffer.")

(defvar minesweeper-board nil
  "The game board.
Each cell is a list of the form (MINE-P REVEALED-P FLAGGED-P MINE-COUNT).")

(defvar minesweeper-game-over nil
  "Whether the current game is over.")

(defvar minesweeper-game-won nil
  "Whether the current game is won.")

(defvar minesweeper-flags-placed 0
  "Number of flags placed on the board.")

(defvar minesweeper-current-pos '(0 . 0)
  "Current cursor position as (ROW . COL).")

;;; Game Functions

(defun minesweeper-init-board ()
  "Initialize the game board."
  (setq minesweeper-board (make-vector minesweeper-board-height nil))
  (let ((board-cells (* minesweeper-board-width minesweeper-board-height))
        (mine-positions (make-vector (* minesweeper-board-width minesweeper-board-height) nil)))
    
    ;; Initialize all cells
    (dotimes (row minesweeper-board-height)
      (let ((row-vec (make-vector minesweeper-board-width nil)))
        (dotimes (col minesweeper-board-width)
          (aset row-vec col (list nil nil nil 0))) ; (mine-p revealed-p flagged-p mine-count)
        (aset minesweeper-board row row-vec)))
    
    ;; Randomly place mines
    (dotimes (i minesweeper-mine-count)
      (let ((pos (random board-cells)))
        (while (aref mine-positions pos)
          (setq pos (random board-cells)))
        (aset mine-positions pos t)
        (let* ((row (/ pos minesweeper-board-width))
               (col (% pos minesweeper-board-width))
               (cell (aref (aref minesweeper-board row) col)))
          (setcar cell t)))) ; Set mine-p to t
    
    ;; Calculate adjacent mine counts
    (dotimes (row minesweeper-board-height)
      (dotimes (col minesweeper-board-width)
        (unless (car (aref (aref minesweeper-board row) col)) ; Skip if it's a mine
          (let ((count 0))
            (dolist (r (list -1 0 1))
              (dolist (c (list -1 0 1))
                (unless (and (= r 0) (= c 0))
                  (let ((new-row (+ row r))
                        (new-col (+ col c)))
                    (when (and (>= new-row 0) (< new-row minesweeper-board-height)
                               (>= new-col 0) (< new-col minesweeper-board-width))
                      (when (car (aref (aref minesweeper-board new-row) new-col))
                        (setq count (1+ count))))))))
            (setcar (nthcdr 3 (aref (aref minesweeper-board row) col)) count))))))
  (setq minesweeper-game-over nil
        minesweeper-game-won nil
        minesweeper-flags-placed 0
        minesweeper-current-pos '(0 . 0)))

(defun minesweeper-get-cell (row col)
  "Get the cell at ROW and COL."
  (aref (aref minesweeper-board row) col))

(cl-defun minesweeper-reveal (row col)
  "Reveal the cell at ROW and COL."
  (interactive
   (if current-prefix-arg
       (list (read-number "Row: ") (read-number "Column: "))
     (list (car minesweeper-current-pos) (cdr minesweeper-current-pos))))
  
  (when minesweeper-game-over
    (message "Game over. Press 'r' to restart.")
    (cl-return-from minesweeper-reveal nil))
  
  (let* ((cell (minesweeper-get-cell row col))
         (mine-p (nth 0 cell))
         (revealed-p (nth 1 cell))
         (flagged-p (nth 2 cell))
         (mine-count (nth 3 cell)))
    
    (when flagged-p
      (cl-return-from minesweeper-reveal nil))
    
    (when revealed-p
      (cl-return-from minesweeper-reveal nil))
    
    (setcar (nthcdr 1 cell) t) ; Set revealed-p to t
    
    (if mine-p
        (progn
          (setq minesweeper-game-over t)
          (minesweeper-reveal-all-mines)
          (minesweeper-draw-board)
          (message "BOOM! Game over."))
      
      ;; Reveal adjacent cells if this is an empty cell
      (when (= mine-count 0)
        (dolist (r (list -1 0 1))
          (dolist (c (list -1 0 1))
            (unless (and (= r 0) (= c 0))
              (let ((new-row (+ row r))
                    (new-col (+ col c)))
                (when (and (>= new-row 0) (< new-row minesweeper-board-height)
                           (>= new-col 0) (< new-col minesweeper-board-width))
                  (minesweeper-reveal new-row new-col)))))))
      
      (minesweeper-check-win)))
  
  (minesweeper-draw-board))

(cl-defun minesweeper-flag (row col)
  "Toggle flag on cell at ROW and COL."
  (interactive
   (if current-prefix-arg
       (list (read-number "Row: ") (read-number "Column: "))
     (list (car minesweeper-current-pos) (cdr minesweeper-current-pos))))
  
  (when minesweeper-game-over
    (message "Game over. Press 'r' to restart.")
    (cl-return-from minesweeper-flag nil))
  
  (let* ((cell (minesweeper-get-cell row col))
         (revealed-p (nth 1 cell))
         (flagged-p (nth 2 cell)))
    
    (when revealed-p
      (cl-return-from minesweeper-flag nil))
    
    (if flagged-p
        (progn
          (setcar (nthcdr 2 cell) nil) ; Remove flag
          (setq minesweeper-flags-placed (1- minesweeper-flags-placed)))
      (setcar (nthcdr 2 cell) t) ; Add flag
      (setq minesweeper-flags-placed (1+ minesweeper-flags-placed))))
  
  (minesweeper-draw-board))

(defun minesweeper-reveal-all-mines ()
  "Reveal all mines on the board."
  (dotimes (row minesweeper-board-height)
    (dotimes (col minesweeper-board-width)
      (let* ((cell (minesweeper-get-cell row col))
             (mine-p (nth 0 cell)))
        (when mine-p
          (setcar (nthcdr 1 cell) t)))))) ; Set revealed-p to t

(defun minesweeper-check-win ()
  "Check if the game is won."
  (let ((all-non-mines-revealed t))
    (dotimes (row minesweeper-board-height)
      (dotimes (col minesweeper-board-width)
        (let* ((cell (minesweeper-get-cell row col))
               (mine-p (nth 0 cell))
               (revealed-p (nth 1 cell)))
          (when (and (not mine-p) (not revealed-p))
            (setq all-non-mines-revealed nil)))))
    
    (when all-non-mines-revealed
      (setq minesweeper-game-over t
            minesweeper-game-won t)
      (message "You win!")
      (minesweeper-flag-all-mines))))

(defun minesweeper-flag-all-mines ()
  "Flag all mines on the board."
  (dotimes (row minesweeper-board-height)
    (dotimes (col minesweeper-board-width)
      (let* ((cell (minesweeper-get-cell row col))
             (mine-p (nth 0 cell))
             (flagged-p (nth 2 cell)))
        (when (and mine-p (not flagged-p))
          (setcar (nthcdr 2 cell) t))))))

;;; UI Functions

(defun minesweeper-draw-cell (row col)
  "Draw the cell at ROW and COL."
  (let* ((cell (minesweeper-get-cell row col))
         (mine-p (nth 0 cell))
         (revealed-p (nth 1 cell))
         (flagged-p (nth 2 cell))
         (mine-count (nth 3 cell))
         (char " ")
         (face 'minesweeper-hidden-face)
         (current-p (and (= row (car minesweeper-current-pos))
                         (= col (cdr minesweeper-current-pos)))))
    
    (cond
     (flagged-p
      (setq char "F")
      (setq face 'minesweeper-flag-face))
     
     (revealed-p
      (cond
       (mine-p
        (setq char "*")
        (setq face 'minesweeper-mine-face))
       
       ((= mine-count 0)
        (setq char " ")
        (setq face 'minesweeper-empty-face))
       
       (t
        (setq char (number-to-string mine-count))
        (setq face (intern (format "minesweeper-number-%d-face" mine-count))))))
     
     (t
      (setq char " ")
      (setq face 'minesweeper-hidden-face)))
    
    (insert (propertize char 'face face))
    
    (when current-p
      (put-text-property (1- (point)) (point) 'cursor t))))

(defun minesweeper-draw-board ()
  "Draw the game board."
  (let ((inhibit-read-only t)
        (old-point (point)))
    (erase-buffer)
    
    ;; Draw header
    (insert (format "Minesweeper: %d mines, %d flags placed\n\n"
                    minesweeper-mine-count
                    minesweeper-flags-placed))
    
    ;; Draw column numbers
    (insert "  ")
    (dotimes (col minesweeper-board-width)
      (insert (format "%d" (% col 10))))
    (insert "\n")
    
    ;; Draw top border
    (insert "  ")
    (dotimes (col minesweeper-board-width)
      (insert "-"))
    (insert "\n")
    
    ;; Draw board rows
    (dotimes (row minesweeper-board-height)
      (insert (format "%d|" (% row 10)))
      (dotimes (col minesweeper-board-width)
        (minesweeper-draw-cell row col))
      (insert "|\n"))
    
    ;; Draw bottom border
    (insert "  ")
    (dotimes (col minesweeper-board-width)
      (insert "-"))
    (insert "\n\n")
    
    ;; Draw status
    (cond
     (minesweeper-game-won
      (insert "You won! Press 'r' to restart or 'q' to quit."))
     
     (minesweeper-game-over
      (insert "Game over! Press 'r' to restart or 'q' to quit."))
     
     (t
      (insert "Press 'r' to restart, 'q' to quit.\n")
      (insert "Use arrows to move, ENTER to reveal, SPACE to toggle flag.")))
    
    ;; Restore point or set to position of cursor
    (goto-char (point-min))
    (let ((result (text-property-search-forward 'cursor)))
      (if result
          (goto-char (prop-match-beginning result))
        (goto-char old-point)))))

;;; Movement Functions

(defun minesweeper-move-up ()
  "Move cursor up."
  (interactive)
  (let ((row (car minesweeper-current-pos))
        (col (cdr minesweeper-current-pos)))
    (when (> row 0)
      (setq minesweeper-current-pos (cons (1- row) col))
      (minesweeper-draw-board))))

(defun minesweeper-move-down ()
  "Move cursor down."
  (interactive)
  (let ((row (car minesweeper-current-pos))
        (col (cdr minesweeper-current-pos)))
    (when (< row (1- minesweeper-board-height))
      (setq minesweeper-current-pos (cons (1+ row) col))
      (minesweeper-draw-board))))

(defun minesweeper-move-left ()
  "Move cursor left."
  (interactive)
  (let ((row (car minesweeper-current-pos))
        (col (cdr minesweeper-current-pos)))
    (when (> col 0)
      (setq minesweeper-current-pos (cons row (1- col)))
      (minesweeper-draw-board))))

(defun minesweeper-move-right ()
  "Move cursor right."
  (interactive)
  (let ((row (car minesweeper-current-pos))
        (col (cdr minesweeper-current-pos)))
    (when (< col (1- minesweeper-board-width))
      (setq minesweeper-current-pos (cons row (1+ col)))
      (minesweeper-draw-board))))

;;; Game Management Functions

(defun minesweeper-restart ()
  "Restart the Minesweeper game."
  (interactive)
  (minesweeper-init-board)
  (minesweeper-draw-board))

(defun minesweeper-quit ()
  "Quit the Minesweeper game."
  (interactive)
  (kill-buffer minesweeper-buffer-name))

(define-derived-mode minesweeper-mode special-mode "Minesweeper"
  "Major mode for playing Minesweeper."
  (setq buffer-read-only t)
  (setq-local cursor-type nil)
  (buffer-disable-undo))

;;;###autoload
(defun minesweeper ()
  "Start a new game of Minesweeper."
  (interactive)
  (switch-to-buffer minesweeper-buffer-name)
  (minesweeper-mode)
  (minesweeper-init-board)
  (minesweeper-draw-board))

(provide 'minesweeper)
;;; minesweeper.el ends here

To run it, you can save the code to a file named "minesweeper.el" and load it in Emacs with M-x load-file. Then start the game with M-x minesweeper.

Dependency Injection with Thunks vs. Global Variables

Revision 2

A thunk (in MIT parlance) is a function that takes no arguments and returns a value. Thunks are simple, opaque objects. The only thing you can do with a thunk is call it. The only control you can exert over a thunk is whether and when to call it.

A thunk separates the two concerns of what to compute and when to compute it. When a thunk is created, it captures the lexical bindings of its free variables (it is, after all, just a lexical closure). When the thunk is invoked, it uses the captured lexical values to compute the answer.

There are a couple of common ways one might use a thunk. The first is to delay computation. The computation doesn't occur until the thunk is invoked. The second is as a weaker, safer form of a pointer. If the thunk is simply a reference to a lexical variable, then invoking the thunk returns the current value of the variable.

I once saw an article about Python that mentioned that you could create functions of no arguments. It went on to say that such a function had no use because you could always just pass its return value directly. I don't know how common this misconception is, but thunks are a very useful tool in programming.

Here is a use case that came up recently:

In most programs but the smallest, you will break the program into modules that you try to keep independent. The code within a module may be fairly tightly coupled, but you try to keep the dependencies between the modules at a minimum. You don't want, for example, the internals of the keyboard module to affect the internals of the display module. The point of modularizing the code is to reduce the combinatorics of interactions between the various parts of the program.

If you do this, you will find that your program has a “linking” phase at the beginning where you instantiate and initialize the various modules and let them know about each other. This is where you would use a technique like “depenedency injection” to set up the dependencies between the modules.

If you want to share data between modules, you have options. The crudest way to do this is to use global variables. If you're smart, one module will have the privilege of writing to the global variable and the other modules will only be allowed to read it. That way, you won't have two modules fighting over the value. But global variables come with a bit of baggage. Usually, they are globally writable, so nothing is enforcing the rule that only one module is in charge of the value. In addition, anyone can decide to depend on the value. Some junior programmer could add a line of code in the display handler that reads a global value that the keyboard module maintains and suddenly you have a dependency that you didn't plan on.

A better option is to use a thunk that returns the value you want to share. You can use dependency injection to pass the thunk to the modules that need it. When the module needs the value, it invokes the thunk. Modules cannot modify the shared value because the thunk has no way to modify what it returns. Modules cannot accidentally acquire a dependency on the value because they need the thunk to be passed to them explicitly upon initialization. The value that the thunk returns can be initialized after the thunk is created, so you can link up all the dependencies between the modules before you start computing any values.

I used this technique recently in some code. One thread sits in a loop and scrapes data from some web services. It updates a couple dozen variables and keeps them up to date every few hours. Other parts of the code need to read these values, but I didn't want to have a couple dozen global variables just hanging around flapping in the breeze. Instead, I created thunks for the values and injected them into the constructors for the URL handlers that needed them. When a handler gets a request, it invokes its thunks to get the latest values of the relevant variables. The values are private to the module that updates them, so no other modules can modify them, and they aren't global.

I showed this technique to one of our junior programmers the other day. He hadn't seen it before. He just assumed that there was a global variable. He couldn't figure out why the global variables were never updated. He was trying to pass global variables by value at initialization time. The variables are empty at that time, and updates to the variable later on have no effect on value that have already been passed. This vexed him for some time until I showed him that he should be passing a thunk that refers to the value rather than the value itself.

Vibe Coding Common Lisp Through the Back Door

I had no luck vibe coding Common Lisp, but I'm pretty sure I know the reasons. First, Common Lisp doesn't have as much boilerplate as other languages. When boilerplace accumulates, you write a macro to make it go away. Second, Common Lisp is not as popular language as others, so there is far less training data.

Someone made the interesting suggestion of doing this in two steps: vibe code in a popular language, then ask the LLM to translate the result into Common Lisp. That sounded like it might work, so I decided to try it out.

Again, I used "Minesweeper" as the example. I asked the LLM to vibe code Minesweeper in Golang. Golang has a lot of boilerplate (it seems to be mostly boilerplate), and there is a good body of code written in Golang.

The first problem was that the code expected assets of images of the minesweeper tiles. I asked the LLM to generate them, but it wasn't keen on doing that. It would generate a large jpeg image of a field of tiles, but not a set of .png images of the tiles.

So I asked the LLM to vibe code a program that would generate the .png files for the tiles. It took a couple of iterations (the first time, the digits in the tiles were too small to read), but it eventually generated a program which would generate the tiles.

Then I vibe coded minesweeper. As per the philosophy of vibe coding, I did not bother writing tests, examining the code, or anything. I just ran the code.

Naturally it didn't work. It took me the entire day to debug this, but there were only two problems. The first was that the LLM simply could not get the API to the image library right. It kept thinking the image library was going to return an integer error code, but the latest api returns an Error interface. I could not get it to use this correctly; it kept trying to coerce it to an integer. Eventually I simply discarded any error message for that library and prayed it would work.

The second problem was vexing. I was presented with a blank screen. The game logic seemed to work because when I clicked around on the blank screen, stdout would eventually print "Boom!". But there were no visuals. I spent a lot of time trying to figure out what was going on, adding debugging code, and so on. I finally discovered that the SDL renderer was simply not working. It wouldn't render anything. I asked the LLM to help me debug this, and I went down a rabbit hole of updating the graphics drivers, reinstalling SDL, reinstalling Ubuntu, all to no avail. Eventually I tried using the SDL2 software renderer instead of the hardware accelerated renderer and suddenly I had graphics. It took me several hours to figure this out, and several hours to back out my changes tracking down this problem.

Once I got the tiles to render, though, it was a working Minesweeper game. It didn't have a timer and mine count, but it had a playing field and you could click on the tiles to reveal them. It had the look and feel of the real game. So you can vibe code golang.

The next task was to translate the golang to Common Lisp. It didn't do as good a job. It mentioned symbols that didn't exist in packages that didn't exist. I had to make a manual pass to replace the bogus symbols with the nearest real ones. It failed to generate working code that could load the tiles. I looked at the Common Lisp code and it was a horror. Not suprisingly, it was more or less a transliteration of the golang code. It took no advantage of any Common Lisp features such as unwind-protect. Basically, each and every branch in the main function had its own duplicate copy of the cleanup code. Since the tiles were not loading, I couldn't really test the game logic. I was in no mood to debug the tile loading (it was trying to call functions that did not exist), so I left it there.

This approach, vibe in golang and then translate to Common Lisp, seems more promising, but with two phase of LLM coding, the probability of a working result gets pretty low. And you don't really get Common Lisp, you get something closer to fully parenthesized golang.

I think I am done with this experiment for now. When I have some agentic LLM that can drive Emacs, I may try it again.

Thoughts on LLMs

I've been exploring LLMs these past few weeks. There is a lot of hype and confusion about them, so I thought I'd share some of my thoughts.

LLMs are a significant step forward in machine learning. They have their limitations (you cannot Vibe Code in Common Lisp), but on the jobs they are good at, they are uncanny in their ability. They are not a replacement for anything, actually, but a new tool that can be used in many diverse and some unexpected ways.

It is clear to me that LLMs are the biggest thing to happen in computing since the web, and I don't say that lightly. I am encouraging everyone I know to learn about them, gain some experience with them, and learn their uses and limitations. Not knowing how to use an LLM will be like not knowing how to use a web browser.

Our company has invested in GitHub Copilot, which is nominally aimed at helping programmers write code, but if you poke around at it a bit, you can get access to the general LLM that underlies the code generation. Our company enables the GPT-4.1, Claude Sonnet 3.5, and Claude Sonnet 3.7 models. There is some rather complicated and confusing pricing for these models, and our general policy is to push people to use GPT-4.1 for the bulk of their work and to use Claude Sonnet models on an as-needed basis.

For my personal use, I decided to try a subscription to Google Gemini. The offering is confusing and I am not completely sure which services I get at which ancillary cost. It appears that there is a baseline model that costs nothing beyond what I pay for, but there are also more advanced models that have a per-query cost above and beyond my subscription. It does not help that there is a "1 month free trial", so I am not sure what I will eventually be billed for. (I am keeping an eye on the billing!) A subscription at around $20 per month seems reasonable to me, but I don't want to run up a few hundred queries at $1.50 each.

The Gemini offering appears to allow unlimited (or a large limit) of queries if you use the web UI, but the API incurs a cost per query. That is unfortunate because I want to use Gemini in Emacs.

Speaking of Emacs. There are a couple of bleeding edge Emacs packages that provide access to LLMs. I have hooked up code completion to Copilot, so I get completion suggestions as I type. I think I get these at zero extra cost. I also have Copilot Chat and Gemini Chat set up so I can converse with the LLM in a buffer. The Copilot chat uses an Org mode buffer whereas the Gemini chat uses a markdown buffer. I am trying to figure out how to hook up emacs as an LLM agent so that that the LLM can drive Emacs to accomplish tasks. (Obviously it is completely insane to do this, I don't trust it a bit, but I want to see the limitations.)

The Gemini offering also gives you access to Gemini integration with other Google tools, such as GMail and Google Docs. These look promising. There is also AIStudio in addition to the plain Gemini web UI. AIStudio is a more advanced interface that allows you to generate applications and media with the LLM.

I am curious about Groq. They are at a bit of a disadvantage in that they cannot integrate with Google Apps or Microsoft Apps as well as Gemini and Copilot can. I may try them out at some time in the future.

I encourage everyone to try out LLMs and gain some experience with them. I think we're on the exponential growth part of the curve at this point and we will see some amazing things in the next few years. I would not wait too long to get started. It will be a significant skill to develop.

Roll Your Own Bullshit

Many people with pointless psychology degrees make money by creating corporate training courses. But you don't need a fancy degree to write your own training course. They all follow the same basic format:

1. Pick any two axes of the Myers-Briggs personality test.
2. Ask the participants to answer a few questions designed to determine where they fall on those axes. It is unimportant what the answers are, only that there is a distribution of answers.
3. Since you have chosen two axes, the answers will, by necessity, fall into four quadrants. (Had you chosen three axes, you'd have eight octants, which is too messy to visualize.)
4. Fudge the median scores so that the quadrants are roughly equal in size. If you have a lot of participants, you can use statistical methods to ensure that the quadrants are equal, but for small groups, just eyeball it.
5. Give each quadrant a name, like “The Thinkers”, “The Feelers”, “The Doers”, and “The Dreamers”. It doesn't matter what you call them, as long as they sound good.
6. Assign to each quadrant a set of traits that are supposed to be broad stereotypes of people in that quadrant. Again, it doesn't matter what you say, as long as it sounds good. Pick at least two positive and two negative traits for each quadrant.
7. Assign each participant to a quadrant based on their answers.
8. Have the participants break into focus groups for their quadrants and discuss among themselves how their quadrant relates to the other quadrants.
9. Break for stale sandwiches and bad coffee.
10. Have each group report back to the larger group, where they restate what they discussed in their focus groups.
11. Conclude with a summary of the traits of each quadrant, and how they relate to each other. This is the most important part, because it is where you can make up any bullshit you want, and nobody will be able to call you on it. Try to sound as if you have made some profound insights.
12. Have the participants fill out a survey to see how they feel about the training. This is important, because it allows you to claim that the training was a success.
13. Hand out certificates of completion to all participants.
14. Profit.

It is a simple formula, and it is apparently easy to sell such courses to companies. I have attended several of these courses, and they all follow this same basic formula. They are all a waste of time, and they are all a scam.

More Bullshit

Early on in my career at Google I attended an offsite seminar for grooming managers. We had the usual set of morning lectures, and then we were split into smaller groups for discussion. The topic was “What motivates people?” Various answers were suggested, but I came up with these four: Sex, drugs, power, and money.

For some reason, they were not happy with my answer.

They seemed to think that I was not taking the question seriously. But history has shown that these four things are extremely strong motivations. They can motivate people to do all sorts of things they wouldn't otherwise consider. Like, for example, to betray their country.

If you look for them, you can find the motivations I listed. They are thinly disguised, of course. Why are administrative assistants so often attractive young women? Is Google's massage program completely innocent? Are there never any “special favors”? The beer flows pretty freely on Fridays, and the company parties were legendary. Of course there are the stock options and the spot bonuses.

I guess I was being too frank for their taste. They were looking for some kind of “corporate culture” answer, like “team spirit” or “collaboration”. I was just being honest.

I soon discovered that the true topic of this three day offsite seminar was bullshit. It was a “course” dreamed up by business “psychologists” and peddled to Silicon Valley companies as a scam. If you've ever encountered “team building” courses, you'll know what I mean. It is a lucrative business. This was just an extra large helping.

They didn't like my frankness, and I didn't see how they could expect to really understand what motivates people if they were not going to address the obvious. They thought I wasn't being serious with my answer, but it was clear that they weren't going to be seriously examining the question either.

So I left the seminar. I didn't want to waste my time listening to corporate psychobabble. My time was better spent writing code and engineering software. I returned to my office to actually accomplish some meaningful work. No doubt I had ruined any chance of becoming a big-wig, but I simply could not stomach the phoniness and insincerity. I was not going to play that game.

Management = Bullshit

The more I have to deal with management, the more I have to deal with bullshit. The higher up in the management chain, the denser the bullshit. Now I'm not going to tell you that all management is useless, but there is a lot more problem generation than problem solving.

Lately I've been exploring the potentials of LLMs as a tool in my day-to-day work. They have a number of technical limitations, but some things they excel at. One of those things is generating the kinds of bullshit that management loves to wallow in. Case in point: our disaster recovery plan.

Someone in management got it into their head that we should have a formal disaster recovery plan. Certainly this is a good idea, but there are tradeoffs to be made. After all, we have yearly fire drills, but we don't practice "duck and cover" or evacuation in case of flooding. We have a plan for what to do in case of a fire, but we don't have a plan for what to do in case of a zombie apocalypse. But management wants a plan for everything, no matter how unlikely.

Enter the LLM. It can generate plans like nobody's business. It can generate a plan for what to do in case of a fire, a meteor strike, or a zombie apocalypse. The plans are useless, naturally. They are just bullshit. But they satisfy management's jonesing for plans, and best of all, they require no work on my part. It saved me hours of work yesterday.

Purchasing White Elephants

As a software engineer, I'm constantly trying to persuade management to avoid doing stupid things. Management is of the opinion that because they are paying the engineers anyway, the software is essentially free. In my experience, bespoke software is one of the most expensive things you can waste money on. You're usually better off setting your money on fire than writing custom software.

But managers get ideas in their heads and it falls upon us engineers to puncture them. I wish I were less ethical. I'd just take the money and spend it as long as it kept flowing. But I wouldn't be able to live with myself. I have to at least try to persuade them to avoid the most egregious boondoggles. If they still insist on doing the project, well, so be it.

I'm absolutely delighted to find that these LLMs are very good at making plausible sounding proposals for software projects. I was asked about a project recently and I just fed the parameters into the LLM and asked it for an outline of the project, estimated headcount, time, and cost. It suggested we could do it in 6 months with 15 engineers at a cost of $3M. (I think it was more than a bit optimistic, frankly, but it was a good start.) It provided a phased breakdown of the project and the burn rate. Management was curious about how long it would take 1 engineer and the LLM suggested 3-6 years.

Management was suitably horrified.

I've been trying to persuade them that the status quo has been satisfying our needs, costs nothing, needs no engineers, and is ready today, but they didn't want to hear it. But now they are starting to see the light.

It Still Sucks

Don’t get me wrong. I”m not saying that the alternatives are any better or even any different.

Unix has been around more than forty years and it is still susceptible to I/O deadlock when you try to run a subprocess and stream input to it and output from it. The processes run just fine for a while, then they hang indefinitely waiting for input and output from some buffer to synchronize.

I’m trying to store data in a database. There aren't any good database bindings I could find, so I wrote a small program that reads a record from stdin and writes it to the database. I launch this program from Common Lisp and write records to the input of the program. It works for about twenty records and then hangs. I've tried to be careful to flush and drain all streams from both ends, to no avail.

I have a workaround: start the program, write one record, and quit the program. This doesn’t hang and reliably writes a record to the database, but it isn’t fast and it is constantly initializing and creating a database connection and tearing it back down for each record.

You'd think that subprocesses communicating via stream of characters would be simple.

Senior Programmers Have Nothing to Fear From AI

I have, through experimentation, discovered that vibe coding in Common Lisp is not effective. But other kinds of AI coding are highly effective and have been saving me hours of work. AI is not going to replace senior programmers, but it will take over many of the tasks that junior programmers do. I’m not worried about my job, but were I a junior programmer, I’d be concerned.

Part of my job as a senior programmer is to identify tasks that are suitable for junior programmers. These tasks have certain properties:

• They are well-defined.
• They are repetitive, making them suitable for development of a program to carry them out.
• They are not too difficult, so that a junior programmer can complete them with a little help.
• They have a clear acceptance criteria, so that the junior programmer can tell when they are done.
• They have a clear abstraction boundary so that integrating the code after the junior programmer is done is not too difficult.

But because junior programmers are human, we have to consider these factors as well:

• The task must not be too simple or too boring.
• The task must be written in a popular programming language. Junior programmers don’t have the inclination to learn new programming languages.
• The task must not be time critical because junior programmers are slow.
• The task should not be core critical to the larger project. Junior programmers write crappy code, and you don’t want crappy code at the heart of your project.

Oftentimes, I find some tasks that fits many of these criteria, but then I find that I can do it myself better and faster than a junior programer could.

AI coding can handle many of the tasks that I would otherwise assign to a junior programmer. It works best when the task is well defined, not too difficult, and written in a popular language. It doesn’t care if the task is boring and repetitive. AI coding is much faster than a junior programmer, and it writes code that tends to follow standard conventions. If you can specify good abstraction barriers, the AI can do a good job of coding to them. While AI coding is not perfect, neither are junior programmers. In either case, a senior programmer needs to carefully review the code.

AI coding is not going to replace senior programmers. The AI will not generate code without a prompt, and the better the prompt, the better the generated code. Senior programmers can take a large program and break it down into smaller tasks. They can create definitions of the smaller tasks and define the acceptance criteria, the API, and the abstractions to be used. They can carefully and precisely craft the prompts that generate the code. Senior programmers are needed to drive the AI.

Which leads to the question of where senior programmers will come from if junior programmers are no longer needed. I don’t have a good answer for this.

Get Over It (ai content)

I'm tired of people complaining about all the parentheses in Lisp, so I told Gemini to vent for me. This came out pretty good.

I suppose I'm guilty of contributing to the glut of AI slop, but while the text and tone are generated, the core idea and sentiment is mine, so it isn’t pure slop.

---

Alright, let's drop the hand-holding. You — yes, you — the one still whimpering about the parentheses in Lisp. It's time someone told you bluntly: Get over it.

Your constant refrain about "too many parentheses" isn't some profound insight into language design; it's a confession of intellectual laziness. It screams that you encountered something different, something that didn't conform to the aesthetic you were spoon-fed, and you threw up your hands rather than engage your brain.

Are parentheses really an insurmountable cognitive barrier? Are matching pairs of symbols truly beyond your capacity to track? Let's be honest. The core issue isn't difficulty; it's unfamiliarity coupled with a stubborn refusal to adapt. You've decided what code ought to look like, and anything else is dismissed as "hard" or "ugly" without genuine effort.

Thousands upon thousands of programmers — people with brains presumably no bigger than yours — have not only managed Lisp's syntax but have thrived with it. They've built complex, powerful systems. They didn't possess some secret anti-parenthesis superpower; they simply possessed the willingness to learn and adapt. They saw the structure, the consistency, the power behind the syntax, instead of getting stuck on the superficial shape of the characters.

Your complaint isn’t about usability; it’s about preference, and a remarkably shallow one at that. It’s like refusing to read a brilliant novel because you don’t like the font. It demonstrates a lack of curiosity, an unwillingness to look past the surface.

So, here's the unvarnished truth: The parentheses aren't the problem. Your rigid thinking is. Your demand that every language cater to your pre-existing biases is.

Stop whining. Stop making excuses based on trivial syntax. Either put in the minimal mental effort required to see the structure beneath the curves, recognise the direct representation of the abstract syntax tree, and understand why it is the way it is – or don't. But don't pretend your aesthetic preference is a legitimate technical critique.

The Lisp world isn't waiting for you to overcome your parenthesis phobia. It's moving on, building things, leveraging a unique and powerful paradigm. You can either engage your intellect and join in, or you can stay on the sidelines complaining about the punctuation.

Frankly, it's time to grow up and get over the parentheses.

Lisp Debugger Wins

I'm gathering statistics from thousands of pull requests in GitHub. I wrote a little Lisp program to do that. It's taking a long time because it has to make a lot of API calls to GitHub and the calls are rate limited.

After about half an hour, I got an unexpected error. A user who made the pull request I was looking at had deleted their account. No problem. I used the Lisp debugger to walk up the stack to a convenient frame and returned NIL from that frame, causing that particular PR to be skipped. The program continued running from where it left off. I didn't have to restart from the beginning and lose a half hour of work.

The Lisp debugger for the win!

Well This Was Interesting

I was playing with notebooklm.google.com and for fun I entered a few of my recent blog posts. I asked it to generate a conversation. The AI generated what sounds a lot like a podcast discussing my blog. One host sounds a bit like Mike Rowe. They get a lot of the detail right, but there are a couple of glaring mistakes. (Read - EVIL - Print - Loop) I suppose I am contributing to the soup of AI slop, but I was suprised at how natural this sounds. Podcast

I also tried giving it some text files about Tic Tac Toe representations. It generated a remarkably good “Deep Dive” that really sounds as if it has an understanding of the text: Deep Dive

There are some “tells” that this is AI and not human, but I wouldn't be surprised if this could fool the average layman. In a few years, it’s going to be really hard to detect, though.

Stupid reader tricks

Here are some stupid reader tricks for Lisp. I've tested them on SBCL, and they are of questionable portability and utility.

Run Shell Commands from the Lisp Prompt

(set-macro-character #\! 
    (lambda (stream char)
      (declare (ignore stream char))
      (uiop:run-program (read-line stream) :output *standard-output*))
    t)

> !ls -als
total 4068
   4 drwxr-x--- 21 jrm  jrm     4096 Apr 18 06:42 .
   4 drwxr-xr-x  4 root root    4096 Mar 22 17:27 ..
1900 -rwx--x--x  1 jrm  jrm  1940604 Apr 17 19:10 .bash_history
   4 -rw-r--r--  1 jrm  jrm      220 Mar 19 12:16 .bash_logout
   8 -rw-r--r--  1 jrm  jrm     4961 Apr  1 11:13 .bashrc
   4 drwx------  6 jrm  jrm     4096 Mar 21 07:52 .cache
   0 lrwxrwxrwx  1 jrm  jrm       51 Mar 24 05:20 .config -> /mnt/c/Users/JosephMarshall/AppData/Roaming/.config
   0 lrwxrwxrwx  1 jrm  jrm       50 Mar 26 03:12 .emacs -> /mnt/c/Users/JosephMarshall/AppData/Roaming/.emacs
   4 drwx------  6 jrm  jrm     4096 Apr 17 12:13 .emacs.d
      ... etc ...

>

Make λ an alias for lambda

(set-macro-character #\λ (lambda (stream char) (declare (ignore stream char)) 'cl:lambda) t)

> ((λ (x) (+ x 4)) 3)
7

If you do this you might want to add a print function for the lambda symbol:

(defmethod print-object ((obj (eql 'cl:lambda)) stream) ;; doubt this is portable
  (format stream "λ"))

> '(λ (x) (+ x 4))
(λ (x) (+ x 4))

> (symbol-name (car *))
"LAMBDA"

DES Machine

The MIT CADR Lisp Machine had a number of static RAMs that were used in the processor for various things such as state machines and register files. The core parts of the LMI Lambda Lisp Machine were similar to the CADR (similar enough that they could run the same microcode) but technology had advanced such that the static RAM chips were typically double the size of the CADR's. The LMI Lambda thus had twice as many registers as the CADR, but because there weren't any extra bits in the instruction set, you couldn't address half of them. The extra address bit from the RAM was wired to a status register. So the LMI Lambda had, in effect, two banks of registers which you could swap between by toggling the bit in the status register. This was not normally used — the microcode would set the bit to zero and leave it there.

A friend of mine was interested in security and he had written a high performance version of the encryption algorithm used by Unix to encrypt passwords. He was experimenting with dictionary attacks against passwords and one bottleneck was the performance of the password encryption algorithm.

It occurred to me that I could store the DES S-boxes in the alternate register bank of the LMI Lambda. With some special microcode, I could turn an LMI Lambda into a DES machine that could churn through a dictionary attack at a high speed. I added a special Lisp primitive that would swap the register banks and then run several hundred rounds of the DES algorithm before swapping back and returning to Lisp. Then I wrote a Lisp program that would feed a dictionary into the DES primitives when the processor was idle.

I was able to discover a few passwords this way, but I was more interested in the proof of concept that the actual results. A microcoded DES machine would work, but you'd get better performance out of dedicated hardware.

Mea Culpa

OH NO! There's something wrong on the Internet!

It is often me. Mea culpa. Mea maxima culpa. I'm only human.

But this is a blog, not a reference manual. I use it to organize my thoughts, get things off my chest, provoke discussion, maybe entertain a few fellow hackers, and show others how much fun I'm having playing with computers. Accuracy and precision aren't the primary objectives although I try not to be egregiously incorrect.

Mostly I see people misinterpreting something I say casually. I gloss over some details that some find important but I consider boring. I make the first-order error of assuming everyone has the same backgroud as I do and will interpret what I say in the way I had in mind. Clearly this isn't the case, yet I persist in thinking this way. Oh well.

I'll try to correct errors that are brought to my attention and will elaborate things in more detail if asked, but if my blog irritates you with its broad generalizations, inattention to detail, omission of specifics, and things that are just plain wrong, why are you reading it?

Emacs and Lisp

The first editor I learned how to use was TECO on a line printer. You’d print the line of code you were on, then you’d issue commands to move the cursor around. You tried to avoid printing the line because that would be wasting paper. So you’d move the cursor around blind until you thought you got it to where you wanted, and then you’d start inserting characters. When you thought you had it, you’d print out the edited line.

Another undergrad saw me struggling with this and asked why I wasn’t using vi. I had never heard of vi and I was amazed that you could view the code on the screen and move your cursor around visually before going into insert mode and adding text. With vi I was orders of magnitude more productive than with TECO.

When I came to the ’tute in the early 80s, I found that computer accounts were only routinely issued to students taking computer science courses. I hadn’t decided on a computer science major, so I didn’t have an account. However the Student Information Processing Board would give out a Multics account to interested students, so I signed up for that. The Multics terminal was in the basement and it had a dial up connection with an acoustically coupled modem: two rubber cups that the handset would cradle in.

Everyone at the AI Lab used a home grown editor called emacs, and there was a Multics port. I abandoned vi and learned emacs. The paradigm was different, but I didn’t see one as superior to the other. When I declared computer science as my major, I got an account at the AI Lab on the Decsystem 20 machine. The editor was TECO with the editor macros (emacs) package loaded.

When I took S&ICP, we had a lab with HP9836 “Chipmunks” running MIT Scheme. The Chipmunks were PCs, not time-shared, and each acted as its own Scheme machine, complete with an emacs clone for editing the code.

At the AI Lab, there were a couple of machines running ITS, the Incompatible Timesharing System. You could run Maclisp on them, but Maclisp was such a pig, using over a megabyte of RAM, that a couple of instances of Maclisp would bring the machine to its knees. The Lab had developed the Lisp Machine, a single user computer that would run ZetaLisp (the successor to Maclisp). In addition to Lisp, the Lisp machine ran the ZWEI editor. Zwei Was Eine Initially, and Eine Is Not Emacs, but rather an emacs clone written in Zetalisp.

ZWEI was integrated with the Lisp environment. You could insert Lisp objects in the ZWEI editor and their printed representation would appear in the edited text. The printed represention was mouse sensitive and had its own context menu.

If you weren’t using a Lisp Machine, your options were Unipress Emacs and Gosling Emacs which you could run on this new OS called “Unix”

Around this time (in the late 80s) a hacker named Stallman decided to write a new OS. His first task was to write an editor and he decided on a new version of Emacs written in its own Lisp dialect.

If you wanted to use Lisp, you interacted with it via Emacs.

These days, I use GNU Emacs and I load up the sly package. Sly is a slime fork and it turns GNU Emacs into an IDE for a Lisp running in another process. The interface gives you much of what you used to get when using ZWEI on the Lisp machine. You can evaluate subexpressions, macroexpand and compile programs, gather output, and run the Lisp debugger from within GNU emacs.

Emacs and Lisp co-evolved at MIT and Emacs has always been used as a front-end to Lisp. I’ve never gone back to vi, and when I’ve had to use it I’ve found it frustrating (but this is because I have forgotten everything about how to use it).

I understand that some people find Emacs impossible to use and have a strong preference for vi. Is the experience of hacking Lisp in vi any good?

Writing Your OS in Lisp

How to write an OS in Lisp is beyond the scope of a single post in this blog, and I don‘t have a series prepared. However, I can drop some hints of how you can overcome some problems.

If you are writing your OS in Lisp, it helps to have some idea of how Lisp compiles your program to machine code. The disassemble function prints out the disassembly of a Lisp function. It is obviously implementation dependent.

The inner dispatch of the compiler, when it is called, will be given a target location in which to deposit the result of evaluating the compiled expression. The target location given to the compiler will typically be a register, the top of stack, a fixed offset within the stack, or a global memory location, that sort of thing. The compiler should generate code that ultimately results in the value of the expression ending up in the target location.

A number of Lisp primitive functions can be implemented as a single CPU instruction. (Alternatively, you can create quirky Lisp “CPU subprimitive” functions out of each of the non-jump CPU instructions.) When compiling a function call to such a subprimitive function, the compiler emits code that fetches each argument from its location and places the value in a register, and then emits the single CPU instruction that the subprimitive consists of. It arranges for the result of the CPU instruction to be placed in the target location. What I’m describing here is basically what is known as a “compiler intrinsic” in other languages.

If you have a tree of compound expressions, each of which is one of these CPU subprimitive functions, the compiler will assign locations to all the intermediate computed values, determine an order in which to compile the primitives (linearized left to right), and then emit linear code that carries out the primitive operations. If all your code consists of calls to CPU primitives, then the compiler can generate straight-line assembly code CPU instructions. The compiler in this case only acts as a register allocator. From here, you can bootstrap yourself to a set of primitive procedures each of which is written in straght-line assembly code.

When writing an OS, you occasionally run into places where you want a very specific sequence of CPU instructions. You have a couple of options: some Lisp compilers offer a way to insert literal assembly code instructions in the compiled code instruction stream in a progn like manner. Naturally such code is “unsafe”, but it nicely solves the problem where you need hand-crafted assembly code in your solution. The other solution is to write the code as a compound expression of CPU primitives and let the compiler sort out the register allocation.

Bloom Filter

This is the response time of the Google Mini search appliance on several thousand queries. There is an odd spike at 300 ms. A number of machines were taking exactly 300 ms to respond regardless of the query.

I soon tracked this down to the spell server. This is the microservice that puts “Did you mean foobar?” on the top of the page when you spell something wrong. The results page generator will wait up to 300 ms for the spell server to come up with its suggestions and then it will proceed without it. What appeared to be happening is that the spell server was giving a “no go” signal to the page generator at the beginning of page composition. The results page generator would then wait for the spell server to make a suggestion. The spell server would invariably take too long, so after 300 ms, the results page generator would time out and ship the page as is. This happened often enough that it showed up as a blip in the performance graph.

The spell server was based on a Bloom filter. A Bloom filter is a variation on a hash table where you only record that a bucket exists, but not its contents. A Bloom filter will quickly and reliably tell you if an entry is not in the table, but only probabilistically tell you if an entry is in the table. Bloom filters rely on having a good hash function and having a mostly empty hash table. If the hash table is mostly empty, the Bloom filter will usually end up hitting an empty bucket and returning false immediately.

A quick look at the spellserver showed that the Bloom filter was almost always getting a hit, this would send the “no go” signal and trigger a slow lookup to find the misspelled word. The problem was that the Bloom filter was too small. It had too few buckets, so most buckets had an entry. Words would always get a hit in the Bloom filter and so the search appliance thought that all words were misspelled.

I adusted the size of the Bloom filter, giving it several million buckets. Now correctly spelled words would likely hit an empty bucket and the filter would give a “go” signal to the response page generator. Problem solved, and the spike at 300 ms went away.

Why I Program in Lisp

Lisp is not the most popular language. It never was. Other general purpose languages are more popular and ultimately can do everything that Lisp can (if Church and Turing are correct). They have more libraries and a larger user community than Lisp does. They are more likely to be installed on a machine than Lisp is.

Yet I prefer to program in Lisp. I keep a Lisp REPL open at all times, and I write prototypes and exploratory code in Lisp. Why do I do this? Lisp is easier to remember, has fewer limitations and hoops you have to jump through, has lower “friction” between my thoughts and my program, is easily customizable, and, frankly, more fun.

Lisp's dreaded Cambridge Polish notation is uniform and universal. I don't have to remember whether a form takes curly braces or square brackets or what the operator precedency is or some weird punctuated syntax that was invented for no good reason. It is (operator operands ...) for everything. Nothing to remember. I basically stopped noticing the parenthesis 40 years ago. I can indent how I please.

I program mostly functionally, and Lisp has three features that help out tremendously here. First, if you avoid side effects, it directly supports the substitution model. You can tell Lisp that when it sees this simple form, it can just replace it with that more complex one. Lisp isn't constantly pushing you into thinking imperatively. Second, since the syntax is uniform and doesn't depend on the context, you can refactor and move code around at will. Just move things in balanced parenthesis and you'll pretty much be ok.

Third, in most computer languages, you can abstract a specific value by replacing it with a variable that names a value. But you can perform a further abstraction by replacing a variable that names a quantity with a function that computes a quantity. In functional programming, you often downplay the distinction between a value and a function that produces that value. After all, the difference is only one of time spent waiting for the answer. In Lisp, you can change an expression that denotes an object into an abtraction that computes an object by simply wrapping a lambda around it. It's less of a big deal these days, but properly working lambda expressions were only available in Lisp until recently. Even so, lambda expressions are generally pretty clumsy in other languages.

Functional programming focuses on functions (go figure!). These are the ideal black box abstraction: values go in, answer comes out. What happens inside? Who knows! Who cares! But you can plug little simple functions together and get bigger more complex functions. There is no limit on doing this. If you can frame your problem as "I have this, I want that", then you can code it as a functional program. It is true that functional programming takes a bit of practice to get used to, but it allows you to build complex systems out of very simple parts. Once you get the hang of it, you start seeing everything as a function. (This isn't a limitation. Church's lambda calculus is a model of computation based on functional composition.)

Lisp lets me try out new ideas as quickly as I can come up with them. New programs are indistinguishable from those built in to the language, so I can build upon them just as easily. Lisp's debugger means I don't have to stop everything and restart the world from scratch every time something goes wrong. Lisp's safe memory model means that bugs don't trash my workspace as I explore the problem.

The REPL in lisp evaluates expressions, which are the fundamental fragments of Lisp programs. You can type in part of a Lisp program and see what it does immediately. If it works, you can simply embed the expression in a larger program. Your program takes shape in real time as you explore the problem.

Lisp's dynamic typing gives you virtually automatic ad hoc polymorphism. If you write a program that calls +, it will work on any pair of objects that have a well-defined + operator. Now this can be a problem if you are cavalier about your types, but if you exercise a little discipline (like not defining + on combinations of strings and numbers, for example), and if you avoid automatic type coercion, then you can write very generic code that works on a superset of your data types. (Dynamic typing is a two-edged sword. It allows for fast prototyping, but it can hide bugs that would be caught at compile time in a statically typed language.)

Other languages may share some of these features, but Lisp has them all together. It is a language that was designed to be used as a tool for thinking about problems, and that is the fun part of programming.

Lisp Programs Don't Have Parentheses

Lisp programs don't have parentheses — they are made of nested linked lists. The parentheses only exist in the printed representation — the ASCII serialization — of a Lisp program. They tell the Lisp reader where the nested lists begin and end. Parenthesis are the contour lines in the topographic map of your Lisp program.

The parentheses allow other programs, such as editors, to manipulate the program text as a tree structure. You can use the parenthesis to determine the structure of the Lisp program without needing a complicated parser. You only need to know how to count the opening and closing parentheses to determine the boundaries of expressions in the text of a program. You don't need an IDE or a treesitter process running a language parser in the background to make sense of the lexical structure of the program.

This makes refactoring of a Lisp program easy because the expression boundaries are explicitly marked. Additionally, Lisp expressions do not have a dependency on the context in which they appear — Lisp expressions don't change form when you move them around. Contrast this with, for example, expression sequences in C. In C, in a statement context, expressions are terminated by semicolons, but in an expression context, they are separated by commas. If you move a sequence of expressions in C from statement to expression context, you also have to change the semicolons to commas.

As another example, in C and Java, conditional statements follow the if … else … form, but conditional expressions use the infix ternary ?: operator, so moving conditionals around may require a substantial edit. In a language without ternary conditionals, like Go and Rust, wrapping a subexpression with a conditional may require large rewrites of the surrounding code.

These days, people use complex IDEs to write and refactor code. But still, you are dependent upon what the IDE provides. A refactoring that is not supported by the IDE has to be done manually. But Lisp just lets you move expressions around as text. No muss, no fuss. You can even use a simple text editor to do it.

Are You Tail Recursive?

I was trying to write a procedure that would test whether tail recursion was enabled or not. It turns out that this is semi-decidable. You can only tell if it is not tail recursive by blowing the stack, but you can never be sure that somebody didn’t make a really, really big stack.

But for the sake of argument, let’s say assume that 2²⁸ recursive calls is enough to blow the stack. Also, let’s assume that the system will correctly signal an error and be able to recover from the blown stack once it is unwound. Then we can test for tail recursion as follows:

(defconstant +stack-test-size+ (expt 2 28))

(defun test-self-tail-recursion (x)
  (or (> x +stack-test-size+)
      (test-self-tail-recursion (1+ x))))

(defun test-mutual-tail-recursion (x)
  (or (> x +stack-test-size+)
      (test-mutual-tail-recursion-1 (1+ x))))

(defun test-mutual-tail-recursion-1 (x)
  (or (> x +stack-test-size+)
      (test-mutual-tail-recursion (1+ x))))

(defun self-tail-recursive? ()
  (ignore-errors (test-self-tail-recursion 0)))

(defun mutually-tail-recusive? ()
  (ignore-errors (test-mutual-tail-recursion 0)))

Naturally, your optimize settings are going to affect whether or not you have tail recursion enabled, and even if this code says it is enabled, it doesn’t mean that a different compilation unit compiled at a different time with different optimizations would be tail recursive as well. But if you run this in your default environment and it returns NIL, then you can be pretty sure your default is not tail recursive. If it returns T, however, then there are at least some conditions under which your system is tail recursive.

Use of certain features of Common Lisp will “break” tail recursion, for example special variable binding, multiple-value-bind, unwind-protect, and catch, and basically anything that marks the stack or dynamically allocates on the stack. If control has to return to the current function after a call, then it is not tail recursive, but if control can return directly to the caller of the current function, then the compiler should be able to make a tail recursive call.

Most, but not all, Common Lisp implementations can be configured to enable tail recursion, and it is usually possible to disable it if desired. If you want tail recursion, but your implementation cannot provide it, you are SOL. If you don’t want tail recursion, but your implementation provides it by default, there are a number of things you can do to disable it. Usually, you can set the debugging options to retain every stack frame, or you can set the debug optimization to disable tail recursion. If the recursive call is not in tail position, then it is incorrect to tail call it, so you can disable tail recursion by moving the recursive call out of tail position. For example, you could write a without-tail-call macro:

(defmacro without-tail-call (form)
  (let ((value (gensym)))
    `((lambda (,value) ,value) ,form)))

;; Use like this:

(defun factorial (x &optional (acc 1))
  (if (zerop x)
      (progn (cerror "Return the factorial" "Computed a factorial")
             acc)
      (without-tail-call
        (factorial (1- x) (* acc x)))))

Running this program will drop us into the debugger because of the cerror and we can inspect the stack.

> (factorial 100)

Computed a factorial
   [Condition of type SIMPLE-ERROR]

Restarts:
 0: [CONTINUE] Return the factorial
 1: [RETRY] Retry SLY mREPL evaluation request.
 2: [*ABORT] Return to SLY’s top level.
 3: [ABORT] abort thread (#<THREAD tid=179 "sly-channel-1-mrepl-remote-1" RUNNING {1000BA8003}>)

Backtrace:
 0: (FACT 0 2432902008176640000)
 1: (FACT 1 2432902008176640000)
 2: (FACT 2 1216451004088320000)
 3: (FACT 3 405483668029440000)
 4: (FACT 4 101370917007360000)
 5: (FACT 5 20274183401472000)
 6: (FACT 6 3379030566912000)
  ...

As requested, each recursive calls pushes a stack frame.

But what if the compiler “optimizes” ((λ (x) x) (foo)) to simply be (foo)? That is a questionable “optimization”. Lisp is a call-by-value language, meaning that the arguments to a function are fully evaluated before the function is applied to them. The call to (foo) should be fully evaluated before applying (λ (x) x) to it. The “optimization” essentially treats (foo) as unevaluted and then tail calls it after applying the lambda expression. This is call-by-name evaluation. While anything is possible, an “optimization” that sometimes changes the function call semantics from call-by-value to call-by-need is dubious.

When Laymen Try to be Programmers

When I worked on Google Offers (a Groupon clone), we had a user interaction problem. When a user purchased an item, there were three important steps that we wanted to acknowledge:

1. When Google recieves an order. The user should get positive feedback that the order was recognized. If the user doesn’t get this, they will either re-submit the order, or be surprised when the order is fulfilled. The order is placed on a queue.
2. When Google processes an order from the queue. The user should get positive feedback that Google is working on fulfilling the order. Usually, an order is fulfilled reasonably quickly, but there are situations where critical systems are unavailable and the order has to remain in the queue for an extended period of time (several hours). The user gets nervous if they get ghosted by the system after getting positive feedback that Google got the order.
3. Finally, when Google has made the decision whether to fulfill the order or has declined the order. The user needs to be told whether to expect shipment or a refund. If a refund, then the user can take action to re-submit the order.

So in submitting an order to Google Offers, a total of three emails would be sent to the user so they could watch their order proceed through the system. The sending of these emails was controlled by the “commerce” API. The commerce API was a walled off section of the Google infrastructure that knew how to talk to the credit card companies and charge money. Normal Google code was not allowed to do these things but had to work via the commerce API, and the commerce API would take care of ensuring that the appropriate pop-ups would appear on the user’s screen and that the credit card information was securely obtained. Normal Google code never got its hands on the user’s credit card information, it only got a "go/no-go" signal from the commerce API.

So the commerce API would be the system actually taking the steps of recieving the order, charging the credit card, and returning the go/no-go signal to our system. We would instruct it to send email for each of these steps. So far so good.

The problem was that often the order would go through very quickly. The emails were processed in batches, so the email that acknowledged the reciept of the order could end up being received after the email that acknowledged that the order had been fulfilled. The user would first get an email saying "We charged your card." and only after this would they get an email saying "We got your order." This would confuse the user.

There was no way to add an artifical time lag, nor would we want to. We could not guarantee that the emails would arrive in the right order. (Even if we could, we couldn’t guarantee that the user would read them in the right order.) The solution that I proposed was to explicitly number the emails so that each email would say "This is email number N of 3 expected emails." and even perhaps a small message that said "Emails can arrive in the wrong order." If a user got email 2 first, then email 1, they could figure it out.

But the product managers didn’t see it that way. As far as they were concerned, it was confusing when email 1 arrived after email 2, so they wanted to not send email 1 if email 2 had been recieved. This is a nice idea, but I pointed out that we had no control over the order of arrival of emails, so there was no way to know if email 2 would be received prior to email 1 at the time we were sending email 1. They were adamant: "Don’t send the second email (that is, email 1, which arrived second in some situations)."

Ok, then. I adjusted the code to suppress the sending of email 1. This solved the problem of email 1 arriving after email 2, sure, but recall that email 1 was the "Google has received your order and has placed it on a queue to be processed" acknowledgement. Now when people placed an order, they would no longer get confirmation that Google had received it. Usually, Google would process the order in a timely manner and they’d quickly get email 2 which said "We are processing your order", but if there were some reason that we could not process the queue for some time, the user would be left in the dark about whether Google had heard them in the first place.

Complaints poured in.

The subsequent conversation was something like this:

“Why aren’t you acknowledging that the order has been received?”

“You explicitly told us to not send that email. See this communication (cite reference).”

“But that was not what we meant. We meant, don’t send it if the user has received the ‘Your order has been processed.’ email.”

“How are we supposed to know if email system delivered his mail and that he read it in the right order? We’re good, but not that good.”

“You mean emails can arrive or be read in the wrong order?”

“Exactly what we said in this communication (cite reference).”

“...”

“May I suggest we number the emails so that the user can figure it out if they arrive in the wrong order?”

“No, don’t do that. Just put it back the way it was.”

Done, and we are back to the original problem.

Out-of-order packets are an old problem that existed and was solved before computers. Computer programmers are, of course, very aware of the problem and the solutions. Computer programmers are well versed in the problems of “process”, and when laymen try to play at being programmers by interfering with process, they generally screw it up.

Suddenly

Suddenly this week, Copilot is reporting Emacs among our company's top IDEs and CommonLisp among the top languages. All on me.

Blacksmithing and Lisp

One of my hobbies is blacksmithing (not farrier work). Mild steel is an amazingly versatile material. It's very strong and hard at room temperature and it gets soft and easily workable when you heat it up. You use a hammer to move the metal once it is hot. You don't have to hit it very hard, just firmly. Hot metal is a very forgiving medium. If you make a mistake, simply heat the work up and try again. You rarely encounter mistakes you cannot recover from and you have to throw your work away.

A blacksmith uses tongs to manipulate work that would otherwise be too hot to handle. You don't want to drop a piece of hot steel, so you'd like your tongs to be a good fit on your work. Find some tongs that are an approximate fit and stick them in the fire to get good and hot. When they have softened, put the hot tongs around the cold workpiece and tap them into shape with your hammer. Voila! Custom tongs.

When I first saw this trick I was quite amused. It reminded me of Lisp programming — you can work on your problem, or you can customize the language to fit your problem better. And, yes, I'm the kind of nerd that sees a blacksmith trick and thinks “Lisp!”

Another computer-sciency question is one of bootstrapping. Where do tongs come from? How do you make tongs if you don't have them? This isn't too hard. A simple pair of tongs is basically two sticks with a rivet. You can shape half a pair of tongs (a single tong) by holding one end while you work the other. It will take a bit of time for the end in your hand becomes too hot to hold.

A good part of blacksmithing is creating ad hoc tools in pursuit of the end goal. You fairly often recur and create tools that help create tools. Metacircular blacksmithing.

The downside of working hot steel is that it is quite hot. You will get burned, but usually only mildly. Your reflexes take over pretty quickly when you touch hot metal. Then you learn early on that if you drop something, you do not attempt to catch it.