fidzu : LISP

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

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

27 Jan 2025 4:37pm GMT

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.

18 Jan 2025 5:38am GMT

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.

17 Jan 2025 8:36pm GMT

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

• 🚀 https://web-apps-in-lisp.github.io/

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.

15 Jan 2025 9:39am GMT

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.

14 Jan 2025 11:04pm GMT

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.

06 Jan 2025 11:18pm GMT

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.

06 Jan 2025 1:19pm GMT

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.

05 Jan 2025 5:38pm GMT

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.

05 Jan 2025 2:00am GMT