New projects:

• audio-tag - tool to deal with audio tags. read and write - BSD-2-Clause License
• canonicalized-initargs - Provides a :canonicalize slot option accepting an initarg canonicalization function. - Unlicense
• cl-debug-print - A reader-macro for debug print - MIT
• cl-json-schema - Describe cl-json-schema here - Specify license here
• cl-ses4 - AWS SES email sender using Signature Version 4 of Amazon's API - Public Domain
• cl-telebot - Common Lisp Telegram Bot API - MIT
• consfigurator - Lisp declarative configuration management system - GPL-3+
• cricket - A library for generating and manipulating coherent noise - MIT
• cubic-bezier - A library for constructing and evaluating cubic Bézier curve paths. - MIT
• defconfig - A configuration system for user exposed variables - GPLv3
• enhanced-defclass - Provides a truly extensible version of DEFCLASS that can accurately control the expansion according to the metaclass and automatically detect the suitable metaclass by analyzing the DEFCLASS form. - Unlicense
• freesound - A client for Freesound.org. - MIT
• mnas-graph - Defines basic functions for creating a graph data structure and displaying it via graphviz. - GNU GENERAL PUBLIC LICENSE Version 3, 29 June 2007 or later
• mnas-hash-table - Defines some functions for working with hash tables. - GNU GENERAL PUBLIC LICENSE Version 3, 29 June 2007 or later
• nyaml - Native YAML Parser - MIT
• pvars - easily define persistent variables - MIT
• random-uuid - Create and parse RFC-4122 UUID version 4 identifiers. - MIT
• sanity-clause - Sanity clause is a data contract and validation library. - LGPLv3
• seedable-rng - A seedable random number generator. - MIT
• slot-extra-options - Extra options for slots using MOP. - LGPL-3.0-or-later
• tailrec - Guaranteed tail call optimization. - LLGPL
• tfeb-lisp-tools - TFEB.ORG Lisp tools - MIT

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

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

• The new patch set can be found on the static-executable-v2 branch of my SBCL fork or at https://www.timmons.dev/static/patches/sbcl/$VERSION/static-executable-support-v2.patch with a detached signature available at https://www.timmons.dev/static/patches/sbcl/$VERSION/static-executable-support-v2.patch.asc signed with GPG key 0x9ACF6934.
• You'll definitely want to build SBCL with the :sb-prelink-linkage-table feature (newly added by the patch). You'll probably also want the :sb-linkable-runtime feature (already exists, but the patch also enables it on arm/arm64).
• The new patch lets you build a static executable with less compilation of Lisp code.
• The asdf-release-ops system automates the process of building a static executable by tying it into ASDF.

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 :sb-prelink-linkage-table feature does not work on 32-bit ARM + Musl libc >= 1.2. Musl switched to 64-bit time under the hood while still mataining compatibility with everything compiled for 32-bit time.

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.

• The :sb-prelink-linkage-table works on Windows but causes test failures. The root issue is that mingw64 has implemented their own libm. Their trig functions are fast, but use inaccurate instructions (like FSIN) under the hood. When prelinking these inaccurate implementations are used instead of the more accurate ones (from msvcrt.dll ?) found when using dlsym to look up the symbol.

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

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:

Syntax:
   http url &key verbose
                 (https t)
                 auth
                 (user default_username)
                 (password default_password)
                 accept
                 content-type
                 (method :get)
                 data
     => result-string

Examples:
   ;; HTTP GET:
   (http "http://192.168.179.41:2342" :https nil)
 
   ;; HTTP PUT:
   (http "http://192.168.179.41:2342"
         :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\" .~%"
                           (get-time)))

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

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.

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.

Increased WORKSPACESIZE and SYMBOLTABLESIZEfor M5Stack

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).

References

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

Read the whole article.

16 Feb 2021 7:41pm GMT

16 Feb 2021 12:00am GMT

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

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

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

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.

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.

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.

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:

• Make sure to keep a consistent tone throughout your paragraph or trailer. This means that you want to avoid going back and forth between advertising game features or narrative elements, for instance. In Kandria's case we had a lot of back and forth in our press kit and steam page texts, which we've now gone over and revised to be more consistent.
• Marketing is as much about attracting as many people as possible as it is about pushing people away. You want to be as efficient as possible at advertising to your target group. This also means being as up-front as possible about what your game is and who it is for, so you immediately pull in the people that would care about it, and push away the people that would not.
• You need to figure out which part of your game best appeals to your core audience, and how you need to put it to make it attractive. Having an advertisement platform that gives you plenty of statistics and targeting features is tremendously helpful for this. Rami specifically suggested using short Facebook ads, since those can be targeted towards very specific groups. Do many small ads using different copy texts and trailers to see which work the best at attracting people to your Steam page.
• Always use a call to action at the end of your top of the funnel (exposure) marketing. In fact, don't just use one link, use one for every way people have to interact with your game, if you have several. For us in specific this means I'll now include a link to our mailing list, our discord, and our steam page in our material.
• Only use community/marketing platforms that you're actually comfortable with engaging with yourself. This means don't force yourself to make a Discord or whatever if you're not going to really engage with it. I'm fairly comfortable with where we are now, though I'm considering also branching out to imgur for more top of the funnel marketing. We'll see.
• Two years is plenty of time to get marketing going. Generally you want to really up the hype train about three months before release. The wishlist peak about one month before release should give you a rough idea of whether the game is going to be successful or not - 5-10k is good, 15-20k should be very good.
• Three weeks before release is when you want to start contacting press - write emails to people that have reviewed the games that inspired yours and seem to generally fit the niche you're targeting. Let them know you'll send a final build a week before release.
• Actually do that exactly a week before release. Ideally your game will be done and you won't fudge with it until after release.
• On the day before release, log onto gamespress.com and submit your game. Actual journalists don't tend to look there it seems, since they already get way more than enough mail, but third parties and independent people might!

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

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)
         0)))

where

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

(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
              when=)
    (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))))
    pr))

(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)
                                       pr)))))
    pr))

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