Planet Scheme

Wednesday, June 12, 2024

Idiomdrottning

Finding PGP keys

Here’s how I find PGP public keys. I have a zsh function that runs this, where “$1” means the email address I want to send to:

gpg --auto-key-locate local,wkd,keyserver --locate-keys "$1" ||
    curl -XGET https://api.protonmail.ch/pks/lookup\?op\=get\&search\=$(uenc "$1")|gpg --import

That second clause doesn’t get invoked very often; Proton users who don’t have their own domain, their keys are available over WKD, and some users who do have their own domain still have WKD set up, and some (all?) who don’t are still in Proton’s HPK keyserver. Maybe that covers all of them and there’s nothing left. I put it in the script before I knew about their keyserver, and got good mileage out of it early on. I’m never ever gonna get Proton myself and it’s so nice to just be able to normally email people who’re on there and step one to doing that is getting their keys.

This doesn’t find Autocrypt keys; that’s something I might wanna fix somehow, maybe introducing a notmuch query into the mix? I’d have to reindex with that header.

Now, local is checked first and that’s bad, don’t try that at home, kids. If I already have some old, stale key to them, that’s what’s gonna pop up first and end the search. But I’m such a ditz that I kept re-importing keys that I’ve already got until I introduced local as the first step.

The keyservers I currently check are these:

keyserver hkps://keys.openpgp.org
keyserver hkps://mail-api.proton.me
keyserver hkps://keys.mailvelope.com
keyserver hkps://keyserver.ubuntu.com
keyserver hkps://pgp.mit.edu

I’m not sure my own keys are in any of them, I might’ve submitted them at one time or another. I primarily rely on WKD or Autocrypt. The keyserver idea was pretty flawed compared to WKD, and then Autocrypt is a good workaround for email providers that don’t allow WKD. Which are pretty few, but Posteo does and anything that allows you to use your own domain.

by Idiomdrottning (sandra.snan@idiomdrottning.org) at Wednesday, June 12, 2024

Thursday, June 6, 2024

Idiomdrottning

Coding for yourself is OK

Re: Learning to be a programmer

I’ve made tons of driveby commits since pandemic started. 100 contributions in the last year just on GitHub and probably just as many on other repos.

So “even they can’t read programs written by others without 1000x effort” isn’t literally true.

I also… I think “programming for the household” is actually awesome. Automating our own lives, autonomously, not squeezing our lives into someone else’s automation.

When what we do can be extracted into reusable tools or libraries, that’s great. I’ve started 136 repos on idiomdrottning.org also since pandemic started. Programming for your own needs doesn’t have to end there.

There’s no shame in programming for yourself.

The other day I was pondering if egoism can be used for altruism and in hindsight, the answer’s closer than I would’ve guessed: in FOSS licensing and paying it forward.

by Idiomdrottning (sandra.snan@idiomdrottning.org) at Thursday, June 6, 2024

Monday, June 3, 2024

spritely.institute

Cirkoban: Sokoban meets cellular automata written in Scheme

Last week, we released a small puzzle game called Cirkoban. Cirkoban is the very first publicly accessible application developed by Spritely that features the Goblins distributed programming library running in web browsers. We bet big on Hoot, our Scheme-to-WebAssembly compiler, a little over a year ago in order to bring Goblins to the web. That bet is starting to pay off! In this post, we’ll talk in detail about how we made Cirkoban and how it showcases Spritely technology.

About Cirkoban

Cirkoban combines Sokoban block pushing with the Wireworld cellular automaton. It was made in 10 days for the Spring Lisp Game Jam 2024.

In Cirkoban, you play as an owl stuck in a secret, ethereal lab filled with strange circuitry. You must solve devious puzzles to ascend the stairs and reach the top floor. It has minimal controls (4 direction movement and an “undo” button) and contains 15 levels of increasing difficulty. Solving the puzzles requires precise movement, but you can travel back in time to undo mistakes. For an added challenge, there is a gem in each level that is harder to reach than the stairs to the next level.

Goals

While it is fun to make games, the real reason we made Cirkoban was to exercise Spritely technology and produce an appealing user-facing application under a tight deadline. We wanted to demonstrate the current state of Hoot, as well as the early progress made towards porting Goblins to the web. Games also have the tendency to stress language implementations and libraries since they require asynchronous event loops, perform a lot of math calculations and I/O, and need to refresh at 60Hz or so to appear smooth to the player.

I successfully used Hoot in the autumn edition of the Lisp Game Jam, when it was barely usable for such things. This time around, we were hoping that to spend very little time debugging Hoot issues and much more time making the game and testing out something new: Goblins!

Thanks to the work of Juli Sims, it is now possible to compile and run a subset of the Goblins library with Hoot. Specifically, we had a working port of the (goblins core) module that we wanted to incorporate into the architecture of the game. The port is not yet at the state where we can do networking, so instead we set out to demonstrate local actors and transactional rollback.

Design

If you’re a regular reader of our blog, then you know that Wireworld comes up often around here. It is our favorite cellular automaton because, with a few simple rules, you can build logic gates, diodes, and other components which can be composed into complicated circuitry. The simplicity of Wireworld has made it a compelling demo program for Hoot at various stages of its development.

Christine Lemmer-Webber thought it would be interesting to create a puzzle game where the levels contain broken circuits that need to be fixed by moving some puzzle pieces around. Sokoban was a natural starting point for such a game, and it also provided an opportunity to show off Goblins’ rollback feature. In Sokoban, if you push a block into a corner then you can’t push it anymore and thus may not be able to complete the puzzle. Games like Baba is You allow the player to undo previous moves when they get stuck. With the addition of a similar undo mechanic, we now had a way for a user to directly experience rollback as part of the gameplay.

Terminal Phase time-traveldemo

In the past, we have shown off rollback using the space shooter game Terminal Phase, a text-based game that runs in the player’s terminal. With Cirkoban, we now demonstrate that we have successfully ported this core feature to the web!

For the sake of fun gameplay, we decided to take some liberties with the Wireworld rules. For example, we wanted to condense common constructs which require many cells in Wireworld, such as electron-emitting generators and logic gates, into a single cell. This would help us keep the levels small and more readable, especially for the average player who isn’t already familiar with Wireworld, at the expense of more complicated code under the hood.

Development

To model the game state, we used Goblins actors. Every object in the game world is represented as an actor that responds to messages sent from other actors. Every time the player presses a key, the game either advances by a turn or rolls back to the state of the previous turn, in the case of the “undo” key. The game “client” then procsses the events of that turn, playing sound and visual effects as appropriate, and updates the visual representation of the level. The game state and rendering state are thus separated from one another.

Emacs with Cirkoban actor source code open

To edit the code, we used Emacs, naturally. I use paredit and rainbow-delimiters to efficiently edit Scheme, and the unsurpassed magit for working with our Git repository. A simple Makefile handles build automation and running a local web server for testing the game.

For graphics, we thought a low-resolution pixel art style with our own original art would work well. Using HTML5 canvas was an obvious choice to make rendering the game as simple as possible. WebGL/WebGPU are not currently viable options with Wasm GC, anyway. We chose to feature an owl as the player character because the Hoot mascot is an owl. Christine came up with the ethereal “technomancer” theme and created lots of amazing sprites in Libresprite.

Musical artist and Spritely community member EncryptedWhispers whipped up a background music track that fit our theme based on a very funny recording of Christine imitating a theremin. Juli and I made retro sound effects using the classic game jam tool sfxr.

Tiled map editor window with a Cirkoban level loaded

To design the levels, we used Tiled. We kept the map structure as simple as possible so that we could build levels quickly. There are only two layers in each map: A background tile layer for the static level tiles and an object layer for dynamic objects such as pushable blocks. Tiled’s native .tmx format uses XML, but we did not want to be in the business of fetching and parsing XML at runtime. Instead, we baked the levels into the Wasm binary by compiling Tiled map files to Scheme. The compiled levels use Scheme bytevector literals to densely pack only the essential map data needed at runtime. As levels were added, the change to the total binary size was nearly imperceptible. The compiled game code takes up much more space than all of the levels combined.

At the last minute I added some onscreen controls for touchscreens using Kenney assets so the game was playable on phones and tablets. The controls were shown or hidden based on the pointer CSS media query. When the pointer is fine (mouse), the onscreen controls are display: none; when coarse (touchscreen), they are shown. I used Inkscape to export just the directional pad and A button from Kenney’s combined SVG file, made some modifications to the resulting XML by hand to remove extraneous things, and then inlined the SVG into index.html. With the SVG inlined, I was able attach click handlers to individual components of the graphic, such as each button on the directional pad. I had no idea you could this before! After the deployment freeze of the jam rating period I made some additional improvements to how the game canvas is scaled on small phone screens.

I even had the time to sneak in some quality-of-life improvements. For instance, game progress is automatically saved to localStorage at the start of each level. We save the last completed level and the set of levels for which gems have been collected. This small feature became very important for testing as the level count grew, and players who played multiple sessions appreciated it.

Reflections

We’re a bit biased, but Hoot is actually pretty good now! We built Cirkoban using the latest unstable code in Hoot’s main branch, rather than the most recent 0.4.1 release. Even so, I only found one small problem during development and it was trivial to fix.

Now that Hoot is feeling quite stable, the lack of proper Scheme debug tools has become the most annoying developer experience issue. The current state of WebAssembly makes it hard for Hoot to do things like show a proper Scheme backtrace, but we need to see what we can do with the tools we have to improve the debugging story.

