Joe Marshall — Advent of Code 2024: Day 7

· 11 hours ago

You don’t have to use named-lets for tail recursive loops. You can use them for any recursive function. Here is an example of a named let that computes the factorial of 5:

(let fact ((n 5))
  (if (= n 0)
      1
      (* n (fact (- n 1)))))

Day 7 is an unremarkable puzzle. On each line of input we are given a target number and some terms. We work on the terms from left to right and we can add the next term or multiply by it. We are to sum the target numbers which can be identified as a result of some combination of adding and multiplying.

;;; -*- Lisp -*-

(in-package "ADVENT2024/DAY7")

(defun can-satisfy? (target ops terms)
  (let recur ((accum (first terms))
              (terms (rest terms)))
       (cond ((and (> accum target)
                   (not (find-if #’zerop terms)))
              nil)
             ((consp terms)
              (find-if
               (lambda (op)
                 (recur (funcall op accum (first terms)) (rest terms)))
               ops))
             ((null terms) (= target accum))
             (t (error "Dotted list.")))))

(defun parse-integer-list (str)
  (map ’list #’parse-integer (str:split #\Space str :omit-nulls t)))

(defun parse-line (str)
  (let ((key+value (str:split #\: str)))
    (cons (parse-integer (first key+value))
          (parse-integer-list (second key+value)))))

(defun puzzle (ops)
  (collect-sum
    (let* ((equations
             (#Mparse-line
              (scan-file (input-pathname) #’read-line)))
           (satisfied (#M(lambda (equation)
                           (can-satisfy? (car equation) ops (cdr equation)))
                         equations)))
      (#Mcar (choose satisfied equations)))))

(defun part-1 ()
  (puzzle (list #’+ #’*)))

Part two allows us to concatenate the digits in addition to muliplying or adding.

(defun concatenate-digits (left right)
  (+ (* left (expt 10 (1+ (integer-log right 10))))
     right))

(defun part-2 ()
  (puzzle (list #’+ #’* #’concatenate-digits)))

vindarel — These years in Common Lisp: 2023-2024 in review

· 27 hours ago

This is a personal pick of the most interesting projects, tools, libraries and articles that popped-up in Common Lisp land in the last two years.

Newcomers might not realize how the Common Lisp ecosystem, though stable in many ways, actually evolves, sharpens, tries new solutions, proposes new tools, ships new libraries, revives projects. And everyone might enjoy a refresher.

Here’s my previous overview for 2022.

The same warnings hold: I picked the most important links, in my view, but this list is by no means a compilation of all new CL projects or articles published on the topic. Look for yourself on Reddit, Quicklisp releases, GitHub, and use your favourite search engine.

There are too many great news and achievements to pick 3. I love what’s happening around SBCL (and ECL, and Clozure’s revival), I love everything that got included into Lem and the work on all other editors, I love the webviews and I love the scripting tools that are emerging. What are your top picks?

OK, there’s a news I want to put at the forefront: HackerNews now runs on top of SBCL ;)

If you are discovering the ecosystem, my recommendaton is to not miss these two resources:

  • Awesome-cl - a curated list of libraries (there might be more than you think)
    • if you are looking for a list of recommended libraries on each topic, look here.
  • the CL Cookbook

Now let’s dive in and thanks to everyone involved.

The OpusModus music composition software.

Table of Contents

Community

We could start with some reddit stats: 2025 - a New Year for an old programming language! (numbers are up).

The ELS team kept organizing the conference. We have a date and place for 2025: European Lisp Symposium 2025 in Zürich, May 19⁄20

We saw new and regular Lisp Ireland meetups.

Here’s one of their videos: Lisp Ireland, February 2024 Meetup - Lisp & Hardware Verification with ACL2

@djha-skin ran a survey, which is not an established practice in the community, and analysed the results: Common Lisp Community Survey 2024 Results .

@shinmera (Yukari), the author of many useful libraries and an active member of the ELS, and even the host of the next one, opened a Patreon. “If you’d like to help me continue my full-time open source Lisp work, please consider supporting me.”. Sponsoring Yukari is money well spent. She is on GH sponsors and ko-fi too.

The community is on reddit, Discord, Mastodon, LinkedIn... and also on XMPP.

Documentation

The CL Cookbook is a collaborative resource with new contributors each year: new Cookbook EPUB and PDF release: 2025-01.

We got a great contribution: Cookbook: Building Dynamic Libraries with SBCL-Librarian · by em7

PAIP is a classic, now available on the web: Peter Norvig: Paradigms of Artificial Intelligence Programming, Case Studies in Common Lisp (web version).

New resource: Web Apps in Lisp: Know-how: I wanted a resource specialized for web development in Common Lisp. I mean to continuously extend it from now on.

I’ll include a couple general videos in this section. More videos and more documentation improvements are to be found in their respective sections.

FreeCodeCamp released an extensive Common Lisp course on Youtube: Lisp Programming Language - Full Course for Beginners - freeCodeCamp.org - Youtube.

David Botton of CLOG fame released more beginner material, among which Common Lisp - The Tutorial - Fast, Fun and Practical (with CLOG).

I carry on the work on my Common Lisp course in videos, on the Udemy platform. Lately, I worked on a CLOS tutorial: I published 9 videos (1h 22min) on my course. You’ll know enough to read the sources of Hunchentoot or the Kandria game 🎥 comments. The course is comprised of more than 7 hours of short videos, with a code first approach, divided in 9 chapters. We see some basics but we quickly dive into more advanced Common Lisp topics. You can learn more about it here on GitHub. Students can send me an email for a free link.

Here’s the feedback of redditors:

I can vouch for the Udemy course. From the very first lesson, just firing up the REPL and Emacs/SLIME I was taught something new. It’s a great course.

fuzzmonkey35, January 2025 (reddit)

It is an amazing tutorial. What is really strange is I thought CLOS was complicated. I guess it can be but Vincent is amazing at explaining everything and demystifying it.

intergallactic_llama, January 2025 (reddit)

;)

Implementations

Great times for Common Lisp implementations.

SBCL

SBCL ships monthly releases. You really should look at and appreciate all the activity and the continous improvements.

One noticeable addition: its new garbage collector. SBCL: merge of the mark-region GC.

More improvements include:

  • “the mark-region parallel garbage collector can be enabled on arm64. (Thanks to Hayley Patton)”,
  • new contrib module sb-perf, “a performance-analysing tool for Linux. (thanks to Luke Gorrie and Philipp Marek)”
  • support for cross-compiling the system to Android has been added (thanks to Gleefre)
  • “support for memory allocation arenas is now available on the arm64 platform.”
  • haiku support
  • sb-simd improvements

More good stuff with SBCL:

SBCL on the Nintendo Switch

There are open bounties to improve SBCL:

ABCL

New release: ABCL 1.9.1 “never use a dot oh”: CFFI compatibilities, Java virtual threads, ASDF 3.3.6, fixed loading of Fricas0 and Maxima...

New release ABCL 1.9.2.

New tool: Announcing the First Release of abcl-memory-compiler - Now Available!

CCL

Clozure was a bit active, but rather dormant.

Great news: Clozure is back

Clozure CL 1.13 released.

Allegro

Allegro Common Lisp 11.0 from Franz Inc.

LispWorks

I didn’t spot a patch release (they had a major release in 2022), so let’s link to a discussion: is LispWorks worth it? you might learn some things about LW’s feature set.

ECL

Embeddable, targetting WASM... is it the future?

CLASP

CLASP targets C++ on LLVM.

Release: Clasp v2.5.0

They realeased Clasp v2.7.0 in January, 2025.

For context:

New implementations

Historical: Medley Interlisp

We can run the Medley Interlisp Lisp machine in a browser O_o The work achieved by this group is phenomenal, look:

I suggest to follow @interlisp@fosstodon.org on Mastodon.

Companies and jobs

Yes, some companies still choose Common Lisp today, and some hire with a public job posting.

It’s of course the visible top of the iceberg. If you dream of a Lisp job, I suggest to be active and make yourself visible, you might be contacted by someone without a proper job announce. This could be for an open-source project with funding (happened to me), for a university, etc.

We knew these companies since awesome-lisp-companies -it’s only a list of companies we know about, nothing offical. Additions welcome.

Discussions on the topic:

Projects

Editors

Please check out the Cookbook: editors for a list of good editors for Common Lisp. You migth be surprised.

Let’s highlight a new editor in town: Neomacs: Structural Lisp IDE/computing environment . Mariano integrated it in his moldable web desktop: Integrating Neomacs into my CLOG-powered desktop.

About Emacs

About VSCode

About Lem and Rooms pair programming environment

  • Lem 2.0.0 released
    • released in May 2023, this version added the SDL2 frontend, adding mouse support, graphic capabilities, and Windows support.
    • it brought the possibility to draw images and shapes at any location on a buffer or window.
    • addition of many base16 color themes (180), by @lukpank.
  • Lem 2.1.0 released, with many new contributors. Lem 2.0 definitely caught the eyes of many developers IMO.
    • this is when Lem got its website: https://lem-project.github.io/
    • @sasanidas worked on supporting other implementations: “ECL and CCL should work fairly well”, “ABCL and Clasp are still work in progress, working but with minor bugs.”.
    • I added project-aware commands, find-file-recursively
    • @cxxxr added (among everything else) great Lisp mode additions (just look at the release notes and the screenshots)
    • added a sidebar / filer
    • and much more. Just look at the release.
  • then came out Lem 2.2.0
    • the release notes are less organized ;)
    • added libvterm integration
    • this is when I added the interactive git mode.

Unfortunately these latest releases do not ship a readily usable executable. But the installation recipes have been greatly simplified and use Qlot instead of Roswell. There’s a one-liner shell command to install Lem on Unixes.

Lem’s creator cxxxr is now on GitHub sponsors.

He is also working on Rooms, aka Lem on the cloud: it’s a Lem-based “pair programming environment where you can share your coding sessions”. Only the client is open-source, so far at least.

Demo: https://www.youtube.com/watch?v=IMN7feOQOak

Those are the Lem related articles that popped up:

Lem's Legit Git interface.

About LispWorks

About the Jetbrains plugin

About Jupyter

Other tools

Coalton

I found Coalton-related projects:

E. Fukamachi added Coalton support for Lem: https://lem-project.github.io/modes/coalton-lang/. This adds completion, syntax highlighting, interactive compilation and more inside “coalton-toplevel” forms.

Package managers

Quicklisp had a one year hiatus, because it relies on one man. It finally got an update after 1 year: Quicklisp libraries were updated 2024-10-12. Despite a call for collaboration, we don’t really know how we can help.

But Quicklisp isn’t the only library manager anymore.

Also:

Gamedev

The Kandria game was released: https://kandria.com/

If you are into game dev, this is a paper you cannot miss: Kandria: experience report, presented at the ELS 2023.

Great articles:

and more:

I almost forgot the Lisp Game Jams and the new cool little games. For example: Nano Towers

a simple tower defense game written in Common Lisp with the EON framework based on Raylib, submitted for the Spring Lisp Game Jam 2024.

Links to the jams:

GUI

Many solutions exist. Disclaimer: the perfect GUI library doesn’t exist. Please see the Cookbook/gui and awesome-cl. Also don’t miss the web views available today.

releases:

As always, we might not highlight the work achieved on existing libraries that didn’t get a proper announce. There are more GUI libraries for CL.

demos:

Web

CLOG appeared in 2022 and is kicking. Its API has been stable for 4 years.

You know Hacker News, the website, right? Hacker News now runs on top of SBCL

HN runs on top of Arc, the language. Arc was implemented on top of Racket (-> MzScheme). A new, faster / more efficient, implementation of Arc in SBCL was in the works by a Hacker News site maintainer for some time: called Clarc. Its source code has not been published. Since [late september, 2024], the official Hacker News site runs using Clarc and SBCL.

Here’s (again) my new resource for web development in Common Lisp: Web Apps in Lisp: Know-how.

Now the links:

  • CLOG CLOG 2.0 - Now with a complete Common Lisp IDE and GUI Builder (with or w/o emacs)
  • CLOG OS shell
CLOG shell

Projects built with CLOG:

moldable desktop

Weblocks (continued in the Reblocks project):

More:

Articles:

videos:

libraries:

The web views I mentioned: Electron is a thing, but today we have bindings to webview.h and webUI:

More libraries

Data structures:

Language extensions, core libraries:

Iteration:

Developer tools:

Threads, actors:

Documentation builders:

Databases:

relational database and first order logic:

Numerical and scientific:

Plotting:

Bindings and interfaces:

Serialization:

Date and time:

Utilities:

Bindings and interfaces to other software:

Networking:

Scripting

(I love what’s being done here)

Software releases

Other articles

Videos

Demos:

Web:

More from the ELS (see their Youtube channel):

Learning:

Aaaand that’s it for the tour of the last couple years. Tell me if I missed something. I’ll keep updating this post for a few days.

Happy lisping and show us what you build!

Joe Marshall — Advent of Code 2024: Day 6

· 35 hours ago

A named-lambda is a lambda expression that has a name bound to it only within the scope of the lambda expression. You can use the name to refer to the lambda expression from within the body of the lambda expression. This allows you to recursively call the lambda expression. Named-lambdas are easily created with a macro that expands into a labels form.

Named-lambdas are an alternative to using the Y operator to create recursive lambda expressions. Named-lambdas are a special form, so if you are uncomfortable with adding new special forms to the language, you’ll probably prefer to use the Y operator.

Recall that let expressions are just syntactic sugar for lambda expressions. If you expand a let expression using a named-lambda, you get a named-let expression. The name is bound to the lambda that binds the let variables. Invoking the name will re-invoke the let expression with different values for the bound variables.

Named lets take a moment to get used to, but once you get the hang of them, they are incredibly handy. They are especially useful when you use them for tail recursive loops. Here is an example where we use a named let to partition a list with a predicate:

(let next ((tail list)
           (yes ’())
           (no  ’()))
  (cond ((consp tail) 
         (if (predicate (car tail))
             (next (cdr tail) (cons (car tail) yes) no)
             (next (cdr tail) yes (cons (car tail) no))))
        ((null? tail) (values yes no))
        (t (error "Improper list."))))

When we invoke the name next, we re-invoke the let expression with the new values for the bound variables. In this example, the calls to next are in tail position, so the compiler turns them into jumps, making this a tail recursive loop.

The named-let syntax, with the name being the symbol before the bindings, is borrowed from MIT-Scheme. This syntax is easily implemented with a macro that expands into a labels form if the name is present, but expands into a cl:let if it is absent. You shadowing-import the let symbol into your package so that the macro will override the standard binding of let.



For day 6, we have a guard patrolling a warehouse. The guard moves in straight lines unless he encounters an obstacle, where he will turn clockwise 90 degrees. If he moves off the grid, he goes home for the evening.

First, we’ll read the grid and find the initial position of the guard:

(defun read-input (pathname)
  (read-file-into-grid 
    (char-interner #’char-upcase (find-package "ADVENT2024/DAY6"))
    pathname))

(defun get-initial-position (grid)
  (let ((coord (collect-first
                (choose-if
                 (lambda (coord) (member (grid-ref grid coord) ’(^ < > v)))
                 (scan-grid-coords grid)))))
    (ocoord coord
           (ecase (grid-ref grid coord)
             (^ +north+)
             (> +east+)
             (v +south+)
             (< +west+)))))

In the second part of the problem, we’ll be allowed to place a single additional obstacle in the grid. patrol-step attempts to move the guard one step forward, and turns him clockwise if he cannot move forward. obstacle-coord is the additional obstacle or nil:

(defun patrol-step (grid obstacle-coord oriented-position)
  (let ((next-ocoord (ocoord-advance oriented-position)))
    (cond ((not (on-grid? grid (ocoord-coord next-ocoord))) nil)
          ((or (eq (grid-ref grid (ocoord-coord next-ocoord)) ’|#|)
               (equal (ocoord-coord next-ocoord) obstacle-coord))
           (ocoord-cw oriented-position))
          (t next-ocoord))))

patrol places the guard at his initial position and repeatedly calls patrol-step until the guard either walks off the grid or returns to an ocoord he has visited before (with the same orientation). We keep the history of visited ocoords in two ways: as a list and a hash table. The list gives us the history in order, while the hash table allows us to quickly check if we have visited an ocoord before (otherwise we’d have an O(n^2) algorithm). If the guard walks off the grid, we return the history list. If the guard returns to a previously visited ocoord, we return the symbol :loop. Note the use of a named-let to loop the patrol steps.

(defun patrol (grid obstacle-coord start-opos)
  (let ((history-hash (make-hash-table :test ’equal)))
    (setf (gethash start-opos history-hash) t)
    (let iter ((opos start-opos)
               (history (list start-opos)))
      (let ((next (patrol-step grid obstacle-coord opos)))
        (cond ((null next) history)
              ((gethash next history-hash nil) :loop)
              (t (setf (gethash next history-hash) t)
                 (iter next (cons next history))))))))

For part 1, we simply call patrol with the initial position and nil as the obstacle:

(defun unique-cells (history)
  (length (remove-duplicates (map ’list #’ocoord-coord history) :test #’equal)))

(defun part-1 ()
  (let* ((grid (read-input (input-pathname)))
         (initial-position (get-initial-position grid)))
    (unique-cells (patrol grid nil initial-position))))

For part 2, we iterate over the cells in the paths and see what happens if we place an obstacle there. We accumulate the locations that result in a loop:

(defun part-2 ()
  (let* ((grid (read-input (input-pathname)))
         (initial-position (get-initial-position grid))
         (unmodified-path (patrol grid nil initial-position))
         (answer nil))
    (dolist (obstacle (remove-duplicates (map ’list #’ocoord-coord unmodified-path) :test #’equal)
                      (length (remove-duplicates answer :test #’equal)))
      (unless (and obstacle
                   (equal obstacle (ocoord-coord initial-position)))
        (when (eq (patrol grid obstacle initial-position) :loop)
          (pushnew obstacle answer :test #’equal))))))

Joe Marshall — Advent of Code 2024: Day 5

· 2 days ago

For day 5, the input comes in two parts: There are rules of the form n|m, where n and m are numbers, and there are “updates” which are lists of numbers separated by commas. The rules are used to determine which updates are valid. An update is valid if it passes all applicable rules. A rule is applicable if the two numbers in the rule appear in the update. An update passes an applicable rule if the two numbers in the rule appear in the update in the same order as they appear in the rule.

To read the input, we read the lines and collect them into two lists. The rule list is all the lines that contain a pipe character, and the updates list is all the lines that contain a comma:

(defun read-input (input-file)
  (let ((lines (scan-file input-file #'read-line)))
    (let ((is-rule (#M(lambda (line) (find #\| line)) lines))
          (is-update (#M(lambda (line) (find #\, line)) lines)))
      (values (collect ’list (#M(lambda (rule)
                                  (map ’list #’parse-integer (str:split #\| rule)))
                                (choose is-rule lines)))
              (collect ’list (#M(lambda (update)
                                  (map ’list #’parse-integer (str:split #\, update)))
                                (choose is-update lines)))))))

To test a rule, we find the location of the two numbers in the update and check that they are in the same order as they appear in the rule. If either number is not found, the rule is not applicable and trivially passes.

(defun test-rule (rule update)
  (let ((left-position (position (first rule) update))
        (right-position (position (second rule) update)))
    (or (null left-position)
        (null right-position)
        (< left-position right-position))))

(defun test-rules (rules update)
  (collect-and
   (#Mtest-rule
    (scan ’list rules)
    (series update))))

Part 1 is to sum the middle numbers of all the updates that pass all the rules:

(defun middle-number (list)
  (elt list (/ (1- (length list)) 2)))

(defun part-1 ()
  (multiple-value-bind (rules updates) (read-input (input-pathname))
    (collect-sum
     (#Mmiddle-number
      (choose-if
       (lambda (update) (test-rules rules update))
       (scan ’list updates))))))

For part 2, we select the updates that fail the rules. We repair the update by sorting it using the rules as a sort predicate, then we sum the middle numbers of the repaired updates:

(defun sort-using-rules (rules list)
  (sort list (lambda (left right)
               (find (list left right) rules :test #’equal))))

(defun part-2 ()
  (multiple-value-bind (rules updates) (read-input (input-pathname))
    (collect-sum
     (#Mmiddle-number
      (#M(lambda (update) (sort-using-rules rules update))
       (choose-if
        (lambda (update) (not (test-rules rules update)))
        (scan ’list updates)))))))

Joe Marshall — Advent of Code 2024: Day 4

· 3 days ago

Day 4 part 1 is your standard word search. First we read the grid of letters:

(defun read-input (input-pathname)
  (read-file-into-grid
    (char-interner #'char-upcase (find-package "ADVENT2024/DAY4"))
    input-pathname))

A “trace” is a row, column, or diagonal of letters. To search a trace for the word, we examine each suffix of the trace to see if starts with the word. We also check the reverse of the word:

(defun search-trace (trace target)
  (let ((rev (reverse target)))
    (collect-sum
     (#M(lambda (suffix)
          (if (or (starts-with-subseq target suffix)
                  (starts-with-subseq rev suffix))
              1
              0))
        (scan-suffixes trace)))))

Then we search all the traces:

(defun search-trace-list (trace-list target)
  (collect-sum
   (#M(lambda (trace)
        (search-trace trace target))
    (scan 'list trace-list))))

(defun search-grid (grid target)
  (collect-sum
   (#M(lambda (get-trace-list)
        (search-trace-list (funcall get-trace-list grid) target))
      (scan ’list
         (list (lambda (grid) (collect ’list (scan-rows grid)))
               (lambda (grid) (collect ’list (scan-columns grid)))
               (lambda (grid) (collect ’list (scan-falling-diagonals grid)))
               (lambda (grid) (collect ’list (scan-rising-diagonals grid))))))))

(defun part-1 ()
  (search-grid (read-input (input-pathname)) #(X M A S)))

Note that since scan-rows etc. and collect are macros, so we cannot pass them as first class functions. Instead we pass lambdas that call them so that the full macro expression is visible to the compiler.

For part 2, we are searching for Xs of “MAS” in the grid. We search for As, then check for M and S in the diagonals.

m-s1? is a helper function that checks if a pair of coords contains an M and an S.

(defun m-s1? (grid coord1 coord2)
  (and (on-grid? grid coord1)
       (on-grid? grid coord2)
       (eql (grid-ref grid coord1) 'M)
       (eql (grid-ref grid coord2) 'S)))

m-s? checks if a pair of coords contains an M and an S in any order.

(defun m-s? (grid coord1 coord2)
  (or (m-s1? grid coord1 coord2)
      (m-s1? grid coord2 coord1)))

x-mas? checks whether an A is surrounded by an M and an S.

(defun x-mas? (grid coord)
  (and (on-grid? grid coord)
       (eql (grid-ref grid coord) 'A)
       (and (m-s? grid (coord-northwest coord) (coord-southeast coord))
            (m-s? grid (coord-northeast coord) (coord-southwest coord)))))

Then we just count the occurrances:

(defun search-x-mas (grid)
  (collect-sum
   (#M(lambda (coord)
        (if (x-mas? grid coord)
            1
            0))
      (scan-grid-coords grid))))

(defun part-2 ()
  (search-x-mas (read-input (input-pathname))))

Joe Marshall — Advent of Code 2024: Day 3

· 6 days ago

For Day 3, we are given a “corrupted” block of memory as a string. We are to find the “uncorrupted instructions” in the block and emulate them.

For this problem, we don’t attempt to force things into the series paradigm. The cl-ppcre library provides a bunch of functions for working with regular expressions, and the do-register-groups macro is ideal for this problem. It iterates over all the matches of a regular expression, binding submatches to some variables, with some optional processing of the submatch. (If the cl-ppcre library offered a function that returned a series of matches, we could use that, but it offers a do macro.)

First, we read the input:

(defun read-input (input-pathname)
  (read-file-into-string input-pathname))

Next, we define a regular expression to match the instructions:

(defparameter *mul-instruction* "(mul\\((\\d{1,3}),(\\d{1,3})\\))")

Now we just iterate over all the matches:

(defun part-1 ()
  (let ((answer 0))
    (cl-ppcre:do-register-groups (whole (#’parse-integer left) (#’parse-integer right))
        (*mul-instruction* (read-input (input-pathname)))
      (declare (ignore whole))
      (incf answer (* left right)))
    answer))

do-register-groups is an example of a macro where the parenthesized subexpressions do not indicate function calls. The first parenthesized subgroup is a variable list, and within the variable list, a parenthesized subgroup indicates a transformer to be applied before binding the variable. So in this case, we are binding the variables whole, left, and right, and we run the matching subgroup through parse-integer before binding the left and right variables.

The second parenthesized subgroup is a list of the regular expression to match and the string to match within. After these irregular parenthesized subgroups, the remaining is a body of code that is executed for each match.

In the body of the code, we ignore the whole variable (which is the whole match) and increment the answer by the product of the left and right variables. As is usual for a do macro, we transport the data out of the loop by side effecting a lexically scoped variable.

For part 2, we have additional instructions to emulate. Our loop will now have some state to it, and we will side effect the state as we iterate over the matches. We can just extend the regular expression and add a cond to the body of the do-register-groups to handle the new instructions. As we iterate over the matches, we side effect the emulation state:

(defparameter *do-mul-instruction* "(do\\(\\))|(don’t\\(\\))|(mul\\((\\d{1,3}),(\\d{1,3})\\))")

(defun part-2 ()
  (let ((answer 0)
        (on t))
    (cl-ppcre:do-register-groups (turn-on turn-off whole (#’parse-integer left) (#’parse-integer right))
        (*do-mul-instruction* (read-input (input-pathname)))
      (declare (ignore whole))
      (cond (turn-on (setq on t))
            (turn-off (setq on nil))
            (on (incf answer (* left right)))
            (t nil)))
    answer))

Strictly speaking, we don’t need to use side effects. We could rework this to be purely functional, but this seems unnatural. Yes, there is a bit of cognitive overhead in remembering that there is a state variable that determines whether or not we are executing an instruction, but the code is quite understandable.

“Do” macros usually need some side effects, but we can localize the side effects by using a let to lexically bind the state variables and then side effecting them from within the loop. This is an effective compromise between the functional and imperative programming paradigms.

Joe Marshall — Advent of Code 2024: Day 2

· 6 days ago

For Day 2 in the Advent of Code, we are given a file where each line in the file contains a list of integers separated by spaces. We will be performing some manipulations on these lists.

First, we need to read the file. We make a function to read a line as a string, then read the integers from the string and collect the result into a list.

(defun read-levels (stream eof-error-p eof-value)
  (let ((line (read-line stream eof-error-p eof-value)))
    (if (eq line eof-value)
        eof-value
        (with-input-from-string (stream line)
          (collect ’list (scan-stream stream))))))

We use this function to read the entire file into a list of lists of integers.

(defun read-input (input-pathname)
  (collect ’list (scan-file input-pathname #’read-levels)))

We are concerned with the deltas between adjacent elements in a series of integers. We make a function to calculate the deltas. This will be an optimizable-series-function because it returns a series of deltas. We declare the argument to be an “off-line” input series as well. This code will be transformed into the equivalent loop code where we consume the deltas.

chunk is a series function that takes a series and produces n series of chunks that are offset by a specified amount. We produce chunks of size 2, offset by 1. This returns two series, the left number of each pair of numbers and the right number of each pair of numbers. By mapping #’- over these series, we get the series of deltas between adjacent numbers.

(defun deltas (series)
  (declare (optimizable-series-function)
           (off-line-port series))
  (multiple-value-bind (left right) (chunk 2 1 series)
    (#M- right left)))

As per the puzzle, a series of deltas is considered “safe” if it is strictly ascending or descending, and each step by which it ascends or descends is between 1 and 3 inclusive. We get the series of deltas, map #’plusp to get a series of booleans indicating whether each delta is positive, and collect-and on the series of booleans. Likewise with #’minusp for descending. Finally, we create a series of booleans indicating whether the absolute value of the delta is <= 3 and collect-and this as well. Whether the deltas are considered “safe” is just a boolean operation on these three boolean values:

(defun safe-levels? (list)
  (let ((deltas (deltas (scan list))))
    (let ((ascending (collect-and (#Mplusp deltas)))
          (descending (collect-and (#Mminusp deltas)))
          (small (collect-and (#M<= (Mmabs deltas) (series 3)))))
      (and small
           (or ascending descending)))))

The first part of the puzzle asks us to count the number of lines considered “safe”:

(defun part-1 ()
  (count-if #’safe-levels? (read-input (input-pathname))))

The second part of the puzzle relaxes the safety restriction by saying that you are allowed to ‘dampen’ the list by removing a single outlier before checking for safety.

(defun safe-dampened-levels? (levels)
  (find-if #’safe-levels? (remove-one-element levels)))

(defun part-2 ()
  (count-if #’safe-dampened-levels? (read-input (input-pathname))))

Joe Marshall — Advent of Code 2024: Day 1

· 6 days ago

Half the problem of solving an Advent of Code puzzle is dealing with the puzzle input. It is generally in some ad hoc format that requires a bespoke parser. There are a few approches you can take.

  • Read the input as a string and directly call string manipulation functions to extract the data.
  • Read the input as a string and use regular expressions to extract the data.
  • Use the lisp reader to read the input as a lisp data structure. This requires that the input looks like lisp objects.
  • Tweak the Lisp reader to read the data in a custom format. This works if the input looks a lot like lisp objects.

For Day 1, the input is two columns of numbers. If we just scan the file with the lisp reader, we'll get a single list of numbers. We can convert this into two lists with the series chunk function:

(defun read-input (input-pathname)
  (multiple-value-bind (left-column right-column)
      (chunk 2 2 (scan-file input-pathname))
    (values (collect ’list left-column)
            (collect ’list right-column))))

For part 1 of the puzzle, we sort both columns and then walk through them in parallel finding the absolute difference between the columns and summing that.

(defun part-1 ()
  (multiple-value-bind (left-column right-column)
      (read-input (input-pathname))
    (collect-sum
     (#Mabs
      (#M-
       (scan (sort left-column #’<))
       (scan (sort right-column #’<)))))))

For part 2, we look at each number in the left column and multiply it by how many times it appears in the right column. We sum these quantities.

(defun part-2 ()
  (multiple-value-bind (left-column right-column)
      (read-input (input-pathname))
    (collect-sum
     (#M(lambda (item) (* item (count item right-column)))
        (scan left-column)))))

These examples show how we can use series and built-in sequence functions to eliminate loops.

Joe Marshall — Advent of Code 2024: Day 0

· 7 days ago

I wanted to write some blog posts, but I was short of material. For the fun of it, I’ve decided to write a series of posts about solving the 2024 Advent of Code problems in Common Lisp. I see that other people were doing this in real time, but it is too late for that. Besides, I didn’t want the stress of trying to solve the problems as part of a competition. I wanted to take my time and focus on code quality rather than on how fast I can write it.

I noticed that some programmers were less experienced in Common Lisp. They tended to code up solutions that used low-level Common Lisp operations instead of using one of Common Lisp’s powerful sequence operations. For example, they might use a loop to iterate over a list and incf a counter instead of just using a call to count. I want to show how to effectively use the rich set of Common Lisp library functions to write concise, readable, and efficient code.

I’m trying to decide what I think of the series package that provides a more functional approach to iteration without sacrificing performance. For a lot of iterations, it is easy to write series code, but it for other iterations it isn’t so obvious. I wanted a little practice in using series and seeing its limitations.

Conventions

One of the features of Common Lisp is that you can tailor the language to fit the problem space. The first step in solving the problem suite is to configure the language. Since I wanted to explore using the series package, I set up my Lisp so that series was available in all the packages. I also installed the alexandria library, which is a collection of utilities that flesh out the Common Lisp standard library with some obvious “missing” functions.

The series package includes an optional #M reader macro that gives you a shorthand for writing mapping expressions. I added the “named” let syntax which attaches a name to the binding lambda of a let expression allowing you to invoke the reinvoke the let as a recursive function. The default delarations were set to ensure that the compiler could would generate tail recursive code. Tail recursion coupled with named-let is a powerful iteration facility.

I set up the directory structure to have a subdirectory for each day. Each problem in the entire Advent of Code could fit in its own solution.lisp file, so each subdirectory had files input.txt and solution.lisp, and usually sample-input.txt and maybe one or more sample-input-n.txt

The parent directory had an advent2024.asd file, a package.lisp file that defined all the packages, an initialize.lisp file that customized Common Lisp and installed some bootstrap values in each package, and a misc.lisp file that contained some common definitions that were exported to all the packages.

I set up my Lisp to have a separate package for each day. The package definition file contained 25 package definitions, each one virtually identical, e.g.:

(defpackage "ADVENT2024/DAY16"
  (:shadow "VALIDATE")
  (:import-from "ALEXANDRIA"
                "FLATTEN"
                "HASH-TABLE-ALIST"
                "HASH-TABLE-KEYS"
                "HASH-TABLE-VALUES"
                "LENGTH="
                "MAPPEND"
                "MAP-PERMUTATIONS"
                "MAP-PRODUCT"
                "READ-FILE-INTO-STRING"
                "STARTS-WITH-SUBSTRING"
                )
  (:shadowing-import-from "NAMED-LET" "LET")
  (:shadowing-import-from "SERIES"
                          "DEFUN"
                          "FUNCALL"
                          "LET*"
                          "MULTIPLE-VALUE-BIND"
                          )
  (:export "PART-1" "PART-2" "+SOLUTION-1+" "+SOLUTION-2+" "VALIDATE")
  (:use "ADVENT2024" "COMMON-LISP" "FOLD" "FUNCTION" "NAMED-LET" "SERIES"))

This basically set up Lisp to have series available, and imported a few symbols from alexandria.

Each day’s puzzle has two parts, so each package exports the symbols PART-1 and PART-2 to be defined as zero argument functions that compute and return the solution to the respective parts. The symbols +SOLUTION-1+ and +SOLUTION-2+ are defined as defparameter values. The initialization function installs a validate function checks that (part-1) returns +SOLUTION-1+ and (part-2) returns +SOLUTION-2+ in each package.

misc.lisp

The misc.lisp file contains code that is common to more than one puzzle.

The grid abstraction

The problem space of many of the puzzles is two dimensional, and it is natural to use a two-dimensional lisp array for the representation. I enhance this with a lightweight abstraction called a grid.

A grid is adressed by a coord, which is an ordered pair of column and row. These are simply the car and cdr of a cons cell. The functions that construct and select from a coord are all given compiler-macro definitions. In the 99% of the cases where you simply call the constructor or selector, the compiler macro will expand the code. In the 1% case, where you pass the constructor or selector as a first-class function, the function definition is passed.

(deftype grid-index ()
  ‘(integer ,(- array-dimension-limit) (,array-dimension-limit)))

(deftype coord ()
  ’(cons (grid-index) (grid-index)))

(eval-when (:compile-toplevel :load-toplevel :execute)
(defun coord (column row)
  (check-type column grid-index)
  (check-type row grid-index)
  (cons column row))
)

(define-compiler-macro coord (column row)
  ‘(cons ,column ,row))

(defun column (coord)
  (check-type coord coord)
  (car coord))

(define-compiler-macro column (coord)
  ‘(car ,coord ))

(defun row (coord)
  (check-type coord coord)
  (cdr coord))

(define-compiler-macro row (coord)
  ‘(cdr ,coord))

(defun scan-coords (row-count col-count)
  (declare (optimizable-series-function))
  (multiple-value-bind (rows cols)
      (map-fn ’(values grid-index grid-index)
              #’floor
              (scan-range :below (* row-count col-count))
              (series col-count))
    (declare (type (series grid-index) rows cols))
    (map-fn ’coord #’coord cols rows)))

A grid is just a two-dimensional array of atoms:

(deftype grid () ‘(array atom 2))

(defun make-grid (height width &rest; keys)
  (apply #’make-array (list height width) keys))

(defun row-list->grid (row-list)
  (make-grid (length row-list) (length (first row-list)) :initial-contents row-list))

(defun grid-height (grid)
  (check-type grid grid)
  (array-dimension grid 0))

(define-compiler-macro grid-height (grid)
  ‘(array-dimension ,grid 0))

(defun grid-width (grid)
  (check-type grid grid)
  (array-dimension grid 1))

(define-compiler-macro grid-width (grid)
  ‘(array-dimension ,grid 1))

A coord is on a grid if it is within the bounds of the grid:

(defun on-grid? (grid coord)
  (and (>= (column coord) 0)
       (< (column coord) (grid-width grid))
       (>= (row coord) 0)
       (< (row coord) (grid-height grid))))

You may want to check if the coord is on the grid before calling grid-ref.

(defun grid-ref (grid coord)
  (check-type grid grid)
  (check-type coord coord)
  (aref grid (row coord) (column coord)))

(define-compiler-macro grid-ref (grid coord)
  (let ((coord-var (gensym "COORD-")))
    ‘(let ((,coord-var ,coord))
       (aref ,grid (row ,coord-var) (column ,coord-var)))))

(defsetf grid-ref (grid coord) (value)
  (let ((coord-var (gensym "COORD-")))
    ‘(let ((,coord-var ,coord))
       (setf (aref ,grid (row ,coord-var) (column ,coord-var)) ,value))))

(defun scan-grid-coords (grid)
  (declare (optimizable-series-function))
  (scan-coords (grid-height grid) (grid-width grid)))

(defun scan-grid (grid)
  (declare (optimizable-series-function 2))
  (#2m(lambda (grid coord)
        (values coord (grid-ref grid coord)))
      (series grid)
      (scan-coords (grid-height grid) (grid-width grid))))

You can invert a grid. This will give you a hash table that maps the atoms in the grid to a list of their coords.

(defun invert-grid (grid &optional; initial-value)
  (if initial-value
      (multiple-value-bind (coords vals) (scan-grid grid)
        (collect-hash-push-except vals coords (list initial-value)))
      (multiple-value-bind (coords vals) (scan-grid grid)
        (collect-hash-push vals coords))))

You can extract a row, column, or diagonal from a grid:

(defun grid-row (grid row-number)
  (check-type grid grid)
  (make-array (list (grid-width grid))
              :displaced-to grid
              :displaced-index-offset (array-row-major-index grid row-number 0)))

(defun grid-column (grid columm-number)
  (check-type grid grid)
  (let ((answer (make-array (grid-height grid))))
    (dotimes (row (grid-height grid) answer)
      (setf (svref answer row)
            (grid-ref grid (coord columm-number row))))))

(defun grid-falling-diagonal (grid diagonal-number)
  (check-type grid grid)
  (let ((start-column (if (minusp diagonal-number)
                          0
                          diagonal-number))
        (start-row (if (minusp diagonal-number)
                       (- diagonal-number)
                       0)))
    (let ((limit (min (- (grid-width grid) start-column)
                      (- (grid-height grid) start-row))))
      (let ((answer (make-array (list limit))))
        (do ((row    start-row    (+ row 1))
             (column start-column (+ column 1))
             (index 0 (+ index 1)))
            ((>= index limit) answer)
          (setf (svref answer index)
                (grid-ref grid (coord column row))))))))

(defun grid-rising-diagonal (grid diagonal-number)
  (check-type grid grid)
  (let ((start-column (if (minusp diagonal-number)
                          (- diagonal-number)
                          0))
        (start-row (if (minusp diagonal-number)
                       (1- (grid-height grid))
                       (- (grid-height grid) diagonal-number 1))))
    (let ((limit (min (- (grid-width grid) start-column)
                      (1+ start-row))))
      (let ((answer (make-array (list limit))))
        (do ((row    start-row    (- row 1))
             (column start-column (+ column 1))
             (index 0 (+ index 1)))
            ((>= index limit) answer)
          (setf (svref answer index)
                (grid-ref grid (coord column row))))))))

Given a grid, you can get the series of rows, columns, or diagonals:

(defun scan-rows (grid)
  (declare (optimizable-series-function))
  (map-fn ’vector #’grid-row (series grid) (scan-range :below (grid-height grid))))

(defun scan-columns (grid)
  (declare (optimizable-series-function))
  (map-fn ’vector #’grid-column (series grid) (scan-range :below (grid-width grid))))

(defun scan-falling-diagonals (grid)
  (declare (optimizable-series-function))
  (map-fn ’vector
          #’grid-falling-diagonal
          (series grid)
          (scan-range :from (1+ (- (grid-height grid))) :below (grid-width grid))))

(defun scan-rising-diagonals (grid)
  (declare (optimizable-series-function))
  (map-fn ’vector
          #’grid-rising-diagonal
          (series grid)
          (scan-range :from (- 1 (grid-width grid)) :below (grid-height grid))))

An orientation is a unit coord.

(deftype unit ()
  ‘(integer -1 1))

(deftype orientation ()
  ’(cons (unit) (unit)))

(defun unit-vector (column row)
  (check-type column unit)
  (check-type row unit)
  (cons column row))

(defparameter +north+ (unit-vector 0 -1))
(defparameter +northeast+ (unit-vector 1 -1))
(defparameter +east+  (unit-vector 1 0))
(defparameter +southeast+ (unit-vector 1 1))
(defparameter +south+ (unit-vector 0 1))
(defparameter +southwest+ (unit-vector -1 1))
(defparameter +west+  (unit-vector -1 0))
(defparameter +northwest+ (unit-vector -1 -1))

You can do 2d-vector arithmetic on a coord

(defun 2v+ (left right)
  (coord (+ (column left) (column right))
         (+ (row left) (row right))))

(defun 2v- (left right)
  (coord (- (column left) (column right))
         (- (row left) (row right))))

Given a coord, you can get the coord of the adjacent cell in a given orientation. Note that the new coord might not be on the grid if you’re at the edge.

(defun coord-north (coord)
  (check-type coord coord)
  (2v+ coord +north+))

(define-compiler-macro coord-north (coord)
  (let ((coord-var (gensym "COORD-")))
    ‘(let ((,coord-var ,coord))
       (coord (column ,coord-var) (1- (row ,coord-var))))))

(defun coord-northeast (coord)
  (check-type coord coord)
  (2v+ coord +northeast+))

(define-compiler-macro coord-northeast (coord)
  (let ((coord-var (gensym "COORD-")))
    ‘(let ((,coord-var ,coord))
       (coord (1+ (column ,coord-var)) (1- (row ,coord-var))))))

(defun coord-east (coord)
  (check-type coord coord)
  (2v+ coord +east+))

(define-compiler-macro coord-east (coord)
  (let ((coord-var (gensym "COORD-")))
    ‘(let ((,coord-var ,coord))
       (coord (1+ (column ,coord-var)) (row ,coord-var)))))

(defun coord-southeast (coord)
  (check-type coord coord)
  (2v+ coord +southeast+))

(define-compiler-macro coord-southeast (coord)
  (let ((coord-var (gensym "COORD-")))
    ‘(let ((,coord-var ,coord))
       (coord (1+ (column ,coord-var)) (1+ (row ,coord-var))))))

(defun coord-south (coord)
  (check-type coord coord)
  (2v+ coord +south+))

(define-compiler-macro coord-south (coord)
  (let ((coord-var (gensym "COORD-")))
    ‘(let ((,coord-var ,coord))
       (coord (column ,coord-var) (1+ (row ,coord-var))))))

(defun coord-southwest (coord)
  (check-type coord coord)
  (2v+ coord +southwest+))

(define-compiler-macro coord-southwest (coord)
  (let ((coord-var (gensym "COORD-")))
    ‘(let ((,coord-var ,coord))
       (coord (1- (column ,coord-var)) (1+ (row ,coord-var))))))

(defun coord-west (coord)
  (check-type coord coord)
  (2v+ coord +west+))

(define-compiler-macro coord-west (coord)
  (let ((coord-var (gensym "COORD-")))
    ‘(let ((,coord-var ,coord))
       (coord (1- (column ,coord-var)) (row ,coord-var)))))

(defun coord-northwest (coord)
  (check-type coord coord)
  (2v+ coord +northwest+))

(define-compiler-macro coord-northwest (coord)
  (let ((coord-var (gensym "COORD-")))
    ‘(let ((,coord-var ,coord))
       (coord (1- (column ,coord-var)) (1- (row ,coord-var))))))

An ocoord is a coord that has a direction associated with it. It is a coord plus an orientation.

(deftype ocoord ()
  ’(cons coord orientation))

(defun ocoord (coord orientation)
  (check-type coord coord)
  (check-type orientation orientation)
  (cons coord orientation))

(define-compiler-macro ocoord (coord orientation)
  ‘(cons ,coord ,orientation))

(defun ocoord-coord (ocoord)
  (check-type ocoord ocoord)
  (car ocoord))

(define-compiler-macro ocoord-coord (ocoord)
  ‘(car ,ocoord))

(defun ocoord-orientation (ocoord)
  (check-type ocoord ocoord)
  (cdr ocoord))

(define-compiler-macro ocoord-orientation (ocoord)
  ‘(cdr ,ocoord))

The point of an ocoord is to be able to take a step forward in the direction of the orientation, or to turn clockwise or counterclockwise.

(defun ocoord-advance (ocoord)
  (check-type ocoord ocoord)
  (ocoord (2v+ (ocoord-coord ocoord) (ocoord-orientation ocoord))
          (ocoord-orientation ocoord)))

(define-compiler-macro ocoord-advance (ocoord)
  (let ((ocoord-var (gensym "OCOORD-")))
    ‘(let ((,ocoord-var ,ocoord))
       (ocoord (2v+ (ocoord-coord ,ocoord-var) (ocoord-orientation ,ocoord-var))
               (ocoord-orientation ,ocoord-var)))))

(defun ocoord-cw (ocoord)
  (check-type ocoord ocoord)
  (ocoord (ocoord-coord ocoord)
          (cond ((equal (ocoord-orientation ocoord) +north+) +east+)
                ((equal (ocoord-orientation ocoord) +east+) +south+)
                ((equal (ocoord-orientation ocoord) +south+) +west+)
                ((equal (ocoord-orientation ocoord) +west+) +north+))))

(defun ocoord-ccw (ocoord)
  (check-type ocoord ocoord)
  (ocoord (ocoord-coord ocoord)
          (cond ((equal (ocoord-orientation ocoord) +north+) +west+)
                ((equal (ocoord-orientation ocoord) +east+) +north+)
                ((equal (ocoord-orientation ocoord) +south+) +east+)
                ((equal (ocoord-orientation ocoord) +west+) +south+))))

The grid input to many of the puzzles is presented as “ASCII art” characters in a file. For example, the input might look like this:

....#.....
.........#
..........
..#.......
.......#..
..........
.#..^.....
........#.
#.........
......#...

To read this into a grid, we’ll need a function that converts a string into a list of atoms. We’ll need a function that converts a char to an atom:

(defun string-mapper (char-fn)
  "Returns a function that maps strings to lists."
  (lambda (line)
    (collect ’list
      (map-fn ’t
        char-fn
        (scan ’string line)))))

We can use this to read the input file into a grid:

(defun read-file-into-grid (char-fn filename)
  "Returns the contents of the file as a two-dimensional array."
  (row-list->grid
   (collect ’list
     (map-fn ’list
             (string-mapper char-fn)
             (scan-file filename #’read-line)))))

char-fn is called on each character in the file. If it is #’identity, then the grid will be a grid of characters. However, we usually want a grid of atoms, so we supply a function that converts a character to an atom.

(defun char->decimal (char)
  (- (char-code char) (char-code #\0)))

(defun char-interner (char-folder package)
  (lambda (char)
    (if (digit-char-p char)
        (char->decimal char)
        (intern (string (funcall char-folder char)) package))))

We can use this to read the input file into a grid:

;; Case folding
(read-file-into-grid (char-interner #’char-upcase *package*) "input.txt")

;; Case preserving
(read-file-into-grid (char-interner #’identity *package*) "input.txt")

Other miscellaneous functions

advent-pathname converts a relative pathname to an absolute pathname in the advent2024 directory. advent-pathname is used to find the input files.

(defun advent-pathname (pathname)
  (merge-pathnames pathname
                   (asdf/system:system-source-directory "advent2024")))

cartesian-product-list takes a list of lists and returns a list of lists that are the cartesian product of the input lists. For example, (cartesian-product-list ’((1 2) (3 4))) returns ((1 3) (1 4) (2 3) (2 4)).

(defun map-cons (car cdrs)
  (map ’list (lambda (cdr) (cons car cdr)) cdrs))

(defun cartesian-product (&rest; lists)
  (cartesian-product-list lists))

(defun cartesian-product-list (lists)
  (fold-left (lambda (tails terms)
               (mappend (lambda (term)
                          (map-cons term tails))
                        terms))
             (list nil)
             (reverse lists)))

integer-log is used to find the number of digits an integer has in a given base.

(defun integer-log (n base)
  "Returns two values, the integer-log of <n> in <base>, and the leftmost digit
in <base>."
  (if (< n base)
      (values 0 n)
      (multiple-value-bind (ilog l) (integer-log n (* base base))
        (if (< l base)
            (values (* ilog 2) l)
            (values (+ (* ilog 2) 1) (/ l base))))))

Miscellaneous list functions

I gave the miscellaneous list functions as a puzzle in a previous post. I’ll repeat them here for convenience.

map-pairs takes a list of items and maps a function over all pairs of items. For example: 

(map-pairs #’list ’(1 2 3))

((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))

revmap is like map, but it returns a list in reverse order.

revmap-cons, given a car and list of cdrs, returns a list of lists where each list has the car and one of the cdrs. The lists are returned in reverse order.

revmappend is like mappend, but it returns the list in reverse order.

remove-one-element returns a list of lists. Each sublist is the input list with one element removed.

Miscellaneous scanner

scan-suffixes takes a sequence and returns a series of the suffixes of the sequence. If include-empty? is true (the default), then the empty sequence is the last suffix. If proper? is true (default false), then the original full sequence is omitted from the series.

Armed with these miscellaneous functions, we can tackle the puzzles. I’ll write up some solutions in the next few posts.

Joe Marshall — Out of Practice List-fu

· 8 days ago

How is your list-fu? Mine gets rusty when I don’t manipulate lists for a while. Here are some simple puzzles to get the rust out.

1. Write a function that takes a list of items and maps a function over the pairs of items in the list, in the following way: The first argument to the function is taken from one of the elements in the list. The second argument is taken from one of the subsequent elements in the list. E.g., if the list is (a b c d), then

(map-pairs (lambda (x y) ‘(F ,x ,y)) ’(a b c d))

((F A B) (F A C) (F A D) (F B C) (F B D) (F C D))

2. Write a function revmap that is like mapcar, but the result is in reverse order.

3. Write a function map-cons that takes a car and a list of cdrs, and returns a list of the car consed on each of the cdrs.

4. Write a function revmappend that is like alexandria:mappend but is more efficient because it doesn’t try to preserve the order of the elements.

5. Write a function remove-one-element that takes a list of n elements and returns n lists of n-1 elements, where each sublist has one element removed from the original list.

Tim Bradshaw — The modern real programmer

· 18 days ago

This is adapted from an email from my friend Zyni, used with her permission. Don’t take it too seriously.

Real programmers do not write programs like this. If a real programmer has to deal with a collection of particles, they do not have some silly object which represents a particle, perhaps made up of other objects representing physical vectors, and then some array of pointers to these particle objects. That is a bourgeois fantasy and the people who do that will not long survive the revolution. They will die due to excessive pointer-chasing; many of them have already died of quiche.

Real programmers do today as they have always done: if they have some particles to simulate a galaxy they make an array of floating point numbers, in which the particles live.

This is how it has always been done, and how it always will be done, by people who care about performance.

And this is why Lisp is so superb. Because you can write this:

(for* ((i1 (in-particle-vector-indices pv))
       (i2 (in-particle-vector-indices pv i1)))
  (declare (type particle-vector-index i1 i2))
  (with-particle-at (i1 pv :name p1)
    (with-particle-at (i2 pv :name p2)
      (let/fpv ((rx (- p2-x p1-x))
                (ry ...)
                ...)
        ... compute interactions ...))))

And this is:

  • very fast1, because it all turns into optimized loops over suitable (simple-array double-float (*)) with no silly objects or consing;
  • relatively easy for a human to read, since you can see, for instance what (for ((i (in-particle-vector-indices v))) ...) is doing and do not have to second-guess some idiot loop form which will be full of obscure bugs;
  • quiche-compatible: you can easily write a function particle-at which will construct a particle object from a particle vector entry (such a function will later be excised as it has no callers, of course);
  • perhaps most important it is possible for a program to take this code and to look at it and to say, ‘OK, this is an iteration over a particle vector - it is not some stupid hard-to-parse (loop for ... oh I have no idea what this is ...) as used by the quiche people, it is (for ((i (in-particle-vector-indices v))) ...) and it is very easy to see what this is - and there are things I can do with that’ and generate Fortran which can be easily (or, less difficultly — is ‘difficultly’ a word? English is so hard) be made to run well on proper machines with sensible numbers of processors.

And this is the thing they still do not see. You write your program which uses the only useful data structure, but you also write your program in a language you have built designed so that both a human and another program can understand it, and do useful things with it, because your program says what it means. Every construct in your program should be designed so that this other program can get semantic information from that construct to turn it into something else.

And this is why Lisp is so uniquely useful for real orogrammers. Lisp has only one interesting feature today: it is a language not for writing programs, but for writing languages.

That is what real programmers do: they build languages to solve their problems. The real programmer understands only two things:

  • the only data structure worth knowing about is the array;
  • her job as a programmer is to write languages which will make writing programs to manipulate arrays easy for a human to understand;
  • and her other job is to write other programs which will take these programs and turn them into Fortran;
  • and when that is done she can go and ride her lovely cob to the fair.

Real programmers also can count only to two.

  1. I (Tim, not Zyni, who would use a cleverer integrator) wrote a mindless program to integrate systems of gravitating particles to test some of the things we’ve written that are mentioned in this email. On an Apple M1 it sustains well over 1 double precision GFLOP. Without using the GPU I think this is about what the processor can do. ↩

Neil Munro — Ningle Tutorial 3: Static Files Middleware

· 18 days ago

Contents

Introduction

Welcome back to this tutorial series, in this chapter we will be looking at the topic of static files, before we begin, we need to come to an understanding on just what static files are. Static files are files that do not need to be further processed by your application; images, videos, css, JavaScript files all generally do not need to be processed by your web applications, and thus can simply be served as is. Files that must be processed by your web application (like the templates from the previous tutorial) typically need further processing by your web application and thus are not static files, and could be called dynamic files (although this term isn't really used).

While developing an application there's often a requirement to de-couple these static files from the main application code, you might want to serve these separately in production and many web servers help you do this for performance reasons (in fact NGINX is very good at this), however you might not need the scalability locally while you are working on your application, and so Ningle has a middleware module to serve these static files when you don't need a dedicated static file server.

Another, more practical consideration of serving static files is that if you don't have a way to serve these files for you, you would have to write a controller for every image, or css file in your application, this wont scale well at all, and you'll spend most of the time writing code to serve files rather than building your application. Static file management allows you to serve a directory of files and reference them by path, but you must set it up correctly in the first place.

Note: We will be using djula, as we did before, however as of 2025-01-15 this has not yet been merged into quicklisp, you may need to clone the latest djula from github into your quicklisp/local-projects directory to gain access to the latest version needed for this tutorial.

Introducing Middleware

In reality Ningle deligates the responsibility of serving static files to the underlying lack package by way of the lack middleware. There are a number of different lack middleware modules available by default and throughout this tutorial we will look at most (if not all) of them.

In most web frameworks (Ningle included) middleware runs between the request being accepted and the code in your controller running. It is similar to a controller in that it has access to the request and response objects, and it may pass its response onto the next middleware function or a controller, it depends on what the middleware function is written to do.

In the case of static files here, the end goal will be that a request for a file will come to your webserver, and the static middleware module will run before any controllers, and if the static resource is found, the middleware function will return a response and with our not-found method, if the url couldn't be found, our not-found method runs instead.

Simple Middleware Example

To illustrate how this works in practice, we will write a piece of custom middleware that will add a new variable to the request environment, which we will then extract in a controller and display in a template, we'll use a number that gets incremented each time the middleware is run. In effect we will implement a hit counter in middleware!

Please note: This will not actually be used in the tutorial overall and serves only as a guide for how to write custom middleware generally, please follow this section to complete your understanding and feel free to include it (if you wish), but it will not be featured in the accompanying github code or used anywhere else in this tutorial.

In our main application code we define an app objects, under this we will define a new variable to track our count.

(defvar *app* (make-instance 'ningle:app))
(defvar *count* 0)

Now in order to take advantage of using middleware we must restructure how we built the ningle app, you may recall writing a start function that looked like the following.

(defun start (&key (server :woo) (address "127.0.0.1") (port 8000))
    (clack:clackup
     *app*
     :server server
     :address address
     :port port))

We will need to edit this and introduce the idea of a lack builder. This is a way of building an application with more capabilities. Instead of simply passing our *app* object to the clackup function, we instead wrap our *app* object in the lack builder function which allows us to plug in middleware.

(clack:clackup
     (lack.builder:builder *app*)
     :server server
     :address address
     :port port)

It may not be immediately obvious, but where previously the first argument to clackup was our *app* object, we instead call lack.builder.builder passing in *app*, it is in this builder call that we will hook in our middleware. Before we can do that however, we must write some middleware!

Above our start function I will write our middleware function:

(defun hit-counter-middleware (app)
  (lambda (env)
    (setf (getf env :hit-counter) (incf *count*))
    (funcall app env)))

This is all it needs, we need to define a function that first accepts a ningle application object, and it returns a function (a lambda in this instance) that accepts the env (the request environment), because there may be a chain of middleware functions that potentially terminate with our controller, the lambda must return the result of calling the next middleware function with the app and environment.

Within the body of the lambda, however, we are free to begin doing whatever we want!

In this example, we only do one thing, we add a new entry into the environment and assign it to be the incremented (incf) value of *count* with this line (setf (getf env :hit-counter) (incf *count*)).

We next must edit the controller to retrieve this stored value and render it into the template (which means we'll also need to edit the template).

Thankfully editing our controller is easy, we need only add a new keyword argument to the render-template* function.

(setf (ningle:route *app* "/")
      (lambda (params)
        (let ((user  (list :username "NMunro"))
              (posts (list (list :author (list :username "Bob")  :content "Experimenting with Dylan" :created-at "2025-01-24 @ 13:34")
                           (list :author (list :username "Jane") :content "Wrote in my diary today" :created-at "2025-01-24 @ 13:23"))))
          (djula:render-template* "index.html" nil :title "Home"
                                                   :user user
                                                   :posts posts
                                                   :hit-counter (getf (lack/request:request-env ningle:*request*) :hit-counter)))))

The only addition is the :hit counter (getf (lack/request:request-env ningle:*request*) :hit-counter) line. This will retrieve the :hit-counter value from the request environment.

In our index.html template, in the div with the class="container", we will add the following:

    <div class="row">
        <div class="col-12">
            <h4>Hits</h4>
            <p>{{ hit-counter }}</p>
        </div>
    </div>

The last thing we must do is return to the lack.builder section of our start function and hook the middleware into the app.

(lack.builder:builder #'hit-counter-middleware *app*)

It must be included before *app* as the hit-counter-middleware will be wrapping our application and run before anything in our app does. As this tutorial (and your own applications) grow, this line and the different middleware modules will change as requirements do.

If you save and load the project, you should see that there is a div in your template that updates a count every time the page is refreshed. At this point you may notice that the counter is incremented by 2 each time, this is not a mistake, this is because your web browser will request the page itself, and a favicon.ico file (and hit the not-found controller).

For clarity here is the edited main.lisp file:

(defpackage ningle-tutorial-project
  (:use :cl)
  (:export #:start
           #:stop))

(in-package ningle-tutorial-project)

(defvar *app* (make-instance 'ningle:app))
(defvar *count* 0)

(setf (ningle:route *app* "/")
      (lambda (params)
        (let ((user  (list :username "NMunro"))
              (posts (list (list :author (list :username "Bob")  :content "Experimenting with Dylan" :created-at "2025-01-24 @ 13:34")
                           (list :author (list :username "Jane") :content "Wrote in my diary today" :created-at "2025-01-24 @ 13:23"))))
          (djula:render-template* "index.html" nil :title "Home"
                                                   :user user
                                                   :posts posts
                                                   :hit-counter (getf (lack/request:request-env ningle:*request*) :hit-counter)))))

(defmethod ningle:not-found ((app ningle:<app>))
    (declare (ignore app))
    (setf (lack.response:response-status ningle:*response*) 404)
    (djula:render-template* "error.html" nil :error "Not Found"))

(defun hit-counter-middleware (app)
  (lambda (env)
    (setf (getf env :hit-counter) (incf *count*))
    (funcall app env)))

(defun start (&key (server :woo) (address "127.0.0.1") (port 8000))
    (djula:add-template-directory (asdf:system-relative-pathname :ningle-tutorial-project "src/templates/"))
    (clack:clackup
        (lack.builder:builder #'hit-counter-middleware *app*)
     :server server
     :address address
     :port port))

(defun stop (instance)
    (clack:stop instance))

Understanding how to write custom middleware is very important, and I hope that this has served as a good foundation, however, as mentioned at the beginning of this section we will not be using this piece of custom middleware in our application. You are free to include it if you wish, but it will not feature in the companion code in github.

Aceesslog Middleware

Now that we have discussed what middleware is, work it does, how it works, and how to implement it, we will look at some of the middleware modules included in lack which ningle therefore has access to.

We will start with what is known as accesslog middleware, it's a very simple piece of middleware that just logs requests as they come in.

As we did in the previous section, we must adjust the lack.builder line, however, this time we do not need to write any function, the middleware that comes with lack uses some simplified syntax.

(defun start (&key (server :woo) (address "127.0.0.1") (port 8000))
    (djula:add-template-directory (asdf:system-relative-pathname :ningle-tutorial-project "src/templates/"))
    (clack:clackup
        (lack.builder:builder :accesslog *app*)
     :server server
     :address address
     :port port))

If you recompile and run your application, and view the terminal output, you will see information about the incoming requests to the web server.

This is a simple example, but it highlights an important distinction that the bundled lack middleware isn't a reference to a function, it's a keyword, as we will see in the next section, they can be a little more complicated than just a keyword, but this particular piece of middleware, it is just a keyword to turn it on. Other pieces of middleware may be a list that include configuration options, if needed.

Static Files Middleware

What we would like to do, when we write our templates is to be able to tell our template that a file is a static file and must be served from the static location. We will need to use a special djula tag to inform our templates that a file is a static file, which may seem a little counter intuitive, however, if for some reason we need to change where static files are served from (for example we may initially host them locally, but then switch to s3 or cloudflare or something), we'd have to go through all our templates changing the url, whereas using static file middleware, we'd set up a base once, and if we need to change it, we change it in one place and then our templates wouldn't need to change at all.

While this sounds like a lot of work, remarkably, it isn't!

There's only really three steps to setting up static file handling in Ningle!

As we are using djula (and a reminder quicklisp may not yet have the latest version of djula, you may need to use git to clone it into your quicklisp/local-projects), we must configure djula to be aware of where our static files will be mounted. So, just as we added a template directory, we must also add a static directory, in our example this is in the start function:

(djula:add-template-directory (asdf:system-relative-pathname :ningle-tutorial-project "src/templates/"))
(djula:set-static-url "/public/")

This second line is the one we have added, when we use the static tag later on, it will know to use "/public/" as our static path.

NOTE: Be mindful to ensure there's a trailing slash when calling set-static-url!

The second thing we must do is hook into the lack static middleware.

(lack.builder:builder :accesslog
                      (:static
                       :root (asdf:system-relative-pathname :ningle-tutorial-project "src/static/")
                       :path "/public/")
                      *app*)

Mentioned previously, some middleware setup will be lists, in this instance, a list where the first item is a keyword naming the lack middleware module to use (this will be a common pattern with other lack middleware) and then any arguments that the middleware module uses. In this case, we need to define where on our host file system we will be storing our static files, this is the :root argument and we specify that relative to our project, static files will be stored in /src/static and we need to have these mounted on a path which is exactly what the :path argument does, we will hide the physical location of our static files (good security) and state that they're available behind "/public/".

For clarity, this is what the start function should look like:

(defun start (&key (server :woo) (address "127.0.0.1") (port 8000))
    (djula:add-template-directory (asdf:system-relative-pathname :ningle-tutorial-project "src/templates/"))
    (djula:set-static-url "/public/")
    (clack:clackup
      (lack.builder:builder :accesslog
                            (:static
                             :root (asdf:system-relative-pathname :ningle-tutorial-project "src/static/")
                             :path "/public/")
                            *app*)
     :server server
     :address address
     :port port))

The final thing we need to do is, in our templates, use the static tag to load a given static file. In the base.html file, you might want to display an image. You can use whatever image you like, but if you want to use the one I've created, you can use this.

You should put this file (or the image of your choice) in the src/static/images/ directory (and create it, if you have not), I have called the image logo.jpg and have stored it in src/static/logo.jpg. This will exposed it as /public/images/logo.jpg and from here we can place these into our templates.

<img src='{% static "images/logo.jpg" %}' alt='Logo'>

If you save, reload, and view this project in your web browser, you should see the image rendered as you might expect. Inspecting the page you will see that the src attribute will be src="/public/images/logo.jpg". The image is being served without writing having to write a controller, and is served from the root you defined.

Tidying Up

Now that we have the ability to serve images, css etc, we might want to take this time to writing some css (although I personally hate writing CSS), and making the site look good. Although it is beyond this tutorial to teach bootstrap or other css frameworks (although I will use bootstrap), I will be using bootstrap to make my site look a little nicer, you can refer to the github code to see exactly what I have done regarding frontend styling.

There is something I will do to help our application look a little better...

I will create a nicer looking error page that will take advantage of our new staticfiles middleware, so the contents of src/templates/error.html will be:

{% extends "base.html" %}

{% block content %}
    <div class="container">
        <div class="row">
            <div class="col-12">
                <h1>{{ error }}</h1>
                <img src="{% static "images/lua.jpg" %}" alt="A picture of a dog looking sad and confused" class="error-404">
            </div>
        </div>
    </div>
{% endcontent %}

I will save this photo to src/static/images/lua.jpg.

And in the main.lisp file, I will modify the not-found method:

(defmethod ningle:not-found ((app ningle:<app>))
    (declare (ignore app))
    (setf (lack.response:response-status ningle:*response*) 404)
    (djula:render-template* "error.html" nil :error "Not Found"))

I have also edited the controller for the index page:

(setf (ningle:route *app* "/")
      (lambda (params)
        (let ((user  (list :username "NMunro"))
              (posts (list (list :author (list :username "Bob")  :content "Experimenting with Dylan" :created-at "2025-01-24 @ 13:34")
                           (list :author (list :username "Jane") :content "Wrote in my diary today" :created-at "2025-01-24 @ 13:23"))))
          (djula:render-template* "index.html" nil :title "Home"
                                                   :user user
                                                   :posts posts))))

In my frontend I have edited the html to include a created-at attribute to the posts and included it as we did before with the post author and content:

<h5 class="card-title">{{ post.author.username }}</h5>
<p class="card-text">{{ post.content }}</p>
<p class="text-muted small">Posted on: {{ post.created-at }}</p>

The exact styling I leave up to you, but I wanted to be clear that there is a small content change to the html.

Conclusion

To recap, after working your way though this tutorial you should be able to:

  • Describe what static files are.
  • Describe what application middleware is.
  • Explain why it is advantagous to handle static files differently.
  • Explain how middleware works.
  • Create and use simple middleware functions.
  • Incorporate lack static middleware into your application.
  • Incorporate djula static tags in your html templates to serve static content.

Github

The link for this tutorial is available here.

Resources

Zach Beane — Maxima in the browser with ECL and wasm

· 22 days ago

Via Raymond Toy on the ecl mailing list, Maxima in the browser.

Joe Marshall — Valid Use Case for Copilot

· 31 days ago

Our compay proides us with GitHub copilot, which is yet another example of an “AI” engine. I’ve reviewed it before and I wasn’t particulary impressed. It writes mediocre code.

However, I found a use case where it really shines. I was setting up the blank project repositories for our upcoming hackathon. This involved creating a bunch of otherwise empty repositories with a customize README.md file. The simple solution was to automate this with an ad hoc shell script.

I don’t make a practice of writing shell scripts. I write a few every now and then, but I don’t live and breathe bash. It takes me a while because I forget the flags. I have to look up the exact syntax for things like the find command. Then I have to fight with the shell to get the quoting and escaping right. It’s a tedious chore. No doubt I would become adept at it if it were something I did daily, but it’s not.

So I decided to ask GitHub copilot to write some scripts for me. I gave it my problem statement: start with a file with a list of repository and description pairs. For each pair, look for the subdirectory with that name and descend into it. Use the sed command to modify the README.md file in the subdirectory to add the repository discription. Then use git to commit and push the change.

Copilot gave this a couple of seconds thought and came up with this script:

while IFS= read -r line; do
  dir_name=$(echo "$line" | cut -d' ' -f1)
  description=$(echo "$line" | cut -d' ' -f2-)
  if [ -d "$dir_name" ]; then
    sed -i "s/\[\[github_repo_description\]\]/$description/g" "$dir_name/README.md"
  else
    echo "Directory $dir_name does not exist."
  fi
done < descriptions.txt

find . -type d -name "hack*" -exec sh -c '
  cd "$0"
  if [ -f README.md ]; then
    git add README.md
    git commit -m "Update description."
    git push
  fi
' {} \;

It isn’t a script that’d I’d write home about, but it got the job done. I ran the script and had the repositories set up in couple of minutes. I could have written the script myself, but it would have take me longer. I had forgotten the options to the find command. I had forgotten the arguments to the cut command. I would have had to look them up. Copilot saved me that time.

A co-worker of mine questioned the engineering tradeoff of using a resource hog like generative AI to write crappy, throwaway shell scripts. From the standpoint of an indiviual developer, though, this is the first use case for copilot that I’ve where it actualy saved me time and effort.

Joe Marshall — Iteration

· 31 days ago

Iteration is simply that special case of recursion that doesn’t accumulate storage in the long term. It’s a notable special case because computer storage is finite, and you want to be able to write agorithms that are bound by constant space.

There are two common strategies that computer languages use to approach iteration. Functional languages like Scheme and Haskell make sure that normal function calls do not accumulate storage per se. Function calls can be used to direct the control flow, and if they direct the control flow in a loop, you will iterate. Most other languages achieve iteration via special iteration constructs that you must use if you want to iterate. Each of these approaches has its own advantages and disadvantages.

The advantage of using special iteration constructs are these:

  • It is clear that you are iterating.
  • Special constructs are usually optimized for iteration and have particular compiler support to make them efficient.
  • Special constructs are constrained so that you cannot accidentally write non-iterative code.

The disadvantage of using special iteration constructs are these:

  • Special constructs are drawn from a fixed set of constructs that are built in to the language. If you want to iterate differently, you are out of luck.
  • Special constructs usually do not cross function boundaries. Iteration must reside in a single function.
  • You have to decide beforehand that you want to iterate and choose an iteration construct.
  • Special constructs are usually imperative in nature and operate via side effects.

The alternative approach used by functional languages is to make the language implementation tail recursive. This has these advantages:

  • Iteration is automatic. You don’t have to decide that you want to iterate, it just happens when it can.
  • Iteration can cross function boundaries.
  • You can write your own iteration constructs and build them out of ordinary functions.
  • Iteration can be done purely functionally, without side effects.

The disadvantages of using tail recursion for iteration are these:

  • It is not obvious that you are iterating or intended to.
  • You have to be careful to place all the iteration in tail position or you will blow the stack. Beginner programmers often have difficulty recognizing which calls are tail calls and can find it hard to avoid blowing the stack.
  • Small, innocent looking changes in the code can change its behavior to be non tail recursive, again blowing the stack.
  • The stack no longer contains a complete call history. If you rely on the stack as a call history buffer for debugging, you may find debugging more difficult.

The code in an iteration can be classified as being part of the machinery of iteration — the part that sets up the itertion, tests the ending conditional, and advances to the next iteration — or part of the logic of the iteration — the specific part that you are repeating. The machinery of the iteration is usually the same across many iterations, while the logic of the iteration is idiomatic to the specific instance of iteration. For example, all iterations over a list will have a null test, a call to CDR to walk down the list, and a call to CAR to fetch the current element, but each specific iteration over a list will do something different to the current element.

There are several goals in writing iterative code. One is to have efficient code that performs well. Another is to have clear code that is easy to understand, debug, and maintain. You choose how to iterate based on these considerations. For the highest performing code, you will want detailed control over what the code is doing. You may wish to resort to using individual assignments and GOTO statements to squeeze the last clock cycles out of an inner loop. For the clearest code, you will want to use a high degree of abstraction. A clever compiler can generate efficient code from highly abstracted code, and experienced programmers know how to write abstract code that can be compiled to efficient code.

Here are some examples of iteration strategies Lisp. To make these examples easy to compare I chose a simple problem to solve: given a list of numbers, return both a list of the squares of the numbers and the sum of the squares. This is a simple problem that can be solved in many ways.

Tagbody and Go

A tagbody is a block of code that is labeled with tags. You can jump to a tag with a go statement. This is a very low level form of iteration that is not used much in modern Lisp programming. Here is an example of a tagbody:

(defun iteration-example-with-tagbody (numbers)
  (let ((squares ’())
        (total 0)
        (nums numbers))
    (tagbody
     start
       (if (null nums)
           (go end))
       (let ((square (* (car nums) (car nums))))
         (setq squares (cons square squares))
         (incf total square))
       (setq nums (cdr nums))
       (go start)
     end
       (values (nreverse squares) total))))

This is like programming in assembly code. The go instructions turn into jumps. This code is very efficient, but it is not particularly clear. The machinery of the iteration is mixed in with the logic of the iteration, making it hard to see what is going on. The code is not very abstract.

State Machine via Mutual Tail Recursion

Here we use tail recursion to iterate. The compiler will turn the tail recursive call into a jump and the variable rebinding into assignments, so this code will be about as efficient as the tagbody code above.

(defun iteration-example-tail-recursive (numbers &optional (squares ’()) (total 0))
  (if (null numbers)
      (values (nreverse squares) total)
      (let ((square (* (car numbers) (car numbers))))
        (iteration-example-tail-recursive
         (cdr numbers)
         (cons square squares)
         (+ total square)))))

This state machine only has one state, so it is not a very interesting state machine. The ultimate in iteration control is to write an iterative state machine using mutually tail recursive functions. The compiler will generate very efficient code for this, and you can write the code in a very abstract way. Here is an example of a state machine that simulates the action of a turnstile:

(defun turnstile (actions)
  "State machine to simulate a turnstile with actions ‘push’, ‘coin’, and ‘slug’."
  (locked-state actions ’() ’()))

(defun locked-state (actions collected return-bucket)
  (cond ((null actions) (list collected return-bucket))
        ((eql (car actions) ’coin)
         (unlocked-state (cdr actions) collected return-bucket))
        ((eql (car actions) ’push)
         (locked-state (cdr actions) collected return-bucket))  ;; Ignore push in locked state
        ((eql (car actions) ’slug)
         (locked-state (cdr actions) collected (append return-bucket ’(slug)))) ;; Return slug
        (t (locked-state (cdr actions) collected return-bucket))))

(defun unlocked-state (actions collected return-bucket)
  (cond ((null actions) (list collected return-bucket))
        ((eql (car actions) ’push)
         (locked-state (cdr actions) (append collected ’(coin)) return-bucket))
        ((eql (car actions) ’coin)
         (unlocked-state (cdr actions) collected (append return-bucket ’(coin)))) ;; Return coin
        ((eql (car actions) ’slug)
         (unlocked-state (cdr actions) collected (append return-bucket ’(slug)))) ;; Return slug
        (t (unlocked-state (cdr actions) collected return-bucket))))

;; Example usage:
(turnstile ’(coin push coin push))  ;; => ((coin coin) ())
(turnstile ’(push coin push))       ;; => ((coin) ())
(turnstile ’(coin coin push push))  ;; => ((coin) (coin))
(turnstile ’(push))                 ;; => (NIL NIL)
(turnstile ’(coin push push))       ;; => ((coin) ())
(turnstile ’(coin coin coin push))  ;; => ((coin) (coin coin))
(turnstile ’(slug coin push))       ;; => ((coin) (slug))
(turnstile ’(coin slug push))       ;; => ((coin) (slug))
(turnstile ’(slug slug push coin push)) ;; => ((coin) (slug slug))

The iteration machinery is still interwoven with the logic of the code. We’re still finding calls to null and cdr sprinkled around the code. Nonetheless, structuring iterative code this way is a big step up from using a tagbody and go. This is my go-to method for compex iterations that cannot easily be expressed as a map or reduce.

Loop Macro

Common Lisp’s loop macro is a very powerful iteration construct that can be used to express a wide variety of iteration patterns.

defun loop-iteration-example (numbers)
  (loop for num in numbers
        for square = (* num num)
        collect square into squares
        sum square into total
        finally (return (values squares total))))

Call me a knee-jerk anti-loopist, but this doesn’t look like Lisp to me. It has some major problems:

  • It is highly imperative. To understand what is going on, you have to follow the code in the order it is written. You need to have a mental model of the state of the loop at each point in the iteration. Running into a loop when reading functional code takes you out of the zen of functional programming.
  • The bound variables are not lexical, they are scattered around the code. You have to carefully examine each clause to figure out what variables are being bound.
  • You need a parser to walk the code. There is nothing that delimits the clauses of the loop; it is a flat list of random symbols and forms. You couldn’t easily write a program that takes a loop form and transforms it in some way.

Do and Friends

The do macro, and its friends dolist, dotimes, and do*, etc., are the most common iteration constructs in Common Lisp.

(defun iteration-example-with-do (numbers)
  (let ((squares ’())
        (total 0))
    (do ((nums numbers (cdr nums)))
        ((null nums) (values (nreverse squares) total))
      (let ((square (* (car nums) (car nums))))
        (setq squares (cons square squares))
        (incf total square)))))

The do macros have some drawbacks:

  • They are imperative. The body of a do loop ultimately must have some sort of side effect or non-local exit to “get a value out”. Notice how we bind accumulator variables in an outer scope and assign them in the inner one. This is a common pattern in a do loop.
  • They do not compose. You can nest a dotimes inside a dolist, e.g., but you cannot run a dotimes in parallel with a dolist.
  • They are incomplete. There is no do-array or do-string, for example.

But at least you can parse them and transform them. They are structured, and you can write a program that walks the clauses of a do loop and does something with them.

Map and Reduce

Map and reduce abstract the machinery of iteration away from the logic of the iteration through use of a monoid (a higher order function). The resulting code is clear and concise:

(defun iteration-example-with-map-reduce (numbers)
  (let* ((squares (map ’list (lambda (num) (* num num)) numbers))
         (total (reduce #’+ squares)))
    (values squares total)))

The looping is implicit in the mapcar and reduce functions. You can usually make the assumption that the language implemetors have optimized these functions to be reasonably efficient.

I often see programmers writing looping code when a perfectly good library function exists that does the same thing. For example, it is common to want to count the number of items in a sequence, and Commmon Lisp supplies the count function just for this purpose. There is no need to write a loop.

Common Lisp provides a filter function, but it is called remove-if-not.

The drawback of using these functions is that large intermediate sequences can be created. In our example code, the entire list of squares is constructed prior to reducing it with #’+. Of course the entire list is one of the return values, so you need it anyway, but if you only needed the sum of the squares, you would prefer to sum it incrementally as you go along rather than constructing a list of squares and then summing it. For small sequences, it doesn’t make a difference.

Series

The series macro suite attempt to bring you best of both worlds. You write series expressions that look like sequence functions, but the macro recognizes that you are iterating and generates efficient incremental code.

(defun iteration-example-with-series (numbers)
  (let ((squares (map-fn ’integer (lambda (n) (* n n)) (scan ’list numbers)))
    (values (collect ’list squares)
            (collect-sum squares))))

This code is very similar to the sequence case, but the series macro will generate code that does not construct the entire list of squares before summing them. It will sum them incrementally as it goes along.

Series will expand into a tagboy. For example, the above code will expand into something like this:

(COMMON-LISP:LET* ((#:OUT-1015 NUMBERS))
  (COMMON-LISP:LET (#:ELEMENTS-1012
                    (#:LISTPTR-1013 #:OUT-1015)
                    (SQUARES 0)
                    #:SEQ-1018
                    (#:LIMIT-1019
                     (COMMON-LISP:MULTIPLE-VALUE-BIND (SERIES::X SERIES::Y)
                         (SERIES::DECODE-SEQ-TYPE (LIST ’QUOTE ’LISTS))
                       (DECLARE (IGNORE SERIES::X))
                       SERIES::Y))
                    (#:LST-1020 NIL)
                    (#:SUM-1023 0))
    (DECLARE (TYPE LIST #:LISTPTR-1013)
             (TYPE INTEGER SQUARES)
             (TYPE (SERIES::NULL-OR SERIES::NONNEGATIVE-INTEGER) #:LIMIT-1019)
             (TYPE LIST #:LST-1020)
             (TYPE NUMBER #:SUM-1023))
    (TAGBODY
     #:LL-1026
      (IF (ENDP #:LISTPTR-1013)
          (GO SERIES::END))
      (SETQ #:ELEMENTS-1012 (CAR #:LISTPTR-1013))
      (SETQ #:LISTPTR-1013 (CDR #:LISTPTR-1013))
      (SETQ SQUARES ((LAMBDA (N) (* N N)) #:ELEMENTS-1012))
      (SETQ #:LST-1020 (CONS SQUARES #:LST-1020))
      (SETQ #:SUM-1023 (+ #:SUM-1023 SQUARES))
      (GO #:LL-1026)
     SERIES::END)
    (COMMON-LISP:LET ((SERIES::NUM (LENGTH #:LST-1020)))
      (DECLARE (TYPE SERIES::NONNEGATIVE-INTEGER SERIES::NUM))
      (SETQ #:SEQ-1018 (MAKE-SEQUENCE ’LISTS (OR #:LIMIT-1019 SERIES::NUM)))
      (DO ((SERIES::I (1- SERIES::NUM) (1- SERIES::I)))
          ((MINUSP SERIES::I))
        (SETF (ELT #:SEQ-1018 SERIES::I) (POP #:LST-1020))))
    (VALUES #:SEQ-1018 #:SUM-1023)))

90% of the time, the series macro will produce very efficient code, but 10% of the time the macro loses its lunch. It takes a little practice to get use to when the series macro will work and to write code that the series macro can handle.

Conclusion

There are many ways to iterate in Lisp, some are more efficient than others, some are more abstrac than others. You choose the way that suits your needs. I like the abstraction of the series macro, but I will also use a library function like count when it is appropriate. When I need tight control, I’ll write a state machine.

vindarel — New resource specialized on web development in Common Lisp

· 34 days ago

I just released a new documentation website specialized on web development in Common Lisp:

I’d be embarrassed to tell how long it took me to grasp all the building blocks and to assemble a resource that makes sense. I hope it serves you well, now don’t hesitate to share what you are building, it creates emulation!

In the first tutorial we build a simple app that shows a web form that searches and displays a list of products.

We see many necessary building blocks to write web apps in Lisp:

  • how to start a server
  • how to create routes
  • how to define and use path and URL parameters
  • how to define HTML templates
  • how to run and build the app, from our editor and from the terminal.

In doing so, we’ll experience the interactive nature of Common Lisp.

In the user log-in section, we build a form that checks a user name and a password:

We also introduce databases, and more topics.

The sources are here: https://github.com/web-apps-in-lisp/web-apps-in-lisp.github.io/ and the GitHub Discussions are open.

Joe Marshall — &lambda; Calculus

· 34 days ago

A lambda calculus is a set of rules and strategies for manipulating logical expressions. As Church defined them, these logical expressions are linear lists of symbols. A symbol is effectively a variable. Two expressions in sequence indicate a function application. The special symbol λ is just a marker to indicate a function. Parenthesis can be used to group expressions.

McCarthy’s S-expressions are an alternative representation of a logical expression that is more suitable for a computer. Rather than a linear list of symbols, S-expressions use a tree structure of linked lists in memory. Symbols are still variables, lists represent function application, the special symbol lambda at the beginning of a list indicates a function, and grouping is achieved by nesting a list within another.

When McCarthy invented S-expressions, he wanted to show that the nested list structure of S-expressions could faithfully represent the logical expressions from lambda calculus. (It can.) A lambda calculus can be restated as a set of rules and strategies for manipulating S-expressions. This makes it easier for a computer to do lambda calculus. As a Lisp hacker, I find it also makes it easier for me to think about lambda calculus.

Your basic lambda calculus just has symbols, lists, and λ expressions. That’s it. But let us introduce one more element. Recall that we can think of a LET expression as syntactic sugar for a list (function call) where the first element (the operator) is a lambda expression. We’ll keep our S-expressions fully sugared and write all such lists as LET expressions. So now our S-expressions have symbols, lists, λ expressions, and LET expressions.

The two basic rules for manipulating S-expressions are α, which is a recursive rule for renaming a symbol in an S-expression, and β, which gets rid of a selected LET expression. A basic lambda calculus consists of these two rules and a strategy for selecting which LET expressions to get rid of. β reduces a LET expession by substituting the variables for their bindings in the body of the LET. α is used as needed to avoid unwanted variable capture during β-reduction. β eliminates one LET expression, but it can introduce more if you end up substituting a λ expression into operator position.

If an expression contains no LET expressions, we say it is in “normal form”. A common task in lambda calculus is to try to reduce an expression to normal form by attempting to eliminate all the LET expressions. Sometimes you cannot achieve this goal because every time you apply the β rule to eliminate a LET expression, it ends up introducing further LET expressions.

There are many strategies for selecting LET expressions to eliminate. Not all strategies will necessarily end up getting you to a normal form, but all strategies that do end up at a normal form end up at the same normal form (modulo the variable names). One strategy is of note: selecting the leftmost, outermost LET expression and reducing it first is called “normal order”. It is notable because if any strategy converges to normal form, then the normal order strategy will, too. However, the normal order strategy can lead to an exponential explosion of intermediate expressions. There are other strategies that avoid the exponential explosion, but they don’t always converge to normal form. Pick your poison.

α and β are the only rules we need to compute with S-expressions. The simple lambda calculus with α and β is universal — it can compute anything that can be computed. It is Turing complete.

I don’t know about you, but I find it quite remarkable that this can compute anything, let alone everything. Nothing is going on here. α just renames symbols. Using α-conversion to rename all the foos to bars doesn’t change anything but the symbol names. We define expression equivalence modulo α, so the actual names of the symbols isn’t important. Apparently β-reduction does computation, but it is hard to say how, exactly. It is just simplifying LET expressions by replacing variables with what they are bound to. But a variable is simply a name for a binding. When you replace a variable with what it is bound to, you don’t change any values. The resulting expression may be simpler, but it means the same thing as the original.

We use β reduction as a model of subroutine (function) calls. In a subroutine call, the values of the arguments are bound to the names of the arguments before evaluating the body of the subroutine. In β reduction, the body of the expression is substituted with the names bound to the value expressions. The lambda calculus model of a computer program will have a β reduction wherever the program has a subroutine call. A lambda calculus expression with opportunities for β reduction can be translated into a computer program with subroutine calls at those locations. It’s a one-to-one mapping. Since we can compute anything using just the α and β rules, we can likewise compute anything with just function calls. I think that’s pretty remarkable, too.

Turing’s machine formalism was designed to be understandable as a physical machine. Turing was particular that his machine could be realized as a mechanical object or electronically. It is far less clear how to make a lambda calculus into a physical machine. Once we recognize that β can be realized as a subroutine in software, we can see that Church’s lambda calculus formalism can be understable as a virtual machine.

Church’s Calculi of Lambda Conversion is a cool book where he lays out the principals of lambda calculus. It is pretty accessible if you have experience in Lisp, and the examples in the book will run in a Scheme interpreter if you translate them.

Joe Marshall — Substitution vs. State Transition

· 42 days ago

With a traditional curly-brace language, you have a model of a machine. A program specifies a sequence of state transitions that the machine should go through. When all the state transitions have taken place, the machine is in a final state, and the program is done.

As a programmer, you have to keep a mental model of the state of the machine at various points in the program. Your mental model has to include a temporal element — you have to remember what instruction you are working on, and what comes next. For each instruction, you have to consider the state before and after executing the instruction.

Lisp is very different from this. A Lisp program isn't a series of instructions, it is a tree of symbols. If you don’t use side effects, you can think of the Lisp interpreter as a simple substitution engine that operates on this tree. The interpreter just substitutes symbols with their values. You don’t have to consider any state before and after substitution because substitution doesn’t change anything.

Even if you do use side effects, you can still think of the interpreter as a substitution engine, but the substitution algorithm is more complicated. You will need a mental model that includes state and a temporal component, but it is still basically a substitution model.

Substitution models are easier to reason about than state transition models. This is why Lisp is so powerful. It takes a little practice to get used to programming with a simple substitution model. That’s why Lisp has a learning curve, especially for people who expect, and are used to, a state transition model.

You can also reason about a Lisp program using a state transition model. You can switch between the two models and use whatever mental model is most appropriate for the problem at hand.

You can impose a substitution model on curly-brace language, but it is more difficult. Curly-brace languages are designed to make you think about state transitions — indeed, many such languages force you to use a state transition to accomplish even the most simple conditionals and iterations — and the language doesn’t make it easy to ignore them and focus on the final value.

If Lisp is your first computer language, you learn the simple substitution model first. You’ll eventually have to learn about state transitions because they are needed to explain side effects. But you’ll mostly want to write programs that you can reason about using a substitution model. If you learn a curly-brace language first, you’ll have to think beyond the state transition model you have been taught and are using to reason about programs.

Many people find it difficult to learn how to reason with a new model. After all, the old model should work — it is universal. “Just assign the variable, don’t make me jump through hoops.” People who have a hard time wrapping their heads around substitution will probably find Lisp confusing and frustrating. But some people are able to embrace the substitution model and learn how it relates to the state transition model. These people will find Lisp to be a mind-expanding, powerful, expressive language.

Zach Beane — OCR from Common Lisp

· 43 days ago

Neat use of CL for OCR by Nick Faro. It leverages FFI and run-program nicely to get the job done.

I think run-program or equivalent is amazingly handy at getting quick CL access to outside functionality.

I ran a busy website that used imagemagick a lot, but I never bothered to use FFI. I called “convert” and friends via run-program, and it had the advantage that incorrect use of the C API never crashed my CL session.

run-program is not particularly fast, but for my application (and many others) it can be fast enough.

Joe Marshall — GitHub glitch bites hard (and update)

· 44 days ago

Update: Possible rogue process

GitHub reports that the call that removed the users was not the Copilot API but rather a call to the org membership API made by one of our bots.

We have a cron job that runs daily and keeps GitHub in sync with our internal databases. When GitHub and our internal databases disagree, the cron job makes API calls to reconcile the difference. It has the ability to remove users if it think they are no longer supposed to be members of the org.

It seems to have erroneously removed a large number of members. It was purely coincidence that I was editing copilot licenses at or around the time.

The question now is why? My hypothesis is that a query to our internal database only produced a partial result. The number of people determined to be valid users was far fewer than it should have been, and the cron job acted (correctly) and removed the users that were not verified by the database query. But it is hard to say for sure. I’ll need to check the cron job logs to see if I can determine what went wrong. It is very unusual, though. I’ve been here for years and I’ve never seen the cron job glitch out before. This is my working hypothesis for the moment. Perhaps it was some other error that made it think that the membership was greatly reduced.

I got bit hard by a GitHub bug last week.

Now GitHub has “organizations” which are owners of groups of repositories. GitHub carefully handles organization membership. You cannot directly join an organization, you must be invited by the organization. This gives the organization control over who can join the organization. But an organization also cannot directly add you as a member. It can invite you to join, but you must choose to accept the invitation. This gives you control over which organizations you are associated with. Membership in an organization is jointly controlled by the organization and the member. There is no way to bypass this.

This is source of friction in the onboarding process in our company. We have a few repositories on GitHub that are owned by the company. When a new hire joins the company, we want to make them members of the organization. GitHub does not provide any way to automate this. Instead, we direct new hires to an internal web site that will authenticate and authorize them and then let them issue an invitation to join the organization. GitHub won’t give them access until they accept the invitation. This is a manual process that is error prone and places the burden of doing it correctly on the new hire. We often have to intervene and walk them through the process.

Keep this in mind.

Our company provides GitHub Copilot to our developers. Some developers like it, but many of our developers choose not to use it. While Copilot licenses are cheap, there is no point in paying for a license that is not used. The UI for GitHub Copilot will display the last time a person used Copilot. It is easy to see a small set of our users who have never logged on to Copilot. We decided to save a few bucks by revoking unused Copilot licenses. We reasoned that we could always turn it back on for them if they wanted to use it.

To test this out, I selected a few of the users who had never logged in to Copilot. I turned off the checkbox next to their names in the Copilot UI and clicked the save button. It appeared to work.

Within an hour I started getting complaints. People who claimed to be active Copilot users were getting messages that their Copilot access was revoked. It seems that the UI had listed several active users as “never logged in” and I had just revoked their access.

It got worse. I had only revoked a few licenses, but dozens of people had had their access revoked. It seems that GitHub had eagerly revoked the licenses of far more people than I had selected.

It got even worse. I have a list of everyone who should have access, so I know who to re-enable. But I cannot re-enable them. It seems that in addition to revoking their Copilot access, GitHub had taken the extra step of removing their membership in the organization. I cannot restore their membership because of the way GitHub handles organization membership, so until they visit our internal web site and re-issue the invitation to the organization, I cannot restore their Copilot access. This has been a monumental headache.

I’ve spent the week trying to explain to people why their Copilot access and organization membership was revoked, what steps they need to take to restore it, and why I cannot restore it for them.

It looks like I’m going to be spending a lot of time on this next week as well.

GitHub has an enterprize offering that allows you to automate account creation and organization membership. We've been considering this for a while. Unfortunately, you cannot mix legacy accounts with enterprize accounts, so we would have to atomically migrate the entire company and all the accounts to the enterprize offering. This would be a risky endeavor for only a little gain in convenience.

Joe Marshall — fold-&hellip; and monoids

· 44 days ago

Suppose you satisfy these axioms:

  • you have a binary function · and a set that · is closed over (i.e. for all x, y in the set, x·y is in the set)
  • · is associative, ((a · b) · c) = (a · (b · c))
  • There is an an identity element I: a · I = I · a = a

Then · is called a semigroup or “monoid”.

Monoids come from abstract algebra, but they are ubiquitous in computer science. Here are some monoids: string-append over strings, addition over integers, state transition over machine states, compose over unary functions.

Alternatively, we can define a monoid as a binary function · that is closed under folds fold-left or fold-right. That is, (fold-left #’· I list-of-set-elements) is an element of the set. Folds abstract the processing lists of set elements. The walk through the list, the end test, and the accumulation of the result are all taken care of by the implementation of fold. You get to focus on the monoid that acts on each element.

Folds come in two flavors: fold-left and fold-right. fold-left has an obvious iterative implementation, but the result is accumulated left to right, which can come out backwards. fold-right has an obvious recursive implementation which accumulates right to left, The result comes out in the right order, but the recursion can cause problems if the stack space is limited.

Here are some stupid tricks you can do with folds and monoids.

Create n-ary functions

If we curry the call to fold, we extend the binary function of two arguments to an n-ary function of a list of arguments. For example, n-ary addition is just a fold over binary addition. (fold-left #’+ 0 list-of-integers). Likewise, n-ary compose is just a fold over binary compose.

Fold-… is self documenting

If I haven’t used fold-left or fold-right in a while, I sometimes forget which one computes what. But fold-left and fold-right can document themselves: use a combining function that returns the list (F a b) to indicate a call to F:

> (fold-left (lambda (a b) (list ’F a b)) ’|...| ’(c b a))
(F (F (F |...| C) B) A)

> (fold-right (lambda (a b) (list ’F a b)) ’(a b c) ’|...|)
(F A (F B (F C |...|)))

You can see the structure of the recursion by using list as the combining function:

> (fold-left #’list ’|...| ’(c b a))
(((|...| C) B) A)

> (fold-right #’list ’(a b c) ’|...|)
(A (B (C |...|)))

fold-… works on groups

A group is a special case of a monoid where the combining function is also invertible. fold-… can be used on a group as well. For example, fold-left can be used on linear fractional transformations, which are a group under function composition.

fold-… as an accumulator

The combining function in fold-left must be at least semi-closed: the output type is the same as the type of the left input. (In fold-right, the output type is the same as the type of the right input.) This is so we can use the output of the prior call as the input to the next call. In effect, we set up a feedback loop between the output to one of the inputs of the binary function. This feedback loop has a curious property: it behaves as if it has state. This is happens even though both fold-… and the combining functions are pure functions. The state appears to arise from the feedback loop.

We can use fold-… to accumulate a value. For fold-left, at each iteration, the accumulator is passed as the first (left) argument to the combining function while the next element of the list is the second (right) argument. The combining function returns a new value for the accumulator (it can return the old value if nothing is to be accumulated on this step). The result of the fold-left is the final value of the accumulator.

Note that because the accumulated value is passed as the first argument, you cannot use cons as the combining function to accumulate a list. This is unfortunate because it seems obvious to write (fold-left #’cons ’() ...) to accumulate a list, but that isn’t how it works. However, if you swap the arguments to cons you’ll accumulate a list:

(defun xcons (cdr car) (cons car cdr))

(defun revappend (elements base)
  (fold-left #’xcons base elements))

fold-… as a state machine

Although fold-left is commonly used to accumulate results, it is more general than that. We can use fold-left as a driver for a state machine. The second argument to fold-left is the initial state, and the combining function is the state transition function. The list argument provides a single input to the state machine on each state transition.

For example, suppose you have a data structure that is a made out of nested plists. You want to navigate down through the plists to reach a final leaf value. We set up a state machine where the state is the location in the nested plists and the state transition is navigation to a deeper plist.

(defun getf* (nested-plists path)
  (fold-left #’getf nested-plists path))

Alternatively, we could drive a state machine by calling fold-left with an initial state and list of state transtion functions:

(defun run-state-machine (initial-state transitions)
  (fold-left (lambda (state transition)
               (funcall transition state))
             initial-state
             transitions))

Visualizing fold-left

If we unroll the recursion in fold-left, and introduce a temp variable to hold the intermediate result, we see the following:

(fold-left F init ’(c b a))

temp ← init
temp ← F(temp, c)
temp ← F(temp, b)  
temp ← F(temp, a)

I often find it easier to write the combining function in a fold-… by visualizing a chain of combining functions wired together like this.

Generating pipelines

Now let’s partially apply F to its right argument. We do this by currying F and immediately supplying an argument:

(defun curry-left (f)
  (lambda (l)
    (lambda (r)
      (funcall f l r))))

(defun curry-right (f)
  (lambda (r)
    (lambda (l)
      (funcall f l r))))

(defun partially-apply-left (f l)
  (funcall (curry-left f) l))

(defun partially-apply-right (f r)
  (funcall (curry-right f) r))

We can partially apply the combining function to the elements in the list. This gives us a list of one argument functions. In fact, for each set element in the set associated with our monoid, we can associate a one-argument function. We can draw from this set of one-argument functions to create pipelines through function composition. So our visualization

temp ← init
temp ← F(temp, c)
temp ← F(temp, b)  
temp ← F(temp, a)

becomes

temp ← init
temp ← Fc(temp)
temp ← Fb(temp)  
temp ← Fa(temp)

We can write this pipeline this way:

result ← Fa ← Fb ← Fc ← init

or this way:

result ← (compose Fa Fb Fc) ← init

We can pretend that the elements of the set associated with monoid are pipeline stages. We can treat lists of set elements as though they are pipelines.

Notice how we never write a loop. We don’t have the typical list loop boilerplate

(if (null list)
         ... base case ...
  (let ((element (car list))
        (tail (cdr list)))
    ... ad hoc per element code ...
    (iter tail)))

Instead, we have a function that processes one element at a time and we “lift” that function up to process lists of elements.

Pipelines are easier to reason about than loops. fold-… converts loops into pipelines.

It takes a little practice to use fold-… in the less obvious ways. Once you get used to it, you’ll see them everywhere. You can eliminate many loops by replacing them with fold-….

Monoids vs. Monads

A monad is a monoid over a set of curried functions. You use a variant of compose to combine the curried functions. Monads force sequential processing because you set up a pipeline and the earlier stages of the pipeline naturally must run first. That is why monads are used in lazy languages to embed imperative subroutines.

Zach Beane — Toilet Lisp

· 45 days ago

This seems like an interesting old incomplete project - Toilet Lisp with some old source code too.

Joe Marshall — A Newbie Is Exposed to Common Lisp

· 45 days ago

At ChangeSafe our product was written in Common Lisp. But for "black box" testing, we didn't need the test code to be written in Common Lisp. In fact, we wanted the test code to be written in an unrelated language so that we could be sure that the product's API was language neutral.

Skill in Common Lisp was simply not a requirement — not even relevant — for QA jobs. We were a startup company, so the initial hires for QA would set the culture for the department. We were looking for people who had initiative, were self-motivated, could work with vague and underspecified guidance, figure out the job that needed to be done, and then do it. We found a young guy named Eric who fit the bill.

Eric set up our QA efforts and wrote the initial black box test code for the product. In his spare time, off the clock, he got curious about Common Lisp and why we chose to develop the product using it. He had never heard of the language. He decided to pick up the Common Lisp specification and teach himself the language. I told him that it was unnecessary for the job, but I didn't discourage him from broadening his horizons.

Eric came to me early on and asked me to explain some details about Common Lisp. He had just learned about lambda expressions and was trying them out with mapcar and other higher-order functions. It was obvious to him that a lambda expression was capturing the local stack variables. When the lambda was passed downwards to mapcar, it was able to access the variables from its point of origin further up the stack. He could see the potential, and thought it was an interesting feature.

Then, just to see what would happen, he returned a lambda expression up the stack. To his suprise, it still worked, even though the stack frame was no longer there. He had three questions for me the next day: Was this intentional? How did it work? And why would anyone do this?

I assured him that it was intentional. The feature worked by the compiler generating code to move the captured variables off of the stack and into the heap. The designers of Lisp wanted lambda expressions to “just work”, regardless of how you passed them around. The correct engineering decision — the “right thing” — was to place the burden of making this happen on the language implementor, not on the user of lambda expressions.

I told him that the reason we used Common Lisp was because the designers of the language placed a high value on doing thing “the right way”. Things were carefully designed to be easy to use and to work correctly, even in the corner cases. It was recognized that this would make it more difficult to implement the language, but a lot easier to program in it.

Eric was, quite frankly, impressed by this. It was clear to him that the designers of Lisp were in a league of their own. He couldn't wait to learn more about the language.

Incidentaly, Eric wasn't the least bit put off by the paretheses. He considered them to be a quirk that was ideomatic of the language. Some languages use infix notation, some calculators use postfix. Lisp happened to use prefix notation. It was no big deal.

Eric was a great hire and had the potential to go far had the company not gone under when the internet bubble burst.

Joe Marshall — Dvorak and Lisp

· 45 days ago

I use a slightly modified Dvorak keyboard. It is like a standard Dvorak keyboard, but the parentheses have been relocated to be unshifted keys.


I don't believe Dvorak is any faster than QWERTY, but it feels more comfortable to me, and the unshifted parens make Lisp a lot easier to type.

Except for the word lambda. The M, B, and D, are all right index finger.

Alas.

Joe Marshall — REBOL 1.0 Was Slow

· 45 days ago

Rebol 1.0 was slow. I paid little attention to speed in the implementation — I was concerned with correctness. The intepreter was intended to be a reference implementation, with well-defined behavior on every edge case. My intent was to add a compiler at a later date.

Once source of slowness was the liberal use of first-class continuations in the interpreter. Rebol 1.0 used a “Cheney on the MTA” interpretation strategy, where no function ever returned a value and the stack simply got deeper and deeper. When the stack overflowed, a stack garbage collection was triggered. Since most of the stack was garbage, this was a fast operation (I used a garbage collector that used time proportional to live storage). With such an implementation, first-class continuations were trivial to implement — all continuations were first-class, it was just a question of whether you surfaced them to the user. I didn’t have an ideological belief either way, but there they were, so why not? Many control flow constructs that would otherwise require an ad hoc implementation can be easily implemented with first-class continuations.

Rebol had return statements that would return control to the caller from within the function. 99% of the time, the caller is sitting on the stack just above the current frame. But 1% of the time, the user would do something weird like create a lexical closure over the return statement and pass it downward. Like as not he didn’t deliberately do this, but rather used some library that was implemented in continuation-passing style. If this happened, the return statement might have to unwind an arbitrary amount of stack. To implement this, I captured the current continuation at the entry of each function and bound it to the implicit “return” variable. Invoking return invoked the continuation and returned control to the caller. The advantage of doing it this way was that return statements had the correct semantics under all circumstances. There were no special rules governing use of return and no code had to have special cases for unexpected returns.

A similar thing happened in the implementation of break and continue in loops. These were implemented by capturing the continuation at the entry of the loop and binding it to the implicit break variable, and capturing the continuation on each iteration and binding it to the implicit continue variable. Because these were first-class continuations, they could be used to restart the loop after it exited. That wasn’t a requirement. I was perfectly happy to stipulate that break and continue only work while a loop is in progress, but in Rebol 1.0, they’d continue to work after the loop finished.

Worrying about continuations captured in lexical closures may seem weird, but it’s a real issue. It is common to introduce implicit lexical contours in a program: even a let expression does it. You would like to be able to use break and continue in the body of a let expression in a loop. Some Rebol constructs were implemented by implicitly macroexpanding the code into a call to a helper function. break and continue would work across function call boundaries, so there were no limitations on introducing helper functions within a loop.

A more traditional language has a handful of ad hoc iteration constructs that are implemented with special purpose code. The special purpose code knows it is a loop and can be optimized for this. break and continue statements have a special dependency on the enclosing loop.

Rebol 1.0 was properly tail recursive, so there was no special implementation of loops. They were ordinary functions that happened to call themselves. Non-standard iteration constructs could be created by the user by simply writing code that called itself. break and continue just surfaced the interpreter’s continuation to the user. As a consequence, loops in Rebol 1.0 were implemented completely in Rebol code but had signifcant interpreter overhead.

Rebol 2.0 and later are not properly tail recusive. As a consequence, special looping constructs are required to be written in C to support iteration. Common iteration constucts such as for and while are provided and do not have interpreter overhead, but if you want a non-standard iteration construct, there is no way to achieve it. You have to re-write your code to use one of the built-in iteration constructs or go without and risk blowing the stack.

My intent was to eventually write a compiler for Rebol. I wrote a prototype called Sherman that compiled to MIT-Scheme and was supported by the MIT-Scheme runtime library. Loops compiled with Sherman ran quickly as expected.

Joe Marshall — GitHub Copilot Revisited

· 47 days ago

It’s been a year since I wrote a review of GitHub Copilot. A reader asked me to write an update. He wanted to know what I thought of the apparent negative effects of Copilot on the quality of code in several codebases.

GitHub Copilot acts as an autocomplete tool. Suggested completions appear in the editor as you enter code. You can accept the suggestion or ignore it. But your frame of mind informs how you decide whether to accept or ignore a suggestion. Here are a few of the ways you can interact with GitHub Copilot.

The StackOverflow mode. On the StackOveflow web site, you’ll find questions about coding and answers that often contain sample code. As an engineer, you craft the solution to your specific problem by adapting some of the sample code to your specific needs. The problem with StackOverflow is that the quality of the answers varies widely. Some answers come with some well written and well tested sample code. Other times you’ll find that someone posts a code snippet that they didn’t even attempt to run. Sometimes the code in the answer is just plain wrong. You have to draw on your engineering skills to carefully evaluate and adapt the code you find on StackOverflow.

In StackOverflow mode, you pretend that GitHub Copilot is a StackOverflow search engine. You prompt Copilot to generate snippets of code. You evaluate the generated code as though it were taken from a StackOverflow answer. The code may be fairly well written and work as is, it might be completely wrong, or it might be somewhere inbetween. You have to be be prepared to evaluate the code critically. You may need to tweak the code to make it work in your specific context. There may be subtle bugs you need to watch for.

The autocomplete mode. When using Copilot in this mode, you treat Copilot as an autocomplete tool. As you type your program, Copilot will attempt to complete the snippet you are typing. The best way to interact with Copilot in this mode is to ignore most of the suggested completions and only accept the ones that are obviously right. Often Copilot suggests exactly what you were going to type anyway. Accept those suggestions. You don’t want to spend the time and intellectual energy evaluating and adapting suggested code in this mode. You just to want to get your code written quickly. Accept the code that saves you typing and reject everything else.

Code generation mode. Copilot is pretty good at discovering repeated patterns in your code. In code generation mode, you craft some prompt code attempting to induce Copilot to generate templated output. Typically writing out one or two examples of a repeating pattern of code is sufficient for Copilot to get the gist of what you are doing and have it automatically generate the next few repetitions.

Each of these modes of interacting with GitHub Copilot requires different amounts of attention and focus, and applying your attention and focus to different areas. To get the most out of Copilot, you need to be able to switch your attention and focus between the interaction modes. The better you can do this, the more you will get out of Copilot. It takes practice.

Copilot produces mediocre code. It’s not imaginative, it doesn’t have the big picture. It writes the same code that J. Random Neckbeard would write. Mr. Neckbeard will hack out servicable solutions, but won’t craft elegant ones. If you let Copilot take over writing large sections of code, you’ll end up with a pile of bad code. It may run, but it will be hard to read, understand, and maintain. You have to assert yourself and not let Copilot take control.

When you use Copilot, you have to be the boss. It’s too easy to be lazy and accept suggestons that Copilot makes because although they aren’t great, and they aren’t what you would have written, they are adequate. Do this enough and the resulting code won’t be great, but instead barely adequate. Resist the temptation to be lazy and reject suggestions that aren’t what you want.

I’ve been using Copilot for over a year now. I’ve used it in anger on a medium sized go project. It turns out that if you point Copilot at a text file or html file, it will generate prose as well as source code. As you write, Copilot will try to finish your sentences. If you let it do this too much, you’ll end up sounding like a section of a Wikipedia article. It is best to already have some text in mind and let Copilot try to guess what it is. Reject the suggestion when it guesses wrong. This way you can use Copilot to save you typing, but you sound like yourself. Copilot does however, occasionally suggest continuations that raise points you hadn’t addressed. The suggestion may be a bit of a non-sequitur at the point where it is made, but I’ve found that Copilot can remind me of things I’ve forgotten to mention.

Copilot is not a pair programmer. It is a complex program generation model with a front-end that appears to have a deceptively shallow learning curve. There are several different ways to effectively use Copilot, but they all present themselves as autocomplete. It takes time and practive to learn the different effective ways to use Copilot and to switch between them as you program.

If you are J. Random Neckbeard, Copilot will help you become much more prolific without a lot of effort. But if your standards are higher, you’ll have to work harder to get the most out of Copilot, and you’ll find yourself rejecting it more. Be prepared to put a few months of effort into practicing the different ways to use Copilot. Like any complex tool, it takes time to get good at using it.

Can you trust Copilot? Can you trust an engineer who uses Copilot? Ask yourself, do you trust StackOverflow? Do you trust an engineer who uses StackOverflow? Do you trust your engineers? Copilot may be the ultimate source of buggy code, but the engineer is responsible.

Many codebases have reported a decrease in quality since Copilot has come on the scene. I think it is reasonable to discourage its use in these codebases. But I don’t think Copilot makes programmers worse. It makes lazy programmers more prolific, which is probably not what you want. If you are a good programmer, Copilot can be a useful tool in your toolbox. If you are careful to not let Copilot write too much of your code, you can save time without your code suffering.

Joe Marshall — Scheme Interpreter: Conclusions

· 47 days ago

This experiment with writing an MIT-Scheme S-code interpreter in C# was successful in these ways:

  • It showed that the S-code interpreter is an independent component of the Scheme system. The interpreter substrate can be replaced with a new implementation, written in a different language, using a different evaluation strategy, without replacing the Scheme runtime system written in Scheme.
  • It showed that the S-code interpreter can, on small segments of code, perform as fast as compiled code. However, growing the size of these small segment causes an exponential increase in the number of interpreter specializations. The obvious solution of automatically generating interpreter specializations on demand is the equivalent of JIT compilation.
  • It validated the idea that the lexical environment can be represented as a flattened vector of values. Mutable variables can be implemented by cell conversion. Variable values are copied from outer scopes to inner scopes when closures are created. The semantics of such an implementation is equivalent to the semantics of a nested series of frames as used in MIT-CScheme.
  • It showed that you can implement tail recursion via trampolines at each call site, and that you can implement first-class continuations by testing for a magic return value after the return of each trampoline. We don’t use the C# exception handling mechanism to unwind the stack when implementing first-class continuations, just a conditional branch and a normal return. This is far less complicated and expensive.

It was a failure in these ways:

  • Although it showed one way in which we could take incremental steps to increase the speed of the interpreter until it approached the speed of compiled code, each step resulted in an exponential increase in the number of specializations in the interpreter and had diminishing returns.
  • The ultimate outcome of this process would be an interpreter with thousands of specializations. Small Scheme programs could be completely represented by a single specialization, and they would be interpreted as fast as compiled code. But this is because the specialization is eessentially a compiled version of the Scheme program. In other words, we ultimately will have an interpreter that “optimizes” by looking up a program in a huge table that maps small programs to their precomputed compiled bodies. This is just an unusual and inefficient way to implement a compiler.
  • Because C# offers no way to dump a the heap in binary format, we must cold load the system each time we start it.
  • One of the tasks in the cold load is to initialize the unicode tables. These are big tables that take a long time to initialize.
  • It took an annoyingly long time to get to Scheme’s initial top-level prompt.
  • Debugging crashes in the Scheme system was annoying and slow because we have to cold load the Scheme system to reproduce bugs.
  • I have understated a large component of the work: providing a new C# implementation for each of the hundreds of primitives in the Scheme runtime. I only bothered to implement those primitives called as part of the cold lood boot sequence, but still there were a lot of them. For many of these primitives, the C# implementation just achieved the same effect “in spirit” as the MIT-CScheme implementation. These were easy to implement. But some were more persnickety where it was vital that the C# implementation produced exactly the same bits as the MIT-CScheme implementation. For instance, the code used to hash the types for generic method dispatch had to produce the exact same hash values in both implementations. This is because there is code that depends on the hashed multimethod ending up at a precomputed location in a method cache.
  • The C# interpreter was complete enough to boot a Scheme cold load and run it to the top-level prompt. It could run the top-level REPL. But much was missing. It could not host the SF program, which generates the S-code for the Scheme runtime. You’d have to run an original instance of MIT-CScheme to generate the S-code that you would then run in the C# interpreter.

I think the next Lisp system I will try should be based around a simple, portable JIT compiler.

Joe Marshall — Calling Conventions in the Interpreter

· 47 days ago

C# is not tail recursive. It could be. The IL that it compiles to supports tail recursion, but the C# compiler doesn’t generate the tail call instruction. It would be a simple thing to add: when the compiler emits a call instruction, it could check if the next instruction is a return, and if so, emit a tail call instruction. This could be controlled by a compiler flag so only us weirdos who want this feature would enable it.

But until the C# compiler adds this feature, we have to resort to other methods. I chose to use a trampoline at each call site. This is a small segment of code that awaits the result of the function call. If the callee wants to tail call, it returns the tail call target to the caller, which performs the call on the callee’s behalf. This requires a modification to the calling conventions.

EvalStep is the virtual method that all S-code objects implement to perform an evaluation. Its signature is this:

abstract class Control : SchemeObject
{
     public abstract TailRecursionFlag EvalStep (out object answer, 
                                                 ref Control expression, 
                                                 ref Environment environment);
}

The result of the evaluation is returned in the answer parameter. This is an out parameter, so the answer is allocated in the caller and a pointer to it is passed to the callee. The callee returns the answer by modifying it in the callers stack frame.

The expression and environment parameters are the expected parameters for a call to Eval. They, too, are allocated in the caller’s frame and references to them are passed to the callee. The callee is allowed to modify the caller’s values of these variables.

The returned value is a TailRecursionFlag. This is either 1, indicating that a value has been returned in the answer, or 0, indicating that the caller should perform another EvalStep. To return a value, the callee modifies the answer. To perform a tail call, the callee modifies the expression and environment references and returns 0.

Any caller must call EvalStep as follows: The caller allocates an answer variable to receive the answer of the call. It also allocates an expression, and environment variable to pass to the callee. It then calls EvalStep in a loop until the callee returns a TailRecursionFlag of 1, indicating that the answer has been set to the return value.

In the EvalStep for an S-code Conditional we see an example of the calling convention:

  object ev;
  Control unev = predicate;
  Environment env = environment;

  while (unev.EvalStep (out ev, ref unev, ref env) == TailRecursionFlag.TailCall) { };

We are making a recursive call to evaluate the predicate. We set up ev to receive the result of the evaluation. We set up unev and env to hold the expression and environment to pass to EvalStep. unev.EvalStep does the eval dispatch via virtual function dispatch.

If the predicate returns a TailRecursionFlag of ReturnValue, the loop will exit. The predicate is assumed to have put the return value in the ev variable.

If the predicate wants to tail call, it will modify the values of unev and env to the new expression and new environment, and return a TailRecursionFlag of TailCall. The loop will iterate, using the new value of unev and env to again dispatch a call to EvalStep.

When the while loop exits, the ev variable will contain the return value of the predicate. Control may be returned to the while loop several times before the loop exits. This is the trampoline in action.

Conditional expressions don’t return a value. They either tail call the consequent or the alternative. The EvalStep for a conditional ends like this:

  answer = null;
  expression = (ev is bool evb && evb == false) ? alternative :
  return TailRecursionFlag.TailCall;
}

The answer variable in the caller is set to null. out parameters must always be assigned to before the function exits, so this just keeps the compiler happy. If the return value of calling EvalStep on the predicate is the boolean false, we set the expression in the caller to the alternative, otherwise the consequent. This is the target of our tail call to EvalStep. For the scode for a conditional, we leave the environment alone — the tail call uses the same environment unchanged. We finally return TailRecursionFlag.TailCall so that the caller’s trampoline makes another iteration around its while. It will call EvalStep on the alternative or consequent that we stuffed in the caller’s expression.

This little song and dance is performed at every recursive call to EvalStep making EvalStep behave as a tail-recursive function. This calling convention is about half the speed of a normal C# method call. It is the cost of using a trampoline for tail recursion.

First Class Continuations

There is one more obscure reason that the control might return to us when evaluating the predicate. If some function further down the call chain invokes call-with-current-continuation, we need to copy the stack. The callee indicates this by returning a magic return value of Special.UnwindStack. The callee sets the caller’s environment to an UnwinderState that will accumulate the stack frames as we unwind the stack. So our calling convention says we need to check the return value of EvalStep, and if it is Special.UnwindStack, we allocate a ConditionalFrame on the heap that will contain the state of the current stack frame. We AddFrame to the UnwinderState. We propagate this up the stack by putting it in the caller’s environment, setting the caller’s value of answer to Special.UnwindStack and returning TailRecursionFlag.ReturnValue to stop the caller’s trampoline loop.

The full code of EvalStep for an S-code if expression is this:

 public override TailRecursionFlag EvalStep (out object answer, 
                                             ref Control expression,
                                             ref Environment environment)
{
    object ev;
    Control unev = predicate;
    Environment env = environment;

    // Tail recursion trampoline.
    while (unev.EvalStep (out ev, ref unev, ref env) == TailRecursionFlag.TailCall) { };
    // Support for first class continuations.
    if (ev == Special.UnwindStack)
    {
        ((UnwinderState) env).AddFrame (new ConditionalFrame (this, environment));
        environment = env;
        answer = Special.UnwindStack;

        return TailRecursionFlag.ReturnValue;
    }

    // Tail call EvalStep on the consequent or alternative.
    answer = null;
    expression = (ev is bool evb && evb == false) ? alternative : consequent;
    return TailRecursionFlag.TailCall;
}

First class continuations allow you unload and reload the pending call chain. We see that at each call site, we must check the return value and, if it is Special.UnwindStack, we create a new Frame on the heap and add it to the unwinder state befor we propagate the Special.UnwindStack up the call chain.

At the very top of the call chain, we have the outermost call to EvalStep. If the Special.UnwindStack value is returned to this call, the stack has been unwound and the UnwinderState is sitting in the environment variable. We need to rewind the stack and put the stack frames back on the stack. We create a RewindState from the UnwinderState. Each time we PopFrame from the RewindState, we get a deeper frame. We reload the stack by getting the outermost frame from the RewindState and calling EvalStep on it. The EvalStep for a Frame sets up the trampoline loop, calls PopFrame to get the next frame, and calls EvalStep on it. When we run out of stack frames to reload, the stack is reloaded and we return control the innermost frame so it can continue where it left off. This is the rewind loop.

The EvalStep for a Frame, after making the recursive call to EvalStep on the next frame, continues with code that is a duplicate of the code in the original frame before the cotinuation was captured. A specific example will make this clear. If an if expression is on the stack when it is uwound, a ConditionalFrame is created. A ConditionalFrame is a subclass of SubproblemFrame which has this EvalStep method:

public override TailRecursionFlag EvalStep (out object answer,
                                            ref Control expression,
                                            ref Environment environment)
{
    object temp;
    Control expr = ((RewindState) environment).PopFrame ();
    Environment env = environment;
    while (expr.EvalStep (out temp, ref expr, ref env) == TailRecursionFlag.TailCall) { };
    if (temp == Special.UnwindStack)
    {
        ((UnwinderState) env).AppendContinuationFrames (continuation);
        environment = env;
        answer = Special.UnwindStack;

        return TailRecursionFlag.ReturnValue;
    }
    expression = this.expression;
    environment = this.environment;
    return Continue (out answer, ref expression, ref environment, temp);
}

public abstract TailRecursionFlag Continue (out object answer,
                                            ref Control expression,
                                            ref Environment environment,
                                            object value);

That is, the EvalStep of the SubproblemFrame establishes a trampoline, pops the next frame from the RewindState, and invokes its EvalStep method. When an answer is returned, the SubproblemFrame calls its Continue method.

The Continue method is a virtual method that is implemented by each subclass of SubproblemFrame. It finishes the work of the frame. In the case of a ConditionalFrame, the Continue method is this:

public override TailRecursionFlag Continue (out object answer,
                                            ref Control expression,
                                            ref Environment environment,
                                            object value)
{
    answer = null;
    expression = value is bool bvalue && bvalue == false
      ? SCode.EnsureSCode (this.expression.Alternative)
      : SCode.EnsureSCode (this.expression.Consequent);
    return TailRecursionFlag.TailCall;
}
compare this to the code in the original Conditional: 
    // Tail call EvalStep on the consequent or alternative.
    answer = null;
    expression = (ev is bool evb && evb == false) ? alternative : consequent;
    return TailRecursionFlag.TailCall;

There are only superficial differences: the Continue method gets the value returned by the predicate in an argument rather than in a local variable. It type checks the alternative and consequent components of the if expression by calling SCode.EnsureSCode. Otherwise, the code does the same thing.

It is not possible to actually rewind the stack with the original set of pending methods. What we do instead is rewind the stack with methods that do the same thing as the original pending methods. It is close enough. The same values will be computed.

There is one place you can see the difference. If you look at the stack trace in the debugger before you capture a continuation, you will see the pending recursive calls to the S-code EvalStep methods. If you look at the stack trace in the debugger after you capture a continuation, you will instead see pending calls to the EvalStep methods of a set of frames. The pending frames are in the same order and have names similar to the original pending methods. They compute the same values, too. But the debugger can notice that these are not the originals.

Joe Marshall — More Inlining

· 47 days ago

Calls to (null? x) usually appear as the predicate to a conditional. We can specialize the conditional. Instead of

[if
  [primitive-null?-argument0]
  [quote 69]
  [quote 420]]

We create a new S-code construct, if-null?-argument0, and construct the conditional as

[if-null?-argument0 
  [quote 69]
  [quote 420]]

We avoid a recursive call and generating a ’T or ’NIL value and testing it, we just test for null and jump to the appropriate branch, just like the compiled code would have done.

Multiple arguments

We can further specialize the conditional based on the types of the consequent and alternative. In this case, they are both quoted values, so we can specialize the conditional to [if-null?-argument0-q-q 69 420]. (Where the name of the S-code type is derived from the type of the consequent and alternative.)

if-null?-argument0-q-q is an esoteric S-code type that codes a test of the first argument for null, and if it is null, returns the first quoted value, otherwise the second quoted value. This S-code type runs just as fast as compiled code. Indeed the machine instructions for evaluating this S-code are the same as what the compiler would have generated for the original Lisp form.

But there is a problem

Why not continue in this vein specializing up the S-code tree? Wouldn’t our interpreter be as fast as compiled code? Well it would, but there is a problem. Every time we add a new S-code type, we add new opportunities for specialization to the containing nodes. The number of ways to specialize a node is the product of the number of ways to specialize its children, so the number of ways to specialize the S-code tree grows exponentially with the number of S-code types. The few specializations I’ve just mentioned end up producing hundreds of specialized S-code types. Many of these specialized S-code types are quite esoteric and apply at most to only one or two nodes in the S-code tree for the entire program and runtime system. Performing another round of inlining and specialization would produce thousands of specialized S-code types — too many to author by hand, and most of which would be too esoteric to ever be actually used.

The solution, of course, is to automate the specialization process. We only generate a specialized S-code type when it is actually used by a program. The number of specialized S-code types will be limited by the number of ways programs are written, which is linear in the size of the program.

But specializing the code when we first encounter it is just JIT compiling the code. We’ve just reinvented the compiler. We might as well skip the multi-level specialization of the S-code tree and write a simple JIT compiler.

Joe Marshall — Inlinig Primitive Function Calls and Argument Evaluation

· 47 days ago

Inlining some primitives

Reconsider our model of a Lisp program as a “black box” that issues a series primitive function calls. We can eliminate some of the primitive function calls by implementing them directly within our “black box”. We inline some primitives.

Take null? as an example. Instead of constructing (null? arg) as

[primitive-funcall1
  [quote [primitive null?]]
  [argument 0]]

we add a new S-code construct, primitive-null?, and construct (null? arg) as

[primitive-null?
  [argument 0]]

We don't have to evaluate the function. We don't even have to jump to the entry point of the null? primitive. After we evaluate argument 0, we just test for null in the interpreter and return T or NIL as appropriate.

There are maybe 20 or so primitives that are used frequently enough to be worth inlining in this way. Each primitive you inline like this adds bloat to the interpreter.

Inlining simple arguments

The leaves of a tree of S-code are the atomic expressions, whereas the internal nodes of the tree are compound expressions. We can eliminate the leaves by inlining them into their parent nodes. For example if a leaf node is a lexical variable reference, we inline this into the parent node. We unroll the evaluation of the leaf node thus saving a recursive call to the interpreter and an evaluation dispatch.

Consider our previous example which we consructed as

[primitive-null?
  [argument 0]]

We further specialize primitive-null? based on its argument type into primitive-null?-argument or primitive-null?-lexical. Now our S-code becomes:

[primitive-null?-argument 0]

The leaf node [argument 0] is absorbed into the parent node [primitive-null? ...] making a new leaf node [primitive-null?-argument]. The evaluator for this S-code node simply tests if argument 0 is null and returns T or NIL as appropriate.

Compare this to the original S-code:

[funcall
  [global 'null?]
  [argument 0]]

This required two recursive calls to the interpreter, a global lookup, and a primitive function call on top of the null test. We’ve eliminated all of those. There’s not much left to do. Testing null? in the interpreter is almost as fast as testing null? in compiled code.

The number of S-code types needed to perform this inlining is the number of kinds of leaf nodes raised to the power of the number of leaves in the parent node. A call to a one-argument primitive would need specializations for the cases where the argument is a quoted value, an argument, a lexical variable or a global variable — four specializations. Calls to a two-argument primitive turn into one of sixteen specializations — the product of four for each argument. A call to a three-argument primitive would turn into one of sixty-four specializations.

We can inline all the non-compound argument evaluations, both to primitive functions and to user-defined functions. In our S-code tree, we have removed all the leaf nodes and absorbed them into their parent nodes (which have now become new leaves). The interpreter is now quite a bit faster, although still not as fast as compiled code.

For older items, see the Planet Lisp Archives.

Last updated: 2025-02-18 08:51