Planet Lisp

Eric TimmonsNew Project: cl-tar

· 3 days ago

I have just published the first release of a new project: cl-tar. This was supposed to be my summer side-project, but it ran long as they often do :).

The goal of this project is to provide a Common Lisp interface to tar archives. It has its foundations in Nathan Froyd's archive library, but has been significantly extended and improved.


There are actually two subprojects under the cl-tar umbrella. The first is cl-tar-file, which provides the ASDF system and package tar-file. This project provides low-level access to physical entries in tar files. As a consequence, two tar files that extract to the same set of files on your filesystem may have two very different sets of entries of tar-file's point of view, depending on the tar format used (PAX vs ustar vs GNU vs v7).

The cl-tar-file project is technically a fork of archive. Except, all non-portable bits have been removed (such as code to create symlinks), better support for the various archive variants has been added, better blocking support added (tar readers/writers are supposed to read/write in some multiple of 512 bytes), cpio support removed, and a test suite added, along with other miscellaneous fixes and improvements.


The second sub project is cl-tar itself, which provides three ASDF systems and packages: tar, tar-simple-extract, and tar-extract.

The tar system provides a thin wrapper over the tar-file system that operates on logical entries in tar files. That is, a regular file is represented as a single entry, no matter how many entries it is composed of in the actual bits that get written to the tar file. This system is useful for analyzing a tar file or creating one using data that is not gotten directly from the file system.

The tar-simple-extract system provides a completely portable interface to extract a tar archive to your file system. The downside of portability is that there is information loss. For example, file owners, permissions, and modification times cannot be set. Additionally, symbolic links cannot be extracted as symbolic links (but they can be dereferenced).

The tar-extract system provides a more lossless extraction capability. The downside of being lossless is that it is more demanding (osicat must support your implementation and OS) and it raises security concerns.

A common security concern is that a malicious tar file can extract a symlink that points to an arbitrary location in your filesystem and then trick you into overwriting files at the location by extracting later files through that symlink. This system tries its best to mitigate that (but makes no guarantees), so long as you use its default settings. If you find a bug that allows an archive to extract to an arbitrary location in your filesystem, I'd appreciate it if you report it!

Also note that tar-extract currently requires a copy of osicat that has the commits associated with this PR applied.

next steps

First, close the loop on the osicat PR. It started off as a straightforward PR that just added new functions. However, when I tested on Windows, I realized I couldn't load osicat. So I added a commit that fixed that. There may be some feedback and changes requested on how I actually acomplished that.

Second, integrate tar-extract into CLPM. CLPM currently shells out to a tar executable to extract archives. I'd like to use this pure CL solution instead. Plus, using it with CLPM will act as a stress test by exposing it to many tar files.

Third, add it to Quicklisp. tar-extract won't compile without the osicat changes, so those definitely need to be merged first. Additionally, I want to have at least some experience with real world tar files before making this project widely available.

Fourth, add support for creating archives from the filesystem.

Fifth, add the ability to compile to an executable so you could use this in place of GNU or BSD tar :).

If the fourth and fifth steps excite you, I'd love to have your help making them a reality! They're not on my critical path for anything at the moment, so it'll likely be a while before I can get to them.

Eric TimmonsCLPM 0.4.0 released

· 13 days ago

I have tagged CLPM 0.4.0 and posted the build artifacts at This release brings quite the laundry list of bug fixes and enhancements, including the much awaited Mac M1 support. The full changelog summary is below the break.

Additionally, the burgeoning CLPM community now has more spaces to interact. If you're interested in learning about or getting help on CLPM, I encourage you to join #clpm on We have a Matrix room as well (, but the Libera room is currently more active and preferred.

