28 Feb 2021

feedPlanet Lisp

Quicklisp news: February 2021 Quicklisp dist update now available

New projects:

Updated projects: algae, april, async-process, black-tie, cepl, cl+ssl, cl-ana, cl-async, cl-change-case, cl-coveralls, cl-data-structures, cl-dbi, cl-fxml, cl-grip, cl-gserver, cl-html-readme, cl-ipfs-api2, cl-kraken, cl-liballegro-nuklear, cl-libusb, cl-patterns, cl-pdf, cl-prevalence, cl-reexport, cl-shlex, cl-smtp, cl-string-generator, cl-threadpool, cl-typesetting, cl-unicode, cl-utils, cl-webkit, cl-yesql, clog, closer-mop, clsql, cmd, common-lisp-jupyter, core, cover, croatoan, datum-comments, defenum, dexador, easy-audio, eclector, fast-websocket, feeder, file-select, flare, float-features, freebsd-sysctl, functional-trees, fxml, geco, gendl, gtirb-capstone, gtirb-functions, gtwiwtg, harmony, hu.dwim.bluez, hu.dwim.common-lisp, hu.dwim.defclass-star, hu.dwim.logger, hu.dwim.quasi-quote, hu.dwim.reiterate, hu.dwim.sdl, hu.dwim.walker, hu.dwim.zlib, hunchenissr, iterate, jingoh, lass, lichat-protocol, linear-programming, lisp-chat, lmdb, magicl, maiden, mailgun, markdown.cl, mcclim, mgl-pax, mito, monomyth, named-read-macros, nodgui, num-utils, numcl, open-location-code, origin, orizuru-orm, osicat, periods, petalisp, plump-sexp, portal, py4cl, py4cl2, qlot, quri, read-as-string, repl-utilities, rpcq, rutils, s-sysdeps, sel, select, serapeum, shared-preferences, sly, spinneret, studio-client, stumpwm, ten, trivia, trivial-clipboard, trivial-features, ttt, uax-15, ucons, umlisp, uncursed, utm-ups, with-contexts, zacl, zippy.

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

28 Feb 2021 10:36pm GMT

24 Feb 2021

feedPlanet Lisp

Eric Timmons: Static Executables with SBCL v2

It's taken me much longer than I hoped, but I finally have a second version of my patches to build static executables tested and ready to go! This set of patches vastly improves upon the first by reducing the amount of compilation needed at the cost of sacrificing a little purity. Additionally I have created a system that automates the process of building a static executable, along with other release related tasks.

At a Glance

What's New?

If you need a refresher about what static executables are or what use cases they're good for, see my previous post on this topic.

With my previous patch, the only way you could create a static executable was to perform the following steps:

  1. Determine the foreign symbols needed by your code. The easiest way to do this is to compile all your Lisp code and then dump the information from the image.
  2. From that list of foreign symbols, create a C file that contains fills an array with references to those symbols.
  3. Recompile the SBCL core and runtime with this new file, additionally disabling libdl support and linking against your foreign libraries.
  4. (Re)compile all your Lisp code with the new runtime (if you made an image in step 1 it will not be compatible with the new runtime due to feature and build ID mismatches).
  5. Dump the executable.

In the most general case, this involved compiling your entire Lisp image twice. After some #lisp discussions, I realized there was a better way of doing this. While the previous process still works, the new recommended process now looks like:

  1. Build the image you would like to make into a static executable and save it.
  2. Dump the foreign symbol info from this image and write the C file that SBCL can use to prelink itself.
  3. Compile that C file and link it into an existing sbcl.o file to make a new runtime. sbcl.o is the SBCL runtime in object form, created when building with the :sb-linkable-runtime feature.
  4. Load the image from step 1 into your new runtime. It will be compatible because the build ID and feature set are the same!
  5. Dump your now static executable.

This new process can significantly reduce the amount of time needed to make an executable. Plus it lets you take more advantage of image based development. It's fairly trivial to build an image exactly like you want, dump it, and then pair it with a custom static runtime to make a static executable.

There were two primary challenges that needed to be overcome for this version of the patch set.

First, the SBCL core had to be made robust to every libdl function uncondtionally returning an error. Since we want the feature set to remain constant we can't recompile the runtime with #-os-provides-dlopen. Instead, we take advantage of the fact that Musl libc lets you link static executables against libdl, but all those functions are noops. This is the "purity" sacrifice I alluded to above.

