16 Feb 2025
Planet Lisp
Joe Marshall: Advent of Code 2024: Day 5
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)))))))
16 Feb 2025 8:24am GMT
15 Feb 2025
Planet Lisp
Joe Marshall: Advent of Code 2024: Day 4
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 A
s, 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))))
15 Feb 2025 7:09am GMT
12 Feb 2025
Planet Lisp
Joe Marshall: Advent of Code 2024: Day 3
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.
12 Feb 2025 1:49pm GMT
Joe Marshall: Advent of Code 2024: Day 2
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))))
12 Feb 2025 12:54pm GMT
Joe Marshall: Advent of Code 2024: Day 1
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.
12 Feb 2025 12:45pm GMT
11 Feb 2025
Planet Lisp
Joe Marshall: Advent of Code 2024: Day 0
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.
11 Feb 2025 1:39pm GMT
10 Feb 2025
Planet Lisp
Joe Marshall: Out of Practice List-fu
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 cdr
s, and returns a list of the car
consed on each of the cdr
s.
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.
10 Feb 2025 7:45pm GMT
31 Jan 2025
Planet Lisp
Tim Bradshaw: The modern real programmer
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 idiotloop
form which will be full of obscure bugs; - quiche-compatible: you can easily write a function
particle-at
which will construct aparticle
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.
-
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. ↩
31 Jan 2025 7:17pm GMT
30 Jan 2025
Planet Lisp
Neil Munro: Ningle Tutorial 3: Static Files Middleware
Contents
- Part 1 (Hello World)
- Part 2 (Basic Templates)
- Part 3 (Introduction to middleware and Static File management)
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
- Clack
- class
- div
- djula
- djula documentation
- favicon
- function
- getf
- incf
- keyword
- quicklisp
- setf
- Lack
- ningle
- format
- lambda
- middleware
- NGINX
30 Jan 2025 11:55pm GMT
27 Jan 2025
Planet Lisp
Zach Beane: Maxima in the browser with ECL and wasm
Via Raymond Toy on the ecl mailing list, Maxima in the browser.
27 Jan 2025 4:37pm GMT