Planet Scheme

Tuesday, May 6, 2025

spritely.institute

Hoot 0.6.1 released!

We are excited to announce the release of Hoot 0.6.1! Hoot is a Scheme to WebAssembly compiler backend for Guile, as well as a general purpose WebAssembly toolchain. In other words, Scheme in the browser!

This small patch release contains bug fixes and a few new features added since the 0.6.0 release back in January. Just in time for the upcoming Lisp Game Jam!

Make a game with Hoot!

The 2025 edition of the Spring Lisp Game Jam starts on Friday, 5/9! The Lisp Game Jam is a casual, 10-day long event where participants build small games using the Lisp implementation of their choice. We’d like to encourage you to join the jam and try making a game with Hoot! Hoot is a great choice for game jams because web-based games are both easy to distribute and easy for other people to play.

To make it easy to jump right in and make a game with Hoot, we have a ready-to-go template repository on Codeberg that you can clone. It takes care of all the boilerplate and provides some useful bindings to essential web APIs like HTML5 Canvas.

Okay, game jam promotion over! Read on for the full release notes.

New features

  • New --bundle flag for guild compile-wasm that will automatically install runtime libraries alongside the generated binary (reflect.js, reflect.wasm, wtf8.wasm).

  • Integrated psyntax-based macro expander (hoot expander) into eval.

  • Add -g flag for controlling compiler debug level.

  • Changed current-module to require compilation with -g.

  • Changed (hoot environments) to use run-time module registry.

  • Added logcount and vector-move-left! procedures, part of Guile's default environment.

  • Added experimental (hoot time) module for date/time calculations (currently undocumented).

  • Internal make-port procedure now uses keyword arguments.

  • Keyword error constructors are now exported from Hoot's Wasm ABI.

  • Added external-function? and call-external to (hoot ffi).

  • Added quote-syntax to (hoot core-syntax) and (hoot syntax).

  • Documented (fibers streams) module.

Bug fixes

  • Fixed inexact->exact conversion for a subset of flonums.

  • Fixed number->string for radix 16.

  • Fixed current-time which was mistakenly using jiffies.

  • Fixed string-split when delimiter is the first character in the string.

  • Fixed string-utf8-length opcode emission.

  • Fixed define-values macro that was causing compilation errors on newer Guile Git builds.

  • Fixed cond-expand error condition.

  • Fixed Wasm linker handling of call_ref and return_call_ref.

  • Fixed Wasm linker handling of catch bodies.

  • Fixed ,wasm-eval metacommand.

  • Fixed NodeJS example in the manual. Thanks to Jelle Licht for the patch!

  • External references now have a printed representation.

  • Exported sleep from (fibers) to match upstream Fibers API.

Performance improvements

  • Optimized Wasm validation pass (validate-wasm).

  • Optimized Wasm linker (add-stdlib).

  • Optimized Wasm resolver (resolve-wasm).

  • Optimized Wasm emission in compiler backend (high-level-cps->wasm).

Browser compatibility

  • Compatible with Firefox 121 or later.

  • Compatible with Google Chrome 119 or later.

  • Compatibility with Safari/WebKit is still a bit complicated, unfortunately. We thought everything was in place when Hoot 0.6.0 was released, but then we found a bug in WebKit’s Wasm tail call implementation. This bug was fixed nearly two months ago but the fix has not yet propagated out to stable Safari and iOS releases, as far we’re aware. We verified that some of our larger Hoot programs are now working on a Git build of WebKit, so we are optimistic that Hoot will finally be supported on all major browsers soon.

Get Hoot 0.6.1!

Hoot is already available in GNU Guix:

$ guix pull
$ guix install guile-next guile-hoot

(Hoot currently requires a bleeding-edge version of Guile, hence guile-next above.)

Otherwise, Hoot can be built from source via our release tarball. See the Hoot homepage for a download link and GPG signature.

Documentation for Hoot 0.6.1, including build instructions, can be found here.

Get in touch!

For bug reports, pull requests, or just to follow along with development, check out the Hoot project on Codeberg.

If you build something cool with Hoot (for the upcoming game jam or otherwise), let us know on our community forum!

Special thanks to the MetaMask folks for funding this work!

Until next time, happy hooting! 🦉

by Dave Thompson (contact@spritely.institute) at Tuesday, May 6, 2025

Monday, May 5, 2025

spritely.institute

Announcing Spritely Oaken

Spritely's Oaken mascot

Hi! I’m Daphne Preston-Kendal! You may remember me from such programming languages as the Revised⁷ Report on the Algorithmic Language Scheme. In this guest post, I’m going to explain the work I’m doing for Spritely, funded by NLnet: developing a new secure Scheme sublanguage for running untrusted code, like modifications to an existing app, in a safe way!

Usually, loading some random third-party code into your program is considered a security risk. Games are probably the most popular category of app these days where it’s normal for them to be moddable by adding more code, but we can see what a security disaster this is. Hardly a week goes by without yet another story of some rascal sharing a Minecraft mod pack on a forum or uploading a mod to the Steam Workshop which, in reality, exists to steal browser cookies or passwords.

If fun things like games can’t stop malicious mods, what hope do we have to build more serious moddable apps which get deployed on major server systems? What if a malicious mod got onto servers with sensitive data about thousands or millions of people?

Obviously, though, not all code is evil: probably most code isn’t, at least not deliberately. Do we really have to throw out the entire idea of running third-party modifications to our software just because some small amount of it might do bad stuff?

What code can you trust?

Here’s a pop quiz! What potential security problems could the following Scheme code cause? (Assume that we are working on a fully-conformant implementation of the R6RS, and this is evaluated with just the (rnrs base (6)) library imported.)

(lambda (x) (+ x 1))

Go ahead – it’s not a trick question!

The answer, obviously, is none! Evaluating this expression can’t access any system resources; once evaluated, you get a procedure, and the worst thing that can happen then is that someone gives it something that’s not a number (which will just safely raise an exception). This code will never steal your bank account information, eat all the cheese in your fridge, cause demons to fly out of your nose, etc.

So obviously, we can trust some code. For a simple procedure like this, we can audit it and see what it does! But for more complex code, it’s not reasonable to carefully read thousands of lines to try and find anything that looks nefarious. Attackers also keep finding new ways to hide malicious code from human auditors, from weird tricks with Unicode control characters to just putting loads of spaces at the start of lines so you have to scroll horizontally to see the evil code.

What if we could automatically audit code to be sure that it doesn’t do anything dodgy? Could that avoid human errors (like failing to notice a horizontal scrollbar)?

To do that, we have to go a level further and consider how we came to the conclusion that procedures like the one above are safe. How do we know? Well, + is a pure function: it takes some input value and returns a new, completely different output value. It doesn’t change anything about the input value: if you call ((lambda (x) (+ x 1)) sensitive-number), the value of sensitive-number itself won’t have changed when the add-one procedure is done with it. It doesn’t open any files or connect to any other remote computers, so your sensitive-number won’t be leaked to any bad guys. Also, it doesn’t allocate any memory or loop. Even a pure-functional program can do that – but at scale, that causes resource exhaustion, which could make an important service inaccessible until the tied-up resources are released. Well, we can treat any pure functional program as safe, so pretty much everything in the (rnrs base (6)) library is okay – and maybe when we run it we’ll be sure to watch it to make sure it doesn’t use too many CPU cycles.