Second, since we are reusing a image, the prelink info table (the generated C file) needed to order the symbols exactly as the image expects them to be ordered. The tricky bit here is that some libraries (like cl-plus-ssl) add symbols to the linkage table that will always be undefined. cl-plus-ssl does this in order to support a wide range of openssl versions. The previous patch set unconditionally filtered out undefined symbols, which horribly broke things in the new approach.

More Documentation

As before, after applying the patch you'll find a README.static-executable file in the root of the repo. You'll also find a Dockerfile and an example of how to use it in the README.static-executable.

You can also check out the tests and documentation in the asdf-release-ops system.

Known Issues

The issue is how they maintained backwards compatibility. Every time related symbol still exists and implements everything on top of the 32-bit time interface. However, if you include the standard header file where the symbol is defined or you look up the symbol via dlsym you actually get a pointer to the 64-bit time version of the symbol. We can't use dlsym (it doesn't work in static executables). And the generated C file doesn't include any headers.

This could be fixed if someone is motiviated enough to create/find a complete, easy to use map between libc symbols and the headers that define them and integrate it into the prelink info generator.

Next Steps

  1. I would love to get feedback on this approach and any ideas on how to improve it! Please drop me a line (etimmons on Freenode or daewok on Github/Gitlab) if you have suggestions.

  2. I've already incorporated static executables into CLPM and will be distributing them starting with v0.4.0! I'm going to continue rolling out static executables in my other projects.

  3. Pieces of the patch set are now solid enough that I think they can be submitted for upstream consideration. I'll start sending them after the current 2.1.2 freeze.

24 Feb 2021 12:50pm GMT

23 Feb 2021

feedPlanet Lisp

Max-Gerd Retzlaff: "Curl/Wget for uLisp"
Or: An HTTP(s) get/post/put function for uLisp

Oh, I forgot to continue posting… I just published a quite comprehensive HTTP function supporting put, post, get, auth, HTTP and HTTPS, and more for uLisp at ulisp-esp-m5stack.

Activate #define enable_http and #define enable_http_keywords to get it; the keywords used by the http function are to be enabled separately as they might be used more general and not just by this function.

Note that you need to connect to the internet first. Usually with WIFI-CONNECT.

Here is the full documentation with example calls:

   http url &key verbose
                 (https t)
                 (user default_username)
                 (password default_password)
                 (method :get)
     => result-string