If you are already using CLPM, I encourage you to subscribe to the clpm-announce mail list. This is a low traffic list where new releases will be announced.

  • Changed layout of release tarballs.
  • Published tarballs now contain a static executable (#11).
  • No longer using the deploy library to build releases (#15 #11).
  • Updated build script to more easily build static or dynamic executables (#11).
  • Fixed bug in computing the source-registry.d file for the clpm client (#16)
  • Starting to build up a test suite (#3)
  • Added automated testing on Gitlab CI.
  • Added clpm-client:*activate-asdf-integration* to control default integration with ASDF upon context activation.
  • The default directories for CLPM cache, config, and data have changed on Windows. They are now %LOCALAPPDATA%\clpm\cache\, %LOCALAPPDATA%\clpm\config\, and %LOCALAPPDATA%\clpm\data\.
  • Added new config option (:grovel :lisp :command). This string is split via shlex into a list of arguments that can be used to start the child lisp process.
  • Deprecated (:grovel :lisp :path) in favor of (:grovel :lisp :command).
  • Added new value for (:grovel :lisp :implementation) - :custom. When :custom is used, no arguments are taken from the lisp-invocation library, the user must specify a command that completely starts the child lisp in a clean state.
  • Better support for using MSYS2's git on Windows.
  • Support for Mac M1 (#20).
  • Fixed bug causing groveling to take an inordinately long time for systems with :defsystem-depends-on or direct calls to asdf:load-system in their system definition files (!9).
  • Fixed bug causing unused git and asd directives to linger in clpmfile.lock (#32).
  • Add support for bare git repos in clpmfile (not from Github or Gitlab) (#22).
  • Add clpmfile :api-version "0.4". Remains backwards compatible with 0.3. (#22).
  • Fix bug saving project metadata on Windows.
  • Fix client's UIOP dependency to better suit ECL's bundled fork of ASDF.
  • Fix issue READing strings in client from a lisp that is not SBCL (#13).
  • Parse inherited CL_SOURCE_REGISTRY config in client using ASDF (#14).

Nicolas Hafner0.2.2 Demo Release, Gamescom & more - September Kandria Update

· 21 days ago

Big news this month: there's a new free demo release (!!), news on the Pro Helvetia grant and on Gamescom, and a lot of stuff to look at that we worked on!

0.2.2 Demo Release

There's a new demo release for Kandria that you can now get for free! If you're on our mailing list, you should have gotten a download link already. There's a lot of changes for this version since the last release in April, but let me highlight a few of the big ones:

  • Major revisions to all the dialogue and quest logic to make it flow better

  • A proper tutorial sequence to introduce the controls and the game's world

  • UI for everything, including a map, main menu, quest log, etc

  • A new fishing minigame to relax and take in the world

  • Major changes to the combat to improve the flow and feel

  • Lots and lots of bugfixes and tweaks based on user feedback. Thank you!

  • Custom sound effects for everything

  • Custom music, including horizontal mixing of music tracks!

The game is now not only on Steam, but also on, if you prefer to follow updates on that platform!

Again, to get the new demo, sign up here:

Pro Helvetia Grant

The Pro Helvetia Interactive Media Grant deadline was on the 1st, and we've submitted our stuff for it! I'm quite happy with the game design pitch doc that we put together, but since there's probably quite a few very capable studios applying for the grant, who knows whether we'll have any luck with it.

I'm definitely keeping my fingers crossed for it, as getting the grant would not only be very important for us financially, but also be a huge boost in confidence, to have support like that. It would also make negotiations with publishers easier, as another organisation has then already given their vote of confidence. Getting the first foot in the door like that is always the hardest!

Anyway, it'll probably take a few months before we know anything, so there's no point in worrying about the result of it now, we'll just keep on trucking in the meantime.

Gamescom, Devcom, IndieArenaBooth

So, Gamescom was this month, which took up a week with meetings and such. We've contacted a bunch of publishers and met with a few that expressed interest in Kandria as well, which is cool. I'm not expecting anything of course, competition in this area is extremely fierce, but it's nice that we're at least getting warm receptions and actual interest.

They'll look at the new demo release now and hopefully get back to us on what they think of the game in the next few weeks. We'll be sure to let you know if we hear anything about that!

Aside from that, Kandria and Eternia both were part of the Steam listing for Gamescom, which gave us a nice spike on our wishlist numbers:

We definitely need a bunch more spikes like that though, so I'm keeping my eyes open for other festival opportunities like that!


This month was a "UI month" and as such there's a lot of changes for that. Overall I'm really glad we had time for this finally, as it really improved the overall polish of the game by a lot.

There's now a main menu and load screen:

A handy shop UI:

An in-game map showing you where you and NPCs are, as well as where you've gone:

Finally a way to change key mappings to your liking:

And all sorts of other improvements to things like the item menu, options menus, etc.


Since this was the last month before the Pro Helvetia submission and new demo, I've spent a lot of time playtesting the questline, reporting and fixing bugs, and just polishing the content as much as possible - such as adding descriptions for all items and fish, and a first-pass economy for when you buy/sell with Sahil. I also proofed Nick's pitch doc and did a little market research for this on similar games. Since we want to make a bit of a fuss over this new demo, I've also researched into reddit and prepped a couple of stories, which we could post to announce the release.

Since Gamescom also happened this month, I filtered the list of attending publishers and researched them, trying to find those who'd be most suitable for our game. Nick was then able to use this to prioritise meetings.

Finally, I've started to look beyond the demo to the horizontal slice, which we're planning to tackle next. We'd already done some work outlining the remaining acts of the story (the current demo is essentially act 1 of 5), writing some backstory and lore for the other factions and regions (which Fred has been concepting); but now we need to bring these acts to life with actual mainline quest content. I'm still in the middle of this, but I've already made a good start at planning out the main quests for acts 2 and 3. Next I'll be getting feedback on these from the team, but already it's nice to be pushing back the fog of war, and defining the rest of the story in more concrete terms.


Fred's been working on the horizontal slice content already, doing concept work for the second and third areas:

We're trying to keep all the areas very visually distinct, and I think that's working out quite well so far! I'm really excited to see it in-game.


Mikel's got all the necessary tracks for the demo finished in record time, and in the past week has been going over all of them to revise them and make them fit even better to the game's feel. Here's some of the tracks:

These tracks have many variants still to adapt to the mood of the game at the moment, so there's a lot more work behind this than might first be apparent!


Cai's been hard at work implementing all the needed sound effects that I'd been slacking on so far. We now have sounds for almost every interaction in the game, and it has contributed a ton to make the game feel more alive. We even have stuff like distinguished footsteps based on the terrain you're walking on.

There's still a few revisions left to be done, but otherwise this first batch of sounds got done really well. We'll probably wait a bit more until we do another batch, as we have to focus on actually making some more content, first.


And with that, let's look at the roadmap from last month with the updates from this month added on top:

  • Implement a main menu, map, and other UI elements

  • Implement a load screen and fix UI issues

  • Create and integrate new sound effects for 90% of the interactions in the game

  • Start work on the horizontal slice

  • Complete and revise all the music tracks for the current regions

  • Update marketing materials like the capsule image

  • Start work on modding integration

  • Implement RPG mechanics for levelling and upgrades

  • Explore platforming items and mechanics

  • Practise platforming level design

  • Draft out region 2 main quest line levels and story

  • Draft out region 3 main quest line levels and story

  • Complete the horizontal slice

But, before we get to all that we got a well deserved two weeks of holidays ahead of us. Once we're all back though, I'm sure we'll get that horizontal slice knocked out in no time!

In the meantime, I sincerely hope you give the new demo a try, and let us know what you think if you do!

Eric TimmonsToward a New CL Project Index

· 21 days ago

Quicklisp has had a profound impact on the CL community. It's transformed the way CL devs share libraries, made it easier and encouraged devs to re-use existing code instead of implementing everything in house, and is widely used. While Quicklisp took the CL community a huge step forward, I nevertheless think we can and should do better.

To that end, I've been working on two interlinked projects, CLPM and the Common Lisp Project Index (CLPI). I've posted about CLPM in various places before and awareness of it is already growing in the CL community. Therefore, this post will focus on CLPI and why I think it is important. My ultimate goal is to find like-minded people to collaborate with on bringing CLPI (or something similar) to reality.

I've been meaning to make a post like this for a while, but life kept putting it on the back burner. However, I've recently found more CLPM users in the wild, which always gets my energy levels up for this type of work. Plus, discussions I've seen in various Lisp forums (including this tweet that was brought to my attention) have made me think that the time may finally be ripe to start discussing this topic more broadly.

Before continuing, I want to make clear that I have the utmost respect for Xach, Quicklisp, and the services he provides to the community. This post does critique what is probably Xach's most well known work, but it is by no means an attack against either QL or him and I will not tolerate any comments or discussion that cross that line.

What is a Project Index?

First, let's clarify at a high level what I mean by a project index. Basically, a package index is a listing of projects and ASDF systems. For every project, it contains information on what releases are available (how to actually get the code), along with what systems are included in each release and what the dependencies of those systems are.

A project index lets you quickly answer questions like "what is the latest version of cffi?", "what are the dependencies of the latest version of cffi?", or "where can I download the latest version of ironclad?" without needing to load any code.

Quicklisp Issues

Now let's look at what I consider to be flaws of the Quicklisp project index model.

  1. Conflation of project manager and project index. When I mention Quicklisp, what do you think of first? Perhaps the quicklisp-client that gets loaded into your image and provides ql:quickload? Or is it the distinfo.txt, systems.txt, and releases.txt files that contain all the projects known to Quicklisp?
    The problem is that it's both! I think that there needs to be a clear separation between the project index (distinfo.txt and friends) and the consumers of the project index (quicklisp-client). Such a separation both makes it clearer to what is being referred in casual conversation, and makes it easier to build competing consumers or servers of the project index.

  2. The project index format is not documented. I believe this is a consequence of the previous issue. To the best of my knowledge, the only documentation of the QL project index format is the quicklisp client code that interacts with it. This makes it harder to implement both competing clients (I had to do quite a bit of code diving to get CLPM to understand the QL project index) and competing servers (there exist several forks of the quickdist project, yet none of them seem to create the dist versions file that CLPM needs).

  3. Not a lot of data is provided. The QL project index does not contain critical information, such as license, ASDF system version number, location of the canonical VCS repo, or author names.

  4. Not easily extensible. The only way to include more information in a QL project index is to add more files. Information cannot be added to releases.txt nor systems.txt without breaking the QL client. Additionally, if the current aesthetics are to be maintained, each line in a file must represent one entry that consists of tokens to be interpreted as strings, integers, or a list of strings (but only one list per entry).

  5. Enforces a particular style of development. A QL project index is rolling: it always grabs the latest version of projects. This forces projects to always use the latest and "greatest" (scare quotes intended) versions of their dependencies or risk being cut from the index. Additionally, it makes it difficult for developers to continue supporting old versions of their code that they would like to maintain; if version 1.0.0 of system A is released, then version 2.0.0, followed by 1.1.0, version 1.1.0 will never show up in a QL project index.

  6. Takes control of releases away from developers. Not only does the QL project index preclude releasing bug fixes to older, stable code, it also takes away the choice of when to perform a release. A developer cannot say "oh crap, I just realized 1.0.0 had a huge bug, I need to get 1.0.1 out today!", instantly publish 1.0.1, and then have others immediately use it. Instead, they have to wait until the next time the QL project index maintainer decides to poll them and see if a new version is available. For the primary QL index, this process can take about a month.

  7. The index is not space efficient. There is a lot of duplicated information in a QL project index. If a project had new releases in QL version M and N, then the information for the release in version M is replicated identically for releases M through N-1. This is an issue if you want to make a consumer that can show when things changed, can install any version of a project, or just wants to efficiently sync index data over the internet.


A side note on Ultralisp. Ultralisp largely seeks to address issue 6. However, as far as I can tell, it still polls, so developers cannot push new versions to it on demand (please correct me if I'm wrong here!). However, even if it does allow pushes, it still falls victim to the all the other issues except 1. Additionally, Ultralisp is very affected by issue 7 given its update frequency.


To address these concerns, I've been slowly developing the Common Lisp Project Index (CLPI) specification. Additionally, I currently have two instances of the index running. One mirrors the data available in the primary QL index, the other is for internal use with my coworkers. Last, CLPM can efficiently consume an index that follows the CLPI spec.

I'm not claiming that CLPI is perfect, but I think it is a significant step forward from QL project indices. Plus, I have some experience running it so I also know that it works (albeit for relatively small audiences). The QL mirror is located at

Now, let's take a brief dive into each of the issues I raised with the QL project index and see how CLPI addresses them.

Conflation of project manager and project index

There is no project manager named CLPI. I do not ever plan on creating one. In any case, Common Lisp Project Index would be a weird name for a project manager.

The project index format is not documented

The current specification of the format of CLPI indices is located at

The current object model used by CLPI is located at

Not a lot of data is provided

CLPI allows a project's canonical VCS to be provided. Each system can have the author, license, description, and version specified. System dependencies can include ASDF's (:version ...) and (:feature ...) specifiers.

Not easily extensible

Every file must contain one or more forms that are suitable for READing. Additionally, all the non trivial files consist of plists. This makes it trivial to both write a parser for each file and to extend files with extra information without breaking consumers (so long as the extra information does not change the semantics on which older versions are relying).

Enforces a particular style of development

Every release of every project is made available. Additionally, with the preservation of (:version ...) specifiers from ASDF's dependency lists, developers can easily provide version constraints and project managers can also take those constraints into account.

Takes control of releases away from developers

The proof of concept CLPI server I have developed for my internal use allows a developer to push releases on demand. I am using this in conjunction with Gitlab CI to push releases when tags are created on our git repos.

The index is not space efficient

CLPI borrows a lot of ideas from Rubygems' compact_index. While it is not required as part of the spec, CLPI instances can signal that they intend to only append to the files served to consumers. This lets consumers easily use HTTP headers to download only the new parts of each file that they have yet to see.

Additionally, instead of a monolithic file like releases.txt that contains release information, CLPI splits this info into project specific files. For example, you can get all the known releases for fiveam by downloading To do the same thing with a QL index, you'd have to download releases.txt for every dist version (currently 117 in the primary QL index). For comparison, the CLPI file is currently 2183 bytes, while a single releases.txt file (from the 2021-08-07 dist) is 506134 bytes, or over 200 times bigger. Additionally, the CLPI version also tells you the dependencies. To get that from QL, you also need to download systems.txt (the 2021-08-07 version is 374391 bytes).

Next Steps

Does CLPI excite you? Do you want it to become reality? Awesome, I'd love to collaborate with you to bring CLPI or something similar to the CL community at large! Please reach out to me here, on #commonlisp or #clpm on (I'm etimmons), on Matrix at (I'm, or via email at

There's a lot to do and I really want to make this a community effort.

  • I'd love it people could provide feedback on both the object model and the index format!

  • I'd love to work with people excited to help take my proof of concept CLPI server and make it production ready (or just make a new one from scratch)! This would include implementing a database backend, support for multiple users, and a permissions system.

  • I'd love to work with others interested in standing up a CLPI server for the whole community to craft a set of community guidelines and policies that address concerns such as when and how projects can be pulled (remember NPM's leftpad incident??), project ownership, etc!

  • I'd love to have feedback from all the people out there that are unsatisfied by both the QL client and CLPM! If you're making your own project manager, is there anything we can do with the CLPI spec to make your life easier? Do you have something like CLPI that we can learn from/build off?

  • But perhaps most of all, I'd love to hear if developers would be interested in publishing their code to a community CLPI server! This is one place where QL's model shines. Xach does all the work, so it is nearly effortless for individual developers to get their latest releases into the QL index. Under the CLPI model, someone (ideally the developer, but potentially a proxy maintainer) would have to perform an action on every release to get it into the CLPI instance.

It's likely that I'll continue putzing along with CLPI, even if I don't get any help. But it'll likely never get to the point of being usable by the community at large without input from others. And even if I somehow managed to get a CLPI server that is usable by the whole community, I wouldn't host it without a team willing to help maintain it, both policy- and tech-wise. I run enough projects with a bus factor of one as it is.

Eric TimmonsCLPM 0.4.0-rc.1 Available

· 22 days ago

I have just tagged CLPM 0.4.0-rc.1 and posted the build artifacts at Assuming there are no show stoppers discovered, I plan to release v0.4.0 next weekend.

This release will bring quite the laundry list of bug fixes and enhancements, including the much awaited Mac M1 support. The complete list (at this point in time) is included below.

But first, I want to inform you that I plan on getting v0.5.0 out the door ASAP. And that 0.5 will likely include some breaking changes to clpmfiles. For more information, see this issue. The breaking change is necessary to fix issue 39 and will in general lead to CLPM being cleaner and faster.

Additionally, the two other big ticket features I plan to add are groups inside clpmfiles (e.g. you can have dependencies that are only installed for dev/testing purposes) and support for versioning ASDF/UIOP in bundles. The latter change is going to be difficult due to both ASDF being a dependency of clpm-client and the special relationship the UIOP and ASDF enjoy. However, I have most of a plan and think it will be feasible without placing too much of a burden on the end user.

I would have liked to include all of these changes in v0.4, but I've been sitting on v0.4 for a long time, have been telling enough people variants of "use the latest v0.4 alpha, it's good to go except M1 support!", and I told people to use v0.4 along with my demo paper (page 21) at ELS '21. So I'd feel pretty bad about breaking clpmfiles at the moment.

If you like CLPM, have feedback, or just want to chat about it, please join us on Matrix (preferred) or #clpm on

The current changelog entry for v0.4.0 is:

  • Changed layout of release tarballs.
  • Published tarballs now contain a static executable (#11).
  • No longer using the deploy library to build releases (#15 #11).
  • Updated build script to more easily build static or dynamic executables (#11).
  • Fixed bug in computing the source-registry.d file for the clpm client (#16)
  • Starting to build up a test suite (#3)
  • Added automated testing on Gitlab CI.
  • Added clpm-client:*activate-asdf-integration* to control default integration with ASDF upon context activation.
  • The default directories for CLPM cache, config, and data have changed on Windows. They are now %LOCALAPPDATA%\clpm\cache\, %LOCALAPPDATA%\clpm\config\, and %LOCALAPPDATA%\clpm\data\.
  • Added new config option (:grovel :lisp :command). This string is split via shlex into a list of arguments that can be used to start the child lisp process.
  • Deprecated (:grovel :lisp :path) in favor of (:grovel :lisp :command).
  • Added new value for (:grovel :lisp :implementation) - :custom. When :custom is used, no arguments are taken from the lisp-invocation library, the user must specify a command that completely starts the child lisp in a clean state.
  • Better support for using MSYS2's git on Windows.
  • Support for Mac M1 (#20).
  • Fixed bug causing groveling to take an inordinately long time for systems with :defsystem-depends-on or direct calls to asdf:load-system in their system definition files (!9).
  • Fixed bug causing unused git and asd directives to linger in clpmfile.lock (#32).
  • Add support for bare git repos in clpmfile (not from Github or Gitlab) (#22).
  • Add clpmfile :api-version "0.4". Remains backwards compatible with 0.3. (#22).
  • Fix bug saving project metadata on Windows.
  • Fix client's UIOP dependency to better suit ECL's bundled fork of ASDF.
  • Fix issue READing strings in client from a lisp that is not SBCL (#13).
  • Parse inherited CL_SOURCE_REGISTRY config in client using ASDF (#14).

Joe MarshallTail recursion and fold-left

· 27 days ago

fold-left has this basic recursion:

(fold-left f init ())      = init
(fold-left f init (a . d)) = (fold-left f (f init a) d)
A straightforward implementation of this is
(defun fold-left (f init list)
  (if (null list)
      (fold-left f (funcall f init (car list)) (cdr list))))
The straightforward implementation uses a slightly more space than necessary. The call to f occurs in a subproblem position, so there the stack frame for fold-left is preserved on each call and the result of the call is returned to that stack frame.

But the result of fold-left is the result of the last call to f, so we don't need to retain the stack frame for fold-left on the last call. We can end the iteration on a tail call to f on the final element by unrolling the loop once:

(defun fold-left (f init list)
  (if (null list)
      (fold-left-1 f init (car list) (cdr list))))

(defun fold-left-1 (f init head tail)
  (if (null tail)
      (funcall f init head)
      (fold-left-1 f (funcall f init head) (car tail) (cdr tail))))

There aren't many problems where this would make a difference (a challenge to readers is to come up with a program that runs fine with the unrolled loop but causes a stack overflow with the straightforward implementation), but depending on how extreme your position on tail recursion is, this might be worthwhile.

Joe MarshallA Floating-point Problem

· 30 days ago

Here's a 2x2 matrix:

[64919121   -159018721]
[41869520.5 -102558961]
We can multiply it by a 2 element vector like this:
(defun mxv (a b
            c d


  (funcall receiver
           (+ (* a x) (* b y))
           (+ (* c x) (* d y))))

* (mxv 64919121     -159018721
       41869520.5d0 -102558961


(35738642 2.30496005d7)
Given a matrix and a result, we want to find the 2 element vector that produces that result. To do this, we compute the inverse of the matrix:
(defun m-inverse (a b
                  c d

  (let ((det (- (* a d) (* b c))))
    (funcall receiver
             (/ d det) (/ (- b) det)
             (/ (- c) det) (/ a det))))
and multiply the inverse matrix by the result:
(defun solve (a b
              c d


  (m-inverse a b
             c d
             (lambda (ia ib
                      ic id)
               (mxv ia ib
                    ic id

So we can try this on our matrix
* (solve 64919121     -159018721
         41869520.5d0 -102558961


(1.02558961d8 4.18695205d7)
and we get the wrong answer.

What's the right answer?

* (solve 64919121         -159018721
         (+ 41869520 1/2) -102558961


(205117922 83739041)
If we use double precision floating point, we get the wrong answer by a considerable margin.

I'm used to floating point calculations being off a little in the least significant digits, and I've seen how the errors can accumulate in an iterative calculation, but here we've lost all the significant digits in a straightforward non-iterative calculation. Here's what happened: The determinant of our matrix is computed by subtracting the product of the two diagonals. One diagonal is (* 64919121 -102558961) = -6658037598793281, where the other diagonal is (* (+ 41869520 1/2) -159018721) = -6658037598793280.5 This second diagonal product cannot be represented in double precision floating point, so it is rounded down to -6658037598793280. This is where the error is introduced. An error of .5 in a quantity of -6658037598793281 is small indeed, but we amplify this error when we subtract out the other diagonal. We still have an absolute error of .5, but now it occurs within a quantity of 1, which makes it relatively huge. This is called “catastrophic cancellation” because the subtraction “cancelled” all the significant digits (the “catastrophe” is presumably the amplification of the error).

I don't care for the term “catastrophic cancellation” because it places the blame on the operation of subtraction. But the subtraction did nothing wrong. The difference betweeen -6658037598793280 and -6658037598793281 is 1 and that is the result we got. It was the rounding in the prior step that introduced an incorrect value into the calculation. The subtraction just exposed this and made it obvious.

One could be cynical and reject floating point operations as being too unreliable. When we used exact rationals, we got the exactly correct result. But rational numbers are much slower than floating point and they have a tendancy to occupy larger and larger amounts of memory as the computation continues. Floating point is fast and efficient, but you have to be careful when you use it.

Joe MarshallFold right

· 39 days ago

fold-left takes arguments like this:

(fold-left function init list)
and computes
* (fold-left (lambda (l r) `(f ,l ,r)) 'init '(a b c))
(F (F (F INIT A) B) C)
Notice how init is the leftmost of all the arguments to the function, and each argument appears left to right as it is folded in.

Now look at the usual way fold-right is defined:

(fold-right function init list)
It computes
* (fold-right (lambda (l r) `(f ,l ,r)) 'init '(a b c))
(F A (F B (F C INIT)))
although init appears first and to the left of '(a b c) in the arguments to fold-right, it is actually used as the rightmost argument to the last application.

It seems to me that the arguments to fold-right should be in this order:

; (fold-right function list final)
* (fold-right (lambda (l r) `(f ,l ,r)) '(a b c) 'final)
(F A (F B (F C FINAL)))
The argument lists to fold-left and fold-right would no longer match, but I think switching things around so that the anti-symmetry of the arguments matches the anti-symmetry of the folding makes things clearer.

Quicklisp newsAugust 2021 Quicklisp dist update now available

· 50 days ago

 New projects

  • cache-while — A Common Lisp macro for defining temporary caches that invalidate based on expressions evaluating to different values. — LLGPL
  • cl-coinpayments — Helpers for working with the api. — MIT
  • cl-drawille — cl-drawille: Drawing in terminal with Unicode Braille characters. — MIT
  • cl-sha1 — SHA1 Digest and HMAC for LispWorks. — Apache 2.0
  • cl-webdriver-client — cl-webdriver-client is a binding library to the Selenium 4.0 — MIT
  • clj-con — Implements Clojure-styled concurrency operations such as `future` and `promise`. — MIT
  • clj-re — Implements Clojure-styled regexp operations such as `re-matches` and `re-find`. — MIT
  • depot — Protocol for transparent collections of files. — zlib
  • fof — Enable rapid file search, inspection and manipulation — GPL3+
  • hash-table-ext — Tiny extensions for common lisp hash-tables. — MIT
  • hunchenissr-routes — Better routes to be used with Hunchenissr. — LLGPL
  • omglib — A Common Lisp library to build fully dynamic web interfaces — GPL3
  • query-repl — REPL for user query. — MIT
  • slite — SLIME based Test-runner for FiveAM tests (and possibly others in the future) — Apache License, Version 2.0
  • with-c-syntax — with-c-syntax is a fun package which introduces the C language syntax into Common Lisp. — WTFPL

Updated projects: 3d-vectors, alexandria, also-alsa, april, architecture.builder-protocol, bdef, caveman, check-bnf, chipz, chirp, cl+ssl, cl-ana, cl-collider, cl-cuda, cl-debug-print, cl-environments, cl-form-types, cl-gamepad, cl-gserver, cl-i18n, cl-kraken, cl-las, cl-liballegro, cl-migratum, cl-mixed, cl-opencl, cl-opencl-utils, cl-patterns, cl-ses4, cl-sse, cl-utils, cl-webkit, clack, clem, clog, closer-mop, cmd, colored, command-line-arguments, common-doc, common-html, common-lisp-jupyter, consfigurator, core-reader, croatoan, cserial-port, cytoscape-clj, dartscluuid, data-frame, dexador, dfio, drakma, drakma-async, file-attributes, flexi-streams, gendl, generic-cl, harmony, imago, introspect-environment, jingoh, kekule-clj, lack, lisp-binary, lisp-stat, lispbuilder, lyrics, markup, mcclim, mito, mnas-package, mnas-string, mutility, neural-classifier, null-package, nyxt, overlord, parachute, petalisp, portable-condition-system, postmodern, prompt-for, qlot, quickutil, quilc, read-as-string, rove, sanity-clause, screamer, sel, serapeum, shasht, shop3, sketch, sly, snappy, snooze, special-functions, speechless, static-dispatch, stumpwm, tailrec, ten, tfeb-lisp-hax, tfeb-lisp-tools, trestrul, trivial-ed-functions, trivial-inspector-hook, ufo, uiop, uncursed, vellum, vellum-csv, vgplot, vk, websocket-driver, whirlog, zacl.

Removed projects: lucerne

To get this update, use (ql:update-dist "quicklisp"). Enjoy!

Nicolas HafnerGDC, fighting, and more - August Kandria Update

· 56 days ago

A big ole update for Kandria this month!


One of the main events this month was GDC. This was my first time attending, and I'm really glad that I was offered the chance to with the great support by Pro Helvetia and SwissNex. Thank you very much again for all of your support this year!

The highlight of the event for me were the daily video networking sessions, where you were led onto a virtual floor with a bunch of tables. Each table could seat up to six people and you'd chat over audio and video. It was really cool to hang out and chat with fellow attendees about... well, pretty much whatever!

What wasn't so cool about those sessions, was that they only lasted for an hour, at the end of which you were unceremoniously booted out, without even the ability to see who you were at the table with, nor the accompanying text chat. I do not understand at all why that platform was not just up throughout the entirety of the conference. It's not like there were ever that many people there to begin with, I never saw the total number rise above 120.

With regards to the booth that we had at the Swiss country pavilion, that unfortunately turned out to be almost pointless. Everyone I talked to at the virtual meet wasn't even aware that booths existed at all, let alone the ones in the country pavilions. Being buried under ten links almost guaranteed that we wouldn't be found except by the most vigilant. It isn't surprising then that we didn't get any contact requests through the booth's message box.

I'm really confused as to why they had practically zero visibility for the showfloors and booths. It seems to me that those are a rather large part of a usual conference, so advertising them so poorly is strange. I can't even imagine what SwissNex had to pay to get our booths set up, and I feel sorry for what they got for that.

I hope that next year the presentation is going to be better, as for the amount of money involved in the tickets and everything, I have to say I'm quite disappointed with the GDC organisers. We'll see how Gamescom goes next month, I suppose.

Combat developments

This month was meant to be devoted to combat revisions. I did get a number of those done, so movement is now a lot more satisfying and you can actually juggle enemies in the air:

However, due to the mass of feedback amounted by the playtesting, GDC interruptions, and my general reluctance to work on it there hasn't been as much progress as I would like. I'll definitely have to revisit this again later down the road. In the very least though I feel like we have the features required in the engine now to make the system work well, it's "just" down to tweaking the parameters.

To give you some perspective on why tweaking of these parameters is a pain though, let me show you a screenshot of our in-house animation editor:

For each frame (the player has around 700 frames of animation at this point), you can set a mass of different properties that change combat behaviour and movement. Tweaking them one by one, performing the attack, going back to tweak it again, and repeating that is an extremely arduous process.

I tried my best to keep at it throughout the month, but the tedium of it made it quite difficult. I hope I can instead gradually improve it with time.

UI look and feel

I've taken some time to change the look and feel of the UI in the game. Most notably the button prompts now look a lot better than they used to. The fishing minigame shows that best:

The textbox also got a revision and it's now capable of doing text effects:

Aside from those tweaks there were a myriad of changes from the further blind playtest sessions as well.

Eternia update

A new update for Eternia: Pet Whisperer was rolled out. This update took two days to put together and includes important stability fixes for MacOS and Windows users. On MacOS the behaviour on Retina displays is improved and audio output on devices with samplerates above 44.1kHz has been fixed. General performance has also been improved. On Windows spurious crashes caused by antivirus software should now no longer occur.

Eternia will also likely be on sale during the upcoming Gamescom Steam sale, so keep an eye out for that!


This month has been about press and polish. With GDC happening, I helped prioritise the press list and reach out to the most relevant people; we didn't get a huge response, which isn't unexpected (press are inundated at the best of times, never mind during GDC) - but it's been encouraging to get some replies; and most importantly, it's getting the game on peoples' radars.

I've also been working through tons of feedback Nick has gathered from blind playtests of the game, using it to make the quests easier to understand and more accessible: finessing spawn locations, clarifying objectives more in dialogue, etc. I ran a few tests myself, and it's amazing how things you thought were obvious sometimes don't translate to the player. A highlight was watching my brother return to the surface after the first quest: he didn't know the rest of the settlement was over to the right, and instead went left, all the way back to the tutorial area; since Catherine was following him at the time, it re-triggered all her tutorial dialogue! Noooooooooo! (But in a good way :) )

Nick also made some cool new features like random spawners that can add a myriad of world-building items to the levels (and which later you'll be able to sell to Sahil); I spent time organising and placing these. Also, text effects and colouring! I went a bit bananas with this at first, using the swirly rainbow effect right off the bat in the tutorial, when Catherine gets excited; to be fair it's probably the only point in the game I could've justified using it. But I've since toned things back, as although the game has quirk, we need to watch the tone and make sure we don't go too cartoony. I've also established a basic visual language for using these effects and colours (hint: sparingly).


Fred has been working on new sets of animations and some concept work. Some of the new animations are for expanded combat moves, so there's now a heavy and light charge attack:


Mikel finished a couple more tracks, well on ... track to make the September release date with all the music for the current areas included! These tracks are for the camp area, and as such convey a more chill atmosphere:

Aside from the music there's also been more audio changes, by way of a new team member:


I'm Cai, I'm a Sound Designer for video games. I've been in the industry for 2 years! I focus on making impactful, meaningful sounds that help to immerse the player in the world we create! Kandria is a really exciting project to be involved with! The story and atmosphere of the game are both compelling and exciting so I'm thrilled to have the opportunity to contribute to this through the sound!

Cai has been hard at work remaking the existing sounds and adding new ones. One of the bigger changes in that respect is the addition of atmospheric sound layers that now underlay each music track. The atmospherics and music both change independently depending on the area the player is currently in.

It still needs some tuning, though. We need to make sure the loudness levels of each track work properly in conjunction with the atmospherics, and that the transitions between areas work smoothly without calling too much attention to themselves.


Let's look at the roadmap from last month with the updates from this month:

  • Polish the ProHelvetia submission material

  • Polish and revise the combat design

  • Finish the desert music tracks

  • Further blind playtesting and bugfixing

  • Revise the general UI look and feel

  • Implement a main menu, map, and other UI elements (partially done)

  • Create and integrate new sound effects for 90% of the interactions in the game

  • Explore platforming items and mechanics

  • Practise platforming level design

  • Start work on the horizontal slice

I'm quite confident I can get all the UI stuff done in time, so we should be well set for the Pro Helvetia submission!

Until the submission is done, be sure to check our mailing list for weekly updates, and the discord community for fan discussions!

Michał HerdaCommon Lisp Recipes, 2nd Edition

· 59 days ago

Let's talk a little about the second edition of Edi Weitz's Common Lisp Recipes! What would you like to see added or changed in it? What problems have you possibly faced that could be described in a new recipe?

Please let me know via mail, Fediverse, IRC (phoe at Libera Chat), or, if you absolutely have to, Twitter.

McCLIMProgress report #12

· 76 days ago

Dear Community,

A lot of time passed since the last blog entry. I'm sorry for neglecting this. In this post, I'll try to summarize the past two and a half year.

Finances and bounties

Some of you might have noticed that the bounty program has been suspended. The BountySource platform lost our trust around a year ago when they have changed their ToS to include:

If no Solution is accepted within two years after a Bounty is posted, then the Bounty will be withdrawn, and the amount posted for the Bounty will be retained by Bountysource.

They've quickly retracted from that change, but the trust was already lost. Soon after, I've suspended the account and all donations with this platform were suspended. BountySource refunded all our pending bounties.

All paid bounties were summarized in previous posts. Between 2016-08-16 and 2020-06-16 (46 months of donations) we have collected in total $18700. The Bounty Source comission was 10% collected upon withdrawal - all amounts mentioned below are presented for before the comission was claimed.

During that time $3200 was paid to bounty hunters who solved various issues in McCLIM. The bounty program was a limited success - solutions that were contributed were important, however harder problems with bounties were not solved. That said, a few developers who contribute today to McCLIM joined in the meantime and that might be partially thanks to the bounty program.

When the fundraiser was announced, I've declared I would withdraw $600 monthly from the project account. In the meantime I've had a profitable contract and for two years I stopped withdrawing money. During the remaining three years I've withdrawn $15500 ($440/month) from the account.

As of now we don't have funds and there is no official way to donate money to the project (however, this may change in the near future). I hope that this summary is sufficient regarding the fundraiser. If you have further questions, please don't hesitate to contact me, and I'll do my best to answer them.

I'd like to thank all people who donated to the project. Your financial support made it possible for me to work on the project more than I would be able without it. The fact that people care about McCLIM enough to contribute to it money gives me the motivation and faith that working on the codebase is an important effort that benefits the Common Lisp community.


The last update was in 2018-12-31. A lot of changes accumulated in the meantime.

  • Bordered output bug fixes and improvements -- Daniel Kochmański
  • Gadget UX improvements (many of them) -- Jan Moringen
  • Text styles fixes and refactor -- Daniel Kochmański
  • Freetype text renderer improvements -- Elias Mårtenson
  • Extended input stream abstraction rewrite -- Daniel Kochmański
  • Implementation of presentation methods for dialog-views -- admich
  • Encapsulating stream missing methods implementation -- admich
  • indenting-output-stream fixes -- Jan Moringen
  • drawing-tests demo rewrite -- José Ronquillo Rivera
  • Line wrap on the word boundaries -- Daniel Kochmański
  • New margin implementation (extended text formatting) -- Daniel Kochmański
  • Presentation types and presentation translators refactor -- Daniel Kochmański
  • Input completion and accept methods bug fixes and reports -- Howard Shrobe
  • Clipboard implementation (and the selection translators) -- Daniel Kochmański
  • CLIM-Fig demo improvements and bug fixes -- Christoph Keßler
  • The pointer implementation (fix the specification conformance) -- admich
  • Drei kill ring improvements -- Christoph Keßler
  • McCLIM manual improvements -- Jan Moringen
  • Frame icon and pretty name change extensions -- Jan Moringen
  • Cleanups and extensive testing -- Nisar Ahmad
  • pointer-tracking rewrite -- Daniel Kochmański
  • drag-and-drop translators rewrite -- Daniel Kochmański
  • Complete rewrite of the inspector Clouseau -- Jan Moringen
  • Rewrite of the function distribute-event -- Daniel Kochmański and Jan Moringen
  • Adding new tests and organizing them in modules -- Jan Moringen
  • Various fixes to the delayed repaint mechanism -- Jan Moringen
  • CLX backend performance and stability fixes -- Christoph Keßler
  • PS/PDF/Raster backends cleanups and improvements -- Jan Moringen
  • Drei regression fixes and stability improvements -- Nisar Ahmad
  • Geometry module refactor and improvements -- Daniel Kochmański
  • Separating McCLIM code into multiple modules -- Daniel Kochmański and Jan Moringen
  • Frames and frame managers improvements -- Jan Moringen and Daniel Kochmański
  • Frame reinitialization -- Jan Moringen
  • PDF/PS backends functionality improvements -- admich
  • Menu code cleanup -- Jan Moringen
  • Pane geometry and graph formatting fixes -- Nisar Ahmad
  • Numerous CLX cleanups and bug fixes -- Daniel Kochmański and Jan Moringen
  • Render backend stability, performance and functionality fixes -- Jan Moringen
  • Presentation types more strict interpretation -- Daniel Kochmański
  • External Continuous Integration support -- Jan Moringen
  • Continuous Integration support -- Nisar Ahmad
  • Improved macros for recording and table formatting -- Jan Moringen
  • Better option parsing for define-application-frame -- Jan Moringen
  • Separation between the event queue and the stream input buffer -- Daniel Kochmański
  • Examples cleanup -- Jan Moringen
  • Graph formatting cleanup -- Daniel Kochmański
  • Stream panes defined in define-application-frames refactor -- admich
  • Menu bar rewrite (keyboard navigation, click to activate) -- Daniel Kochmański
  • Thread-safe execute-frame-command function -- Daniel Kochmański
  • Mirroring code simplification for clx-derived backends -- Daniel Kochmański
  • Arbitrary native transformations for sheets (i.e. zooming) -- Daniel Kochmański
  • extended-streams event matching improvements -- Jan Moringen
  • Render backend performance improvements -- death
  • drei fixes for various issues -- death
  • drei various cleanups -- Jan Moringen
  • clim-debugger improvements -- Jan Moringen
  • Manual spelling fixes and proofreading -- contrapunctus

This is not an exhaustive list of changes. For more details, please consult the repository history. Many changes I've introduced during this iteration were a subject of a careful (and time-consuming) peer review from Jan Moringen which resulted in a better code quality. Continuous integration provided by Nisar Ahmad definitely made my life simpler. I'd like to thank all contributors for their time and energy spent on improving McCLIM.

Pending work

If you are working on some exciting improvement for McCLIM which is not ready, you may make a "draft" pull request in the McCLIM repository. Currently, there are three such branches:

  • the SLIME-based backend for CLIM by Luke Gorrie

  • the dot-based graph layout extension by Eric Timmons

  • the xrender backend by Daniel Kochmański

Other than that, I've recently implemented the polygon triangulation algorithm that is meant to be used in the xrender backend (but could be reused i.e. for opengl). Currently, I'm refining the new rendering for clx (xrender). After that, I want to introduce a portable double buffering and a new repaint queue. Having these things in place after extensive testing, I want to roll out a new release of McCLIM.

Sincerely yours,
Daniel Kochmański

Nicolas HafnerTesting events - July Kandria Update

· 85 days ago

Another month filled with a lot of different stuff! We have a lot of conferences coming up, there was a bunch to do for marketing, the game has seen a lot of visual and gameplay tweaks, and we've started doing a lot of direct playtesting. Finally, the music has also made a lot of progress and the first few tracks are now done!

GDC, Gamescom, and GIC

Thanks to the very generous support from Prohelvetia we're part of the Swiss Games delegation to GDC, Gamescom, and GIC. GDC is coming up this month, and we have our own virtual booth set up for that. Given that both GDC and Gamescom are virtual this year, I honestly don't really know what to expect from them, it's going to be quite different. At least GIC is in person (Poznan, Poland) so I'm really looking forward to that!

So far we've invested quite a bit of time into looking at journalists to reach out to during GDC, and who knows, perhaps we'll also be contacted by publishers or something during the event. In any case, it's going to be an exciting week, for sure.

Gamescom/Devcom are coming up in August, right before the submission deadline for the Prohelvetia grant, so that's going to be a tight squeeze, too. September is gonna be a calmer month, as we've settled for a two weeks holiday for the team during that month. Then in October it's going to be GIC for a week.


Also thanks to Prohelvetia we now have direct mentoring from Chris Zukowski with a monthly meeting for the next six months. His first advice was to focus a lot more on top of the funnel marketing (like imgur, reddit, festivals, influencers), and cut down on all the middle stuff we've been doing (like discord, mailing list, blogs, streams).

I actually quite like doing the weekly and monthly updates though, so I'm going to keep doing those. The Sunday streams have also proven quite productive for me, so I'll use them for that purpose too, rather than for any marketing intent. I am going to cut down drastically on Twitter though, as that does not seem to really bring us much of anything at all, and I'm going to stay away from Discord more in general (not just the Kandria one.).

After some brief experiments with imgur (and once even making it into most viral) I haven't returned to that yet though, as I've found it to be quite exhausting to figure out what to even post and how to post it.

We'll definitely have to try reaching out to influencers and journalists, but we're going to hold off on that until the september demo update is done, as a more polished demo should help a lot to make us look more presentable and respectable. We should also try out Reddit, but we haven't done the necessary research yet into how exactly to post on there without getting downvoted into oblivion.

The second advice Chris had for us was to do more....


We've started inviting people to do blind playtesting. The blind here meaning that they never played the game before, which gives us quite valuable insight into parts of the game that are confusing or annoying. We've done four sessions so far, and even with them being carried out over Discord, the feedback has been very useful.

I've also been inviting people for local playtesting, as being able to observe people in person is a lot better than doing it over the net. We haven't done any of that yet, but there's several appointments scheduled already. If you're near Zürich and would be up for a playtest session, please book a date!

And if you, like most, aren't close to Zürich, but would still like to help us out with testing, let me know anyway and we can arrange something over the net!


We finally finished a tutorial area for the game, giving it a proper starting point, and introducing people to the controls. It doesn't explain all of them in detail though, as I think we should instead keep the more intricate controls to challenges throughout the game, rather than trying to teach everything at once.

Designing the levels to teach the various control parts is going to be challenging, but I think ultimately it is going to be worth it, especially as it allows us to keep the tutorial in the beginning very short.

The only actual tutorial part still missing is a combat primer, for which we haven't worked out a good way of teaching it yet. I'm sure we'll find a way, though.


I took a holiday for part of this month, though otherwise it's been full steam ahead on the marketing research. I've added more reference games and potential contacts to our press & influencer document; while doing this I've taken into account the advice we got from Chris Zukowski, about not looking too closely at games with distinct differences to Kandria (e.g. Celeste has no combat; Dead Cells is a roguelike). I've also done more research on Steam short descriptions, and worked with Nick to redraft ours. It needs a few more edits, but it's nearly there.

I haven't totally forgotten the game though! With the new tutorial prologue in place, I added dialogue. This is now your first meeting with Catherine, after she reactivates you deep underground; but I've deliberately kept things short and sweet, as she guides you back up to the surface. The player has enough to think about at this stage without getting overwhelmed with dialogue; only once the tutorial segues into the settlement introduction from before, does the dialogue really begin.


Mikel's been very busy and completed 6 different versions of the region 1 track:

Which the game can use to do vertical mixing:


Let's look at the roadmap from last month with the updates from this month:

  • Build and add the tutorial sequence to the beginning of the game

  • Finish the region 1 music tracks

  • Add a fishing minigame

  • Improve the UI for the game and editor

  • Implement several editor improvements

  • Compile data on journalists, influencers, and communities

  • Implement a UI animation system

  • Implement a cutscene system

  • Polish the ProHelvetia submission material (partially done)

  • Polish and revise the combat design (partially done)

  • Implement a main menu, map, and other UI elements

  • Reach out to journalists, streamers, and other communities

  • Explore platforming items and mechanics

  • Practise platforming level design

  • Start work on the horizontal slice

The first three are scheduled to be done by September 1st, and so far it looks quite doable. The events are going to jumble things up a bit, but I hope that we still have enough time scheduled around to get it all done in time.

Until then be sure to check our mailing list for weekly updates, and the discord community for fan discussions!

Quicklisp newsJune 2021 Quicklisp dist update now available

· 87 days ago

 New projects

  • cl-megolm — A copy of the python functionality provided as bindings for Olm. — MIT
  • cl-openapi-parser — OpenAPI 3.0.1 and 3.1.0 parser/validator — MIT
  • cl-opencl-utils — OpenCL utility library built on cl-opencl — GPLv3
  • cl-sse — Use sse-server + a web service to serve SSE events to a browser. — MIT
  • trivial-ed-functions — A simple compatibility layer for *ed-functions* — MIT
  • trivial-inspector-hook — A simple compatibility layer CDR6 — MIT
  • webapi — CLOS-based wrapper builder for Web APIs — BSD 2-Clause
  • whirlog — a minimal versioned log structured relational DB — MIT

Updated projects: also-alsa, april, atomics, bdef, binding-arrows, bp, chirp, cl+ssl, cl-ana, cl-collider, cl-conllu, cl-cxx-jit, cl-data-structures, cl-environments, cl-form-types, cl-gamepad, cl-gserver, cl-heredoc, cl-incognia, cl-ipfs-api2, cl-kraken, cl-maxminddb, cl-mixed, cl-mock, cl-murmurhash, cl-naive-store, cl-ntp-client, cl-opencl, cl-patterns, cl-schedule, cl-smt-lib, cl-string-generator, cl-torrents, cl-utils, cl-webkit, clack-pretend, closer-mop, cluffer, clunit2, clx, cmd, common-lisp-jupyter, conium, consfigurator, core-reader, croatoan, defmain, deploy, dexador, djula, doc, easy-routes, eclector, fiveam-asdf, fresnel, functional-trees, gendl, generic-cl, gute, harmony, herodotus, hunchentoot-multi-acceptor, hyperluminal-mem, iolib, lack, lichat-protocol, lichat-tcp-client, lispqr, markup, mcclim, md5, mito, mnas-package, mnas-string, modularize-interfaces, multiposter, neural-classifier, numerical-utilities, nyxt, origin, osmpbf, overlord, plot, plump, portal, postmodern, py4cl2, qlot, quilc, quri, qvm, re, replic, sc-extensions, sel, serapeum, shasht, shop3, sly, smart-buffer, special-functions, spinneret, st-json, static-dispatch, static-vectors, stumpwm, sxql, tailrec, tfeb-lisp-hax, tooter, trivia, trivial-with-current-source-form, trucler, vellum, vk, wasm-encoder, woo, zippy.

Removed projects: with-c-syntax.

To get this update, use (ql:update-dist "quicklisp"). Enjoy!

Nicolas HafnerUpdates Galore - June Kandria Update

· 112 days ago

There's a lot of different news to talk about this month, so strap in!

The New Trailer

The most important thing to come out of this month is the new trailer! Check it out if you haven't yet:

I'm overall really happy with how it came together, and we all had a part in the end result. I'd also like to give a special commendation to Elissa Park who did the amazing voice over for the trailer. It was a pleasure to work together!

It's also been great to finally get some custom music by Mikel into an official part of the game. He's also been working on the first music tracks that'll be in the game, and I've been working on a music system to support horizontal mixing with the tracks. I'm very excited to get all that together into the game and see how it all feels! I hope that by next month's update we'll have a short preview of that for you.

0.1.1 Release

Meanwhile we also pushed out an update to the vertical slice release that makes use of the new linear quest system we put together. It should overall also be a lot more stable and includes many fixes for issues people reported to us. Thanks!

As always, if you want to have a look at the demo yourself, you can do so free of charge.

I think this will be the last patch we put out until September. I can't afford to backport fixes even if more bug reports come in, as the overhead of managing that is just too high. I can't just push out new versions that follow internal development either, as those are frequently in flight and have more regressions that we typically stamp out over time, but would in the meantime provide a more buggy experience. started working on fishing just recently!

Dev Streams

I'm heavily considering doing regular weekly development streams, both to see if we can attract some more interest for the project, and to be more open about the process in general. I feel like we're already very open about everything with our weekly updates, but having an immediate insight into how the game is made is another thing entirely. I think it would be really cool to show that side of development off more often!

In order to coordinate what time would suit the most people, please fill out this Doodle form. The exact dates don't matter, just watch for the day of the week and the time. Don't worry about the name it asks for either, it won't be public!

I'll probably close the poll in a weeks, so make sure to submit an answer soon if you're interested. Streams will happen both on and, with both being reachable through the official stream page at . See you there!

Palestinian Aid Bundle

Some good folks have put together a bundle on gathering money for Palestinian aid. I'm very happy to say that our game, Eternia: Pet Whisperer is a part of this bundle!

If you want to support this cause and get a huge collection of amazing games in the process, head on over to!


This month I had a varied mix of tasks: working on the script for the new trailer; updating the quests in the vertical slice demo to work closer to our original vision; researching press and influencer contacts as we plan more of Kandria's marketing.

The trailer came out great, and I'm really happy with the voice acting that Nick produced with Elissa Park. It was a great idea Nick had to use the character of Fi as the narrator here (originally we were going to use Catherine) - her serious outlook, and reflection on the events of the story, was just what we needed to fit the epic music from Mikel, and the epic gameplay and exploration that Nick captured on screen. The whole thing just screams epic.

The quests were vastly improved too. The first quest now uses Nick's new sequencing system, so that triggers fire automatically (and more robustly) when the player arrives at the correct location, and when combat encounters are completed. The logic is also much quicker to write, so linear quests will be much faster to produce in the future. The mushroom quest also had a big refactor; now you can organically collect mushrooms out in the world, rather than going to specific enabled points. You can even sell what you find to the trader, including those poisonous black knights. It really makes the world feel more interactive. There's been general tweaks to the other quests from playtesting, and I'll continue to refine them from my own playing and players' feedback up until the Pro Helvetia submission later in the year. I'm also planning to add a couple more sidequest diversions based on the new fishing (!) minigame being added at the moment; we think a combat-focused sidequest will work well too.

Finally on the marketing side, it's been rewarding to collect tons of potential press and influencer contacts we could approach in the future. I've basically been taking games that are strong influences and have similarities to Kandria - from hugely popular games like Celeste and Dead Cells, to lesser known ones like Kunai and Armed with Wings - then cataloguing key journalists and influencers who've streamed, made videos, or written about them. This will hopefully highlight some of the right people we can contact to help spread the word about the game.


Let's look at the roadmap from last month with the updates from this month:

  • Make the combat more flashy

  • Finish a new trailer

  • Revise the quest system's handling of linear quest lines

  • Design and outline the factions for the rest of the game

  • Develop the soundscape for Kandria and start working on the tracks for region 1

  • Add a music system that can do layering and timed transitions

  • Build and add the tutorial sequence to the beginning of the game

  • Finish the region 1 music tracks

  • Reach out to journalists, streamers, and other communities

  • Polish the ProHelvetia submission material

  • Polish and revise the combat design

  • Explore platforming items and mechanics

  • Practise platforming level design

  • Start work on the horizontal slice

As always there's some smaller tasks that aren't in the overall roadmap. We seem to be doing pretty well keeping on track with what needs done, which is really good! It's all too easy to misjudge the time required to complete things, especially in games.

In any case, time is flying fast, and there's a lot to do. In the meantime be sure to check our mailing list for weekly updates, and the discord community for fan discussions!

Eric TimmonsASDF 3.3.5 Release Candidate

· 115 days ago

ASDF has been tagged. This is a release candidate for 3.3.5. As the announcement says, please give it a spin on your setup and report any regressions. Bugs can be reported to the Gitlab issue tracker (preferred) or to the asdf-devel mailing list.


The full(ish) Changelog can be found here.

In addition to assorted bug fixes, there are several new features. Both user facing:

  • Support for package local nicknames in uiop:define-package.
  • SBCL should now be able to find function definitions nested in the with-upgradability macro.
  • package-inferred-system source files can use extensions other than .lisp.

And developer facing:

  • Building out a fairly extensive CI pipeline.


This is planned to be the last release in the 3.3 series. We are excited to get this out the door because we already have several focal points for the 3.4 series in mind, including:

  • Support for more expressive version strings and version constraints. issue draft MR.
  • A new package defining form that is explicitly designed to better tie in with package-inferred-system. issue draft MR.

Please join in the conversation if any of these features excite you, you have features you'd like to see added, or you have bugs that need to be squashed.

Michał HerdaCurrent Common Lisp IRC situation

· 117 days ago

Because of the upheaval at Freenode, I've migrated to Libera Chat along with a bunch of other Lisp programmers. We have used that as a chance to make some small changes to the channel structure:

  • #commonlisp is the on-topic Common Lisp channel (formerly #lisp),
  • #lisp is the somewhat on-topic discussion about all Lisp dialects (formerly ##lisp),
  • the rest of the channel names should work the same.

The first two lines of the above were mentioned because #lisp on Freenode used to have a non-trivial volume of people asking questions about Scheme or Emacs Lisp due to the too-generic channel name. Naming the Common Lisp channel #commonlisp resolves this issue, at the cost of sacrificing a lucrative and attractive five-character channel name.

Quicklisp newsMay 2021 Quicklisp dist update now available

· 118 days ago

 New projects: 

  • adopt-subcommands — Extend the Adopt command line processing library to handle nested subcommands. — MIT
  • cl-cerf — Lisp wrapper to libcerf — Public Domain
  • cl-cxx-jit — Common Lisp Cxx Interoperation — MIT
  • cl-form-types — Library for determining types of Common Lisp forms. — MIT
  • cl-incognia — Incognia API Common Lisp Client — MIT
  • cl-info — A helper to an answer a question about OS, Lisp and Everything. — BSD
  • cl-mimeparse — Library for parsing MIME types, in the spirit of, with a Common Lisp flavor. — MIT
  • cl-opencl — CFFI for OpenCL and Lisp wrapper API — Public Domain
  • cl-schedule — cl-schedule is a cron-like scheduling library in common-lisp. It subsumes and replaces traditional cron managers thanks to richer expressiveness of Lisp. — MIT
  • cl-vorbis — Bindings to stb_vorbis, a simple and free OGG/Vorbis decoding library — zlib
  • claw-olm — Thin wrapper over OLM — MIT
  • context-lite — A CLOS extension to support specializing methods on special/dynamic variables. — MIT
  • defmain — A wrapper around net.didierverna.clon which makes command line arguments parsing easier. — BSD
  • defrest — defrest: expose functions as REST webservices for ajax or other stuff — BSD
  • doc — Documentation generator, based on MGL-PAX. Allows to put documentation inside lisp files and cross-reference between different entities. — MIT
  • ec2-price-finder — Quickly find the cheapest EC2 instance that you need across regions — BSD-3-Clause
  • file-notify — Access to file change and access notification. — zlib
  • fresnel — Bidirectional translation with lenses — MIT
  • log4cl-extras — A bunch of addons to LOG4CL: JSON appender, context fields, cross-finger appender, etc. — BSD
  • mnas-package — Система @b(mnas-package) предназначена для подготовки документации, извлекаемой из asdf-систем. @begin(section) @title(Мотивация) Система @b(Codex) является достаточно удобной для выполнения документирования систем, написанных с использованием @b(Common Lisp). Она позволяет получить на выходе документацию приемлемого вида. К недостатку сустемы @b(Codex) можно отнести то, что формирование шаблона документации не выполняется автоматически. Указание на включение разделов документации, относящихся к отдельным сущностям к которым можно отнести: @begin(list) @item(системы;) @item(пакеты;) @item(классы;) @item(функции, setf-функции;) @item(обобщенные функции,методы, setf-методы;) @item(макросы;) @item(и т.д., и т.п.) @end(list) приходится формировать вручную. Этот проект пытается устранить данный недостаток системы @b(Codex) за счет определения функций и методов позволяющих: @begin(list) @item(формировать код, предназначенный для передачи в систему @b(Codex);) @item(формировать представление отдельных частей системы в виде графов.) @end(list) @end(section) — GNU GENERAL PUBLIC LICENSE Version 3, 29 June 2007 or later
  • mnas-string — Система @b(mnas-string) предназначена для: @begin(list) @item(парсинга вещественного числа;) @item(разделения строки на подстроки;) @item(замены всех вхождений подстроки в строке;) @item(замены множественного вхождения паттерна единичным;) @item(подготовки строки в качестве аргумента для like запроса SQL;) @item(обрамления строки префиксом и постфиксом;) @item(вывода представления даты и времени в поток или строку;) @item(траслитерации строки.) @end(list) — GNU GENERAL PUBLIC LICENSE Version 3, 29 June 2007 or later
  • osmpbf — Library to read OpenStreetMap PBF-encoded files. — MIT
  • plot — Plots for Common Lisp — MS-PL
  • scheduler — Extensible task scheduler. — BSD-2-Clause
  • speechless — A dialogue system language implementation. — zlib
  • stumpwm-sndioctl — Interface to OpenBSD's sndioctl for StumpWM. — ISC
  • vellum — Data Frames for Common Lisp — BSD simplified
  • vellum-clim — Simplistic vellum data frames viewer made with mcclim. — BSD simplified
  • vellum-csv — CSV support for Vellum Data Frames — BSD simplified
  • vellum-postmodern — Postgres support for Vellum Data Frames (via postmodern). — BSD simplified
  • vk — Common Lisp bindings for the Vulkan API. — MIT
  • wasm-encoder — Library for serializing WebAssembly modules to binary .wasm files — MIT

Updated projects: adopt, agutil, also-alsa, anypool, april, architecture.builder-protocol, async-process, audio-tag, bdef, bnf, burgled-batteries.syntax, caveman, chirp, cl+ssl, cl-ana, cl-argparse, cl-async, cl-collider, cl-covid19, cl-cuda, cl-data-frame, cl-data-structures, cl-environments, cl-forms, cl-gamepad, cl-glfw3, cl-gserver, cl-kraken, cl-liballegro, cl-liballegro-nuklear, cl-markless, cl-mixed, cl-naive-store, cl-num-utils, cl-patterns, cl-pdf, cl-prevalence, cl-rfc4251, cl-sendgrid, cl-slice, cl-smt-lib, cl-ssh-keys, cl-steamworks, cl-str, cl-tiled, cl-typesetting, cl-utils, cl-webkit, clack, clack-pretend, clath, clavier, clog, closer-mop, cmd, coleslaw, common-lisp-jupyter, configuration.options, consfigurator, croatoan, cytoscape-clj, damn-fast-priority-queue, data-frame, dataloader, defconfig, definitions, deploy, dfio, diff-match-patch, dissect, djula, dns-client, doplus, dufy, duologue, easy-routes, eclector, erudite, file-attributes, flare, fmt, functional-trees, gendl, generic-cl, golden-utils, gute, harmony, herodotus, hu.dwim.presentation, hunchenissr, hunchensocket, hunchentoot-errors, iterate, kekule-clj, lack, language-codes, lichat-protocol, lisp-stat, literate-lisp, magicffi, maiden, math, mcclim, messagebox, mnas-graph, mnas-hash-table, multiposter, mutility, named-readtables, nibbles, nodgui, numcl, numerical-utilities, nyaml, nyxt, overlord, parseq, pathname-utils, plump-sexp, plump-tex, portable-threads, postmodern, pzmq, qlot, qt-libs, rpcq, sb-cga, sc-extensions, screamer, sel, serapeum, shadow, shop3, specialized-function, spinneret, split-sequence, static-dispatch, static-vectors, stumpwm, sxql, ten, tfeb-lisp-hax, trivial-indent, trivial-timer, trivial-with-current-source-form, trucler, uax-15, vgplot, wild-package-inferred-system, with-c-syntax.

To get this update, use (ql:update-dist "quicklisp"). Enjoy!

Pavel Korolev:claw honing - Beta milestone and alien-works

· 120 days ago

Long time no see my C++ autowrapping rants. But several bindings later, :claw has reached the stage where it is ready to leave a garage and see the outside world. Since my last post, some approaches were revised, though the autowrapping process is still not fully cemented yet. I wouldn't expect :claw to be out of beta for at least a year. That doesn't mean it is unusable, but rather I cannot guarantee a stable interface and a trivial procedure for setting it up.

In other big news, :alien-works system got all required foreign libraries wrapped and integrated, including some complex and peculiar C++ ones (Skia 👀). Next step is to write a game, based on :alien-works framework, to see how much lispification of autowrapped systems is possible without loosing any performance and what is required for a solid game delivery.

Joe MarshallStupid Y operator tricks

· 128 days ago

Here is the delta function: δ = (lambda (f) (f f)). Delta takes a function and tail calls that function on itself. What happens if we apply the delta function to itself? Since the delta function is the argument, it is tail called and applied to itself. Which leads again to itself being tail called and applied to itself. We have a situation of infinite regression: the output of (δ δ) ends up being a restatement of the output of (δ δ). Now in this case, regression is infinite and there is no base case, but imagine that somehow there were a base case, or that somehow we identified a value that an infinite regression equated to. Then each stage of the infinite regression just replicates the previous stage exactly. It is like having a perfectly silvered mirror: it just replicates the image presented to it exactly. By calling delta on delta, we've arranged our perfectly silvered mirror to reflect an image of itself. This leads to the “infinite hall of mirrors” effect.

So let's tweak the delta function so that instead of perfectly replicating the infinite regression, it applies a function g around the replication: (lambda (f) (g (f f))). If we apply this modified delta function to itself, each expansion of the infinite regression ends up wrapping an application of the g around it: (g (f f)) = (g (g (f f))) = (g (g (g (f f)))) = (g (g (g (g … )))). So our modified delta function gives us a nested infinite regression of applications of g. This is like our perfectly silvered mirror, but now the reflected image isn't mirrored exactly: we've put a frame on the mirror. When we arrange for the mirror to reflect itself, each nested reflection also has an image of the frame around the reflection, so we get a set of infinitely nested frames.

An infinite regression of (g (g (g (g … )))) is confusing. What does it mean? We can untangle this by unwrapping an application. (g (g (g (g … )))) is just a call to g. The argument to that call is weird, but we're just calling (g <something>). The result of the infinite regression (g (g (g (g … )))) is simply the result of the outermost call to g. We can use this to build a recursive function.

;; If factorial = (g (g (g (g … )))), then
;; factorial = (g factorial), where

(defun g (factorial)
  (lambda (x)
    (if (zerop x)
        (* x (funcall factorial (- x 1))))))
The value returned by an inner invocation of g is the value that will be funcalled in the altenative branch of the conditional.

Y is defined thus:

Y = λg.(λf.g(f f))(λf.g(f f))

A straightforward implementation attempt would be
;; Non working y operator
(defun y (g)
  (let ((d (lambda (f) (funcall g (funcall f f)))))
    (funcall d d)))
but since lisp is a call-by-value language, it will attempt to (funcall f f) before funcalling g, and this will cause runaway recursion. We can avoid the runaway recursion by delaying the (funcall f f) with a strategically placed thunk
;; Call-by-value y operator
;; returns (g (lambda () (g (lambda () (g (lambda () … ))))))
(defun y (g)
  (let ((d (lambda (f) (funcall g (lambda () (funcall f f))))))
    (funcall d d)))
Since the recursion is now wrapped in a thunk, we have to funcall the thunk to force the recursive call. Here is an example where we see that:
* (funcall (Y (lambda (thunk)
                (lambda (x)
                  (if (zerop x)
                      (* x (funcall (funcall thunk) (- x 1)))))))
the (funcall thunk) invokes the thunk in order to get the actual recursive function, which we when then funcall on (- x 1).

By wrapping the self-application with a thunk, we've made the call site where we use the thunk more complicated. We can clean that up by wrapping the call to the thunk in something nicer:

* (funcall
    (y (lambda (thunk)
         (flet ((factorial (&rest args)
                  (apply (funcall thunk) args)))

           (lambda (x)
             (if (zerop x)
                 (* x (factorial (- x 1))))))))
And we can even go so far as to hoist that wrapper back up into the definiton of y
(defun y1 (g)
  (let ((d (lambda (f) (funcall g (lambda (&rest args) (apply (funcall f f) args))))))
    (funcall d d)))

* (funcall
    (y1 (lambda (factorial)
          (lambda (x)           
            (if (zerop x)
                (* x (funcall factorial x))))))
y1 is an alternative formulation of the Y operator where we've η-expanded the recursive call to avoid the runaway recursion.

The η-expanded version of the applicative order Y operator has the advantage that it is convenient for defining recursive functions. The thunkified version is less convenient because you have to force the thunk before using it, but it allows you to use the Y operator to define recursive data structures as well as functions:

  (lambda (delayed-ones)
    (cons-stream 1 (delayed-ones))))
{1 …}

The argument to the thunkified Y operator is itself a procedure of one argument, the thunk. Y returns the result of calling its argument. Y should return a procedure, so the argument to Y should return a procedure. But it doesn't have to immediately return a procedure, it just has to eventually return a procedure, so we could, for example, print something before returning the procedure:

* (funcall (Y (lambda (thunk)
                (format t "~%Returning a procedure")
                (lambda (x)
                  (if (zerop x)
                      (* x (funcall (funcall thunk) (- x 1)))))))
Returning a procedure
Returning a procedure
Returning a procedure
Returning a procedure
Returning a procedure
Returning a procedure
There is one caveat. You must be able to return the procedure without attempting to make the recursive call.

Let's transform the returned function before returning it by applying an arbitrary function h to it:

(Y (lambda (thunk)
     (h (lambda (x)
          (if (zerop x)
              … )))))
Ok, so now when we (funcall thunk) we don't get what we want, we've got an invocation of h around it. If we have an inverse to h, h-1, available, we can undo it:
(y (lambda (thunk)
      (h (lambda (x)
           (if (zerop x)
               (* (funcall (h-1 (funcall thunk)) (- x 1))))))))
As a concrete example, we return a list and at the call site we extract the first element of that list before calling it:
* (funcall (car (y (lambda (thunk)
                     (list (lambda (x)
                             (if (zerop x)
                                 (* x (funcall (car (funcall thunk)) (- x 1))))))))
So we can return a list of mutually recursive functions:
(y (lambda (thunk)
      ;; even?
      (lambda (n)
        (or (zerop n)
            (funcall (cadr (funcall thunk)) (- n 1))))

      ;; odd?
      (lambda (n)
        (and (not (zerop n))
             (funcall (car (funcall thunk)) (- n 1))))
If we use the η-expanded version of the Y operator, then we can adapt it to expect a list of mutually recursive functions on the recursive call:
(defun y* (&rest g-list)
  (let ((d (lambda (f)
             (map 'list (lambda (g)
                          (lambda (&rest args)
                            (apply (apply g (funcall f f)) args)))
     (funcall d d)))
which we could use like this:
* (let ((eo (y* (lambda (even? odd?)
                  (declare (ignore even?))
                  (lambda (n)
                    (or (zerop n)
                        (funcall odd? (- n 1)))))

                (lambda (even? odd?)
                  (declare (ignore odd?))
                  (lambda (n)
                    (and (not (zerop n))
                         (funcall even? (- n 1))))))))
     (let ((even? (car eo))
           (odd?  (cadr eo)))
       (do ((i 0 (+ i 1)))
           ((>= i 5))
         (format t "~%~d, ~s ~s"
                 (funcall even? i)
                 (funcall odd? i)))))))
0, T NIL
1, NIL T
2, T NIL
3, NIL T
4, T NIL
Instead of returning a list of mutually recursive functions, we could return them as multiple values. We just have to be expecting multiple values at the call site:
(defun y* (&rest gs)
  (let ((d (lambda (f)
             (apply #'values
                    (map 'list
                         (lambda (g)
                           (lambda (&rest args)
                             (apply (multiple-value-call g (funcall f f)) args)))
    (funcall d d)))

MIT Scheme used to have a construct called a named lambda. A named lambda has an extra first argument that is automatically filled in with the function itself. So during evaluation of the body of a named lambda, the name is bound to the named lambda, enabling the function to call itself recursively:

(defmacro named-lambda ((name &rest args) &body body)
  `(y1 (lambda (,name)
         (lambda ,args

* (funcall (named-lambda (factorial x)
            (if (zerop x)
                (* x (funcall factorial (- x 1)))))
This leads us to named let expressions. In a named let, the implicit lambda that performs the let bindings is a named lambda. Using that name to invoke the lambda on a different set of arguments is like recursively re-doing the let.
* (named-let fact ((x 6)) (if (zerop x) 1 (* x (funcall fact (- x 1)))))


In Scheme, you use letrec to define recursive or mutually recursive procedures. Internal definitions expand into an appropriate letrec. letrec achieves the necessary circularity not through the Y operator, but through side effects. It is hard to tell the difference, but there is a difference. Using the Y operator would allow you to have recursion, but avoid the implicit side effects in a letrec.

Oleg Kiselyov has more to say about the Y operator at

Joe Marshall&#946;-conversion

· 134 days ago

If you have an expression that is an application, and the operator of the application is a lambda expression, then you can β-reduce the application by substituting the arguments of the application for the bound variables of the lambda within the body of the lambda.

(defun beta (expression if-reduced if-not-reduced)
  (if (application? expression)
      (let ((operator (application-operator expression))
            (operands (application-operands expression)))
        (if (lambda? operator)
            (let ((bound-variables (lambda-bound-variables operator))
                  (body (lambda-body operator)))
              (if (same-length? bound-variables operands)
                  (funcall if-reduced
                           (xsubst body
                                   (table/extend* (table/empty)
                  (funcall if-not-reduced)))
            (funcall if-not-reduced)))
      (funcall if-not-reduced)))

* (beta '((lambda (x y) (lambda (z) (* x y z))) a (+ z 3))
        #'identity (constantly nil))
(LAMBDA (#:Z460) (* A (+ Z 3) #:Z460))

A large, complex expression may or may not have subexpressions that can be β-reduced. If neither an expression or any of its subexpressions can be β-reduced, then we say the expression is in “β-normal form”. We may be able to reduce an expression to β-normal form by β-reducing where possible. A β-reduction can introduce further reducible expressions if we substitute a lambda expression for a symbol in operator position, so reducing to β-normal form is an iterative process where we continue to reduce any reducible expressions that arise from substitution.

(defun beta-normalize-step (expression)
  (expression-dispatch expression

    ;; case application
    (lambda (subexpressions)
      ;; Normal order reduction
      ;; First, try to beta reduce the outermost application,
      ;; otherwise, recursively descend the subexpressions, working
      ;; from left to right.
      (beta expression
            (lambda ()
              (labels ((l (subexpressions)
                         (if (null subexpressions)
                             (let ((new-sub (beta-normalize-step (car subexpressions))))
                               (if (eq new-sub (car subexpressions))
                                   (let ((new-tail (l (cdr subexpressions))))
                                     (if (eq new-tail (cdr subexpressions))
                                         (cons (car subexpressions) new-tail)))
                                   (cons new-sub (cdr subexpressions)))))))
                (let ((new-subexpressions (l subexpressions)))
                  (if (eq new-subexpressions subexpressions)
                      (make-application new-subexpressions)))))))

    ;; case lambda
    (lambda (bound-variables body)
      (let ((new-body (beta-normalize-step body)))
        (if (eql new-body body)
            (make-lambda bound-variables new-body))))

    ;; case symbol
    (constantly expression)))

;;; A normalized expression is a fixed point of the
;;; beta-normalize-step function.
(defun beta-normalize (expression)
  (do ((expression expression (beta-normalize-step expression))
       (expression1 '() expression)
       (count 0 (+ count 1)))
      ((eq expression expression1)
       (format t "~%~d beta reductions" (- count 1))

You can compute just by using β-reduction. Here we construct an expression that reduces to the factorial of 3. We only have β-reduction, so we have to encode numbers with Church encoding.

(defun test-form ()
  (let ((table
            ;; Church numeral one
            (lambda (f) (lambda (x) (f x)))

            ;; Church numeral three 
            (lambda (f) (lambda (x) (f (f (f x)))))

            ;; * (multiply Church numerals)
            (lambda (m n)
              (lambda (f)
                (m (n f))))

            ;; pred (subtract 1 from Church numeral)
            (lambda (n)
              (lambda (f)
                (lambda (x) (((n (lambda (g)
                                   (lambda (h)
                                     (h (g f)))))
                              (lambda (u) x))
                             (lambda (u) u)))))

            ;; zero? (test if Church numeral is zero)
            (lambda (n t f) ((n (lambda (x) f)) t))

            ;; Y operator for recursion
            (lambda (f)
              ((lambda (x) (f (x x)))
               (lambda (x) (f (x x)))))

         '((lambda (factorial)
             (factorial three))
           (y (lambda (fact)
                (lambda (x)
                  (zero? x
                   (* (fact (pred x)) x))))))))
    (xsubst expr table)))

* (test-form)

 ((LAMBDA (F) ((LAMBDA (X) (F (X X))) (LAMBDA (X) (F (X X)))))
    (LAMBDA (X)
      ((LAMBDA (N T F) ((N (LAMBDA (X) F)) T)) X
       (LAMBDA (F) (LAMBDA (X) (F X)))
       ((LAMBDA (M N) (LAMBDA (F) (M (N F))))
         ((LAMBDA (N)
            (LAMBDA (F)
              (LAMBDA (X)
                (((N (LAMBDA (G) (LAMBDA (H) (H (G F))))) (LAMBDA (U) X))
                 (LAMBDA (U) U)))))

* (beta-normalize (test-form))

127 beta reductions
(LAMBDA (F) (LAMBDA (X) (F (F (F (F (F (F X))))))))

This is the Church numeral for 6.

I find it pretty amazing that we can bootstrap ourselves up to arithmetic just by repeatedly β-reducing where we can. It doesn't seem like we're actually doing any work. We're just replacing names with what they stand for.

The β-substitution above replaces all the bound variables with their arguments if there is the correct number of arguments. One could easily implement a partial β-substitution that replaced only some of the bound variables. You'd still have an application, but some of the bound variables in the lambda would be eliminated and the corresponding argument would be removed.

Joe MarshallSubstitution

· 139 days ago

In McCarthy's early papers on Lisp, he notes that he needs a modified version of subst which needs to be aware of quoted expressions (and avoid substituting within them). He would also need a subst that was aware of lambda expressions. It would have to avoid substituting within the lambda if the name substituted matches one of the bound variables. To be useful for evaluation, it will have to deal with accidental variable capture when substituting within a lambda.

The root problem is that expressions are actually structured objects, but we are working with the list representation of those objects. Instead of substituting by operating on objects, we substitute on the list representation. We have to arrange for the syntactic substitution on the list representation to preserve the semantics of substitution on the objects they represent.

In the substitution model, we take a symbolic expression and replace some of the atoms in the expression with other expressions. We first need a way to discriminate between the different kinds of expressions. An expression is either an atomic symbol, or a list of expressions called an application. There are no other kinds of expressions.

(defun expression-dispatch (expression if-symbol if-application)
  (cond ((symbolp expression) (funcall if-symbol expression))
        ((consp expression)   (funcall if-application expression))
        (t (error "~s is not an expression." expression))))
Substitution is straightforward:
(defun xsubst (table expression)
  (expression-dispatch expression
    (lambda (symbol)
      (funcall table symbol #'identity (constantly symbol)))

    (lambda (subexpressions)
      (map 'list (lambda (subexpression) (xsubst table subexpression)) subexpressions))))

* (let ((table (table/extend (table/empty) 'x '(* a 42))))
    (xsubst table '(+ x y)))  
(+ (* A 42) Y)
We need a table of multiple substitutions so that we can substitute in parallel:
* (let ((table (table/extend
                 (table/extend (table/empty) 'x 'y)
                 'y 'x)))
    (xsubst table '(+ x y)))
(+ Y X)

So far, so good. Let's add lambda expressions. First, we need to add a new expression kind:

(defun expression-dispatch (expression if-symbol if-lambda if-application) 
  (cond ((symbolp expression) (funcall if-symbol expression))
        ((consp expression)
         (cond ((eq (car expression) 'lambda)
                (funcall if-lambda (cadr expression) (caddr expression)))
               (t (funcall if-application expression))))
        (t (error "~s is not an expression." expression))))

Substitution within a lambda expression is a bit tricky. First, you don't want to substitute a symbol if it is one of the bound variables of the lambda expression. Second, substituting a symbol may introduce more symbols. We don't want the new symbols to be accidentally captured by the bound variables in the lambda. If any new symbol has the same name as a bound variable, we have to rename the bound variable (and all its occurrances) to a fresh name so that it doesn't capture the new symbol being introduced. We'll need a helper function

(defun free-variables (expression)
   (expression-dispatch expression
     (lambda (symbol) (list symbol))
     (lambda (bound-variables body)
       (set-difference (free-variables body) bound-variables))
     (lambda (subexpressions)
       (fold-left #'union '() (map 'list #'free-variables subexpressions)))))
Now when we substitute within a lambda, we first find each free variable in the lambda, look it up in the substitution table, and collect the free variables of the substituted value:
(map 'list (lambda (var)
             (funcall table var #'free-variables (constantly '())))
      (free-variables expression))
This gives us the new free variables for each substitution. The union of all of these is the set of all the new free variables
(fold-left #'union '()
           (map 'list (lambda (var)
                        (funcall table var #'free-variables (constantly '())))
                 (free-variables expression)))
We have to rename the bound variables that are in this set:
  (fold-left #'union '()
             (map 'list (lambda (var)
                          (funcall table var #'free-variables (constantly '())))
                  (free-variables expression))))
So we make a little table for renaming:
(defun make-alpha-table (variables)
  (fold-left (lambda (table variable)
               (table/extend table variable (gensym (symbol-name variable))))

(let ((alpha-table
          (fold-left #'union '()
                     (map 'list (lambda (var)
                                  (funcall table var #'free-variables (constantly '())))
                          (free-variables expression)))))))
We rename the bound variables as necessary:
    (map 'list (lambda (symbol)
                 (funcall alpha-table symbol #'identity (constantly symbol)))
Finally, we redact the bound variables from the substitution table and append the alpha-table to make the substitutions we need for the lambda body
   (map 'list (lambda (symbol)
                (funcall alpha-table symbol #'identity (constantly symbol)))
   (xsubst (table/append alpha-table (table/redact* table bound-variables))
The entire definition of xsubst is now this:
(defun xsubst (table expression)
  (expression-dispatch expression
    (lambda (symbol)
      (funcall table symbol #'identity (constantly symbol)))

    (lambda (bound-variables body)
      (let ((alpha-table
               (fold-left #'union '()
                          (map 'list (lambda (var)
                                       (funcall table var
                                                (constantly '())))
                               (set-difference (free-variables body) bound-variables)))))))
         (map 'list (lambda (symbol)
                      (funcall alpha-table symbol #'identity (constantly symbol)))
         (xsubst (table/append alpha-table (table/redact* table bound-variables))

    (lambda (subexpressions)
       (map 'list (lambda (subexpression)
                    (xsubst table subexpression))
This is certainly more complicated than simple substitution, but we can see it does the right thing here:
* (xsubst (table/extend (table/empty) 'x '(* a y)) '(lambda (y) (+ x y)))
(LAMBDA (#:Y234) (+ (* A Y) #:Y234))

It should be obvious how to add quoted forms. This would require adding a new kind of expression to expression-dispatch and a new handling clause in xsubst that avoids substitution.

I'm not completely happy with how we've added lambda expressions to the expression syntax. Using the symbol lambda as a syntactic marker for lambda expressions causes problems if we also want to use that symbol as an argument or variable. Initially, it seems reasonable to be able to name an argument “lambda”. Within the body of the function, references to the variable lambda would refer to that argument. But what about references in the operator position? By defining lambda expressions as three element lists beginning with the symbol lambda we've made it ambiguous with two-argument applications whose operator is the variable lambda. We have to resolve this ambiguity. The current behavior is that we always interpret the symbol lambda as a syntactic marker so you simply cannot use a variable named lambda as a function.

Nicolas HafnerEternia release and updated plans - May Kandria Update

· 140 days ago

Another hectic month gone by. Getting Eternia: Pet Whisperer done and published on Steam in such a short time was no small feat. There were a few hurdles along the way as well, especially when it came to getting it ready for Steam, but overall I'm really glad we managed to get it out. Having a bona fide released title is amazing!

Most of the trouble with getting it put on Steam was the manual review process they have. It turns out, real people actually check your builds before you're allowed to sell the game. And not only do they check whether it launches, they also do other tests like whether gamepad support works, whether captions are included, etc. It's a lot more extensive than I had expected, which is really nice!

Unfortunately I was also confused by a couple of options, and misunderstood others, so I had to go through the review a bunch of times, which caused a bunch of stress for me and ultimately delayed the release of Eternia by two days. Welp! At least now I know for the future that I'll have to start with the Steam review process well in advance of the actual release. With Eternia everything was so back to back that there really wasn't any more time for that than we had.

The days since the release haven't been much less hectic either. There were a few bugs that had to be ironed out that prevented people from playing the game. Most notably:

  • People with surround headphones could not play as those headphones announce themselves as 7.1 surround systems, which I didn't expect anyone would have.

  • Some bad versions of shared libraries snuck themselves into the release builds on Linux.

  • The save menu was bugged due to a regression in the UI library

  • Avast antivirus causes random Windows exceptions in the game (this is not fixed and I don't know how to fix it).

There were also some minor content fixes for typos and such along the way. In any case, the automated crash report system I instated for Kandria helped a lot as it told me when people were having issues. Still, it was heartbreaking every time I got a report, as knowing people can't even play the game and are likely very frustrated or disappointed stings a lot.

I really hope the Kandria release will be more smooth and less prone to issues now that we have a better handle on the process. Still, the amount of issues that are only uncovered by having people with various PC setups try to run your game is... well, it's not great. One of the many perils of the PC platform, I suppose.

It hasn't yet been a full week so I don't really want to go into the statistics of the Eternia release, but I'll be sure to talk about that stuff in the next weekly update!

Anyway, aside from supporting the Eternia review and taking care of the marketing around that, I also did some planning for Kandria. I asked ProHelvetia, and it turns out the submission deadline for the grant is going to be 1st of September of this year. This gives us roughly four months to graft a tutorial onto the vertical slice, and polish the fuck out of it to make it look as good as possible.

A first step in that is to iron out egregious bugs that were reported from people playing the public vertical slice, and making a new trailer that shows off all the new content we made. I've now started working on both of those things and we should be able to finish the new trailer in the next week.

I initially also wanted to put out a patch for the vertical slice already, but while we did fix a number of bugs and there's a few improvements, I'd rather wait until the rest of the other known and egregious bugs are ironed out at least. Regardless though, if you're on the Discord or the mailing list, we'll let you know when that patch hits!


In the last monthly I announced that you'll get to hear the pieces the three finalists put together, so here they are! I hope you enjoy listening to them!

While all three of them did a fantastic job and the decision was a hard one, we ultimately went with...


Hey everyone, my name is Mikel - nice to meet you! I'll be working as Kandria's composer from now on, which means I'll bang some notes on the piano and hope they sound good.

In my first week as part of the team, I've been working side by side Shinmera on the game's new trailer. Taking inspiration from OSTs like Astral Chain and Octopath Traveller (as well as using our secret weapon, Julie Elven), we're cooking up something real good!

If you have any suggestions, any soundtracks you'd like me to check out, or any weird instruments/sounds you demand I incorporate in the music, please let me know on the Discord! It'd be great to have some feedback from you too :)

Ah yes, time for shameless plug: if you'd like to listen to some other games I'm working on, feel free to peruse Underdesert (rogue-lite dungeon FPS game), Waves of Steel (naval battle!), Cryptonom (if you like monster RPGs), or Heredity (good ol' fantasy ARPG).

You can also check out my website for more deets.

Look forward to showing you what's next!


The majority of this month has been occupied by our jam game Eternia. It was actually my first game jam, and I've really enjoyed it - I'm not exaggerating when I say it's been some of the most fun I've had in game writing so far. We agreed on the broad concept early on, and then I was given a lot of creative freedom on the story and character dialogue. I'm really pleased with how much content I produced (around 20k words) in such a short time frame, which was definitely helped by the quick-iteration dialogue system, and forced by the necessary constraints.

The game is incredibly non-linear, so the challenge was writing things in a modular way, such that they made sense whichever direction you came at them from. With some crafty narrative design and plotting, I think it holds together remarkably well; players would be surprised how little, if any, conditional branching there is behind the scenes. With such a tight dev time, it was important the game wasn't a spiderweb of quest logic, for both my own sanity, and for playtesting.

Thankfully I didn't have to do too much research either, since my wife Lesleyann and I have rescued animals from shelters in the past (especially rats!). Les used to be an animal behaviourist too, so I've gained a base awareness of things like calming signals in dogs, by osmosis over the years; she was also a big help when I needed a steer on certain things. There really wasn't time for anything more than a cursory amount of research, so this was definitely a plus for this idea when Nick first suggested it.

Towards the end of the month I jumped back on Kandria, fleshing out the lore for the other world factions ready for Fred to concept. This was really beneficial to give me a feel for the wider world, and allowed some tweaking of the plot. As we progress with the content for the rest of this year, these factions will get fleshed out further with their own unique characters and quest lines.

I've also worked with Nick on the script for the new trailer, and helped in sourcing a voice actor. I've also gotten back up to speed on the vertical slice content, playtesting the quests to make sure they're still working correctly after the restructuring of the quest system. With fresh eyes, this has also let me tweak dialogue as I went.

What's next

Here's a rough roadmap for the rest of the year:

  • Make the combat more flashy

  • Finish a new trailer

  • Design and outline the factions for the rest of the game

  • Develop the soundscape for Kandria and start working on the tracks for region 1

  • Add a music system that can do layering and timed transitions

  • Build and add the tutorial sequence to the beginning of the game

  • Polish the ProHelvetia submission material

  • Polish and revise the combat design

  • Explore platforming items and mechanics

  • Practise platforming level design

  • Start work on the horizontal slice

Of course the size of the items varies a lot, but hopefully we should be able to begin work on the horizontal slice by November. If we extrapolate the time it took for the vertical slice and cut some content, this should leave us with enough time to finish by early 2023... provided we don't run outta money.

Anyway, that's why the grant is the primary target for now. Though we were also accepted by ProHelvetia for GDC Online and the SwissNex US Game Industry Week, so that'll give us some more opportunities to look for a publisher. Having a new trailer for that should definitely help a lot!

Well, see you next time then! Remember that there's a mailing list with weekly updates, a discord for the community, and my twitter with short videos and images on the development! Oh, and do check out Eternia if you haven't yet. We've gotten some really nice reviews for it, which has been a joy to see!

Joe MarshallLightweight table

· 146 days ago

You don't need a data structure to make a lookup table. You can make a table just out of the lookup function. In this example, we start with a continuation passing style lookup function:

lookup (key if-found if-not-found)
    Invokes (funcall if-found value) if key is in the table,
    invokes (funcall if-not-found) otherwise.
An empty table just invokes the if-not-found continuation:
(defun table/empty ()
  (lambda (key if-found if-not-found)
    (declare (ignore key if-found))
    (funcall if-not-found)))
A table can be extended by wrapping it:
(defun table/extend (table key* value)
  (lambda (key if-found if-not-found)
    (if (eql key key*)
        (funcall if-found value)
        (funcall table key if-found if-not-found))))
So let's try it out:
(defvar *table-1* (table/extend 
                      'foo 42)
                    'bar 69))

* (funcall *table-1* 'foo #'identity (constantly 'not-found))

* (funcall *table-1* 'quux #'identity (constantly 'not-found))
You can also redact an entry from a table by wrapping the table:
(defun table/redact (table redacted)
  (lambda (key if-found if-not-found)
    (if (eql key redacted)
        (funcall if-not-found)
        (funcall table key if-found if-not-found))))

(defvar *table-2* (table/redact *table-1* 'foo))

* (funcall *table-2* 'foo #'identity (constantly 'not-found))

Are there any advantages to implementing a table in this curious manner? Building a table by nesting a series of lookup steps leads to a linear lookup in linear space, so this kind of table should be more or less comparable to an alist for individual entries. Unlike a traditional table made with a data structure, you cannot enumerate the keys and values in the table. On the other hand, you gain the ability to map keys to values without having to enumerate the keys:

(defun table/bind-predicate (table predicate value)
  (lambda (key if-found if-not-found)
    (if (funcall predicate key)
        (funcall if-found value)
        (funcall table key if-found if-not-found))))

;;; bind all even numbers to the symbol 'EVEN
(defvar *table-3* 
  (table/bind-predicate *table-2* (lambda (n) (and (numberp n) (evenp n))) 'even))

* (funcall *table-3* 6 #'identity (constantly 'not-found))
Or you can add a default value to an existing table:
(defun table/add-default (table default-value)
  (lambda (key if-found if-not-found)
    (declare (ignore if-not-found))
    (funcall table key
      (lambda () (funcall if-found default-value)))))

(defvar *table-4* (table/add-default *table-3* 'default))

* (funcall *table-4* 'bar #'identity (constantly 'not-found))
* (funcall *table-4* 'xyzzy #'identity (constantly 'not-found))

Perhaps the biggest disadvantage of this implementation is the difficulty in inspecting a table.

* *table-4*
We can use the object inspector to peek inside the closure and maybe sleuth out what this table is made out of, but it isn't just an alist where we can print out the entries.

So far, we've defined a table as being a procedure with the (key if-found if-not-found) signature, but we can flip this around and say that any procedure with a (key if-found if-not-found) signature can be thought of as a table. For example, a regular expression matcher could be considered to be a table of strings (if that were a more useful model).

Wimpie NortjeUser feedback during long running external processes.

· 148 days ago

Sometimes it may be necessary to execute an external command that takes a long time to complete, long enough that the user needs visual feedback while it is running to show that the process is still alive.

UIOP provides fantastic tools for running external commands in a portable manner but it was not obvious to me how to show the external command's output to the user while it was still busy. I also wanted to execute the external command in a synchronous fashion, i.e. my lisp application must wait for the external command to finish before continuing. The need for synchronicity sent me down the wrong path of using the synchronous uiop:run-program. It only returns when the external command has finished, which means you can only process the command output once it is completed.

I eventually realised I should use uiop:launch-program, the asynchronous version, and I came up with the following solution. In the example below the (ping) function pings a website and prints the results as they become available. Afterwards it returns the exit code of the ping command.

(defun ping ()
  (let (proc out exit-code)
           (setf proc (uiop:launch-program
                       (list "ping" "-c" "5" "")
                       :ignore-error-status t
                       :output :stream))
           (setf out (uiop:process-info-output proc))
             (while (uiop:process-alive-p proc))
               (while (listen out))
               (write-char (read-char out) *STANDARD-OUTPUT*))
             ;; ... Maybe do something here
             (sleep 0.5))
           (uiop:copy-stream-to-stream out *STANDARD-OUTPUT* 
                                       :linewise t))
      (setf exit-code (uiop:wait-process proc))
      (uiop:close-streams proc))

In the first example the command's output is shown to the user but it is not processed in any other way. If you need to do some extra processing on it after completion then the next example should provide a good starting point.

(defun ping-processing ()
  (let (proc out exit-code output)
    (with-open-stream (output-stream (make-string-output-stream))
      (with-open-stream (broadcast-stream 
                         (make-broadcast-stream *STANDARD-OUTPUT* 
               (setf proc (uiop:launch-program
                           (list "ping" "-c" "5" 
                           :ignore-error-status t
                           :output :stream))
               (setf out (uiop:process-info-output proc))
                 (while (uiop:process-alive-p proc))
                   (while (listen out))
                   (write-char (read-char out) broadcast-stream))
                 (sleep 0.5))
               (uiop:copy-stream-to-stream out broadcast-stream 
                                           :linewise t)))
          (setf exit-code (uiop:wait-process proc))
          (uiop:close-streams proc)
        (setf output (get-output-stream-string output-stream))
        ;; ... process output here

Eric TimmonsNew Project: adopt-subcommands

· 158 days ago

I have just released a new project: adopt-subcommands. This project extends the excellent Adopt library with support for arbitrarily nested subcommands. See the README for more information.

I have just asked that it be included in Quicklisp, so hopefully it will be present in the next QL release.


After bouncing around between CL command line processing libraries for a while (including CLON, unix-opts, and another I forget), I tried Adopt shortly after it was released and immediately got hooked. It was just super easy to use and it used functions as the default way to define interfaces (which encouraged reuse and programatic generation). To be fair, other libraries have similar features, but there's just something about Adopt that clicked with me.

The big thing missing for me was easy support for subcommands. Libraries like CLON support that out of the box, but (at least in CLON's case) required that you completely specify every option at the terminal nodes. I wanted to define a folder-like hierarchy where options defined at some level get automatically applied to everything below it as well.

I was able to hack together a solution using Adopt, but I built it in a hurry and it was definitely not fit for general consumption. Since then, I was inspired by Steve Losh's Reddit comment giving an example of how he'd make a simple subcommand CLI parser using Adopt. His post made me realize I missed the existence of the adopt:treat-as-argument restart (d'oh!) and after that, all the pieces fell into place on how to cleanly rewrite my solution. This library is the result!

Nifty Features

I work with a number of programs written in golang that (IMO) have atrocious CLI handling (like helmfile and Kaniko). Maybe it's the individual program's fault, but it's endemic enough that I suspect whatever CLI parser the golang community has landed on is just terrible.^1

For instance, position of the options matters. "Global" options have to come before the subcommand is even specified. So foo --filter=hi run can have a completely different meaning than foo run --filter=hi. Additionally, some of the subcommand style programs I work with don't print all the options if you ask for help, they only print the options associated with the most recent subcommand.

Needless to say, I made sure adopt-subcommands didn't exhibit any of these behaviors. As this library is parsing the command line, it builds up a path of the folders (and eventually the terminal command) it passes through. This path can be passed to adopt-subcommands:print-help to print a help string that includes all the associated options. Additionally, options can come at any point after the subcommand that defines them.^2

There are two major difference between Adopt and this library:

  1. You need to provide functions when you define a terminal subcommand. This function will be called with the results of the parsing when you dispatch.
  2. The dispatch function has a keyword argument :print-help-and-exit. If you provide the symbol naming your help option, then this library will automatically print the help and exit if that option is specified, and after doing as much parsing as possible.

Give it a try and let me know of any issues that you find!

1: although, it wouldn't surprise me if some gophers started arguing that it's totally on purpose, is actually quite elegant, blah blah blah. I kid. I'm just salty about golang's lack of conditions and insistence on using tabs and let that color my take on the entire language.

2: It would be possible to let them come before as well, but at the risk of introducing ambiguity. It's not clear to me that it's worth it.

Joe Marshall&#951;-conversion and tail recursion

· 160 days ago

Consider this lambda expression: (lambda (x) (sqrt x)). This function simply calls sqrt on its argument and returns whatever sqrt returns. There is no argument you could provide to this function that would cause it to return a different result than you would get from calling sqrt directly. We say that this function and the sqrt function are extensionally equal. We can replace this lambda expression with a literal reference to the sqrt function without changing the value produced by our code.

You can go the other way, too. If you find a literal reference to a function, you can replace it with a lambda expression that calls the function. This is η-conversion. η-reduction is removing an unnecessary lambda wrapper, η-expansion is introducting one.

η-conversion comes with caveats. First, it only works on functions. If I have a string "foo", and I attempt to η-expand this into (lambda (x) ("foo" x)), I get nonsense. Second, a reduction strategy that incorporates η-reduction can be weaker than one that does not. Consider this expression: (lambda (x) ((compute-f) x)). We can η-reduce this to (compute-f), but this makes a subtle difference. When wrapped with the lambda, (compute-f) is evaluated just before it is applied to x. In fact, we won't call (compute-f) unless we invoke the result of the lambda expression somewhere. However, once η-reduced, (compute-f) is evaluated at the point the original lambda was evaluated, which can be quite a bit earlier.

When a function foo calls another function bar as a subproblem, an implicit continuation is passed to bar. bar invokes this continuation on the return value that it computes. We can characterize this continuation like this:

kbar = (lambda (return-value)
         (kfoo (finish-foo return-value)))
this just says that when bar returns, we'll finish running the code in foo and further continue by invoking the continuation supplied to foo.

If foo makes a tail call to bar, then foo is just returning what bar computes. There is no computation for foo to finish, so the continuation is just

kbar = (lambda (return-value)
         (kfoo return-value))
But this η-reduces to just kfoo, so we don't have to allocate a new trivial continuation when foo tail calls bar, we can just pass along the continuation that was passed to foo.

Tail recursion is equivalent to η-reducing the implicit continuations to functions where possible. A Scheme aficionado might prefer to say avoiding η-expanding where unnecessary.

This is a mathematical curiosity, but does it have practical significance? If you're programming in continuation passing style, you should be careful to η-reduce (or avoid η-expanding) your code.

Years ago I was writing an interpreter for the REBOL language. I was getting frustrated trying to make it tail recursive. I kept finding places in the interpreter where the REBOL source code was making a tail call, but the interpreter itself wasn't, so the stack would grow without bound. I decided to investigate the problem by rewriting the interpreter in continuation passing style and seeing why I couldn't η-convert the tail calls. Once in CPS, I could see that eval took two continuations and I could achieve tail recursion by η-reducing one of them.

Wimpie NortjeProcess sub-command style command line options with Adopt.

· 161 days ago

How to process sub-command style command line arguments is a question that arises more and more. Many of the basic option handling libraries can not handle this at all, or they make it very difficult to do so.

One of the newer libraries in the option processing field is Adopt by Steve Losh. It was not designed to handle sub-commands but it is in fact very capable to do this without having to jump through too many hoops.

In a Reddit thread someone asked if Adopt can handle sub-command processing and Steve answered with the following example:

(eval-when (:compile-toplevel :load-toplevel :execute)
  (ql:quickload '(:adopt) :silent t))

(defpackage :subex
  (:use :cl)
  (:export :toplevel *ui*))

(in-package :subex)

;;;; Global Options and UI ----------------------------------------------------
(defparameter *o/help*
  (adopt:make-option 'help :long "help" :help "display help and exit" :reduce (constantly t)))

(defparameter *o/version*
  (adopt:make-option 'version :long "version" :help "display version and exit" :reduce (constantly t)))

(defparameter *ui/main*
    :name "subex"
    :usage "[subcommand] [options]"
    :help "subcommand example program"
    :summary "an example program that uses subcommands"
    :contents (list *o/help* *o/version*)))

(defparameter *ui* *ui/main*)

;;;; Subcommand Foo -----------------------------------------------------------
(defparameter *o/foo/a*
  (adopt:make-option 'a :result-key 'mode :short #\a :help "run foo in mode A" :reduce (constantly :a)))

(defparameter *o/foo/b*
  (adopt:make-option 'b :result-key 'mode :short #\b :help "run foo in mode B" :reduce (constantly :b)))

(defparameter *ui/foo*
    :name "subex foo"
    :usage "foo [-a|-b]"
    :summary "foo some things"
    :help "foo some things"
    :contents (list *o/foo/a* *o/foo/b*)))

(defun run/foo (mode)
  (format t "Running foo in ~A mode.~%" mode))

;;;; Subcommand Bar -----------------------------------------------------------
(defparameter *o/bar/meow*
  (adopt:make-option 'meow :long "meow" :help "meow loudly after each step" :reduce (constantly t)))

(defparameter *ui/bar*
    :name "subex bar"
    :usage "bar [--meow] FILE..."
    :summary "bar some files"
    :help "bar some files"
    :contents (list *o/bar/meow*)))

(defun run/bar (paths meow?)
  (dolist (p paths)
    (format t "Bar-ing ~A.~%" p)
    (when meow?
      (write-line "meow."))))

;;;; Toplevel -----------------------------------------------------------------
(defun toplevel/foo (args)
  (multiple-value-bind (arguments options) (adopt:parse-options-or-exit *ui/foo* args)
    (unless (null arguments)
      (error "Foo does not take arguments, got ~S" arguments))
    (run/foo (gethash 'mode options))))

(defun toplevel/bar (args)
  (multiple-value-bind (arguments options) (adopt:parse-options-or-exit *ui/bar* args)
    (when (null arguments)
      (error "Bar requires arguments, got none."))
    (run/bar arguments (gethash 'meow options))))

(defun lookup-subcommand (string)
    ((null string) (values nil *ui/main*))
    ((string= string "foo") (values #'toplevel/foo *ui/foo*))
    ((string= string "bar") (values #'toplevel/bar *ui/bar*))
    (t (error "Unknown subcommand ~S" string))))

(defun toplevel ()
  (multiple-value-bind (arguments global-options)
      (handler-bind ((adopt:unrecognized-option 'adopt:treat-as-argument))
        (adopt:parse-options *ui/main*))
    (when (gethash 'version global-options)
      (write-line "1.0.0")
    (multiple-value-bind (subtoplevel ui) (lookup-subcommand (first arguments))
      (when (or (null subtoplevel)
                (gethash 'help global-options))
        (adopt:print-help-and-exit ui))
      (funcall subtoplevel (rest arguments)))))

Quicklisp newsApril 2021 Quicklisp dist update now available

· 161 days ago

 New projects

  • cluffer — Library providing a protocol for text-editor buffers. — FreeBSD, see file LICENSE.text
  • data-frame — Data frames for Common Lisp — MS-PL
  • dfio — Common Lisp library for reading data from text files (eg CSV). — MS-PL
  • herodotus — Wrapper around Yason JSON parser/encoder with convenience methods for CLOS — BSD
  • lisp-stat — A statistical computing environment for Common Lisp — MS-PL
  • numerical-utilities — Utilities for numerical programming — MS-PL
  • nyxt — Extensible web-browser in Common Lisp — BSD 3-Clause
  • shop3 — SHOP3 Git repository — Mozilla Public License
  • special-functions — Special functions in Common Lisp — MS-PL
  • tfeb-lisp-hax — TFEB.ORG Lisp hax — MIT

Updated projects: 3bmd, 3d-matrices, alexandria, algae, anypool, april, array-operations, async-process, audio-tag, bdef, bp, canonicalized-initargs, cffi, chanl, ci-utils, cl+ssl, cl-autowrap, cl-change-case, cl-clon, cl-collider, cl-colors2, cl-coveralls, cl-cxx, cl-data-structures, cl-digraph, cl-environments, cl-gamepad, cl-gserver, cl-heredoc, cl-json-pointer, cl-kraken, cl-las, cl-liballegro, cl-liballegro-nuklear, cl-markless, cl-marshal, cl-maxminddb, cl-mixed, cl-mock, cl-patterns, cl-rabbit, cl-ses4, cl-shlex, cl-ssh-keys, cl-str, cl-strings, cl-typesetting, cl-utils, cl-webkit, clack, clods-export, clog, closer-mop, common-lisp-jupyter, computable-reals, concrete-syntax-tree, consfigurator, cricket, croatoan, cubic-bezier, cytoscape-clj, damn-fast-priority-queue, dataloader, defconfig, definitions-systems, dexador, doplus, eazy-documentation, eclector, enhanced-defclass, femlisp, file-attributes, flac-metadata, freesound, functional-trees, gadgets, gendl, glacier, golden-utils, gtirb-capstone, gtirb-functions, gtwiwtg, harmony, helambdap, hunchenissr, hyperluminal-mem, imago, ironclad, json-mop, kekule-clj, lake, lass, lichat-protocol, linear-programming, linux-packaging, lisp-binary, listopia, magicl, maiden, markup, mcclim, mgl-pax, mito, multiposter, mutility, neural-classifier, nodgui, north, omer-count, origin, parachute, parsley, patchwork, perceptual-hashes, petalisp, plump, pngload, postmodern, qlot, quicklisp-stats, quilc, quri, random-uuid, sc-extensions, seedable-rng, sel, select, serapeum, shadow, shasht, slot-extra-options, sly, staple, static-dispatch, stripe, stumpwm, taglib, tfeb-lisp-tools, tfm, trivia, trivial-features, trivial-timer, ttt, umbra, umlisp, utilities.print-items, validate-list, vgplot, with-user-abort, zippy.

Removed projects: its

To get this update, use (ql:update-dist "quicklisp"). Enjoy!

Wimpie NortjeA list of Common Lisp command line argument parsers.

· 162 days ago

I was searching for a command line option parser that can handle git-style sub-commands and found a whole bunch of libraries. It appears as if libraries on this topic proliferate more than usual.

I evaluated them only to the point where I could decide to skip it or give it a cursory test. The information I gathered is summarised below.

If you only need the usual flag and option processing, i.e. not sub-commands, then I would suggest unix-opts. It appears to be the accepted standard and is actively maintained. It is also suggested by both Awesome Common Lisp and the State of the Common Lisp Ecosystem Survey 2020.

If your needs are very complex or specific you can investigate clon, utility-arguments or ace.flag.

For basic flags and options with sub-commands, there are a few libraries that explicitly support sub-command processing but you should be able to make it work with many of the other options and a bit of additional code.

Name Print help Native sub-commands Notes
ace.flag ? ? Not in QL.
adopt Yes No Can generate man files.
apply-argv No No Does not handle -xyz as three flags.
cl-just-getopt-parser No No Easy to use.
cl-cli Yes Yes  
cl-argparse Yes Yes  
cli-parser No No Does not handle free arguments, not in QL.
clon ? Yes Very complex, most feature rich.
command-line-arguments ? ? Not well documented.
getopt No No Does not handle -xyz as three flags, not well documented.
parse-args No No Not in QL
utility-arguments ? ? Complex to set up
unix-options Yes No Easy to use.
unix-opts Yes No The standard recommendation.

For older items, see the Planet Lisp Archives.

Last updated: 2021-09-23 15:10