Relatedly, I also miss the REPL. Towards the end of the jam, compile times were about 20 seconds long. Every time I made a small tweak I had to recompile the entire program. Hoot is a whole-program, ahead-of-time, cross compiler that does a good job generating optimized binaries, but during development it would be nice to have a way to build incrementally like with native Guile. Generating Wasm from within Wasm is something we haven’t done yet, but Andy Wingo has thoughts about how to do it.

Finally, the Goblins port is going well! The (goblins core) module worked reliably and very little time was spent debugging issues. Juli has been making incredible progress porting Goblins to Hoot, and if the jam had been just a week or two later we might have even had vats, our asynchronous event loops, running on top of Hoot’s fibers asynchronous programming API. We could have also had true persistence that saved the game state exactly where you left off; players could take a break in the middle of a level and not have to start that level over when they returned. We are looking forward to having the full power of Goblins available in the browser in the coming months.

Reactions

Cirkoban received positive ratings and comments amongst the other jam participants, ranking second in the jam overall! We are simply thrilled with how the game turned out and the feedback we’ve received. We love shiny demos here, and the positive feedback is a good indicator that we should continue to make them!

by Dave Thompson (contact@spritely.institute) at Monday, June 3, 2024

Friday, May 31, 2024

GNU Guix

Source code archiving in Guix: new publication

We are glad to announce the publication of a new research paper entitled Source Code Archiving to the Rescue of Reproducible Deployment for the ACM Conference on Reproducibility and Replicability. The paper presents work that has been done since we started connecting Guix with the Software Heritage (SWH) archive five years ago:

The ability to verify research results and to experiment with methodologies are core tenets of science. As research results are increasingly the outcome of computational processes, software plays a central role. GNU Guix is a software deployment tool that supports reproducible software deployment, making it a foundation for computational research workflows. To achieve reproducibility, we must first ensure the source code of software packages Guix deploys remains available.

We describe our work connecting Guix with Software Heritage, the universal source code archive, making Guix the first free software distribution and tool backed by a stable archive. Our contribution is twofold: we explain the rationale and present the design and implementation we came up with; second, we report on the archival coverage for package source code with data collected over five years and discuss remaining challenges.

The ability to retrieve package source code is important for researchers who need to be able to replay scientific workflows, but it’s just as important for engineers and developers alike, who may also have good reasons to redeploy or to audit past package sets.

Support for source code archiving and recovery in Guix has improved a lot over the past five years, in particular with:

  • Support for recovering source code tarballs (tar.gz and similar files): this is made possible by Disarchive, written by Timothy Sample.

Diagram taken from the paper showing Disarchive tarball “disassembly” and “assembly”.

  • The ability to look up data by nar hash in the SWH archive (“nar” is the normalized archive format used by Nix and Guix), thanks to fellow SWH hackers. This, in turn, allows Guix to look up any version control checkout by content hash—Git, Subversion, Mercurial, you name it!
  • The monitoring of archival coverage with Timothy’s Preservation of Guix reports has allowed us to identify discrepancies in Guix, Disarchive, and/or SWH and to increase archival coverage.

Graph taken from the paper showing package source code archival coverage over time.

94% of the packages in a January 2024 snapshot of Guix are known to have their source code archived!

Check out the paper to learn more about the machinery at play and the current status.

by Ludovic Courtès, Timothy Sample, Simon Tournier, Stefano Zacchiroli at Friday, May 31, 2024

Monday, May 27, 2024

Andy Wingo

cps in hoot

Good morning good morning! Today I have another article on the Hoot Scheme-to-Wasm compiler, this time on Hoot’s use of the continuation-passing-style (CPS) transformation.

calls calls calls

So, just a bit of context to start out: Hoot is a Guile, Guile is a Scheme, Scheme is a Lisp, one with “proper tail calls”: function calls are either in tail position, syntactically, in which case they are tail calls, or they are not in tail position, in which they are non-tail calls. A non-tail call suspends the calling function, putting the rest of it (the continuation) on some sort of stack, and will resume when the callee returns. Because non-tail calls push their continuation on a stack, we can call them push calls.

(define (f)
  ;; A push call to g, binding its first return value.
  (define x (g))
  ;; A tail call to h.
  (h x))

Usually the problem in implementing Scheme on other language run-times comes in tail calls, but WebAssembly supports them natively (except on JSC / Safari; should be coming at some point though). Hoot’s problem is the reverse: how to implement push calls?

The issue might seem trivial but it is not. Let me illustrate briefly by describing what Guile does natively (not compiled to WebAssembly). Firstly, note that I am discussing residual push calls, by which I mean to say that the optimizer might remove a push call in the source program via inlining: we are looking at those push calls that survive the optimizer. Secondly, note that native Guile manages its own stack instead of using the stack given to it by the OS; this allows for push-call recursion without arbitrary limits. It also lets Guile capture stack slices and rewind them, which is the fundamental building block we use to implement exception handling, Fibers and other forms of lightweight concurrency.

The straightforward function call will have an artificially limited total recursion depth in most WebAssembly implementations, meaning that many idiomatic uses of Guile will throw exceptions. Unpleasant, but perhaps we could stomach this tradeoff. The greater challenge is how to slice the stack. That I am aware of, there are three possible implementation strategies.

generic slicing

One possibility is that the platform provides a generic, powerful stack-capture primitive, which is what Guile does. The good news is that one day, the WebAssembly stack-switching proposal should provide this too. And in the meantime, the so-called JS Promise Integration (JSPI) proposal gets close: if you enter Wasm from JS via a function marked as async, and you call out to JavaScript to a function marked as async (i.e. returning a promise), then on that nested Wasm-to-JS call, the engine will suspend the continuation and resume it only when the returned promise settles (i.e. completes with a value or an exception). Each entry from JS to Wasm via an async function allocates a fresh stack, so I understand you can have multiple pending promises, and thus multiple wasm coroutines in progress. It gets a little gnarly if you want to control when you wait, for example if you might want to wait on multiple promises; in that case you might not actually mark promise-returning functions as async, and instead import an async-marked async function waitFor(p) { return await p} or so, allowing you to use Promise.race and friends. The main problem though is that JSPI is only for JavaScript. Also, its stack sizes are even smaller than the the default stack size.

instrumented slicing

So much for generic solutions. There is another option, to still use push calls from the target machine (WebAssembly), but to transform each function to allow it to suspend and resume. This is what I think of as Joe Marshall’s stack trick (also see §4.2 of the associated paper). The idea is that although there is no primitive to read the whole stack, each frame can access its own state. If you insert a try/catch around each push call, the catch handler can access local state for activations of that function. You can slice a stack by throwing a SaveContinuation exception, in which each frame’s catch handler saves its state and re-throws. And if we want to avoid exceptions, we can use checked returns as Asyncify does.

I never understood, though, how you resume a frame. The Generalized Stack Inspection paper would seem to indicate that you need the transformation to introduce a function to run “the rest of the frame” at each push call, which becomes the Invoke virtual method on the reified frame object. To avoid code duplication you would have to make normal execution flow run these Invoke snippets as well, and that might undo much of the advantages. I understand the implementation that Joe Marshall was working on was an interpreter, though, which bounds the number of sites needing such a transformation.

cps transformation

The third option is a continuation-passing-style transformation. A CPS transform results in a program whose procedures “return” by tail-calling their “continuations”, which themselves are procedures. Taking our previous example, a naïve CPS transformation would reify the following program:

(define (f' k)
  (g' (lambda (x) (h' k x))))

Here f' (“f-prime”) receives its continuation as an argument. We call g', for whose continuation argument we pass a closure. That closure is the return continuation of g, binding a name to its result, and then tail-calls h with respect to f. We know their continuations are the same because it is the same binding, k.

Unfortunately we can’t really slice abitrary ranges of a stack with the naïve CPS transformation: we can only capture the entire continuation, and can’t really inspect its structure. There is also no way to compose a captured continuation with the current continuation. And, in a naïve transformation, we would be constantly creating lots of heap allocation for these continuation closures; a push call effectively pushes a frame onto the heap as a closure, as we did above for g'.

There is also the question of when to perform the CPS transform; most optimizing compilers would like a large first-order graph to work on, which is out of step with the way CPS transformation breaks functions into many parts. Still, there is a nugget of wisdom here. What if we preserve the conventional compiler IR for most of the pipeline, and only perform the CPS transformation at the end? In that way we can have nice SSA-style optimizations. And, for return continuations of push calls, what if instead of allocating a closure, we save the continuation data on an explicit stack. As Andrew Kennedy notes, closures introduced by the CPS transform follow a stack discipline, so this seems promising; we would have:

(define (f'' k)
  (push! k)
  (push! h'')
  (g'' (lambda (x)
         (define h'' (pop!))
         (define k (pop!))
         (h'' k x))))

The explicit stack allows for generic slicing, which makes it a win for implementing delimited continuations.

hoot and cps

Hoot takes the CPS transformation approach with stack-allocated return closures. In fact, Hoot goes a little farther, too far probably:

(define (f''')
  (push! k)
  (push! h''')
  (push! (lambda (x)
           (define h'' (pop!))
           (define k (pop!))
           (h'' k x)))
  (g'''))

Here instead of passing the continuation as an argument, we pass it on the stack of saved values. Returning pops off from that stack; for example, (lambda () 42) would transform as (lambda () ((pop!) 42)). But some day I should go back and fix it to pass the continuation as an argument, to avoid excess stack traffic for leaf function calls.

There are some gnarly details though, which I know you are here for!

splits

For our function f, we had to break it into two pieces: the part before the push-call to g and the part after. If we had two successive push-calls, we would instead split into three parts. In general, each push-call introduces a split; let us use the term tails for the components produced by a split. (You could also call them continuations.) How many tails will a function have? Well, one for the entry, one for each push call, and one any time control-flow merges between two tails. This is a fixpoint problem, given that the input IR is a graph. (There is also some special logic for call-with-prompt but that is too much detail for even this post.)

where to save the variables

Guile is a dynamically-typed language, having a uniform SCM representation for every value. However in the compiler and run-time we can often unbox some values, generally as u64/s64/f64 values, but also raw pointers of some specific types, some GC-managed and some not. In native Guile, we can just splat all of these data members into 64-bit stack slots and rely on the compiler to emit stack maps to determine whether a given slot is a double or a tagged heap object reference or what. In WebAssembly though there is no sum type, and no place we can put either a u64 or a (ref eq) value. So we have not one stack but three (!) stacks: one for numeric values, implemented using a Wasm memory; one for (ref eq) values, using a table; and one for return continuations, because the func type hierarchy is disjoin from eq. It’s.... it’s gross? It’s gross.

what variables to save

Before a push-call, you save any local variables that will be live after the call. This is also a flow analysis problem. You can leave off constants, and instead reify them anew in the tail continuation.

I realized, though, that we have some pessimality related to stacked continuations. Consider:

(define (q x)
  (define y (f))
  (define z (f))
  (+ x y z))

Hoot’s CPS transform produces something like:

(define (q0 x)
  (save! x)
  (save! q1)
  (f))

(define (q1 y)
  (restore! x)
  (save! x)
  (save! y)
  (save! q2)
  (f))

(define (q2 z)
  (restore! x)
  (restore! y)
  ((pop!) (+ x y z)))

So q0 saved x, fine, indeed we need it later. But q1 didn’t need to restore x uselessly, only to save it again on q2‘s behalf. Really we should be applying a stack discipline for saved data within a function. Given that the source IR is a graph, this means another flow analysis problem, one that I haven’t thought about how to solve yet. I am not even sure if there is a solution in the literature, given that the SSA-like flow graphs plus tail calls / CPS is a somewhat niche combination.

calling conventions

The continuations introduced by CPS transformation have associated calling conventions: return continuations may have the generic varargs type, or the compiler may have concluded they have a fixed arity that doesn’t need checking. In any case, for a return, you call the return continuation with the returned values, and the return point then restores any live-in variables that were previously saved. But for a merge between tails, you can arrange to take the live-in variables directly as parameters; it is a direct call to a known continuation, rather than an indirect call to an unknown call site.

cps soup?

Guile’s intermediate representation is called CPS soup, and you might wonder what relationship that CPS has to this CPS. The answer is not much. The continuations in CPS soup are first-order; a term in one function cannot continue to a continuation in another function. (Inlining and contification can merge graphs from different functions, but the principle is the same.)

It might help to explain that it is the same relationship as it would be if Guile represented programs using SSA: the Hoot CPS transform runs at the back-end of Guile’s compilation pipeline, where closures representations have already been made explicit. The IR is still direct-style, just that syntactically speaking, every call in a transformed program is a tail call. We had to introduce save and restore primitives to implement the saved variable stack, and some other tweaks, but generally speaking, the Hoot CPS transform ensures the run-time all-tail-calls property rather than altering the compile-time language; a transformed program is still CPS soup.

fin

Did we actually make the right call in going for a CPS transformation?

I don’t have good performance numbers at the moment, but from what I can see, the overhead introduced by CPS transformation can impose some penalties, even 10x penalties in some cases. But some results are quite good, improving over native Guile, so I can’t be categorical.

But really the question is, is the performance acceptable for the functionality, and there I think the answer is more clear: we have a port of Fibers that I am sure Spritely colleagues will be writing more about soon, we have good integration with JavaScript promises while not relying on JSPI or Asyncify or anything else, and we haven’t had to compromise in significant ways regarding the source language. So, for now, I am satisfied, and looking forward to experimenting with the stack slicing proposal as it becomes available.

Until next time, happy hooting!

by Andy Wingo at Monday, May 27, 2024

Arthur A. Gleckler

papers

I left graduate school decades ago, but I still love to read academic papers. The field of computer science reinvents its wheels constantly, but academic literature is a great way to mine existing ideas and avoid that problem. It's a way to "stand on the shoulders of giants."

For a long time, I maintained and carefully indexed a collection of actual printed papers. Once it reached the hundreds, that approach became too cumbersome. I ended up throwing away papers in order to avoid having too many, but often regretted doing that when some half-remembered idea popped up again in another context.

Now I have a crude system that meets my needs. I keep notes on the most interesting papers using Org-mode files, and I keep my collection in a Git repo in purely digital form. Every paper appears in the top-level directory, and there's a subdirectory to-read/ for papers I haven't yet read. A little bit of automation helps, too. Now managing almost two thousand papers is no problem.

Here's the Scheme program, papers, I use for adding new papers:

#!/usr/local/bin/chibi-scheme -r
;;;; -*- mode: scheme -*-

;;;; Expect environment variable <p> to name a directory that holds
;;;; all papers, e.g. "papers/".  A subdirectory "to-read/" that holds
;;;; unread papers must also exist.

;;;; Copy specified documents into "$p/" directory.

;;;; If <--to-read> is specified, copy them to "$p/to-read/", too.

;;;; If <--commit> is specified, use Git to commit each of the new
;;;; documents.  Each document will be committed separately.  It is an
;;;; error if any other file is already staged.

(import (chibi filesystem)
        (chibi pathname)
        (only (chibi process)
              exit
              process->output+error+status)
        (scheme process-context)
        (scheme small)
        (scheme write)
        (only (srfi 1)
              any
              remove)
        (srfi 98)
        (only (srfi 130)
              string-join
              string-prefix?)
        (srfi 166 base))

(define (echo . rest)
  (apply show #true rest)
  (show #true nl))

(define (echo-command command)
  (apply echo (list "command: " (string-join command " "))))

(define (usage program)
  (echo "Usage: "
        (path-strip-directory program)
        " [--commit] [--to-read] <pathname> ..."
        nl
        nl
        "Environment variable p must be set to a directory for holding papers."
        nl
        "It must have a subdirectory called \"to-read/\"."
        nl))

(define (run command)
  (let* ((out+err+status (process->output+error+status command))
         (stdout (car out+err+status))
         (stderr (cadr out+err+status))
         (status (caddr out+err+status)))
    (unless (zero? status)
      (echo-command command)
      (write-string stderr)
      (write-string stdout)
      (exit 1))))

(define (run/assert command message)
  (unless (zero? (caddr (process->output+error+status command)))
    (echo-command command)
    (echo message)
    (exit 1)))

(define (act document papers commit? to-read?)
  (let ((filename (path-strip-directory document)))
    (link-file document (path-resolve filename papers))
    (when commit? (run `("git" "add" ,filename)))
    (when to-read?
      (let ((place (path-resolve filename (path-resolve "to-read" papers))))
        (symbolic-link-file (path-resolve filename "..") place)
        (when commit? (run `("git"  "add" ,place)))))
    (when commit?
      (run `("git" "commit" "-m" ,filename)))))

(define (switch? string) (string-prefix? "--" string))

(define (main arguments)
  (let* ((program (car arguments))
         (options (cdr arguments))
         (papers (or (get-environment-variable "p")
                     (begin (usage program) (exit 1))))
         (valid-switches '("--commit" "--help" "--to-read")))
    (cond ((member "--help" options) (usage program) (exit 0))
          ((any (lambda (a)
                  (and (switch? a)
                       (not (member a valid-switches))))
                options)
           (usage program)
           (exit 1)))
    (let* ((commit? (member "--commit" options))
           (to-read? (member "--to-read" options))
           (cwd (current-directory))
           (documents (map (lambda (f) (path-resolve f cwd))
                           (remove switch? options))))

      (when (null? documents)
        (usage program)
        (exit 1))
      (change-directory papers)
      (when commit?
        (run/assert `("git" "diff" "--cached" "--quiet")
                    "Error: Files already staged."))
      (for-each (lambda (f) (act f papers commit? to-read?))
                documents))))

For example, to add one paper, including a copy in to-read/, commiting it to the repo:

papers --commit --to-read /tmp/aim-349.pdf

I use MIT Scheme for most of my Scheme hacking, but Alex Shinn's Chibi Scheme is wonderful for implementing this kind of tool. It's small, R7RS-Small-compliant, and has many useful libraries. Thank you, Alex!

Fixed on Wed 29 May 2024 to handle relative pathnames.

by Arthur A. Gleckler at Monday, May 27, 2024

Friday, May 24, 2024

Andy Wingo

hoot's wasm toolkit

Good morning! Today we continue our dive into the Hoot Scheme-to-WebAssembly compiler. Instead of talking about Scheme, let’s focus on WebAssembly, specifically the set of tools that we have built in Hoot to wrangle Wasm. I am peddling a thesis: if you compile to Wasm, probably you should write a low-level Wasm toolchain as well.

(Incidentally, some of this material was taken from a presentation I gave to the Wasm standardization organization back in October, which I think I haven’t shared yet in this space, so if you want some more context, have at it.)

naming things

Compilers are all about names: definitions of globals, types, local variables, and so on. An intermediate representation in a compiler is a graph of definitions and uses in which the edges are names, and the set of possible names is generally unbounded; compilers make more names when they see fit, for example when copying a subgraph via inlining, and remove names if they determine that a control or data-flow edge is not necessary. Having an unlimited set of names facilitates the graph transformation work that is the essence of a compiler.

Machines, though, generally deal with addresses, not names; one of the jobs of the compiler back-end is to tabulate the various names in a compilation unit, assigning them to addresses, for example when laying out an ELF binary. Some uses may refer to names from outside the current compilation unit, as when you use a function from the C library. The linker intervenes at the back-end to splice in definitions for dangling uses and applies the final assignment of names to addresses.

When targetting Wasm, consider what kinds of graph transformations you would like to make. You would probably like for the compiler to emit calls to functions from a low-level run-time library written in wasm. Those functions are probably going to pull in some additional definitions, such as globals, types, exception tags, and so on. Then once you have your full graph, you might want to lower it, somehow: for example, you choose to use the stringref string representation, but browsers don’t currently support it; you run a post-pass to lower to UTF-8 arrays, but then all your strings are not constant, meaning they can’t be used as global initializers; so you run another post-pass to initialize globals in order from the start function. You might want to make other global optimizations as well, for example to turn references to named locals into unnamed stack operands (not yet working :).

Anyway what I am getting at is that you need a representation for Wasm in your compiler, and that representation needs to be fairly complete. At the very minimum, you need a facility to transform that in-memory representation to the standard WebAssembly text format, which allows you to use a third-party assembler and linker such as Binaryen’s wasm-opt. But since you have to have the in-memory representation for your own back-end purposes, probably you also implement the names-to-addresses mapping that will allow you to output binary WebAssembly also. Also it could be that Binaryen doesn’t support something you want to do; for example Hoot uses block parameters, which are supported fine in browsers but not in Binaryen.

(I exaggerate a little; Binaryen is a more reasonable choice now than it was before the GC proposal was stabilised. But it has been useful to be able to control Hoot’s output, for example as the exception-handling proposal has evolved.)

one thing leads to another

Once you have a textual and binary writer, and an in-memory representation, perhaps you want to be able to read binaries as well; and perhaps you want to be able to read text. Reading the text format is a little annoying, but I had implemented it already in JavaScript a few years ago; and porting it to Scheme was a no-brainer, allowing me to easily author the run-time Wasm library as text.

And so now you have the beginnings of a full toolchain, built just out of necessity: reading, writing, in-memory construction and transformation. But how are you going to test the output? Are you going to require a browser? That’s gross. Node? Sure, we have to check against production Wasm engines, and that’s probably the easiest path to take; still, would be nice if this were optional. Wasmtime? But that doesn’t do GC.

No, of course not, you are a dirty little compilers developer, you are just going to implement a little wasm interpreter, aren’t you. Of course you are. That way you can build nice debugging tools to help you understand when things go wrong. Hoot’s interpreter doesn’t pretend to be high-performance—it is not—but it is simple and it just works. Massive kudos to Spritely hacker David Thompson for implementing this. I think implementing a Wasm VM also had the pleasant side effect that David is now a Wasm expert; implementation is the best way to learn.

Finally, one more benefit of having a Wasm toolchain as part of the compiler: %inline-wasm. In my example from last time, I had this snippet that makes a new bytevector:

(%inline-wasm
 '(func (param $len i32) (param $init i32)
    (result (ref eq))
    (struct.new
     $mutable-bytevector
     (i32.const 0)
     (array.new $raw-bytevector
                (local.get $init)
                (local.get $len))))
 len init)

%inline-wasm takes a literal as its first argument, which should parse as a Wasm function. Parsing guarantees that the wasm is syntactically valid, and allows the arity of the wasm to become apparent: we just read off the function’s type. Knowing the number of parameters and results is one thing, but we can do better, in that we also know their type, which we use for intentional types, requiring in this case that the parameters be exact integers which get wrapped to the signed i32 range. The resulting term is spliced into the CPS graph, can be analyzed for its side effects, and ultimately when written to the binary we replace each local reference in the Wasm with a reference of the appropriate local variable. All this is possible because we have the tools to work on Wasm itself.

fin

Hoot’s Wasm toolchain is about 10K lines of code, and is fairly complete. I think it pays off for Hoot. If you are building a compiler targetting Wasm, consider budgetting for a 10K SLOC Wasm toolchain; you won’t regret it.

Next time, an article on Hoot’s use of CPS. Until then, happy hacking!

by Andy Wingo at Friday, May 24, 2024

Wednesday, May 22, 2024

Andy Wingo

growing a bootie

Following on last week’s egregious discussion of the Hoot Scheme-to-WebAssembly compiler bootie, today I would like to examine another axis of boot, which is a kind of rebased branch of history: not the hack as it happened, but the logic inside the hack, the structure of the built thing, the history as it might have been. Instead of describing the layers of shims and props that we used while discovering what were building, let’s look at how we would build Hoot again, if we had to.

I think many readers of this blog will have seen Growing a Language, a talk / performance art piece in which Guy L. Steele—I once mentioned to him that Guy L. was one of the back-justifications for the name Guile; he did not take it well—in which Steele takes the set of monosyllabic words as primitives and builds up a tower of terms on top, bootstrapping a language as he goes. I just watched it again and I think it holds up, probably well enough to forgive the superfluous presence of the gender binary in the intro; ideas were different in the 1900s.

It is in the sense of that talk that I would like to look at growing a Hoot: how Hoot defines nouns and verbs in terms of smaller, more primitive terms: terms in terms of terms.

(hoot features) features (hoot primitives) primitives (ice-9 match) match (ice-9 match):s->(hoot primitives):n (hoot eq) eq (ice-9 match):s->(hoot eq):n (hoot pairs) pairs (ice-9 match):s->(hoot pairs):n (hoot vectors) vectors (ice-9 match):s->(hoot vectors):n (hoot equal) equal (ice-9 match):s->(hoot equal):n (hoot lists) lists (ice-9 match):s->(hoot lists):n (hoot errors) errors (ice-9 match):s->(hoot errors):n (hoot numbers) numbers (ice-9 match):s->(hoot numbers):n (fibers scheduler) scheduler (hoot ffi) ffi (fibers scheduler):s->(hoot ffi):n (guile) (guile) (fibers scheduler):s->(guile):n (fibers channels) channels (fibers channels):s->(ice-9 match):n (fibers waiter-queue) waiter-queue (fibers channels):s->(fibers waiter-queue):n (fibers operations) operations (fibers channels):s->(fibers operations):n (fibers channels):s->(guile):n (srfi srfi-9) srfi-9 (fibers channels):s->(srfi srfi-9):n (fibers waiter-queue):s->(ice-9 match):n (fibers waiter-queue):s->(fibers operations):n (fibers waiter-queue):s->(guile):n (fibers waiter-queue):s->(srfi srfi-9):n (fibers promises) promises (fibers promises):s->(fibers operations):n (hoot exceptions) exceptions (fibers promises):s->(hoot exceptions):n (fibers promises):s->(hoot ffi):n (fibers promises):s->(guile):n (fibers conditions) conditions (fibers conditions):s->(ice-9 match):n (fibers conditions):s->(fibers waiter-queue):n (fibers conditions):s->(fibers operations):n (fibers conditions):s->(guile):n (fibers conditions):s->(srfi srfi-9):n (fibers timers) timers (fibers timers):s->(fibers scheduler):n (fibers timers):s->(fibers operations):n (scheme time) time (fibers timers):s->(scheme time):n (fibers timers):s->(guile):n (fibers operations):s->(ice-9 match):n (fibers operations):s->(fibers scheduler):n (hoot boxes) boxes (fibers operations):s->(hoot boxes):n (fibers operations):s->(guile):n (fibers operations):s->(srfi srfi-9):n (hoot eq):s->(hoot primitives):n (hoot syntax) syntax (hoot eq):s->(hoot syntax):n (hoot strings) strings (hoot strings):s->(hoot primitives):n (hoot strings):s->(hoot eq):n (hoot strings):s->(hoot pairs):n (hoot bytevectors) bytevectors (hoot strings):s->(hoot bytevectors):n (hoot strings):s->(hoot lists):n (hoot bitwise) bitwise (hoot strings):s->(hoot bitwise):n (hoot char) char (hoot strings):s->(hoot char):n (hoot strings):s->(hoot errors):n (hoot strings):s->(hoot numbers):n (hoot match) match (hoot strings):s->(hoot match):n (hoot pairs):s->(hoot primitives):n (hoot bitvectors) bitvectors (hoot bitvectors):s->(hoot primitives):n (hoot bitvectors):s->(hoot bitwise):n (hoot bitvectors):s->(hoot errors):n (hoot bitvectors):s->(hoot match):n (hoot vectors):s->(hoot primitives):n (hoot vectors):s->(hoot pairs):n (hoot vectors):s->(hoot lists):n (hoot vectors):s->(hoot errors):n (hoot vectors):s->(hoot numbers):n (hoot vectors):s->(hoot match):n (hoot equal):s->(hoot primitives):n (hoot equal):s->(hoot eq):n (hoot equal):s->(hoot strings):n (hoot equal):s->(hoot pairs):n (hoot equal):s->(hoot bitvectors):n (hoot equal):s->(hoot vectors):n (hoot records) records (hoot equal):s->(hoot records):n (hoot equal):s->(hoot bytevectors):n (hoot not) not (hoot equal):s->(hoot not):n (hoot values) values (hoot equal):s->(hoot values):n (hoot hashtables) hashtables (hoot equal):s->(hoot hashtables):n (hoot equal):s->(hoot numbers):n (hoot equal):s->(hoot boxes):n (hoot equal):s->(hoot match):n (hoot exceptions):s->(hoot features):n (hoot exceptions):s->(hoot primitives):n (hoot exceptions):s->(hoot pairs):n (hoot exceptions):s->(hoot records):n (hoot exceptions):s->(hoot lists):n (hoot exceptions):s->(hoot syntax):n (hoot exceptions):s->(hoot errors):n (hoot exceptions):s->(hoot match):n (hoot cond-expand) cond-expand (hoot exceptions):s->(hoot cond-expand):n (hoot parameters) parameters (hoot parameters):s->(hoot primitives):n (hoot fluids) fluids (hoot parameters):s->(hoot fluids):n (hoot parameters):s->(hoot errors):n (hoot parameters):s->(hoot cond-expand):n (hoot records):s->(hoot primitives):n (hoot records):s->(hoot eq):n (hoot records):s->(hoot pairs):n (hoot records):s->(hoot vectors):n (hoot symbols) symbols (hoot records):s->(hoot symbols):n (hoot records):s->(hoot lists):n (hoot records):s->(hoot values):n (hoot records):s->(hoot bitwise):n (hoot records):s->(hoot errors):n (hoot ports) ports (hoot records):s->(hoot ports):n (hoot records):s->(hoot numbers):n (hoot records):s->(hoot match):n (hoot keywords) keywords (hoot records):s->(hoot keywords):n (hoot records):s->(hoot cond-expand):n (hoot dynamic-wind) dynamic-wind (hoot dynamic-wind):s->(hoot primitives):n (hoot dynamic-wind):s->(hoot syntax):n (hoot bytevectors):s->(hoot primitives):n (hoot bytevectors):s->(hoot bitwise):n (hoot bytevectors):s->(hoot errors):n (hoot bytevectors):s->(hoot match):n (hoot error-handling) error-handling (hoot error-handling):s->(hoot primitives):n (hoot error-handling):s->(hoot pairs):n (hoot error-handling):s->(hoot exceptions):n (hoot write) write (hoot error-handling):s->(hoot write):n (hoot control) control (hoot error-handling):s->(hoot control):n (hoot error-handling):s->(hoot fluids):n (hoot error-handling):s->(hoot errors):n (hoot error-handling):s->(hoot ports):n (hoot error-handling):s->(hoot numbers):n (hoot error-handling):s->(hoot match):n (hoot error-handling):s->(hoot cond-expand):n (hoot ffi):s->(hoot primitives):n (hoot ffi):s->(hoot strings):n (hoot ffi):s->(hoot pairs):n (hoot procedures) procedures (hoot ffi):s->(hoot procedures):n (hoot ffi):s->(hoot lists):n (hoot ffi):s->(hoot not):n (hoot ffi):s->(hoot errors):n (hoot ffi):s->(hoot numbers):n (hoot ffi):s->(hoot cond-expand):n (hoot debug) debug (hoot debug):s->(hoot primitives):n (hoot debug):s->(hoot match):n (hoot symbols):s->(hoot primitives):n (hoot symbols):s->(hoot errors):n (hoot assoc) assoc (hoot assoc):s->(hoot primitives):n (hoot assoc):s->(hoot eq):n (hoot assoc):s->(hoot pairs):n (hoot assoc):s->(hoot equal):n (hoot assoc):s->(hoot lists):n (hoot assoc):s->(hoot not):n (hoot procedures):s->(hoot primitives):n (hoot procedures):s->(hoot syntax):n (hoot write):s->(hoot primitives):n (hoot write):s->(hoot eq):n (hoot write):s->(hoot strings):n (hoot write):s->(hoot pairs):n (hoot write):s->(hoot bitvectors):n (hoot write):s->(hoot vectors):n (hoot write):s->(hoot records):n (hoot write):s->(hoot bytevectors):n (hoot write):s->(hoot symbols):n (hoot write):s->(hoot procedures):n (hoot write):s->(hoot bitwise):n (hoot write):s->(hoot char):n (hoot write):s->(hoot errors):n (hoot write):s->(hoot ports):n (hoot write):s->(hoot numbers):n (hoot write):s->(hoot keywords):n (hoot lists):s->(hoot primitives):n (hoot lists):s->(hoot pairs):n (hoot lists):s->(hoot values):n (hoot lists):s->(hoot numbers):n (hoot lists):s->(hoot match):n (hoot lists):s->(hoot cond-expand):n (hoot not):s->(hoot syntax):n (hoot syntax):s->(hoot primitives):n (hoot values):s->(hoot primitives):n (hoot values):s->(hoot syntax):n (hoot control):s->(hoot primitives):n (hoot control):s->(hoot parameters):n (hoot control):s->(hoot values):n (hoot control):s->(hoot cond-expand):n (hoot bitwise):s->(hoot primitives):n (hoot char):s->(hoot primitives):n (hoot char):s->(hoot bitvectors):n (hoot char):s->(hoot bitwise):n (hoot char):s->(hoot errors):n (hoot char):s->(hoot match):n (hoot dynamic-states) dynamic-states (hoot dynamic-states):s->(hoot primitives):n (hoot dynamic-states):s->(hoot vectors):n (hoot dynamic-states):s->(hoot debug):n (hoot dynamic-states):s->(hoot lists):n (hoot dynamic-states):s->(hoot values):n (hoot dynamic-states):s->(hoot errors):n (hoot dynamic-states):s->(hoot numbers):n (hoot dynamic-states):s->(hoot match):n (hoot read) read (hoot read):s->(hoot primitives):n (hoot read):s->(hoot eq):n (hoot read):s->(hoot strings):n (hoot read):s->(hoot pairs):n (hoot read):s->(hoot bitvectors):n (hoot read):s->(hoot vectors):n (hoot read):s->(hoot exceptions):n (hoot read):s->(hoot symbols):n (hoot read):s->(hoot lists):n (hoot read):s->(hoot not):n (hoot read):s->(hoot values):n (hoot read):s->(hoot char):n (hoot read):s->(hoot errors):n (hoot read):s->(hoot ports):n (hoot read):s->(hoot numbers):n (hoot read):s->(hoot match):n (hoot read):s->(hoot keywords):n (hoot hashtables):s->(hoot primitives):n (hoot hashtables):s->(hoot eq):n (hoot hashtables):s->(hoot pairs):n (hoot hashtables):s->(hoot vectors):n (hoot hashtables):s->(hoot procedures):n (hoot hashtables):s->(hoot lists):n (hoot hashtables):s->(hoot values):n (hoot hashtables):s->(hoot bitwise):n (hoot hashtables):s->(hoot errors):n (hoot hashtables):s->(hoot numbers):n (hoot fluids):s->(hoot primitives):n (hoot fluids):s->(hoot cond-expand):n (hoot errors):s->(hoot primitives):n (hoot atomics) atomics (hoot atomics):s->(hoot primitives):n (hoot ports):s->(hoot primitives):n (hoot ports):s->(hoot eq):n (hoot ports):s->(hoot strings):n (hoot ports):s->(hoot pairs):n (hoot ports):s->(hoot vectors):n (hoot ports):s->(hoot parameters):n (hoot ports):s->(hoot bytevectors):n (hoot ports):s->(hoot procedures):n (hoot ports):s->(hoot lists):n (hoot ports):s->(hoot not):n (hoot ports):s->(hoot values):n (hoot ports):s->(hoot bitwise):n (hoot ports):s->(hoot char):n (hoot ports):s->(hoot errors):n (hoot ports):s->(hoot numbers):n (hoot ports):s->(hoot boxes):n (hoot ports):s->(hoot match):n (hoot ports):s->(hoot cond-expand):n (hoot numbers):s->(hoot primitives):n (hoot numbers):s->(hoot eq):n (hoot numbers):s->(hoot not):n (hoot numbers):s->(hoot values):n (hoot numbers):s->(hoot bitwise):n (hoot numbers):s->(hoot errors):n (hoot numbers):s->(hoot match):n (hoot boxes):s->(hoot primitives):n (hoot match):s->(hoot primitives):n (hoot match):s->(hoot errors):n (hoot keywords):s->(hoot primitives):n (hoot cond-expand):s->(hoot features):n (hoot cond-expand):s->(hoot primitives):n (scheme lazy) lazy (scheme lazy):s->(hoot primitives):n (scheme lazy):s->(hoot records):n (scheme lazy):s->(hoot match):n (scheme base) base (scheme lazy):s->(scheme base):n (scheme load) load (scheme load):s->(hoot primitives):n (scheme load):s->(hoot errors):n (scheme load):s->(scheme base):n (scheme complex) complex (scheme complex):s->(hoot numbers):n (scheme time):s->(hoot primitives):n (scheme time):s->(scheme base):n (scheme file) file (scheme file):s->(hoot primitives):n (scheme file):s->(hoot errors):n (scheme file):s->(hoot ports):n (scheme file):s->(hoot match):n (scheme file):s->(scheme base):n (scheme write) write (scheme write):s->(hoot write):n (scheme eval) eval (scheme eval):s->(hoot errors):n (scheme eval):s->(scheme base):n (scheme inexact) inexact (scheme inexact):s->(hoot primitives):n (scheme inexact):s->(hoot numbers):n (scheme char) char (scheme char):s->(hoot primitives):n (scheme char):s->(hoot bitwise):n (scheme char):s->(hoot char):n (scheme char):s->(hoot numbers):n (scheme char):s->(scheme base):n (scheme process-context) process-context (scheme process-context):s->(hoot primitives):n (scheme process-context):s->(hoot errors):n (scheme process-context):s->(scheme base):n (scheme cxr) cxr (scheme cxr):s->(hoot pairs):n (scheme read) read (scheme read):s->(hoot read):n (scheme base):s->(hoot features):n (scheme base):s->(hoot primitives):n (scheme base):s->(hoot eq):n (scheme base):s->(hoot strings):n (scheme base):s->(hoot pairs):n (scheme base):s->(hoot vectors):n (scheme base):s->(hoot equal):n (scheme base):s->(hoot exceptions):n (scheme base):s->(hoot parameters):n (scheme base):s->(hoot dynamic-wind):n (scheme base):s->(hoot bytevectors):n (scheme base):s->(hoot error-handling):n (scheme base):s->(hoot symbols):n (scheme base):s->(hoot assoc):n (scheme base):s->(hoot procedures):n (scheme base):s->(hoot write):n (scheme base):s->(hoot lists):n (scheme base):s->(hoot not):n (scheme base):s->(hoot syntax):n (scheme base):s->(hoot values):n (scheme base):s->(hoot control):n (scheme base):s->(hoot char):n (scheme base):s->(hoot read):n (scheme base):s->(hoot errors):n (scheme base):s->(hoot ports):n (scheme base):s->(hoot numbers):n (scheme base):s->(hoot match):n (scheme base):s->(hoot cond-expand):n (scheme base):s->(srfi srfi-9):n (scheme repl) repl (scheme repl):s->(hoot errors):n (scheme repl):s->(scheme base):n (scheme r5rs) r5rs (scheme r5rs):s->(scheme lazy):n (scheme r5rs):s->(scheme load):n (scheme r5rs):s->(scheme complex):n (scheme r5rs):s->(scheme file):n (scheme r5rs):s->(scheme write):n (scheme r5rs):s->(scheme eval):n (scheme r5rs):s->(scheme inexact):n (scheme r5rs):s->(scheme char):n (scheme r5rs):s->(scheme process-context):n (scheme r5rs):s->(scheme cxr):n (scheme r5rs):s->(scheme read):n (scheme r5rs):s->(scheme base):n (scheme r5rs):s->(scheme repl):n (scheme case-lambda) case-lambda (scheme case-lambda):s->(hoot primitives):n (fibers) (fibers) (fibers):s->(fibers scheduler):n (fibers):s->(guile):n (guile):s->(hoot features):n (guile):s->(hoot primitives):n (guile):s->(ice-9 match):n (guile):s->(hoot eq):n (guile):s->(hoot strings):n (guile):s->(hoot pairs):n (guile):s->(hoot bitvectors):n (guile):s->(hoot vectors):n (guile):s->(hoot equal):n (guile):s->(hoot exceptions):n (guile):s->(hoot parameters):n (guile):s->(hoot dynamic-wind):n (guile):s->(hoot bytevectors):n (guile):s->(hoot error-handling):n (guile):s->(hoot symbols):n (guile):s->(hoot assoc):n (guile):s->(hoot procedures):n (guile):s->(hoot write):n (guile):s->(hoot lists):n (guile):s->(hoot not):n (guile):s->(hoot syntax):n (guile):s->(hoot values):n (guile):s->(hoot control):n (guile):s->(hoot bitwise):n (guile):s->(hoot char):n (guile):s->(hoot dynamic-states):n (guile):s->(hoot read):n (guile):s->(hoot fluids):n (guile):s->(hoot errors):n (guile):s->(hoot ports):n (guile):s->(hoot numbers):n (guile):s->(hoot boxes):n (guile):s->(hoot keywords):n (guile):s->(hoot cond-expand):n (guile):s->(scheme lazy):n (guile):s->(scheme time):n (guile):s->(scheme file):n (guile):s->(scheme char):n (guile):s->(scheme process-context):n (guile):s->(scheme base):n (guile):s->(srfi srfi-9):n (srfi srfi-9):s->(hoot primitives):n (srfi srfi-9):s->(hoot records):n

If you are reading this on the web, you should see above a graph of dependencies among the 50 or so libraries that are shipped as part of Hoot. (Somehow I doubt that a feed reader will plumb through the inline SVG, but who knows.) It’s a bit of a mess, but still I think it’s a useful illustration of a number of properties of how the Hoot language is grown from small to large. Click on any box to visit the source code for that module.

the root of the boot

Firstly, let us note that the graph is not a forest: it is a single tree. There is no module that does not depend (possibly indirectly) on (hoot primitives). This is because there are no capabilities that Hoot libraries can access without importing them, and the only way into the Hootosphere from outside is via the definitions in the primitives module.

So what are these definitions, you might ask? Well, these are the “well-known” bindings, for example + for which the compiler might have some special understanding, the sort of binding that gets translated to a primitive operation at the compiler IR level. They are used in careful ways by the modules that use (hoot primitives) to ensure that their uses are all open-coded by the compiler. (“Open coding” is inlining. But inlining to me implies that the whole implementation is inlined, with no slow-path callouts, whereas open coding implies to me that it’s the compiler that knows what the op does and may or may not inline the actual asm.)

But, (hoot primitives) also exposes some other definitions, for example define and let and lambda and all that. Scheme doesn’t have keywords in the sense that Python has def and with and such: there is no privileged way to associate a name with its meaning. It is in this sense that it is impossible to avoid (hoot primitives): the most simple (define x 42) depends on the lexical meaning of define, which is provided by the primitives module.

Syntax definitions are an expander construct; they are not present at run-time. Using a syntax definition causes the expander to invoke code, and the expander runs on the host system, which is Guile and not WebAssembly. So, syntax definitions belong to the host. This goes also for some first-order definitions such as syntax->datum and so on, which are only used in syntax expanders; these definitions are plumbed through (hoot primitives), but can only ever be used by macro definitions, which run on the meta-level.

(Is this too heavy? Allow me to lighten the mood: when I was 22 or so and working in Namibia, I somehow got an advance copy of Notes from the Metalevel. I was working on algorithmic music synthesis, and my chief strategy was knocking hubris together with itself, as one does. I sent the author a bunch of uninvited corrections to his book. I think it was completely unwelcome! Anyway, moral of the story, at 22 you get a free pass to do whatever you want, and come to think of it, now that I am 44 I think I should get some kind of hubris loyalty award or something.)

powerful primitives

So, there are expand-time primitives and run-time primitives. The expander knows about expand-time primitives and the compiler knows about run-time primitives. One particularly powerful primitive is %inline-wasm, which takes an inline snippet of WebAssembly as an s-expression and applies it to a number of arguments passed at run-time. Consider make-bytevector:

(define* (make-bytevector len #:optional (init 0))
  (%inline-wasm
   '(func (param $len i32) (param $init i32)
      (result (ref eq))
      (struct.new
       $mutable-bytevector
       (i32.const 0)
       (array.new $raw-bytevector
                  (local.get $init)
                  (local.get $len))))
   len init))

We have an inline snippet of wasm that makes a $mutable-bytevector. It passes 0 as the hash field, meaning that the hashq of this value will be lazily initialized, and the contents are a new array of a given size and initial value. Inputs will be unboxed to the appropriate type (two i32s in this case), and likewise with outputs; here we produce the universal (ref eq) representation.

The nice thing about %inline-wasm is that the compiler didn’t have to be taught about make-bytevector: this definition suffices, because %inline-wasm can access a number of lower-level capabilities.

dual denotations

But as we learned in my notes on whole-program compilation, any run-time definition is available at compile-time, if it is reachable from a syntax transformer. So this definition above isn’t quite sufficient; we can’t call make-bytevector as part of a procedural macro, which we might want to do. What we need instead is to provide one definition when residualizing wasm at run-time, and another when loading a module at expand-time.

In Hoot we do this with cond-expand, where we expand to %inline-wasm when targetting Hoot, and... what, precisely, at expand-time? Really we need to make a Guile bytevector, so in this sort of case, we end up having to include a run-time make-bytevector definition in the (hoot primitives) module. This happens whereever we end up using %inline-wasm.

building to guile

Returning to our graph, we see that there is a red-colored block for Hoot modules, a teal-colored layer on top for those modules that are defined by R7RS, a few oddballs, and then (guile) and Fibers built on top. The (guile) module provides a shim that implements Guile’s own default set of bindings, allowing Guile modules to be loaded on a Hoot system. (guile) is layered on top of the low-level Hoot libraries, and out of convenience, on top of the various R7RS libraries as well, because it was easiest to remember what was where in R7RS than our ad-hoc nest of Hoot internal libraries.

Having (guile) lets Guile hackers build on Hoot. It’s still incomplete but I think eventually it will be capital-G Good. Even for a library that needed more porting like Fibers (Hoot has no threads so much of the parallel concurrent ML implementation can be simplified, and we use an event loop from the Wasm run-time instead of an epoll-based scheduler), it was still pleasant to be able to use define-module and keyword arguments and all of that.

next layers

I mentioned that this tower of terms is incomplete, and so that is one of the next work items for Hoot: complete support for Guile’s run-time library. At that point we’d probably want to merge it into Guile, but that is another topic.

But let’s leave that for another day; until then, happy hacking!

by Andy Wingo at Wednesday, May 22, 2024

Tuesday, May 21, 2024

Idiomdrottning

Modern XMPP

Modern XMPP:

Modern XMPP is an independent project launched to improve the quality of user-to-user messaging applications that use XMPP. […]

We are developing a handful of simple documents aimed at people who wish to build on top of XMPP. The recommendations are derived from healthy discussions between developers from multiple XMPP projects and other members of the XMPP community.

I’m glad XMPP is getting some love. It’s a protocol that has some advantages over Matrix and ActivityPub and even over IRC. (even though adding OMEMO to IRC might be possible, the way XMPP federates is a li’l more flexible than how IRC federates). Not that I’m ready to take all my proverbial eggs out of the ActivityPub, email, or IRC baskets just yet. Email is my doll my dear my darling♥︎ but ultimately from a user perspective, choosing a protocol is about the people on it. I find a lot of awesome stuff on email, on ActivityPub, on IRC and on XMPP so they’re all great in terms of what’s on it. Philosophically is where it doesn’t make sense to keep spending time developing a protocol when there’s a better protocol for the same thing and I don’t know yet which of these four li’l creatures is the best one. I suspect email is the best♥︎

Matrix has a long way to go before it can even go on the same table as these four other pillars of communication but maybe it’ll get there? I’m more inclined to spend my time on the other horses in that particular race but I’ve been wrong plenty of times.

We also intend to provide a comprehensive set of guidelines for UI and UX design.

Not into that. One thing I love about email, XMPP and ActivityPub is the breadth of experiences available.

Having a concrete set of guidelines will help to provide a more uniform user experience between different applications, ensuring they use the same terminology, and provide interoperable feature sets.

Interoperable feature sets through XEP curation, that’s awesome! That’s great! Uniform user experience is the part that sounds like a nightmare. Like, there’s just no way bitlbee + MS Comic Chat can have the same UI or workflow as Snikket, and that’s a good thing. But this is a resource, a tool, not a straitjacket.

by Idiomdrottning (sandra.snan@idiomdrottning.org) at Tuesday, May 21, 2024

Thursday, May 16, 2024

The Racket Blog

Racket v8.13

posted by Stephen De Gabrielle


We are pleased to announce Racket v8.13 is now available from https://download.racket-lang.org/.

As of this release:

  • The racket/treelist and racket/mutable-treelist libraries provide list-like containers that support many operations in effectively constant time, including appending and extracting sub-lists without mutating the given list. Treelists are implemented as RRB Vectors, invented by Stucki, Riompf, Ureche, and Bagwell. (see 4.16 Treelists and RRB vector: a practical general purpose immutable sequence, ICFP 2015)

  • The hash-filter-keys and hash-filter-values functions allow users to filter hashes using a predicate on either keys or values. (see 4.15 Hash Tables: hash-filter-keys, hash-filter-values)

  • The vector-extend and vector*-extend functions provide a way to pre-populate the prefix of a newly allocated vector using the elements of an existing vector. (see 4.12 Vectors: vector-extend)

  • Command-line raco setup, package update, and package installation use terminal control (when available) to show what they are working on more compactly and with a progress bar.

  • Racket v8.13 uses Unicode 15.1 for character and string operations.

  • Machine-specific cross-module optimization allows improved support for static generation of foreign-function bindings.

  • The scribble/acmart language uses v2.01, which avoids errors concerning the hyperref package in some latex installations.

Thank you

The following people contributed to this release:

Alec Mills, Ben Greenman, Bob Burger, Bogdan Popa, dr-neptune, Fred Fu, Gustavo Massaccesi, Jason Hemann, Jay McCarthy, John Clements, Jordan Johnson, Justin Dhillon, Mao Yifu, Matias Eyzaguirre, Matthew Flatt, Matthias Felleisen, Mike Sperber, olopierpa, Oscar Waddell, Pavel Panchekha, Philip McGrath, Robby Findler, Sam Phillips, Sam Tobin-Hochstadt, Siddhartha Kasivajhula, Sorawee Porncharoenwase, Stephen De Gabrielle, Tim Standen, William E. Byrd, and Wing Hei Chan.

Racket is a community developed open source project and we welcome new contributors. See racket/README.md to learn how you can be a part of this amazing project.

Feedback Welcome

Questions and discussion welcome at the Racket community Discourse or Discord

Please share

If you can - please help get the word out to users and platform specific repo packagers

Racket - the Language-Oriented Programming Language - version 8.13 is now available from https://download.racket-lang.org

See https://blog.racket-lang.org/2024/05/racket-v8-13.html for the release announcement and highlights.

by John Clements, Stephen De Gabrielle at Thursday, May 16, 2024

Andy Wingo

on hoot, on boot

I realized recently that I haven’t been writing much about the Hoot Scheme-to-WebAssembly compiler. Upon reflection, I have been too conscious of its limitations to give it verbal tribute, preferring to spend each marginal hour fixing bugs and filling in features rather than publicising progress.

In the last month or so, though, Hoot has gotten to a point that pleases me. Not to the point where I would say “accept no substitutes” by any means, but good already for some things, and worth writing about.

So let’s start today by talking about bootie. Boot, I mean! The boot, the boot, the boot of Hoot.

hoot boot: temporal tunnel

The first axis of boot is time. In the beginning, there was nary a toot, and now, through boot, there is Hoot.

The first boot of Hoot was on paper. Christine Lemmer-Webber had asked me, ages ago, what I thought Guile should do about the web. After thinking a bit, I concluded that it would be best to avoid compromises when building an in-browser Guile: if you have to pollute Guile to match what JavaScript offers, you might as well program in JavaScript. JS is cute of course, but Guile is a bit different in some interesting ways, the most important of which is control: delimited continuations, multiple values, tail calls, dynamic binding, threads, and all that. If Guile’s web bootie doesn’t pack all the funk in its trunk, probably it’s just junk.

So I wrote up a plan something to which I attributed the name tailification. In retrospect, this is simply a specific flavor of a continuation-passing-style (CPS) transmutation, late in the compiler pipeline. I’ll elocute more in a future dispatch. I did end up writing the tailification pass back then; I could have continued to target JS, but it was sufficiently annoying and I didn’t prosecute. It sat around unused for a few years, until Christine’s irresistable charisma managed to conjure some resources for Hoot.

In the meantime, the GC extension for WebAssembly shipped (woot woot!), and to boot Hoot, I filled in the missing piece: a backend for Guile’s compiler that tailified and then translated primitive operations to snippets of WebAssembly.

It was, well, hirsute, but cute and it did compute, so we continued to boot. From this root we grew a small run-time library, written in raw WebAssembly, used for slow-paths for the various primitive operations that are part of Guile’s compiler back-end. We filled out Guile primcalls, in minute commits, growing the WebAssembly runtime library and toolchain as we went.

Eventually we started constituting facilities defined in terms of those primitives, via a Scheme prelude that was prepended to all programs, within a nested lexical environment. It was never our intention though to drown the user’s programs in a sea of predefined bindings, as if the ultimate program were but a vestigial inhabitant of the lexical lake—don’t dilute the newt!, we would often say [ed: we did not]— so eventually when the prelude became unmanageable, we finally figured out how to do whole-program compilation of a set of modules.

Then followed a long month in which I would uproot the loot from the boot: take each binding from the prelude and reattribute it into an appropriate module. User code could import all the modules that suit, as long as they were known to Hoot, but no others; it was only until we added the ability for users to programmatically consitute an environment from their modules that Hoot became a language implementation of any repute.

Which brings us to the work of the last month, about which I cannot be mute. When you have existing Guile code that you want to distribute via the web, Hoot required you transmute its module definitions into the more precise R6RS syntax. Precise, meaning that R6RS modules are static, in a way that Guile modules, at least in absolute terms, are not: Guile programs can use first-class accessors on the module systems to pull out bindings. This is yet another example of what I impute as the original sin of 1990s language development, that modules are just mutable hash maps. You see it in Python, for example: because you don’t know for sure to what values global names are bound, it is easy for any discussion of what a particular piece of code means to end in dispute.

The question is, though, are the semantics of name binding in a language fixed and absolute? Once your language is booted, are its aspects definitively attributed? I think some perfection, in the sense of becoming more perfect or more like the thing you should be, is something to salute. Anyway, in Guile it would be coherent with Scheme’s lexical binding heritage to restitute some certainty as to the meanings of names, at least in a default compilation node. Lexical binding is, after all, the foundation of the Macro Writer’s Statute of Rights. Of course if you are making a build for development purposes, not to distribute, then you might prefer a build that marks all bindings as dynamic. Otherwise I think it’s reasonable to require the user to explicitly indicate which definitions are denotations, and which constitute locations.

Hoot therefore now includes an implementation of the static semantics of Guile’s define-module: it can load Guile modules directly, and as a tribute, it also has an implementation of the ambient (guile) module that constitutes the lexical soup of modules that aren’t #:pure. (I agree, it would be better if all modules were explicit about the language they are written in—their imported bindings and so on—but there is an existing corpus to accomodate; the point is moot.)

The astute reader (whom I salute!) will note that we have a full boot: Hoot is a Guile. Not an implementation to substitute the original, but more of an alternate route to the same destination. So, probably we should scoot the two implementations together, to knock their boots, so to speak, merging the offshoot Hoot into Guile itself.

But do I circumlocute: I can only plead a case of acute Hoot. Tomorrow, we elocute on a second axis of boot. Until then, happy compute!

by Andy Wingo at Thursday, May 16, 2024

Idiomdrottning

Hardening newlines

Sometimes I just want all newlines in a region to become hardened, for example when writing code or poetry.

Markdown

I have this brev snippet that I run with shell-command-on-region:

(make-sloppy-tree-accessor scadr)

(define (poetry-md)
  (pair-fold
    (fn (if (any empty? (list (car x) (scadr x)))
          (print (car x))
          (print (car x) "  ")))
    (void)
    ((over (strse x " +$" "")) (read-lines))))

use-hard-newlines mode

Here’s a function to harden all newlines in the region:

(defun harden-region (start end)
  (interactive "r")
  (when use-hard-newlines
    (save-excursion
      (goto-char start)
      (while (< (point) (min (point-max) end))
        (end-of-line)
        (forward-char)
        (set-hard-newline-properties
         (- (point) 1) (point))))))

by Idiomdrottning (sandra.snan@idiomdrottning.org) at Thursday, May 16, 2024

Wednesday, May 15, 2024

spritely.institute

Make a game with Hoot for the Lisp Game Jam!

Spring Lisp Game Jam

Twice per year I co-host the Lisp Game Jam: a 10-day game jam where participants create small games in their favorite Lisp dialect. Unlike classic game jams like Ludum Dare, which have an intensive 2-3 day long duration, the Lisp Game Jam is much more casual and spans two whole weekends to give busy people (most of us!) more of a chance to complete a game. There are no prizes, though there is a judging period where we play each other's games and give feedback. Really, the joy of getting creative with Lisp is its own reward. Game jams are the perfect excuse to prototype a gameplay idea and get some practice managing the scope of a project to meet a due date.

The Spring edition of the Lisp Game Jam starts this Friday, May 17th and is on track to be the biggest one yet with over 100 registered participants so far! Will you be among them? On behalf of the Spritely Institute, I would like to encourage you to join this spring's jam and try out Hoot, our Scheme to WebAssembly compiler!

We're so excited for you to join that we've put together a game jam template repository that has everything you need to make a 2D game using Hoot and HTML5 canvas. It even features a mini-Breakout clone as an example of how to put all the pieces together into a playable game!

I can't overstate how web browser support is a huge benefit in a game jam. An HTML5 build embedded directly on the itch.io page for your game makes it relatively frictionless for players to try it out. HTML5 games consistently get more players and ratings on average than native games.

It is much harder to ship native releases that will work reliably on many different computers. I've spent many hours debugging such issues in the past. Native releases also typically need one build per supported operating system. That's a lot of time and energy that could be spent building the actual game instead! When it comes to game jams, people play entries for minutes, not hours. If your game is hard to launch then they will move on to another one that is easier to try. I know I'm on the development team, but ease of distribution is probably the biggest motivating factor for making my jam games with Hoot.

Last year, during the Autumn jam, I used a much more primitive version of Hoot to make a space shooter called Strigoform, and David Wilson (of System Crafters fame) made a Solitaire clone called Cybersol. You can read more about our experiences using Hoot in last year's jam here, but trust me when I say that since then, it's become a lot easier to get started!

Strigoform gameplay animation

We love making small games here at Spritely not only because they make for eye-catching demos, but also for their tendency to stress language/library implementations, routinely exposing bugs and performance issues. Game jams are a great opportunity to "eat your own dog food" and put a technology stack to the test under time and resource constraints in a low stakes, fun way. Spritely staff, myself included, will be participating in the jam, but what I'm really looking forward to is seeing what the community creates and taking note of all the ways that Hoot can be improved moving forward!

For help with Hoot or the game template during the jam, you can post questions in this itch.io forum thread.

To talk about all things Spritely, during the jam and beyond, join our community forum or the #spritely channel on the Libera.Chat IRC network.

For some advice on making games, I recommend reading "How to Make Good Small Games" by Far Away Times. I think I will re-read it before the jam starts.

And finally, for our dedicated and intrepid game jam readers, tessa, our developer advocate, has created a mobile wallpaper to help you celebrate the jam all day every day, wherever you may be:

Painting of Spritely characters hanging out and playing

Happy hooting, jammers! 🦉

by Dave Thompson (contact@spritely.institute) at Wednesday, May 15, 2024

Monday, May 13, 2024

Idiomdrottning

Tooticki

I like toot as a good complement to other ActivityPub clients. It’s friendly for scripting.

I can’t really use the TUI version (maybe there’s some issue with my shell) but I use the CLI interface all the time.

One way I use it is in Emacs shell-mode. I hacked in some Lisp so I can favorite, reblog and even reply right from there; I move the cursor to the body of the post and then hit the key bound to one of these interactive functions. (If I wanna do even more fancy stuff I still can, just typing it in the command line as usual, or for some things I still schlep out another client.)

Here is the elisp:

(defun tooticki-find-id ()
  (interactive)
  (save-excursion
    (beginning-of-line)
    (re-search-forward "^ID ")
    (let ((st (point)))
      (forward-word)
      (buffer-substring-no-properties st (point)))))

(defun tooticki-reply-markdown ()
  (interactive)
  (let* ((id (tooticki-find-id))
	 (topic
	  (string-trim-right
	   (shell-command-to-string
	    (s-concat "toot status --json " id "|jq  .spoiler_text"))))
	 (targs (if (< (length topic) 3) "" (s-concat " -p " topic))))
    (async-shell-command
     (s-concat "toot post -r " id targs))))

(defun tooticki-skele (str)
  (shell-command (s-concat "toot " str " " (tooticki-find-id))))

(defun tooticki-fave ()
  (interactive)
  (tooticki-skele "favourite"))

(defun tooticki-boost ()
  (interactive)
  (tooticki-skele "reblog"))

Except that where I wrote “toot post -r” here, in the version I’ve got bound it’s instead a wrapper around written in zshbrev that tries to guess language (currently doing a really bad job at it since for some reason many emojis trigger false positives making it guess that some English language posts are Swedish) and that offers to post links to linkhut.

One limitation is that it doesn’t pre-populate the reply with @usernames; that’s a work in progress. I currently just manually paste them in. Today I added the feature that it preserves the spoiler text a.k.a. subject line, and a similar route, parsing status --json, could be the ticket for getting the user names in there. One SMOP over the line, sweet Jesus.

Update

Yeah, finding the usernames was possible:

toot-get-usernames () {
	toot status --json $1 | jq -r '..|select(.acct?).acct' |
		mawk '!s[$0]++' | sed 's;^;@;'
}

by Idiomdrottning (sandra.snan@idiomdrottning.org) at Monday, May 13, 2024

Saturday, May 11, 2024

Idiomdrottning

RFC on e-ink readers

I used httrack and Calibre’s ebook-convert for what I thought was the best results.

First, go to rfc-editor.org and select the HTML version of your RFC, for example RFC 9421.

Then, I downloaded it with:

httrack -g https://www.rfc-editor.org/rfc/rfc9421.html --levels 1

Then I converted that like this:

ebook-convert rfc9421.html "RFC 9421: HTTP Message Signatures.epub" --max-levels 1

Background

Since I was heading down this particular yak-shaving rabbit-hole this morning, with a couple of false starts and dead ends, I thought I’d note down for posterity what I landed on.

I tried out three or four other solutions, like RFC2Kindle.py and rfc2epub.php, but they didn’t work very well. I didn’t realize that rfc-editor has HTML versions now.

Truth is, I already had an iPad shortcut set up to grab any URL, SSH into my Debian machine and run httrack and ebook-convert, and calibre-smtp to send it. Sometimes the Kindle app gives better results, usually this httrack method is the best, often neither works since in the grim darkness of the world wide web there is only war.

It just took me a while to think of using that approach for this as opposed to solutions trying to parse the traditional RFC format, and the results ended up good, at least for 9421.

Here’s the shortcut I’ve been using, in zshbrev:

(define (kindlepage url #!key (levels 0))
  (if (strse?* url "youtube")
    (kindletube url)
    (with-temp-dir
      (eif levels (httrack '-g url '-D (conc '-r levels)) (httrack '-g url))
      (with (conc (broodal-title (car (glob "*.html"))) '.epub)
            (ebook-convert (car (glob "*.html")) it '--max-levels levels)
            (kindlesend it)))))

(define (broodal-title (= ->string hfile))
  (strse (with-input-from-file hfile read-string)
         (: "<title>" (* space) (=> keep (* nonl)) (* space) "</title>")
         (return keep)))

(define-ir-syntax*
  (with-temp-dir . body)
  `(let ((cur (current-directory)) (,(inject 'it) (mktemp '-d)))
     (change-directory ,(inject 'it))
     ,@body
     (change-directory cur)
     (delete-directory ,(inject 'it) #t)))

(And then kindlesend is just a wrapper for calibre-smtp that prefills the args with the right email addresses.)

I’ve had this set up for years but didn’t think of using it for RFCs since I was like “I’m sure someone else musta figured out a better solution for reading RFCs on e-ink many years ago” but nope.

by Idiomdrottning (sandra.snan@idiomdrottning.org) at Saturday, May 11, 2024