Arguments and values:
   verbose---t, or nil (the default); affects also debug output of the argument decoding itself and should be put in first position in a call for full effect.

   https---t (the default), nil, or a certificate as string; uses default certificate in C string root_ca if true; url needs to fit: "http://..." for true and and "https://..." for false.

   auth---t, or nil (the default).

   user---a string, or nil (the default); uses default value in C string default_username if nil; only used if :auth t.

   password---a string, or nil (the default); uses default value in C string default_password if nil; only used if :auth t.

   accept---nil (the default), or a string.

   content-type---nil (the default), or a string.

   method---:get (the default), :put, or :post.

   data---nil (the default), or a string; only necessary in case of :method :put or :method :post; error for :method :get.

   ;; HTTP GET:
   (http "" :https nil)
   ;; HTTP PUT:
   (http ""
         :https nil
         :accept "application/n-quads"
         :content-type "application/n-quads"
         :auth t :user "foo" :password "bar"
         :method :put
         :data (format nil "<http://example.com/button> <http://example.com/pressed> \"~a\" .~%"

It can be tested with an minimal HTTP server simulation using bash and netcat:

while true; do echo -e "HTTP/1.1 200 OK\n\n $(date)" | nc -l -p 2342 -q 1; done

(To test with HTTPS in a similar fashion you can use openssl s_server, as explained, for example, in the article Create a simple HTTPS server with OPENSSL S_SERVER by Joris Visscher on July 22, 2015, but then you need to use certificates.)

See also Again more features for uLisp on M5Stack (ESP32):
time via NTP, lispstring without escaping and more space
, More features for uLisp on M5Stack (ESP32):
flash support, muting of the speaker and backlight control
and uLisp on M5Stack (ESP32).

Read the whole article.

23 Feb 2021 11:37am GMT

16 Feb 2021

feedPlanet Lisp

Max-Gerd Retzlaff: Again more features for uLisp on M5Stack (ESP32):
time via NTP, lispstring without escaping and more space

I just pushed three small things to ulisp-esp-m5stack: Get time via NTP, add optional escape parameter to function lispstring, increased WORKSPACESIZE and SYMBOLTABLESIZE for M5Stack.

Getting time via NTP

Enable #define enable_ntptime to get time via NTP. New functions INIT-NTP and GET-TIME. Note that you need to connect to the internet first. Usually with WIFI-CONNECT.

Syntax: INIT-NTP -> nil

Initializes and configures NTP.

Syntax: GET-TIME -> timestamp

Returns a timestamp in the format of xsd:dateTime.

Add optional escape parameter to function lispstring

I have changed the function lispstring to have an optional escape parameter to switch off the default behavior of handling the backslash escape character. The default behavior is not changed.

The C function lispstring takes a C char* string and return a uLisp string object. When parsing data in the n-triples format retrieved via HTTP I noticed that the data got modified already by lispstring which broke my parser implemented in uLisp.

As lispstring might be used in other contexts that expect this behavior, I just added the option to switch the un-escaping off.


The M5Stack ESP32 has 320 kB of usable DRAM in total. Although with a lot of restrictions (see next section),

I increased WORKSPACESIZE to 9000 cells, which equals 72,000 bytes, and SYMBOLTABLESIZE to 2048 bytes. These sizes seem to work still safely even with bigger applications and a lot of consing.

Warning: You cannot load images created with different settings!

The SRAM of the M5Stack ESP32

In total the M5Stack ESP32 comes with 520 kB of SRAM. The catch is that the ESP32 is based on the Harvard architecture and 192 kB is in the SRAM0 block intended(!) for instructions (IRAM). There is another 128 kB block in block SRAM1 which can be used either for instructions or data (DRAM). The third block SRAM2 has got a size of 200 kB and is for data only. But 8 kB of SRAM2 is lost for ROM mappings.

The ESP-IDF and thus also the Arduino environment use only SRAM0 for instructions and SRAM1 and SRAM2 for data, which is fine for uLisp as it is an interpreter and therefore more RAM for data is perfect. SRAM0 will just hold the machine code of the uLisp implementation but no code written in the language uLisp.

Of the remaining 320 kB another 54 kB will be dedicated for Bluetooth if Bluetooth is enabled in ESP-IDF (which it is by default, #define CONFIG_BT_RESERVE_DRAM 0xdb5c) in the SRAM2 block. And if trace memory is enabled, another 32 kB of SRAM1 are reserved (by default it is disabled, #define CONFIG_TRACEMEM_RESERVE_DRAM 0x0).

So, by default with Bluetooth enabled and trace memory disabled, 266 kB are left. At the bottom of SRAM2 right after the 62 kB used for Bluetooth and ROM are the application's data and BSS segments. Sadly, at around the border between SRAM1 and SRAM2 there seem to be two small reserved regions again of a bit more the 1 kB each, limiting statically allocated memory.

Thus, the "shared data RAM" segment dram0_0_seg in the linker script memory layout is configured to have a default length of 0x2c200&nbsp-; CONFIG_BT_RESERVE_DRAM. That is, 176.5 kB (= 180,736 bytes) without Bluetooth and 121.66 kB (= 124,580 bytes) with Bluetooth enabled.

But actually I have already written more than I have intended for this blog post and the rest of my notes, calculations and experiments will have to wait for a future article. For now, I just increased the size of the statically allocated uLisp workspace to make more use of the available memory of the ESP32 in the M5Stack.

See also More features for uLisp on M5Stack (ESP32):
flash support, muting of the speaker and backlight control
and uLisp on M5Stack (ESP32).


Espressif Systems, ESP32 Technical Reference Manual, Shanghai, 2020, section 2.3.2 Embedded Memory.

Read the whole article.

16 Feb 2021 7:41pm GMT

Tycho Garen : Programming in the Common Lisp Ecosystem

I've been writing more and more Common Lips recently and while I reflected a bunch on the experience in a recent post that I recently followed up on .

Why Ecosystems Matter

Most of my thinking and analysis of CL comes down to the ecosystem: the language has some really compelling (and fun!) features, so the question really comes down to the ecosystem. There are two main reasons to care about ecosystems in programming languages:

  • a vibrant ecosystem cuts down the time that an individual developer or team has to spend doing infrastructural work, to get started. Ecosystems provide everything from libraries for common tasks as well as conventions and established patterns for the big fundamental application choices, not to mention things like easily discoverable answers to common problems.

    The more time between "I have an idea" to "I have running (proof-of-concept quality) code running," matters so much. Everything is possible to a point, but the more friction between "idea" and "working prototype" can be a big problem.

  • a bigger and more vibrant ecosystem makes it more tenable for companies/sponsors (of all sizes) to choose to use Common Lisp for various projects, and there's a little bit of a chicken and egg problem here, admittedly. Companies and sponsors want to be confidence that they'll be able to efficiently replace engineers if needed, integrate or lisp components into larger ecosystems, or be able to get support problems. These are all kind of intangible (and reasonable!) and the larger and more vibrant the ecosystem the less risk there is.

    In many ways, recent developments in technology more broadly make lisp slightly more viable, as a result of making it easier to build applications that use multiple languages and tools. Things like microservices, better generic deployment orchestration tools, greater adoption of IDLs (including swagger, thrift and GRPC,) all make language choice less monolithic at the organization level.

Great Things

I've really enjoyed working with a few projects and tools. I'll probably write more about these individually in the near future, but in brief:

  • chanl provides. As a current/recovering Go programmer, this library is very familiar and great to have. In some ways, the API provides a bit more introspection, and flexibility that I've always wanted in Go.
  • lake is a buildsystem tool, in the tradition of make, but with a few additional great features, like target namespacing, a clear definition between "file targets" and "task targets," as well as support for SSH operations, which makes it a reasonable replacement for things like fabric, and other basic deployment tools.
  • cl-docutils provides the basis for a document processing system. I'm particularly partial because I've been using the python (reference) implementation for years, but the implementation is really quite good and quite easy to extend.
  • roswell is really great for getting started with CL, and also for making it possible to test library code against different implementations and versions of the language. I'm a touch iffy on using it to install packages into it's own directory, but it's pretty great.
  • ASDF is the "buildsystem" component of CL, comparable to setuptools in python, and it (particularly the latest versions,) is really great. I like the ability to produce binaries directly from asdf, and the "package-inferred" is a great addition (basically, giving python-style automatic package discovery.)
  • There's a full Apache Thrift implementation. While I'm not presently working on anything that would require a legit RPC protocol, being able to integrate CL components into larger ecosystem, having the option is useful.
  • Hunchensocket adds websockets! Web sockets are a weird little corner of any stack, but it's nice to be able to have the option of being able to do this kind of programming. Also CL seems like a really good platform to do
  • make-hash makes constructing hash tables easier, which is sort of needlessly gawky otherwise.
  • ceramic provides bridges between CL and Electron for delivering desktop applications based on web technologies in CL.

I kept thinking that there wouldn't be good examples of various things, (there's a Kafka driver! there's support for various other Apache ecosystem components,) but there are, and that's great. There's gaps, of course, but fewer, I think, than you'd expect.

The Dark Underbelly

The biggest problem in CL is probably discoverability: lots of folks are building great tools and it's hard to really know about the projects.

I thought about phrasing this as a kind of list of things that would be good for supporting bounties or something of the like. Also if I've missed something, please let me know! I've tried to look for a lot of things, but discovery is hard.


  • rove doesn't seem to work when multi-threaded results effectively. It's listed in the readme, but I was able to write really trivial tests that crashed the test harness.
  • Chanl would be super lovely with some kind of concept of cancellation (like contexts in Go,) and while it's nice to have a bit more thread introspection, given that the threads are somewhat heavier weight, being able to avoid resource leaks seems like a good plan.
  • There doesn't seem to be any library capable of producing YAML formated data. I don't have a specific need, but it'd be nice.
  • it would be nice to have some way of configuring the quicklisp client to be able to prefer quicklisp (stable) but also using ultralisp (or another source) if that's available.
  • Putting the capacity in asdf to produce binaries easily is great, and the only thing missing from buildapp/cl-launch is multi-entry binaries. That'd be swell. It might also be easier as an alternative to have support for some git-style sub-commands in a commandline parser (which doesn't easily exist at the moment'), but one-command-per-binary, seems difficult to manage.
  • there are no available implementations of a multi-reader single-writer mutex, which seems like an oversite, and yet, here we are.

Bigger Projects

  • There are no encoders/decoders for data formats like Apache Parquet, and the protocol buffers implementation don't support proto3. Neither of these are particular deal breakers, but having good tools dealing with common developments, lowers to cost and risk of using CL in more applications.
  • No support for http/2 and therefore gRPC. Having the ability to write software in CL with the knowledge that it'll be able to integrate with other components, is good for the ecosystem.
  • There is no great modern MongoDB driver. There were a couple of early implementations, but there are important changes to the MongoDB protocol. A clearer interface for producing BSON might be useful too.
  • I've looked for libraries and tools to integrate and manage aspects of things like systemd, docker, and k8s. k8s seems easiest to close, as things like cube can be generated from updated swagger definitions, but there's less for the others.
  • Application delievery remains a bit of an open. I'm particularly interested in being able to produce binaries that target other platforms/systems (cross compilation,) but there are a class of problems related to being able to ship tools once built.
  • I'm eagerly waiting and concerned about the plight of the current implementations around the move of ARM to Darwin, in the intermediate term. My sense is that the transition won't be super difficult, but it seems like a thing.

16 Feb 2021 12:00am GMT

15 Feb 2021

feedPlanet Lisp

Max-Gerd Retzlaff: More features for uLisp on M5Stack (ESP32):
flash support, muting of the speaker and backlight control

I finished the IoT sensor device prototype and shipped it last Thursday. It just has a stub bootstrap system in the flash via uLisp's Lisp Library and downloads the actual application in a second boot phase via HTTPS. More on that later.

To make it happen I've added a bunch of things to ulisp-esp-m5stack: flash support, fixes for some quirks of the M5Stack, time via NTP, an HTTP function supporting methods PUT, POST, GET, Auth, HTTP and HTTP, temperature sensors via one wire, and more. I plan to publish all these features in the next days.

Today you get: flash support, muting of the builtin speaker and control of the LED backlight of the builtin display.

Read the whole article.

15 Feb 2021 9:36pm GMT

14 Feb 2021

feedPlanet Lisp

Quicklisp news: Newer Quicklisp client available

I had to revert the change that allows slashes in dist names for Ultralisp. If your Quicklisp directory has a lot of files and subdirectories (which is normal), the wild-inferiors file search for dist info is unacceptably slow.

You can get an updated client with the feature reverted with (ql:update-client).

14 Feb 2021 1:59am GMT

11 Feb 2021

feedPlanet Lisp

Quicklisp news: New Quicklisp client available

I've just published a new version of the Quicklisp client. You can get it with (ql:update-client).

This version updates the fallback ASDF from 2.26 to 3.2.1. (This will not have any effect on any implementation except CLISP, which does not come with ASDF of any version.)

It also includes support for dists with slashes in the name, as published by Ultralisp.

Thanks to those who contributed pull requests incorporated in this update.

11 Feb 2021 11:06pm GMT

08 Feb 2021

feedPlanet Lisp

Nicolas Hafner: Setting Up Camp - February Kandria Update

I hope you've all started well into the new year! We're well into production now, with the vertical slice slowly taking shape. Much of the work in January has been on concept and background work, which is now done, so we are moving forward on the implementation of the new features, assets, and writing. This entry will have a lot of pictures and videos to gander at, so be warned!

The vertical slice will include three areas - the central camp, or hub location, the first underground area, and the desert ruins. We're now mostly done implementing the central camp. Doing so was a lot of work, since it requires a lot of unique assets. It still requires a good amount of polish before it can be called well done, but for the vertical slice I think we're good at the point we are now.

camp-1 camp-3

The camp is where all the main cast are (Fi, Jack, Catherine, and Alex), and where you'll return to after most missions. As such, it's important that it looks nice, since this is where you'll spend a lot of your time. It also has to look believable and reasonable for the cast to try and live here, so we spent a good amount of time thinking about what buildings there would be, what purpose they should fulfil, and so forth.

We also spent a good deal of time figuring out the visual look. Since Kandria is set quite far into the future, with that future also having undergone a calamity, the buildings both have to look suitably modern for a future society to have built, but at the same time ruined and destroyed, to fit the calamity event.

camp-2 camp-4

I also finished the character redesign for Fi. Her previous design no longer really fit with her current character, so I really wanted to get that done.

fi-draft fi

On the gameplay side the movement AI has been revised to be able to deal with far more complicated scenarios. Characters can now follow you along, move to various points on the map independently, or lead the player to a destination.

Quests now also automatically track your time to completion, which allows us both to do some nice tracking for score and speedrun purposes, but also to implement a 'race' quest. We have a few ideas on those, and it should serve as a nice challenge to try and traverse the various areas as quickly as possible.

We're also thinking of setting up leaderboards or replays for this, but that's gonna have to wait until after the vertical slice.

For look and feel there's also been a bunch of changes. First, there's now a dedicated particle system for effects like explosions, sparks, and so forth. Adding such details really enhances the feel of the combat, and gives a nice, crunchy, oomph to your actions. I still have a few more ideas for additional effects to pile on top, and I'll see that I can get to those in due time.


Also on the combat side, there's now a quick-use menu so you can access your healing items and so forth easily during combat. It even has a nice slow-mo effect!

Since we're not making a procedural game, we do have to have a way of gating off far areas in a way that feels at least somewhat natural. To do this I've implemented a shader effect that renders a sandstorm on top of everything. The strength of the effect can be fine-tuned, so we could also use it for certain setpieces or events.

The effect looks a lot better in-game. Video compression does not take kindly to very noisy and detailed effects like this. Having the sand howl around really adds a lot to the feel of the game. In a similar vein, there's also grass and other foliage that can be placed now, which reacts to the wind and characters stepping on it. You can see that in action in this quick run-down of the camp area:

There's a bunch of other things we can't show off quite yet, especially a bunch of excellent animations by Fred. I haven't had the time to integrate all of those yet!

We've also been thinking more about how to handle the marketing side of things. I'm now doing a weekly screenshotsaturday thing on Twitter, and semi-regularly post quick progress gifs and images as well. Give me a follow if you haven't yet!

Then I took advantage of Rami Ismail's excellent consulting service and had a talk with him about what we should do to improve the first impressions for Kandria and how to handle the general strategy. He gave some really excellent advice, though I wish I had had more time to ask other questions, too! I'll probably schedule a consultancy hour with him later this year to catch up with all of that.

Anyway, I think a lot of the advice he gave us isn't necessarily specific to Kandria, so I thought it would be good to share it here, in case you're a fellow developer, or just interested in marketing in general:

And that's about what we managed to discuss in the 20 minutes we had. As mentioned, I'll probably schedule another consultancy later in the year. I'll be sure to let you know how it went!

Alright, I've run my mouth for long enough now, here's some words from Tim about his experience for January:

It's been a documentation-heavy month for me: designing the vertical slice quests on paper (which will become the first act of the narrative), making some tweaks to the characters and plots to fit the game's pillars, and also tweaking the press kit and marketing copy from Rami's feedback.

The last two weeks I've also started implementing the first quest, reminding myself how to use the scripting language and editor (it's amazing how much you forget after a couple of weeks away from it). This has also involved familiarising myself with the "proper" quest structure, using the hierarchy of quest > task > trigger (for the demo quest it was more like task > trigger, trigger, trigger, etc. you get the idea). What's been most fun though is getting into the headspace for Jack and Catherine, writing their initial dialogues, and threading in some player choice. Catherine is quickly becoming my favourite character.

It's also been great to see the level design and art coming along - Nick's sketched layouts, and now the pixel art for the ruined buildings which he and Fred have been working on. Oh, and seeing the AI in action, with Catherine bounding along after The Stranger blew my mind.

Well, that's about it for this month. It's been exciting to finally see a change in the visuals, and I'm excited to start tackling the first underground area. I see a lot more pixel work ahead of us...

Anyway, in the meantime until the next monthly update, do consider checking out the mailing list if you want more in-depth, weekly updates on things. We cover a lot of stuff there that never makes it into the monthlies, too! If you want to get involved in discussions and feedback around the game, hop onto the discord. We're slowly building a community of fans there, and are trying to post more actively about the process. For a more casual thing, there's also my twitter with plenty of gifs and images. Finally, please do wishlist Kandria on Steam! It might seem like it isn't much, but it really does help out a lot!

Thanks for reading, and see you next time!

08 Feb 2021 3:27pm GMT

Vsevolod Dyomkin: "Programming Algorithms in Lisp" Is Out!

The updated version of my book "Programming Algorithms" has been released by Apress recently. It has undergone a number of changes that I want to elaborate on in this post.

But first, I'd like to thank all the people who contributed to the book or supported my work on it in other ways. It was an honor for me to be invited to Apress as "Practical Common Lisp" published by them a decade ago was my one-way ticket to the wonderful world of Lisp. Writing "Programming Algorithms" was, in a way, an attempt to give something back. Also, I was very curious to see how the cooperation with the publisher would go. And I can say that they have done a very professional job and helped significantly improve the book through the review process. That 5-10% change that is contributed by the editors, although it may seem insignificant, is very important to bring any book to the high standard that allows not to annoy many people. Unfortunately, I am not a person who can produce a flawless result at once, so helping with correcting those flaws is very valuable. Part of gratitude for that also, surely, goes to many of the readers who have sent their suggestions.

I was very pleased that Michał "phoe" Herda has agreed to become the technical reviewer. He has found a number of bugs and suggested lots of improvements, of which I could implement, maybe, just a third. Perhaps, the rest will go into the second edition :)

Now, let's speak about some of those additions to Programming Algorithms in Lisp.

Curious Fixes

First of all, all the executable code from the book was published in a github repo (and also republished to the oficial Apress repo). As suggested by Michał, I have added automated tests to ensure (for now, partially, but we plan to make the test suite all-encompassing) that everything compiles and runs correctly. Needless to say that some typos and other issues were found in the process. Especially, connected with handling different corner cases. So, if you have trouble running some code from the book, you can use the github version. Funny enough, I got into a similar situation recently, when I tried to utilize the dynamic programming example in writing a small tool for aligning outputs of different ASR systems and found a bug in it. The bug was is in the matrix initialization code:

- (dotimes (k (1+ (length s1))) (setf (aref ld k 0) 0))
- (dotimes (k (1+ (length s2))) (setf (aref ld 0 k) 0)))
+ (dotimes (k (1+ (length s1))) (setf (aref ld k 0) k))
+ (dotimes (k (1+ (length s2))) (setf (aref ld 0 k) k)))