So we’ve got our first idea – but, sorry, I’ve gotta interrupt this blog post now because Christine just sent me some code she thinks I should put in my next program. It looks pretty nifty – it’s a square root procedure written in just Scheme! Hey, you know what, let’s take a look together:

(library (dustyweb square-root)
  (export square-root)

Looks good so far!

  (import (rnrs base (6))
          (rnrs io ports (6)))

Uh-oh. Why does a square root procedure need port I/O? Square-root should be a pure function, but that library gives Christine’s code complete access to my filesystem. What’s she up to? Is she trying to read my private data? Or has thinking about all those evil Minecraft mods and how to detect them made me paranoid??

  (define (close-enough? guess x)
    (< (abs (- (* guess guess) x)) 0.01))

  (define (improve-guess guess x)
    (/ (+ guess (/ x guess))
       2))

  (define (square-root x)
    (call-with-port
        (open-file-output-port "sqrt-log.txt"
                               (file-options no-fail)
                               (buffer-mode line)
                               (native-transcoder))
      (lambda (log-port)
        (put-string log-port "finding square root of: ")
        (put-datum log-port x)
        (put-char log-port #\newline)
        (let loop ((guess 1.0))
          (put-string log-port "guess: ")
          (put-datum log-port guess)
          (put-char log-port #\newline)
          (cond ((close-enough? guess x)
                 (put-string log-port "good enough, ship it!\n")
                 guess)
                (else
                 (loop (improve-guess guess x)))))))))

Well, actually, that looks perfectly innocent as far as uses of the filesystem go. Christine probably wanted to log the guesses so she could debug her code. Still, if I already have any file called sqrt-log.txt, this will inadvertently delete and write over it. Also, I wanted to use this procedure in a program to work out how much perspective distortion I should expect with various lenses on some of the weird and wacky film formats I photograph on. (The amount of perspective distortion is proportional to a function of the difference between the focal length and the corner-to-corner diagonal of the image plane.) but what weird and wacky film formats I use is my own private business, and I don’t necessarily want it sent to Christine’s server: imagine if instead of (rnrs io ports (6)), she’d imported (srfi :106) (socket library) and sent all that data off to her server to spy on the square roots I’m calculating! I can’t just trust any code Christine sends me.

Hmm. Maybe we’ve learned something here, though – something we can use to improve our intuition about what code we can trust in general. I’m fine with recording what square roots I take, and what steps were taken to calculate them – on my own computer. Can we reformulate Christine’s library so that she can still have her debugging information, but it still only imports the (rnrs base (6)) library? Then we know we can trust her code just by looking at the import list!

How about something like this?

(library (dustyweb square-root)
  (export square-root)
  (import (rnrs base (6)))

  (define (close-enough? guess x)
    (< (abs (- (* guess guess) x)) 0.01))

  (define (improve-guess guess x)
    (/ (+ guess (/ x guess))
       2))

  (define (square-root x debug-log)
    (debug-log "finding square root of" x)
    (let loop ((guess 1.0))
      (debug-log "guess" guess)
      (cond ((close-enough? guess x)
             (debug-log "good enough, ship it!")
             guess)
            (else
             (loop (improve-guess guess x)))))))

Now when I write my perspective-distortion program, I call square-root like this:

(square-root (+ (square image-width)
                (square image-height))
             ignore)

where ignore is a procedure I wrote and trust that accepts any number of arguments, does nothing with them, and returns nothing of interest. In other words, the logging calls do nothing for me because they’re not very interesting to me. Meanwhile, when Christine is debugging her program, she can write a debug-log procedure that looks like this:

(define (make-debug-log-procedure log-port)
  (case-lambda
    ((message)
     (put-string log-port message)
     (put-char log-port #\newline))
    ((message value)
     (put-string log-port message)
     (put-string log-port ": ")
     (put-datum log-port value)
     (put-char log-port #\newline))))

(define debug-log (make-debug-log-procedure
                   (open-file-output-port "sqrt-log.txt"
                                          (file-options no-fail)
                                          (buffer-mode line)
                                          (native-transcoder))))

What happened here? Square-root can still do I/O, but suddenly we’re able to trust it because we know that the library it’s in only has access to procedures we trust. In other words, we only have to look at that one line in the program to know that we can completely trust the whole program! But, somehow, it can still do the I/O for the debug log Christine wants. The reason is that when we call it, we explicitly give it the ability to do I/O in a limited way: we write code ourselves – code we trust to access libraries like (rnrs io ports (6)) or (srfi :106) – and pass in a procedure from outside that exposes the capabilities of those libraries in a specific, limited way. Even if I did want to log what square-root is doing, using Christine’s debug-log procedure would only let it write to one specific file, and in a very specific way. It couldn’t use that ability to start reading my browser cookies like it could if I gave it the full (rnrs io ports (6)) library. Even better, if you do want to get the log, you can change where it goes just by passing a different port to make-debug-log-procedure!

Make-debug-log-procedure uses a technique called closure so that its own argument, the log-port, is available to the debug-log procedure even though it isn’t an argument to it. (We say that the debug-log procedure is closed over the log-port variable – or more informally, that it’s closed over the port itself.) Once make-debug-log-procedure returns, the debug-log procedure it creates has access to that port and exposes it in a limited way, which means the (dustyweb square-root) library doesn’t need to import (rnrs io ports (6)) any more. But Christine can still use open-file-input-port when she writes a debugging procedure like make-debug-log-port, because she obviously trusts herself to use it responsibly. In fact, anyone who actually uses her library can trust themselves to access their own files.

It would still be nice to be able to use square-root as if it were a pure function, not having to pass in this ugly debug-log argument. That gives me an idea: could we close the whole library over a procedure like debug-log? That would mean Christine could also extend her library to include all sorts of useful functions, like cube roots or inverse square roots – all of them safely debug-logging away – and I would only need to pass in the debug-log argument once when I import her library.

Now we’ve actually arrived at a much better idea than trying to audit all the third-party code we might possibly want to use. Instead of doing that, we just make sure it only uses safe procedures or ones we’ve given it!

Unfortunately, neither R6RS nor R7RS Scheme provides the ability to make an entire library into a closure. But maybe we can design a system that does have this ability – that’s Oaken!

Taming libraries to stop them eating resources

In programming security research, this kind of trick of using language features to turn an unsafe library into a safer one is called ‘taming’. Like humans tamed wolves into dogs to stop them eating their sheep programmers can tame libraries to stop them providing access to the procedures that could create a security vulnerability.

I can go down to the pet shop and buy a dog and train it to recognize me as its owner. As its owner, I’m in charge and I can do all the things the dog isn’t allowed to do in my household – sleep on the human bed, eat food from the dinner table, dig holes in the garden, etc. In security terminology, this kind of general permission is called ‘ambient authority’. But, as a treat, I could let the dog do some of those things sometimes, but only when I allow it. The dog doesn’t get the ambient authority to do these things all of the time: it’s only allowed to do it in the way I let it and when I say so.

We are in charge of our own programs and our own computers. We get to do everything, but the code we pull in from some library should only be able to do things we allow it to do. We’ve seen how we could do this by closing those libraries over procedures giving more limited access to a resource, but we should really have a standard library for systematically controlling access to the resources which could cause security problems if evil code uses them in evil ways.

We’re not going to support every use case in the initial version of Oaken: full taming is a really hard problem. (Like any red-blooded programmer, I initially thought it was going to be easy, and then all the individual little difficulties slowly started to dawn on me. In fact, I still keep realizing new problems almost every day.) But we’ll provide some very basic tamings that should be good enough to start off with: the idea of Oaken is that the library system supports taming as a general concept, so more advanced controls can follow later.

Filesystem and network abuse

It should be obvious that giving untrusted code unrestricted read/write access to the whole computer filesystem is a bad idea. In combination with unrestricted ability to connect to other computers over the internet, it’s an even worse idea.

We already saw a simple idea for taming filesystem access in the square root example, but real-world libraries might legitimately want to create and read their own files to provide some useful functionality to the trusted code which uses those libraries.

We already have a real world example of how this could work. When you upload a file to a website in your browser, the web site can’t directly read the files on your computer. Instead, your browser, which does have that unrestricted filesystem access, pops up a file selection dialogue box and asks you to choose a file. The browser then makes that file available to the website by giving it a File object which it can use to read that file – and only that file. This pattern of passing limited access to some restricted resource to untrusted code is called the ‘powerbox pattern’.

Just as you give a website access to one file, with Oaken you can close a library over a version of the file-system access library which, for example, only gives access to one directory. That means the code could never go snooping outside that directory and steal or destroy information that doesn’t belong to it. Simple!

Unfortunately, file access is really tricky to fully tame. We can easily make it so that a tamed library can only access one directory on the disk, but it’s not so easy to stop that library from writing files in that directory which would eventually eat up all space on the drive. Ideally, you’d be able to limit how much disk space untrusted code can use and not just access to individual files. But that would require looking at what special support the operating system can give us and how to make use of the tools it has to restrict storage abuse, so full taming of filesystem access – beyond restricting code’s access to a single file or directory – is probably out of scope for the initial version of Oaken.

But what about network access? Should we instantiate each library a different time, passing it in multiple times, for each server and port it wants to access? That sounds a bit annoying. Maybe it would be better to use a different mechanism for powerboxing than the one the library system provides. I’ll be thinking a lot about this and trying to come up with a workable design!

Timing attacks

Another surprising source of security issues in apps comes just from giving programs access to a simple system clock. Timing attacks can let untrusted code find out information about what’s going on inside of trusted procedures they shouldn’t be able to extract information from, or see the inner workings of; or they can let two untrusted bits of code communicate with one another when they shouldn’t. Mark S. Miller, an influential researcher in the area of secure programming systems, talks about this as ‘prisoners tapping on the pipes’ – sending messages to one another in their cells with Morse code or whatever. You really do have to be careful to ensure that all potential back-channels for unwanted communication are closed off.

Preventing this particular kind of attack seems quite simple – there’s no real taming to be done. It’s just a matter of making sure a library only has access to the system clock if you explicitly give it access when you instantiate it, which is an all-or-nothing proposition – unlike carefully controlling which individual files or directories a procedure could access and how. But something I’ve already learned in planning this project is that if something looks simple, I probably haven’t thought about it enough yet, so maybe there are more problems lurking beneath the surface here.

Exhaustion attacks

It’s not only external resources like files, the network, or the system clock which can pose a security risk. The computer’s CPU and memory are all you need for another kind of attack: a denial of service. If you tie up all the computer’s memory and processor time with nonsense, you can make a service inaccessible to people who actually need to use it. Typically, attackers find some request they can make to a service that takes massively, disproportionately more resources for the service to respond to than it does for them to make the request.

What tools do you need for this kind of attack? Could we restrict those through the library system too? Unfortunately, that approach won’t work here. In fact, all you need to cause a denial-of-service attack is lambda, as in this example that’s often shown while explaining how the fixed-point combinator is derived:

((lambda (x) (x x)) (lambda (x) (x x)))

By conjuring up two procedures which call each other forever, this cute little Scheme expression will peg one of your CPUs until you find a way to stop it. This isn’t good! But this kind of vulnerability to resource-exhaustion attack can happen entirely by accident: just the other day I was hacking on a procedure and accidentally made it loop infinitely on some input.

It’s mathematically impossible to always detect this kind of bug in advance. Moreover, even if a program eventually stops looping (and there is a useful subset of programs whose halting behaviour is provable), it might still take too much CPU to return its result. (Even just a badly behaved regular expression implementation can make resource exhaustion attacks possible!) So the best we can do is put a limit on the amount of computation an untrusted procedure is allowed to do.

Guile already includes a little library called (ice-9 sandbox) which lets you call code with limits on how much time it can take and how much memory it can allocate. Unfortunately, (ice-9 sandbox) limits wall-clock time, not actual processor resources, which is not ideal. For example, wall-clock time includes time spent waiting for user input! You don’t want your procedure getting killed for DoSing the system when in fact it’s sitting there doing nothing while a hunt-and-peck typist is writing up their life story into a text box. Worse, there’s no way to powerbox time usage with (ice-9 sandbox).

But there might be a solution: engines! Engines are a Scheme idea introduced by Kent Dybvig and Bob Hieb. The basic concept is that the system runtime keeps track of how many units of computation (‘ticks’) have been executed, and when that number exceeds a certain limit (the amount of ‘fuel’ in the engine), it pauses execution and returns the unfinished task back to whoever started it. They can then decide whether to stop running the computation, or give it more fuel and carry on.

The ticks can be measured in any unit – with the right support from the OS, you could even make it actual CPU time – but Dybvig and Hieb suggest counting procedure calls. That works well in Scheme because, once you expand all your macros, everything you could do that might cause CPU exhaustion – in particular, looping – involves a procedure call.

The Guile manual also describes a few problems with the memory limiter in (ice-9 sandbox). For now, we’ll probably have to live with those and a few more, like the fact that it’s also not possible to powerbox memory usage. Guile is getting a new garbage collector soon, thanks to Andy Wingo’s sterling work on Whippet; as the migration from BDW to Whippet progresses, maybe it will become possible to fix some of these issues in future. But here also, many operating systems (cough Linux) make things difficult: we can’t really do anything about the kernel deciding that the Guile process has had quite enough memory for tonight and that it’s time to go home.

Capability attentuation

So far we’ve only considered one level of delegation of trust: you have your dog/program, and the dog/program is only allowed to sleep in the dog bed you gave it/use only the files you gave it. But in reality, software dependencies form a much more complex graph, and it should be possible for the things you trust in some limited way to place their trust in other things in even more limited ways.

Let’s say I have my program, and within it I gave your library access to a key-value store where it gets to store up to 100 MB of data in its own namespace. Your library might want to import some other library, giving it some smaller slice of that data in turn, like 10 MB, and its own subnamespace. So your library needs to be able to take the version of the library you gave it, which is closed over the limit of 100 MB and one namespace, and close it over a different limit and a different, subordinate namespace.

At the moment, I’m still in the early stages of designing the library system, and supporting this use case seems kind of hard! It’s easy to think about a one-level system where the main, trusted program gets to instantiate every (potentially untrusted) library with some fixed limitations. It’s a lot harder to design a system where it’s easy to start with an existing instantiated, untrusted library and impose even stricter limitations on it to create another library with the same interface but even tighter controls.

Onward

I’m looking forward to hacking on Oaken over the next couple of months! Oaken is one of the more intriguing parts of the Spritely Institute’s vision for decentralized internet infrastructure. Imagine spreadsheet macros that won’t make off with your sensitive financial data; imagine not just safe mods to existing games, but even something like the ability to send a whole new multiplayer game to your friends in a chat program, who could then just run it right in place on their computer with no security fears; imagine the Shepherd where each service ran in its own capability sandbox! Oaken will enable all of this by working alongside other Spritely projects like Hoot and Goblins.

Let a thousand Oaken forests bloom!

Further reading

The canonical paper on using Scheme variable scope for security is Jonathan Rees’s Ph.D. dissertation, ‘A Security Based on the Lambda Calculus’. That dissertation is a direct inspiration for Oaken, and Jonathan is advising me on the project.

As far as I know, the idea of closing modules over things, in the way procedures can be closed over things, comes from the Standard ML programming language. David MacQueen’s paper ‘Modules for Standard ML’ explains how it was designed. We’re not the first people to try adapting this idea for Scheme: the Scheme 48 module system, also designed by Jonathan Rees, worked this way. But Oaken will be the first such library system in Scheme specifically designed for security purposes, released for general use, and with a standard library for tamed access to important resources.

The E programming language pioneered many aspects of capability-based security within a programming language, and the Emaker library system is also an inspiration for Oaken. The same idea was proposed for JavaScript as FrozenRealms which evolved into Endo.

by Daphne Preston-Kendal (contact@spritely.institute) at Monday, May 5, 2025

Friday, April 25, 2025

Andy Wingo

partitioning ambiguous edges in guile

Today, some more words on memory management, on the practicalities of a system with conservatively-traced references.

The context is that I have finally started banging Whippet into Guile, initially in a configuration that continues to use the conservative Boehm-Demers-Weiser (BDW) collector behind the scene. In that way I can incrementally migrate over all of the uses of the BDW API in Guile to use Whippet API instead, and then if all goes well, I should be able to switch Whippet to use another GC algorithm, probably the mostly-marking collector (MMC). MMC scales better than BDW for multithreaded mutators, and it can eliminate fragmentation via Immix-inspired optimistic evacuation.

problem statement: how to manage ambiguous edges

A garbage-collected heap consists of memory, which is a set of addressable locations. An object is a disjoint part of a heap, and is the unit of allocation. A field is memory within an object that may refer to another object by address. Objects are nodes in a directed graph in which each edge is a field containing an object reference. A root is an edge into the heap from outside. Garbage collection reclaims memory from objects that are not reachable from the graph that starts from a set of roots. Reclaimed memory is available for new allocations.

In the course of its work, a collector may want to relocate an object, moving it to a different part of the heap. The collector can do so if it can update all edges that refer to the object to instead refer to its new location. Usually a collector arranges things so all edges have the same representation, for example an aligned word in memory; updating an edge means replacing the word’s value with the new address. Relocating objects can improve locality and reduce fragmentation, so it is a good technique to have available. (Sometimes we say evacuate, move, or compact instead of relocate; it’s all the same.)

Some collectors allow ambiguous edges: words in memory whose value may be the address of an object, or might just be scalar data. Ambiguous edges usually come about if a compiler doesn’t precisely record which stack locations or registers contain GC-managed objects. Such ambiguous edges must be traced conservatively: the collector adds the object to its idea of the set of live objects, as if the edge were a real reference. This tracing mode isn’t supported by all collectors.

Any object that might be the target of an ambiguous edge cannot be relocated by the collector; a collector that allows conservative edges cannot rely on relocation as part of its reclamation strategy. Still, if the collector can know that a given object will not be the referent of an ambiguous edge, relocating it is possible.

How can one know that an object is not the target of an ambiguous edge? We have to partition the heap somehow into possibly-conservatively-referenced and definitely-not-conservatively-referenced. The two ways that I know to do this are spatially and temporally.

Spatial partitioning means that regardless of the set of root and intra-heap edges, there are some objects that will never be conservatively referenced. This might be the case for a type of object that is “internal” to a language implementation; third-party users that may lack the discipline to precisely track roots might not be exposed to objects of a given kind. Still, link-time optimization tends to weather these boundaries, so I don’t see it as being too reliable over time.

Temporal partitioning is more robust: if all ambiguous references come from roots, then if one traces roots before intra-heap edges, then any object not referenced after the roots-tracing phase is available for relocation.

kinds of ambiguous edges in guile

So let’s talk about Guile! Guile uses BDW currently, which considers edges to be ambiguous by default. However, given that objects carry type tags, Guile can, with relatively little effort, switch to precisely tracing most edges. “Most”, however, is not sufficient; to allow for relocation, we need to eliminate intra-heap ambiguous edges, to confine conservative tracing to the roots-tracing phase.

Conservatively tracing references from C stacks or even from static data sections is not a problem: these are roots, so, fine.

Guile currently traces Scheme stacks almost-precisely: its compiler emits stack maps for every call site, which uses liveness analysis to only mark those slots that are Scheme values that will be used in the continuation. However it’s possible that any given frame is marked conservatively. The most common case is when using the BDW collector and a thread is pre-empted by a signal; then its most recent stack frame is likely not at a safepoint and indeed is likely undefined in terms of Guile’s VM. It can also happen if there is a call site within a VM operation, for example to a builtin procedure, if it throws an exception and recurses, or causes GC itself. Also, when per-instruction traps are enabled, we can run Scheme between any two Guile VM operations.

So, Guile could change to trace Scheme stacks fully precisely, but this is a lot of work; in the short term we will probably just trace Scheme stacks as roots instead of during the main trace.

However, there is one more significant source of ambiguous roots, and that is reified continuation objects. Unlike active stacks, these have to be discovered during a trace and cannot be partitioned out to the root phase. For delimited continuations, these consist of a slice of the Scheme stack. Traversing a stack slice precisely is less problematic than for active stacks, because it isn’t in motion, and it is captured at a known point; but we will have to deal with stack frames that are pre-empted in unexpected locations due to exceptions within builtins. If a stack map is missing, probably the solution there is to reconstruct one using local flow analysis over the bytecode of the stack frame’s function; time-consuming, but it should be robust as we do it elsewhere.

Undelimited continuations (those captured by call/cc) contain a slice of the C stack also, for historical reasons, and there we can’t trace it precisely at all. Therefore either we disable relocation if there are any live undelimited continuation objects, or we eagerly pin any object referred to by a freshly captured stack slice.

fin

If you want to follow along with the Whippet-in-Guile work, see the wip-whippet branch in Git. I’ve bumped its version to 4.0 because, well, why the hell not; if it works, it will certainly be worth it. Until next time, happy hacking!

by Andy Wingo at Friday, April 25, 2025

Monday, April 21, 2025

LIPS Scheme Blog

Internals: Syntax Extensions

Syntax extensions are a feature in LIPS Scheme that allow users to add new syntax. They work similar to readers, macro in Common Lisp. You create a sequence of characters that maps to a function that is executed by the parser, the function works similar to a macro and a result of the function is returned by the parser in place of the sequence of defined characters.


see the rest of the article

Monday, April 21, 2025

Thursday, April 17, 2025

Idiomdrottning

I stopped sticking to FOSS but immediately regretted that decision

I more or less only used FOSS from late nineties until autumn 2021, where I got an iPad. This decision was partially prompted by frustration with Android’s open washing (I was stuck with an un-updatable Android tablet that wasn’t that old. By comparison, this iPad has received updates for way more years already) and partially in a rash angry moment after interacting with a complete jerk online who made me in one instant give up on the entire FOSS community.

There was also the fact that I realized that I had already been leaking away my own FOSS-y values, that there had been one growing, frogboiling exception; video game consoles. Now, for a while when I was at my most freshly converted GNU-wly brainwashed, I didn’t use any. Then I rationalized that it’s not that bad to use a Game Boy or NES. The roms are runnable on widely available emulators (not to discount the incredible feats of engineering creating those emulators entailed) and often decompilable or simple enough to understand in machine code. I found them similar to Z-machine or Scumm VM which I already thought was OK. After all, the requirement was free software, not all free media. I could still watch normal movies, for example.

But that can hardly be said about modern consoles like Switch or Wii or 3DS. They’re like entire operating systems spamming tons of telemetry and junk.

So “I am already using proprietary apps so why not do it more?” was my thinking.

After getting the iPad I immediately regretted that. It was so much worse than I could’ve ever imagined.

And now I’m stuck with it for as long as I have this device. There’s no chance of a FOSS firmware being made anytime soon. That m1, m2 Linux distro that existed briefly until the kernel guys bullied them away, they were prohibited to make it work on tablets, they could only work on computers.

I’m not gonna get the Switch 2 nor a new iPad. I’m going to try to get better at this in the future. It’s not exactly easy because this world has made it way harder to be FOSS only than it was in the nineties. I’m just gonna do my best from now on and not beat myself up.

The one rule I stuck to and I’m glad I did

I want to steer clear of “network effect” apps like Messenger or WhatsApp or X. Those are much much harder to get out of once you start using them. Do not lightly sign up for them. So on the iPad I never ever used iMessage for example.

by Idiomdrottning (sandra.snan@idiomdrottning.org) at Thursday, April 17, 2025

Sunday, April 13, 2025

Gauche Devlog

Exact and repeating decimals

Exact and repeating decimals

Novice programmers are often perplexed by most programming languages being not able to add 0.1 ten times ``correctly'':

s = 0
for i in range(10):
   s += 0.1
print(s)

# prints: 0.9999999999999999

"Floating point numbers are inexact, that's why," tells a tutor. "You should expect some errors."

Gauche isn't an exception, for decimal notation is read as inexact numbers:

gosh> (apply + (make-list 10 0.1))
0.9999999999999999

However, Scheme also has exact numbers. Numbers without a decimal point or exponent, or rational numbers, are read as exact numbers. You can also prefix decimal numbers with #e to make them exact. Using exact numbers, you can have an exact result.

gosh> (apply + (make-list 10 #e0.1))
1

The trick is that Gauche reads #e0.1 as an exact rational number 1/10, and perform computation as exact rationals. It is revealed when the result is not a whole number:

gosh> (+ #e0.1 #e0.1)
1/5

It is incovenient, though, when you want to perform exact computation with decimal numbers, i.e. adding prices with dollars and cents. If you add $15.15 and $8.91, you want to see the result as 24.06 instead of 1203/50.

;; Inexact
gosh> (+ 15.15 8.91)
24.060000000000002

;; Exact
gosh> (+ #e15.15 #e8.91)
1203/50

So, we added a new REPL print mode, exact-decimal. If you set it to #t, Gauche tries to print exact non-integer result as decimal notation whenever possible.

gosh> ,pm exact-decimal #t
Current print mode:
        length :  50
         level :  10
        pretty :  #t
         width :  79
          base :  10
         radix :  #f
 string-length : 256
    bytestring :  #f
 exact-decimal :  #t

Let's see:

gosh> (+ #e15.15 #e8.91)
#e24.06

We can always have exact decimal notation of rational numbers whose denominator's factor contains only 2 and 5.

gosh> 1/65536
#e0.0000152587890625

As far as we use addition, subtraction, and multiplication of exact decimal notated numbers, the result is always representable with exact decimal notation.

But what if division is involved? Isn't it a shame that we have an exact value (as a rational number), but can't print it as a decimal exactly?

Decimal notation of rational numbers whose denominator contains factors other than 2 and 5 becomes repeating decimals. Hence if we have a notation of repeating decimals, we can cover such cases.

So, here it is. If a numeric literal contains # followed by one or more digits, we understand the digits after # repeating infinitely.

gosh> 0.#3
0.3333333333333333
gosh> 0.0#123
0.012312312312312312
gosh> 0.#5
0.5555555555555556
gosh> 0.1#9
0.2

(Note: If no digits follows #, it is "insignificant digit" notation in R5RS.)

The above examples have limited number of digits because they're inexact numbers (note that we didn't prefix them with #e). For exact numbers, we can represent any rational numbers exactly with this notation:

gosh> 1/3
#e0.#3
gosh> 1/7
#e0.#142857
gosh> (* 1/7 2)
#e0.#285714
gosh> (* #e0.#3 #e0.#142857)
#e0.#047619

Note that the length of repetition can be arbitrarily long, so there are numbers that can't practically be printed in this notation. For the time being, we have a hard limit of 1024 for the length of repetition. If the result exceeds this limitation, we fall back to rational notation.

;; 1/2063 has repeating cycle of 1031 digits
gosh> (/ 1 2063)
1/2063

Tags: Numbers, Syntax

Sunday, April 13, 2025

Tuesday, April 8, 2025

spritely.institute

Successful supporter drive supplements Spritely's story

The Spritely team is overjoyed by the support we've received in our first ever supporter drive. More than just donations, these are individual voices which inspire us to deliver on our promise of a more secure future.

The world needs social media that isn't powered by centralized sources that don't have our best interests in mind. Spritely's mission helps make that more achievable. 🖤

- Josh Mock

Spritely is painting a picture of a hopeful, human future for people and their communication, and have a credible vision to get there. That's a rare thing, and worthy of support.

- David Anderson

My digital life is my life.
Corporations and their centralized web services exist to turn a profit. They’ll eventually do so by extracting what they can from me. And by using their services. I’ve been giving them coercive leverage!
To hold pieces of me hostage.
No mas.

- Moto A

More than five hundred people have decided to donate to Spritely so far, with more than three hundred new voices being heard during this campaign!

We easily surpassed our original goal of $80,000 with weeks to spare! Even though we fell short of our stretch goal we introduced in January, our final amount was $90,000, well in excess of what we expected.

Also, if you donated at the Silver level or higher during the campaign, your name has already been added to the credits for Cirkoban in the shiniest way we could think of. Our founder, Christine Lemmer-Webber, is busy working on doodles to send out to the Diamond tier supporters and those should be received in the mail in the near future. As part of our appreciation for your support, we are keeping the tiered reward system for future donations, regardless of funding drive, and we hope to add even more rewards in the future.

Just because the campaign is over doesn't mean we are slowing down. Just the opposite; your support has given us a second wind. Already, we've released new versions of goblins and hoot and we have even more in store for the near future. On top of this, we gave seven presentations at FOSDEM which laid out our vision and our progress and allowed us to meet with partners and supporters in person.

Despite the recent uncertainty in non-profit funding in the US, we are continuing to work against centralized interests as hard as we can, and all of your support makes that possible. Donor drive or not, we always welcome more donations and we appreciate every dollar and cent.

Thank you to everyone who made this supporter drive a success. We couldn't have done it without you!

by Amy Pillow (contact@spritely.institute) at Tuesday, April 8, 2025

Wednesday, March 26, 2025

Scheme Requests for Implementation

SRFI 258: Uninterned symbols

SRFI 258 is now in final status.

An uninterned symbol is not the same as any other symbol, even one with the same name. These symbols are useful in macro programming and in other situations where guaranteed-unique names are needed. A survey of uninterned and uniquely named symbols in Scheme is also provided.

by Wolfgang Corcoran-Mathe at Wednesday, March 26, 2025

spritely.institute

Spritely Goblins v0.15.1 released!

We are happy to announce the release of Goblins 0.15.1! This patch release includes many bug fixes, documentation fixes, and quality-of-life improvements made since the 0.15.0 release back in January.

Thank you to the Spritely community for identifying and reporting many of these issues! We’re thrilled to see more people trying Goblins for the first time. Big thanks to Jessica Tallon, who has done nearly all of the hard work sanding the rough edges for this release.

For more detail about the changes in this release, see the NEWS file.

Bug fixes

  • Fixed sending ghashes over CapTP that have actor references or other complex objects.

  • Fixed sending messages to far references in persistent vats.

  • Fixed thread-safety issues in CapTP garbage collection.

  • Fixed issue where severed connections to peers couldn’t be re-enlivened.

  • Fixed CapTP crossed hellos mitigation.

  • Fixed call-with-vat blocking the current vat’s event loop. It now returns a promise when called in this context.

  • Fixed prelay netlayer not reconnecting after severance.

  • Fixed prelay severance breaking local references.

  • Fixed on-sever for WebSocket netlayer on Hoot.

  • Fixed WebSocket error handling on Hoot.

  • Fixed (goblins ocapn netlayer base-port) and some of its dependencies not compiling with Hoot.

  • Fixed make install installing utility libraries that are only for the test suite.

Documentation fixes/improvements

  • Fixed documentation for spawning ^onion-netlayer and registering sturdyrefs.

  • Fixed the greeter example in the “Persistence Environments” section.

  • Added additional explanation of cooperative multitasking, event loops, and common vat pitfalls in response to user feedback.

  • Added example of passing an actor reference over OCapN.

Quality-of-life improvements

  • Added race* variant of race joiner in (goblins actor-lib joiners).

  • Vectors and non-list pairs (such as key/value pairs within association lists) are now serializable over CapTP.

  • Exported ^persistence-registry from (goblins) module.

  • The fake netlayer can now be halted, which is useful when testing.

  • Added on-sever support to the prelay netlayer.

  • Added a new procedure, timeout, for creating promises that resolve after a certain amount of time has passed. timeout can be found in the new (goblins actor-lib timers) module.

  • Suppressed warning for the override of Guile core binding spawn when (goblins) is imported.

Getting the release

As usual, if you're using Guix, you can upgrade to 0.15.1 by running:

guix pull
guix install guile-goblins

Otherwise, you can find the source tarball on our release page.

Get in touch!

For bug reports, pull requests, or just to follow along with development, check out the Goblins project on Codeberg.

If you're making something with Goblins or want to contribute to Goblins itself, be sure to join our community at community.spritely.institute! Thanks for following along and hope to see you there!

by David Thompson (contact@spritely.institute) at Wednesday, March 26, 2025

Friday, March 7, 2025

Andy Wingo

whippet lab notebook: untagged mallocs, bis

Earlier this week I took an inventory of how Guile uses the Boehm-Demers-Weiser (BDW) garbage collector, with the goal of making sure that I had replacements for all uses lined up in Whippet. I categorized the uses into seven broad categories, and I was mostly satisfied that I have replacements for all except the last: I didn’t know what to do with untagged allocations: those that contain arbitrary data, possibly full of pointers to other objects, and which don’t have a header that we can use to inspect on their type.

But now I do! Today’s note is about how we can support untagged allocations of a few different kinds in Whippet’s mostly-marking collector.

inside and outside

Why bother supporting untagged allocations at all? Well, if I had my way, I wouldn’t; I would just slog through Guile and fix all uses to be tagged. There are only a finite number of use sites and I could get to them all in a month or so.

The problem comes for uses of scm_gc_malloc from outside libguile itself, in C extensions and embedding programs. These users are loathe to adapt to any kind of change, and garbage-collection-related changes are the worst. So, somehow, we need to support these users if we are not to break the Guile community.

on intent

The problem with scm_gc_malloc, though, is that it is missing an expression of intent, notably as regards tagging. You can use it to allocate an object that has a tag and thus can be traced precisely, or you can use it to allocate, well, anything else. I think we will have to add an API for the tagged case and assume that anything that goes through scm_gc_malloc is requesting an untagged, conservatively-scanned block of memory. Similarly for scm_gc_malloc_pointerless: you could be allocating a tagged object that happens to not contain pointers, or you could be allocating an untagged array of whatever. A new API is needed there too for pointerless untagged allocations.

on data

Recall that the mostly-marking collector can be built in a number of different ways: it can support conservative and/or precise roots, it can trace the heap precisely or conservatively, it can be generational or not, and the collector can use multiple threads during pauses or not. Consider a basic configuration with precise roots. You can make tagged pointerless allocations just fine: the trace function for that tag is just trivial. You would like to extend the collector with the ability to make untagged pointerless allocations, for raw data. How to do this?

Consider first that when the collector goes to trace an object, it can’t use bits inside the object to discriminate between the tagged and untagged cases. Fortunately though the main space of the mostly-marking collector has one metadata byte for each 16 bytes of payload. Of those 8 bits, 3 are used for the mark (five different states, allowing for future concurrent tracing), two for the precise field-logging write barrier, one to indicate whether the object is pinned or not, and one to indicate the end of the object, so that we can determine object bounds just by scanning the metadata byte array. That leaves 1 bit, and we can use it to indicate untagged pointerless allocations. Hooray!

However there is a wrinkle: when Whippet decides the it should evacuate an object, it tracks the evacuation state in the object itself; the embedder has to provide an implementation of a little state machine, allowing the collector to detect whether an object is forwarded or not, to claim an object for forwarding, to commit a forwarding pointer, and so on. We can’t do that for raw data, because all bit states belong to the object, not the collector or the embedder. So, we have to set the “pinned” bit on the object, indicating that these objects can’t move.

We could in theory manage the forwarding state in the metadata byte, but we don’t have the bits to do that currently; maybe some day. For now, untagged pointerless allocations are pinned.

on slop

You might also want to support untagged allocations that contain pointers to other GC-managed objects. In this case you would want these untagged allocations to be scanned conservatively. We can do this, but if we do, it will pin all objects.

Thing is, conservative stack roots is a kind of a sweet spot in language run-time design. You get to avoid constraining your compiler, you avoid a class of bugs related to rooting, but you can still support compaction of the heap.

How is this, you ask? Well, consider that you can move any object for which we can precisely enumerate the incoming references. This is trivially the case for precise roots and precise tracing. For conservative roots, we don’t know whether a given edge is really an object reference or not, so we have to conservatively avoid moving those objects. But once you are done tracing conservative edges, any live object that hasn’t yet been traced is fair game for evacuation, because none of its predecessors have yet been visited.

But once you add conservatively-traced objects back into the mix, you don’t know when you are done tracing conservative edges; you could always discover another conservatively-traced object later in the trace, so you have to pin everything.

The good news, though, is that we have gained an easier migration path. I can now shove Whippet into Guile and get it running even before I have removed untagged allocations. Once I have done so, I will be able to allow for compaction / evacuation; things only get better from here.

Also as a side benefit, the mostly-marking collector’s heap-conservative configurations are now faster, because we have metadata attached to objects which allows tracing to skip known-pointerless objects. This regains an optimization that BDW has long had via its GC_malloc_atomic, used in Guile since time out of mind.

fin

With support for untagged allocations, I think I am finally ready to start getting Whippet into Guile itself. Happy hacking, and see you on the other side!

by Andy Wingo at Friday, March 7, 2025

Wednesday, March 5, 2025

Joe Marshall

Collate / index-list

I was talking to Arthur Gleckler last night and he mentioned that he had been making good use of a function he called index-list. This function takes two selector functions and a list of objects. The first selector extracts a key from each object, and the second selector extracts a value. A table is returned that maps the keys to a list of all the values that were associated with that key.

I had to laugh. I had written the same function a few month back. I called it collate.

Here is Arthur’s version in Scheme:

(define (index-list elements table choose-data choose-key)
  "Given a hash table ‘table’, walk a list of ‘elements’ E, using
‘choose-key’ to extract the key K from each E and ‘choose-data’ to
extract a list of data D from each E.  Store each K in ‘table’ along
with a list of all the elements of all the D for that K."
  (do-list (e elements)
    (hash-table-update!/default
     table
     (choose-key e)
     (lambda (previous) (append (choose-data e) previous))
     ’()))
  table)

And here is my version in Common Lisp:

(defun collate (list &key (key #’car) (test #’eql)
                               (merger (merge-adjoin :test #’eql)) (default nil))
  (let ((table (make-hash-table :test test)))
    (dolist (element list table)
      (let ((key (funcall key element)))
        (setf (gethash key table)
              (funcall merger (gethash key table default) element))))))

So how do they differ?

  • Arthur’s version takes the hash table as a parameter. This allows the caller to control the hash table’s properties. My version creates a hash table using the test parameter, which defaults to eql.
  • Arthur’s version uses choose-key to extract the key from each element. My version uses key, which is a keyword parameter defaulting to car. My choice was driven by the convention of Common Lisp sequence functions to take a :key parameter.
  • Arthur’s version uses a default value of ’() for the entries in the hash table. My version uses the :default keyword argument that defaults to ’().
  • Arthur’s version uses choose-data to extract the datum in each element. My version uses the :merger keyword argument to specify how to merge the entire element into the table. If you only want a subfield of the element, you can compose a selector function with a merger function.
  • Arthur’s version uses append to collect the data associated with each element. My version uses a merger function to merge the element into the entry in the hash table. The default merger is merge-adjoin, which uses adjoin to add the element to the list of elements associated with the key. merge-adjoin is paramterized by a test function that defaults to eql. If the test is true, the new data is not merged, so the result of (merge-adjoin #’eql) is a list with no duplicates.
  • If you instead specify a default of 0 and a merger of (lambda (existing new) (+ existing 1)) you get a histogram.
  • Another merger I make use of is merge-unique, which ensures that all copies of the data being merged are the same, raising a warning if they are not.
  • Finally, I occasionally make use of a higher-order merger called merge-list that takes a list of mergers and applies them elementwise to two lists to be merged. This allows you to create a singleton aggregate merged element where the subfields are merged using different strategies.

Like Arthur, I found this to be a very useful function. I was auditing a data set obtained from GitHub. It came in as a flat list of records of users. Each record was a list of GitHub org, GitHub ID, and SAML/SSO login. Many of our users inadvertently have multiple GitHub IDs associated with their accounts. I used my collate function to create a table that mapped SAML/SSO login to a list of all the GitHub IDs associated with that login, and the list of orgs where that mapping applies.

by Joe Marshall (noreply@blogger.com) at Wednesday, March 5, 2025

Tuesday, March 4, 2025

Andy Wingo

whippet lab notebook: on untagged mallocs

Salutations, populations. Today’s note is more of a work-in-progress than usual; I have been finally starting to look at getting Whippet into Guile, and there are some open questions.

inventory

I started by taking a look at how Guile uses the Boehm-Demers-Weiser collector‘s API, to make sure I had all my bases covered for an eventual switch to something that was not BDW. I think I have a good overview now, and have divided the parts of BDW-GC used by Guile into seven categories.

implicit uses

Firstly there are the ways in which Guile’s run-time and compiler depend on BDW-GC’s behavior, without actually using BDW-GC’s API. By this I mean principally that we assume that any reference to a GC-managed object from any thread’s stack will keep that object alive. The same goes for references originating in global variables, or static data segments more generally. Additionally, we rely on GC objects not to move: references to GC-managed objects in registers or stacks are valid across a GC boundary, even if those references are outside the GC-traced graph: all objects are pinned.

Some of these “uses” are internal to Guile’s implementation itself, and thus amenable to being changed, albeit with some effort. However some escape into the wild via Guile’s API, or, as in this case, as implicit behaviors; these are hard to change or evolve, which is why I am putting my hopes on Whippet’s mostly-marking collector, which allows for conservative roots.

defensive uses

Then there are the uses of BDW-GC’s API, not to accomplish a task, but to protect the mutator from the collector: GC_call_with_alloc_lock, explicitly enabling or disabling GC, calls to sigmask that take BDW-GC’s use of POSIX signals into account, and so on. BDW-GC can stop any thread at any time, between any two instructions; for most users is anodyne, but if ever you use weak references, things start to get really gnarly.

Of course a new collector would have its own constraints, but switching to cooperative instead of pre-emptive safepoints would be a welcome relief from this mess. On the other hand, we will require client code to explicitly mark their threads as inactive during calls in more cases, to ensure that all threads can promptly reach safepoints at all times. Swings and roundabouts?

precise tracing

Did you know that the Boehm collector allows for precise tracing? It does! It’s slow and truly gnarly, but when you need precision, precise tracing nice to have. (This is the GC_new_kind interface.) Guile uses it to mark Scheme stacks, allowing it to avoid treating unboxed locals as roots. When it loads compiled files, Guile also adds some sliced of the mapped files to the root set. These interfaces will need to change a bit in a switch to Whippet but are ultimately internal, so that’s fine.

What is not fine is that Guile allows C users to hook into precise tracing, notably via scm_smob_set_mark. This is not only the wrong interface, not allowing for copying collection, but these functions are just truly gnarly. I don’t know know what to do with them yet; are our external users ready to forgo this interface entirely? We have been working on them over time, but I am not sure.

reachability

Weak references, weak maps of various kinds: the implementation of these in terms of BDW’s API is incredibly gnarly and ultimately unsatisfying. We will be able to replace all of these with ephemerons and tables of ephemerons, which are natively supported by Whippet. The same goes with finalizers.

The same goes for constructs built on top of finalizers, such as guardians; we’ll get to reimplement these on top of nice Whippet-supplied primitives. Whippet allows for resuscitation of finalized objects, so all is good here.

misc

There is a long list of miscellanea: the interfaces to explicitly trigger GC, to get statistics, to control the number of marker threads, to initialize the GC; these will change, but all uses are internal, making it not a terribly big deal.

I should mention one API concern, which is that BDW’s state is all implicit. For example, when you go to allocate, you don’t pass the API a handle which you have obtained for your thread, and which might hold some thread-local freelists; BDW will instead load thread-local variables in its API. That’s not as efficient as it could be and Whippet goes the explicit route, so there is some additional plumbing to do.

Finally I should mention the true miscellaneous BDW-GC function: GC_free. Guile exposes it via an API, scm_gc_free. It was already vestigial and we should just remove it, as it has no sensible semantics or implementation.

allocation

That brings me to what I wanted to write about today, but am going to have to finish tomorrow: the actual allocation routines. BDW-GC provides two, essentially: GC_malloc and GC_malloc_atomic. The difference is that “atomic” allocations don’t refer to other GC-managed objects, and as such are well-suited to raw data. Otherwise you can think of atomic allocations as a pure optimization, given that BDW-GC mostly traces conservatively anyway.

From the perspective of a user of BDW-GC looking to switch away, there are two broad categories of allocations, tagged and untagged.

Tagged objects have attached metadata bits allowing their type to be inspected by the user later on. This is the happy path! We’ll be able to write a gc_trace_object function that takes any object, does a switch on, say, some bits in the first word, dispatching to type-specific tracing code. As long as the object is sufficiently initialized by the time the next safepoint comes around, we’re good, and given cooperative safepoints, the compiler should be able to ensure this invariant.

Then there are untagged allocations. Generally speaking, these are of two kinds: temporary and auxiliary. An example of a temporary allocation would be growable storage used by a C run-time routine, perhaps as an unbounded-sized alternative to alloca. Guile uses these a fair amount, as they compose well with non-local control flow as occurring for example in exception handling.

An auxiliary allocation on the other hand might be a data structure only referred to by the internals of a tagged object, but which itself never escapes to Scheme, so you never need to inquire about its type; it’s convenient to have the lifetimes of these values managed by the GC, and when desired to have the GC automatically trace their contents. Some of these should just be folded into the allocations of the tagged objects themselves, to avoid pointer-chasing. Others are harder to change, notably for mutable objects. And the trouble is that for external users of scm_gc_malloc, I fear that we won’t be able to migrate them over, as we don’t know whether they are making tagged mallocs or not.

what is to be done?

One conventional way to handle untagged allocations is to manage to fit your data into other tagged data structures; V8 does this in many places with instances of FixedArray, for example, and Guile should do more of this. Otherwise, you make new tagged data types. In either case, all auxiliary data should be tagged.

I think there may be an alternative, which would be just to support the equivalent of untagged GC_malloc and GC_malloc_atomic; but for that, I am out of time today, so type at y’all tomorrow. Happy hacking!

by Andy Wingo at Tuesday, March 4, 2025

Sunday, March 2, 2025

The Racket Blog

Racket v8.16

posted by Stephen De Gabrielle


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

As of this release:

Thank you

The following people contributed to this release:

a11ce, Alex Knauth, Alexander Shopov, Alexis King, Andrew Mauer-Oats, Anthony Carrico, Bert De Ketelaere, Bob Burger, Bogdan Popa, D. Ben Knoble, David Van Horn, Gustavo Massaccesi, halfminami, Hao Zhang, Jacqueline Firth, Jinser Kafka, JJ, John Clements, Jörgen Brandt, Kraskaska, lafirest, Laurent Orseau, lukejianu, Marc Nieper-Wißkirchen, Matthew Flatt, Matthias Felleisen, mehbark, Mike Sperber, Noah Ma, Onorio Catenacci, Oscar Waddell, Pavel Panchekha, payneca, Robby Findler, Sam Phillips, Sam Tobin-Hochstadt, Shu-Hung You, Sorawee Porncharoenwase, Stephen De Gabrielle, Wing Hei Chan, Yi Cao, and ZhangHao.

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.16 is now available from https://download.racket-lang.org

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

by John Clements, Stephen De Gabrielle at Sunday, March 2, 2025

Thursday, February 20, 2025

LIPS Scheme Blog

Internals: Finite-State Machine Lexer

The first version of LIPS Scheme had regex based tokenizer. It was using a single regex to split the input string into tokens. In this article, I will show the internals of the new Lexer in LIPS Scheme.


see the rest of the article

Thursday, February 20, 2025

Monday, February 10, 2025

Andy Wingo

whippet at fosdem

Hey all, the video of my FOSDEM talk on Whippet is up:

Slides here, if that’s your thing.

I ended the talk with some puzzling results around generational collection, which prompted yesterday’s post. I don’t have a firm answer yet. Or rather, perhaps for the splay benchmark, it is to be expected that a generational GC is not great; but there are other benchmarks that also show suboptimal throughput in generational configurations. Surely it is some tuning issue; I’ll be looking into it.

Happy hacking!

by Andy Wingo at Monday, February 10, 2025