Another important fix that originated from the review process touched not only the book but also the implementation of the slice function in RUTILS! It turned out that I was naively assuming that displaced arrays will automatically recursively point into the original array, and thus, inadvertently, created a possibility for O(n) slice performance instead of O(1). It explains the strange performance of array sorting algorithms at the end of Chapter 5. After fixing slice, the measurements started to perfectly resemble the theoretical expectations! And, also the performance has improved an order of magnitude :D

CL-USER> (let ((vec (random-vec 10000)))
(print-sort-timings "Insertion " 'insertion-sort vec)
(print-sort-timings "Quick" 'quicksort vec)
(print-sort-timings "Prod" 'prod-sort vec))
= Insertion sort of random vector (length=10000) =
Evaluation took:
0.632 seconds of real time
= Insertion sort of sorted vector (length=10000) =
Evaluation took:
0.000 seconds of real time
= Insertion sort of reverse sorted vector (length=10000) =
Evaluation took:
1.300 seconds of real time
= Quicksort of random vector (length=10000) =
Evaluation took:
0.039 seconds of real time
= Quicksort of sorted vector (length=10000) =
Evaluation took:
1.328 seconds of real time
= Quicksort of reverse sorted vector (length=10000) =
Evaluation took:
1.128 seconds of real time
= Prodsort of random vector (length=10000) =
Evaluation took:
0.011 seconds of real time
= Prodsort of sorted vector (length=10000) =
Evaluation took:
0.011 seconds of real time
= Prodsort of reverse sorted vector (length=10000) =
Evaluation took:
0.021 seconds of real time

Also, there were some missing or excess closing parens in a few code blocks. This, probably, resulted from incorrectly copying the code from the REPL after finishing experimenting with it. :)

New Additions

I have also added more code to complete the full picture, so to say, in several parts where it was lacking, from the reviewers' point of view. Most new additions went into expanding "In Action" sections where it was possible. Still, unfortunately, some parts remain on the level of general explanation of the solution as it was not possible to include whole libraries of code into the book. You can see a couple of snippets below:

Binary Search in Action: a Fast Specialized In-Memory DB

We can outline the operation of such a datastore with the following key structures and functions.

A dictionary *dict* will be used to map words to numeric codes. (We'll discuss hash-tables that are employed for such dictionaries several chapters later. For now, it will be sufficient to say that we can get the index of a word in our dictionary with (rtl:? *dict* word)). The number of entries in the dictionary will be around 1 million.

All the ngrams will be stored alphabetically sorted in 2-gigabyte files with the following naming scheme: ngram-rank-i.bin. rank is the ngram word count (we were specifically using ngrams of ranks from 1 to 5) and i is the sequence number of the file. The contents of the files will constitute the alternating ngram indices and their frequencies. The index for each ngram will be a vector of 32-bit integers with the length equal to the rank of an ngram. Each element of this vector will represent the index of the word in *dict*. The frequency will also be a 32-bit integer.

All these files will be read into memory. As the structure of the file is regular - each ngram corresponds to a block of (1+ rank) 32-bit integers - it can be treated as a large vector.

For each file, we know the codes of the first and last ngrams. Based on this, the top-level index will be created to facilitate efficiently locating the file that contains a particular ngram.

Next, binary search will be performed directly on the contents of the selected file. The only difference with regular binary search is that the comparisons need to be performed rank times: for each 32-bit code.

A simplified version of the main function get-freq intended to retrieve the ngram frequency for ranks 2-5 will look something like this:

(defun get-freq (ngram)
(rt:with ((rank (length ngram))
(codes (ngram-codes ngram))
(vec index found?
(bin-search codes
(ngrams-vec rank codes)
:less 'codes<
:test 'ngram=)))
(if found?
(aref vec rank)


(defun ngram-codes (ngram)
(map-vec (lambda (word) (rtl:? *dict* word))

(defun ngrams-vec (rank codes)
(loop :for ((codes1 codes2) ngrams-vec) :across *ngrams-index*
:when (and (<= (aref codes1 0) (aref codes 0))
(codes< codes codes2 :when= t))
:do (return ngrams-vec)))

(defun codes< (codes1 codes2 &key when=)
(dotimes (i (length codes1)
;; this will be returned when all
;; corresponding elements of codes are equal
(cond ((< (aref codes1 i)
(aref codes2 i))
(return t))
((> (aref codes1 i)
(aref codes2 i))
(return nil)))))

(defun ngram= (block1 block2)
(let ((rank (1- (length block1))))
(every '= (rtl:slice block1 0 rank)
(rtl:slice block2 0 rank)))

We assume that the *ngrams-index* array containing a pair of pairs of codes for the first and last ngram in the file and the ngrams data from the file itself was already initialized. This array should be sorted by the codes of the first ngram in the pair. A significant drawback of the original version of this program was that it took quite some time to read all the files (tens of gigabytes) from disk. During this operation, which measured in several dozens of minutes, the application was not responsive. This created a serious bottleneck in the system as a whole and complicated updates, as well as put normal operation at additional risk. The solution we utilized to counteract this issue was a common one for such cases: switching to lazy loading using the Unix mmap facility. With this approach, the bounding ngram codes for each file should be precalculated and stored as metadata, to initialize the *ngrams-index* before loading the data itself.

Pagerank MapReduce Explanation

;; this function will be executed by mapper workers
(defun pr1 (node n p &key (d 0.85))
(let ((pr (make-arrray n :initial-element 0))
(m (hash-table-count (node-children node))))
(rtl:dokv (j child (node-children node))
(setf (aref pr j) (* d (/ p m))))

(defun pagerank-mr (g &key (d 0.85) (repeat 100))
(rtl:with ((n (length (nodes g)))
(pr (make-arrray n :initial-element (/ 1 n))))
(loop :repeat repeat :do
(setf pr (map 'vector (lambda (x)
(- 1 (/ d n)))
(reduce 'vec+ (map 'vector (lambda (node p)
(pr1 node n p :d d))
(nodes g)

Here, we have used the standard Lisp map and reduce functions, but a map-reduce framework will provide replacement functions which, behind-the-scenes, will orchestrate parallel execution of the provided code. We will talk a bit more about map-reduce and see such a framework in the last chapter of this book.

One more thing to note is that the latter approach differs from the original version in that each mapper operates independently on an isolated version of the pr vector, and thus the execution of Pagerank on the subsequent nodes during a single iteration will see an older input value p. However, since the algorithm is stochastic and the order of calculations is not deterministic, this is acceptable: it may impact only the speed of convergence (and hence the number of iterations needed) but not the final result.

Other Significant Changes

My decision to heavily rely on syntactic utilities from my RUTILS library was a controversial one, from the start. And, surely, I understood it. But my motivation, in this regard, always was and still remains not self-promotion but a desire to present Lisp code so that it didn't seem cumbersome, old-fashioned, or cryptic (and, thankfully, the language provides all possibilities to tune its surface look to your preferences). However, as it bugged so many people, including the reviewers, for the new edition, we have come to a compromise to use all RUTILS code only qualified with the rtl prefix so that it was apparent. Besides, I have changed some of the minor purely convenience abbreviations to their standard counterparts (like returning funcall instead of call).

Finally, the change that I regret the most, but understand that it was inevitable, is the change of title and the new cover, which is in standard Apress style. However, they have preserved the Draco tree in the top right corner. And it's like a window through which you can glance at the original book :)

So, that is an update on the status of the book.

For those who were waiting for the Apress release to come out, it's your chance to get it. The price is quite affordable. Basically, the same as the one I asked for (individual shipping via post is a huge expense).

And for those who have already gotten the original version of the book, all the major changes and fixes are listed in the post. Please, take notice if you had any issues.

I hope the book turns out to be useful to the Lisp community and serves both Lisp old-timers and newcomers.

08 Feb 2021 10:48am GMT