• A number of translations were updated, including Albanian, Arabic, Belarusian, Bulgarian, Chinese (Simplified Han script), Chinese (Traditional Han script), Czech, Dutch, French, German, Hindi, Japanese, Norwegian Bokm l, Polish, Portuguese, Russian, Spanish, Swedish, Telugu, Turkish, and Ukrainian.
• Fix cases where a package or service is used by multiple apps, so that disabling or uninstalling one app does not affect the other app.
• When uninstalling an app, purge the packages, to remove all data and configuration.
• For configuration files that need to be placed into folders owned by other packages, we now install these files under /usr/share/freedombox/etc/, and create a symbolic link to the other package s configuration folder. This prevents the files being lost when other packages are purged.
• Add an action to re-run the setup process for an app. This can fix many of the possible issues that occur.
• Various improvements related to the "force upgrade" feature, which handles upgrading packages with conffile prompts.
• Fix install/uninstall issues for apps that use MySQL database (WordPress, Zoph).
• Improve handling of file uploads (Backups, Feather Wiki, Kiwix).
• Switch to Bootstrap 5 front-end framework.
• Removed I2P app, since the i2p package was removed from Debian.
• Various user interface changes, including:
  • Add tags for apps, replacing short descriptions. When a tag is clicked, search and filter for one or multiple tags.
  • Organize the System page into sections.
  • Add breadcrumbs for page hierarchy navigation.
  • Add next steps page after initial FreedomBox setup.

• Add diagnostic checks to detect common errors.
• Add diagnostics daily run, with notifications about failures.
• Add Repair action for failed diagnostics, and option for automatic repairs.

• Move hostname and domain name configuration to Names page.
• Support multiple static and/or dynamic domains.
• Use systemd-resolved for DNS resolution.
• Add options for setting global DNS-over-TLS and DNSSEC preferences.

• Add more options for IPv6 configuration method.
• Overhaul Wi-Fi networks scan page.

• Add option to disable fallback DNS servers.
• Add option to set the lookup URL to get the public IP address of the FreedomBox.

• Delete or move home folder when user is deleted or renamed.
• When a user is inactivated, also inactivate the user in LDAP.

• This BitTorrent client app should be available once again in Debian 13 "trixie".

• Turn on Message Archive Management setting by default, to help various XMPP clients use it.

• Add new app for note taking.
• This app lives in a single HTML file, which is downloaded from the FreedomBox website.

• Disable snapshot feature, due to high resource use.
• Various fixes for repository operations.

• Add new app to provide a graphical desktop environment.
• Requires a monitor, keyboard, and mouse to be physically connected to the FreedomBox.
• Not suitable for low-end hardware.

• Disable discussion pages by default for new wiki/blog, to avoid spam.

• Add new app for offline reader of Wikipedia and other sites.

• Add an option for token-based registration verification, so that users signing up for new accounts will need to provide a token during account registration.

• Allow setting the site language code.
• Increase PHP maximum execution time to 100 seconds.

• Add media directory selection form.

• Add new app for reading news from RSS/ATOM feeds.

• Add new app for file sync and collaboration.
• Uses a Docker container maintained by the Nextcloud community. The container is downloaded from FreedomBox container registry.

• Renew server/client certificates, and set expiry to 10 years.

• Fix DKIM signing.
• Show DNS entries for all domains.

• Add new app for censorship resistance, separate from Shadowsocks Client app.

• Add new app for groupware (webmail, calendar, tasks, and contacts).
• Works with Postfix/Dovecot email server app.

• Add new app for note taking.
• This app lives in a single HTML file, which is downloaded from the FreedomBox website.

• Add new app for Tor SOCKS proxy, separate from Tor app.

• Allow remote user interfaces to connect.

Offline PKI backed up by 3 YubiKeys

• 2 YubiKeys for the root CA (with a 20-year validity),
• 1 YubiKey for the intermediate CA (with a 5-year validity), and
• 1 Libre Computer Sweet Potato as an air-gapped SBC.

The software part offline-pki is a small Python application to manage an offline PKI. It relies on yubikey-manager to manage YubiKeys and cryptography for cryptographic operations not executed on the YubiKeys. The application has some opinionated design choices. Notably, the cryptography is hard-coded to use NIST P-384 elliptic curve. The first step is to reset all your YubiKeys:

$ offline-pki yubikey reset
This will reset the connected YubiKey. Are you sure? [y/N]: y
New PIN code:
Repeat for confirmation:
New PUK code:
Repeat for confirmation:
New management key ('.' to generate a random one):
WARNING[pki-yubikey] Using random management key: e8ffdce07a4e3bd5c0d803aa3948a9c36cfb86ed5a2d5cf533e97b088ae9e629
INFO[pki-yubikey]  0: Yubico YubiKey OTP+FIDO+CCID 00 00
INFO[pki-yubikey] SN: 23854514
INFO[yubikit.management] Device config written
INFO[yubikit.piv] PIV application data reset performed
INFO[yubikit.piv] Management key set
INFO[yubikit.piv] New PUK set
INFO[yubikit.piv] New PIN set
INFO[pki-yubikey] YubiKey reset successful!

Then, generate the root CA and create as many copies as you want:

$ offline-pki certificate root --permitted example.com
Management key for Root X:
Plug YubiKey "Root X"...
INFO[pki-yubikey]  0: Yubico YubiKey CCID 00 00
INFO[pki-yubikey] SN: 23854514
INFO[yubikit.piv] Data written to object slot 0x5fc10a
INFO[yubikit.piv] Certificate written to slot 9C (SIGNATURE), compression=True
INFO[yubikit.piv] Private key imported in slot 9C (SIGNATURE) of type ECCP384
Copy root certificate to another YubiKey? [y/N]: y
Plug YubiKey "Root X"...
INFO[pki-yubikey]  0: Yubico YubiKey CCID 00 00
INFO[pki-yubikey] SN: 23854514
INFO[yubikit.piv] Data written to object slot 0x5fc10a
INFO[yubikit.piv] Certificate written to slot 9C (SIGNATURE), compression=True
INFO[yubikit.piv] Private key imported in slot 9C (SIGNATURE) of type ECCP384
Copy root certificate to another YubiKey? [y/N]: n

You can inspect the result:

$ offline-pki yubikey info
INFO[pki-yubikey]  0: Yubico YubiKey CCID 00 00
INFO[pki-yubikey] SN: 23854514
INFO[pki-yubikey] Slot 9C (SIGNATURE):
INFO[pki-yubikey]   Private key type: ECCP384
INFO[pki-yubikey]   Public key:
INFO[pki-yubikey]     Algorithm:  secp384r1
INFO[pki-yubikey]     Issuer:     CN=Root CA
INFO[pki-yubikey]     Subject:    CN=Root CA
INFO[pki-yubikey]     Serial:     1
INFO[pki-yubikey]     Not before: 2024-07-05T18:17:19+00:00
INFO[pki-yubikey]     Not after:  2044-06-30T18:17:19+00:00
INFO[pki-yubikey]     PEM:
-----BEGIN CERTIFICATE-----
MIIBcjCB+aADAgECAgEBMAoGCCqGSM49BAMDMBIxEDAOBgNVBAMMB1Jvb3QgQ0Ew
HhcNMjQwNzA1MTgxNzE5WhcNNDQwNjMwMTgxNzE5WjASMRAwDgYDVQQDDAdSb290
IENBMHYwEAYHKoZIzj0CAQYFK4EEACIDYgAERg3Vir6cpEtB8Vgo5cAyBTkku/4w
kXvhWlYZysz7+YzTcxIInZV6mpw61o8W+XbxZV6H6+3YHsr/IeigkK04/HJPi6+i
zU5WJHeBJMqjj2No54Nsx6ep4OtNBMa/7T9foyMwITAPBgNVHRMBAf8EBTADAQH/
MA4GA1UdDwEB/wQEAwIBhjAKBggqhkjOPQQDAwNoADBlAjEAwYKy/L8leJyiZSnn
xrY8xv8wkB9HL2TEAI6fC7gNc2bsISKFwMkyAwg+mKFKN2w7AjBRCtZKg4DZ2iUo
6c0BTXC9a3/28V5aydZj6rvx0JqbF/Ln5+RQL6wFMLoPIvCIiCU=
-----END CERTIFICATE-----

Then, you can create an intermediate certificate with offline-pki yubikey intermediate and use it to sign certificates by providing a CSR to offline-pki certificate sign. Be careful and inspect the CSR before signing it, as only the subject name can be overridden. Check the documentation for more details. Get the available options using the --help flag.

The hardware part To ensure the operations on the root and intermediate CAs are air-gapped, a cost-efficient solution is to use an ARM64 single board computer. The Libre Computer Sweet Potato SBC is a more open alternative to the well-known Raspberry Pi.¹

Libre Computer Sweet Potato SBC, powered by the AML-S905X SOC

I interact with it through an USB to TTL UART converter:

$ tio /dev/ttyUSB0
[16:40:44.546] tio v3.7
[16:40:44.546] Press ctrl-t q to quit
[16:40:44.555] Connected to /dev/ttyUSB0
GXL:BL1:9ac50e:bb16dc;FEAT:ADFC318C:0;POC:1;RCY:0;SPI:0;0.0;CHK:0;
TE: 36574
BL2 Built : 15:21:18, Aug 28 2019. gxl g1bf2b53 - luan.yuan@droid15-sz
set vcck to 1120 mv
set vddee to 1000 mv
Board ID = 4
CPU clk: 1200MHz
[ ]

The Nix glue To bring everything together, I am using Nix with a Flake providing:

• a package for the offline-pki application, with shell completion,
• a development shell, including an editable version of the offline-pki application,
• a NixOS module to setup the offline PKI, resetting the system at each boot,
• a QEMU image for testing, and
• an SD card image to be used on the Sweet Potato or another ARM64 SBC.

# Execute the application locally
nix run github:vincentbernat/offline-pki -- --help
# Run the application inside a QEMU VM
nix run github:vincentbernat/offline-pki\#qemu
# Build a SD card for the Sweet Potato or for the Raspberry Pi
nix build --system aarch64-linux github:vincentbernat/offline-pki\#sdcard.potato
nix build --system aarch64-linux github:vincentbernat/offline-pki\#sdcard.generic
# Get a development shell with the application
nix develop github:vincentbernat/offline-pki

---

1. The key for the root CA is not generated by the YubiKey. Using an air-gapped computer is all the more important. Put it in a safe with the YubiKeys when done!

• [1] https://en.wikipedia.org/wiki/Lemmy_(social_network)
• [2] https://github.com/lemmygtk/lemoa
• [3] https://github.com/theycallhermax/lemonade

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <sys/ioctl.h>
#include <unistd.h>
#include <fcntl.h>
#include <termios.h>
#include <stdint.h>
#include <sys/time.h>
static uint64_t gettimeofday_uint64()
 
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return (uint64_t) tv.tv_sec * 1000000ULL + (uint64_t) tv.tv_usec;
 
int main(int argc, char* argv[])
 
    // open the serial device, and make it as raw as possible
    const char* device = "/dev/ttyS0";
    const speed_t baud = B9600;
    int fd = open(device, O_WRONLY O_NOCTTY);
    tcflush(fd, TCIOFLUSH);
    struct termios options =  .c_iflag = IGNBRK,
                              .c_cflag = CS8   CREAD   CLOCAL ;
    cfsetspeed(&options, baud);
    tcsetattr(fd, TCSANOW, &options);
    const uint64_t T_us = (uint64_t)(1e6 / 58.);
    const uint64_t t0 = gettimeofday_uint64();
    for(int i=0; ; i++)
     
        const uint64_t t_target = t0 + T_us*i;
        const uint64_t t1       = gettimeofday_uint64();
        if(t_target > t1)
            usleep(t_target - t1);
        write(fd, &((char) '\xff' ), 1);
     
    return 0;
 

1. The usleep() doesn't wake up exactly when it should. This is subject to the Linux scheduler waking up the trigger process
2. The write() almost certainly ends up scheduling a helper task to actually write the \xFF to the hardware. This helper task is also subject to the Linux scheduler waking it up.
3. Whatever the hardware does. RS-232 doesn't give you any guarantees about byte-byte timings, so this could be an unfixable source of errors

# ls -lh /dev/ttyS0
crw-rw---- 1 root dialout 4, 64 Mar  6 18:11 /dev/ttyS0
# ls -lh /sys/dev/char/4:64/
total 0
-r--r--r-- 1 root root 4.0K Mar  6 16:51 close_delay
-r--r--r-- 1 root root 4.0K Mar  6 16:51 closing_wait
-rw-r--r-- 1 root root 4.0K Mar  6 16:51 console
-r--r--r-- 1 root root 4.0K Mar  6 16:51 custom_divisor
-r--r--r-- 1 root root 4.0K Mar  6 16:51 dev
lrwxrwxrwx 1 root root    0 Mar  6 16:51 device -> ../../../0000:00:16.3:0.0
-r--r--r-- 1 root root 4.0K Mar  6 16:51 flags
-r--r--r-- 1 root root 4.0K Mar  6 16:51 iomem_base
-r--r--r-- 1 root root 4.0K Mar  6 16:51 iomem_reg_shift
-r--r--r-- 1 root root 4.0K Mar  6 16:51 io_type
-r--r--r-- 1 root root 4.0K Mar  6 16:51 irq
-r--r--r-- 1 root root 4.0K Mar  6 16:51 line
-r--r--r-- 1 root root 4.0K Mar  6 16:51 port
drwxr-xr-x 2 root root    0 Mar  6 16:51 power
-rw-r--r-- 1 root root 4.0K Mar  6 16:51 rx_trig_bytes
lrwxrwxrwx 1 root root    0 Mar  6 16:51 subsystem -> ../../../../../../../class/tty
-r--r--r-- 1 root root 4.0K Mar  6 16:51 type
-r--r--r-- 1 root root 4.0K Mar  6 16:51 uartclk
-rw-r--r-- 1 root root 4.0K Mar  6 16:51 uevent
-r--r--r-- 1 root root 4.0K Mar  6 16:51 xmit_fifo_size

# bpftrace -e 'k:*tty* /comm=="trigger"/
                 printf("%d %d %s\n",pid,tid,probe);  
               t:sched:sched_wakeup /comm=="trigger"/
                 printf("switching to %s(%d); current backtrace:", args.comm, args.pid); print(kstack());   '
...
3397345 3397345 kprobe:tty_ioctl
3397345 3397345 kprobe:tty_check_change
3397345 3397345 kprobe:__tty_check_change
3397345 3397345 kprobe:tty_wait_until_sent
3397345 3397345 kprobe:tty_write
3397345 3397345 kprobe:file_tty_write.isra.0
3397345 3397345 kprobe:tty_ldisc_ref_wait
3397345 3397345 kprobe:n_tty_write
3397345 3397345 kprobe:tty_hung_up_p
switching to kworker/0:1(3400169); current backtrace:
        ttwu_do_activate+268
        ttwu_do_activate+268
        try_to_wake_up+605
        kick_pool+92
        __queue_work.part.0+582
        queue_work_on+101
        rpm_resume+1398
        __pm_runtime_resume+75
        __uart_start+85
        uart_write+150
        n_tty_write+1012
        file_tty_write.isra.0+373
        vfs_write+656
        ksys_write+109
        do_syscall_64+130
        entry_SYSCALL_64_after_hwframe+118
3397345 3397345 kprobe:tty_update_time
3397345 3397345 kprobe:tty_ldisc_deref
... repeated with each pulse ...

pulserate=58
sudo zsh -c \
  '( echo "# dt_write_ns dt_task_latency_ns";
     bpftrace -q -e "k:vfs_write /comm==\"trigger\" && arg2==1/
                      \$t=nsecs(); if(@t0)   @dt_write = \$t-@t0;   @t0=\$t; 
                     k:serial8250_tx_chars /@dt_write/
                      \$t=nsecs(); printf(\"%d %d\\n\", @dt_write, \$t-@t0); "
   )' \
  vnl-filter                  \
    --stream -p dt_write_ms="dt_write_ns/1e6 - 1e3/$pulserate",dt_task_latency_ms=dt_task_latency_ns/1e6 \
  feedgnuplot  \
    --stream   \
    --lines    \
    --points   \
    --xlen 200 \
    --vnl      \
    --autolegend \
    --xlabel 'Pulse index' \
    --ylabel 'Latency (ms)'

• The offset from 58Hz of when each write() call happens. This shows effect #1 from above: how promptly the trigger process wakes up
• The latency of the helper task. This shows effect #2 above.

sudo chrt -p 90  pidof trigger 

taskset -c 0 ./trigger 58
pgrep -f kworker/0   while   read pid     sudo chrt -p 90 $pid  

samplerate=500000;
pulserate=58.;
sigrok-cli -c samplerate=$samplerate -O csv --continuous -C D1 \
  mawk -Winteractive  \
    "prev_logic==0 && \$0==1 \
       
       iedge = NR;
       if(prev_iedge)
        
         di = iedge -prev_iedge;
         dt = di/$samplerate;
         print(dt*1000);
        
       prev_iedge = iedge;
      
      
       prev_logic=\$0;
       "   feedgnuplot --stream --ylabel 'Period (ms)' --equation "1000./$pulserate title \"True $ pulserate Hz period\""

Debian Contributions: 2025-02 Contributing to Debian is part of Freexian s mission. This article covers the latest achievements of Freexian and their collaborators. All of this is made possible by organizations subscribing to our Long Term Support contracts and consulting services.

Debian.Social administration, by Stefano Rivera Over the last year, the Debian.social services outgrew the infrastructure that was supporting them. The matrix bridge in particular was hosted on a cloud instance backed by a large expensive storage volume. Debian.CH rented a new large physical server to host all these instances, earlier this year. Stefano set up Incus on the new physical machine and migrated all the old debian.social LXC Containers, libvirt VMs, and cloud instances into Incus-managed LXC containers. Stefano set up Prometheus monitoring and alerts for the new infrastructure and a Grafana dashboard. The current stack of debian.social services seem to comfortably fit on the new machine, with good room to grow.

DebConf 25, by Santiago Ruano Rinc n and Stefano Rivera DebConf 25 preparations continue. The team is currently finalizing a budget. Stefano helped to review the current budget proposals and suggest approaches for balancing it. Stefano installed a Zammad instance to organize queries from attendees, for the registration and visa teams. Santiago continued discussions with possible caterers so we can have options for the different diet requirements and that could fit into the DebConf budget. Also, in collaboration with Anupa, Santiago pushed the first draft changes to document the venue information in the DebConf 25 website and how to get to Brest.

Time-based test failure in requests, by Colin Watson Colin fixed a fun bug in the Python requests package. Santiago Vila has been running tests of what happens when Debian packages are built on a system in which time has been artificially set to somewhere around the end of the support period for the next Debian release, in order to make it easier to do things like issuing security updates for the lifetime of that release. In this case, the failure indicated an expired test certificate, and since the repository already helpfully included scripts to regenerate those certificates, it seemed natural to try regenerating them just before running tests. However, this failed for more obscure reasons and Colin spent some time investigating. This turned out to be because the test CA was missing the CA constraint and so recent versions of OpenSSL reject it; Colin sent a pull request to fix this.

Priority list for outdated packages, by Santiago Ruano Rinc n Santiago started a discussion on debian-devel about packages that have a history of security issues and that are outdated regarding new upstream releases. The goal of the mentioned effort is to have a prioritized list of packages needing some work, from a security point of view. Moreover, the aim of publicly sharing the list of packages with the Debian Developers community is to make it easier to look at the packages maintained by teams, or even other maintainers where help could be welcome. Santiago is planning to take into account the feedback provided in debian-devel and to propose a tooling that could help to regularly bring collective awareness of these packages.

Miscellaneous contributions

• Carles worked on English to Catalan po-debconf translations: reviewed translations, created merge requests and followed up with developers for more than 30 packages using po-debconf-manager.
• Carles helped users, fixed bugs and implemented downloading updated templates on po-debconf-manager.
• Carles packaged a new upstream version of python-pyaarlo.
• Carles improved reproducibility of qnetload (now reported as reproducible) and simplemonitor (followed up with upstream and pending update of Debian package).
• Carles collaborated with debian-history package: fixed FTBFS from master branch, enabled salsa-ci and investigated reproducibility.
• Emilio improved support for automatically marking CVEs as NOT-FOR-US in the security-tracker, closing #1073012.
• Emilio updated xorg-server and xwayland in unstable, fixing the last round of security vulnerabilities.
• Stefano prepared a few PyPy and cPython uploads, and started the python3.13-only transition.
• Helmut Grohne sent patches for 24 cross build failures.
• Helmut fixed two problems in the Debian /usr-merge analysis tool. In one instance, it would overmatch Debian bugs to issues and in another it would fail to recognize Pre-Depends as a conflict mechanism.
• Helmut attempted making rebootstrap work for gcc-15 with limited success as very many packages FTBFS with gcc-15 due to using function declarations without arguments.
• Helmut provided a change to the security-tracker that would pre-compute /data/json during database updates rather than on demand resulting in a reduced response time.
• Colin uploaded OpenSSH security updates for testing/unstable, bookworm, bullseye, buster, and stretch.
• Colin fixed upstream monitoring for 26 Python packages, and upgraded 54 packages (mostly Python-related, but also PuTTY) to new upstream versions.
• Colin updated python-django in bookworm-backports to 4.2.18 (issuing BSA-121), and added new backports of python-django-dynamic-fixture and python-django-pgtrigger, all of which are dependencies of debusine.
• Thorsten Alteholz finally managed to upload hplip to fix two release critical and some normal bugs. The next step in March would be to upload the latest version of hplip.
• Faidon updated crun in unstable & trixie, resolving a long-standing request of enabling criu support and thus enabling podman with checkpoint/restore functionality (With gratitude to Salvatore Bonaccorso and Reinhard Tartler for the cooperation and collaboration).
• Faidon uploaded a number of packages (librdkafka, libmaxminddb, python-maxminddb, lowdown, tox, tox-uv, pyproject-api, xiccd and gdnsd) bringing them up to date with new upstream releases, resolving various bugs.
• Lucas Kanashiro uploaded some ruby packages involved in the Rails 7 transition with new upstream releases.
• Lucas triaged a ruby3.1 bug (#1092595)) and prepared a fix for the next stable release update.
• Lucas set up the needed wiki pages and updated the Debian Project status in the Outreachy portal, in order to send out a call for projects and mentors for the next round of Outreachy.
• Anupa joined Santiago to prepare a list of companies to contact via LinkedIn for DebConf 25 sponsorship.
• Anupa printed Debian stickers and sponsorship brochures, flyers for DebConf 25 to be distributed at FOSS ASIA summit 2025.
• Anupa participated in the Debian publicity team meeting and discussed the upcoming events and tasks.
• Rapha l packaged zim 0.76.1 and integrated an upstream patch for another regression that he reported.
• Rapha l worked with the Debian System Administrators for tracker.debian.org to better cope with gmail s requirement for mails to be authenticated.

Background When defining a function recursively in Lean that has nested recursion, e.g. a recusive call that is in the argument to a higher-order function like List.map, then extra attention used to be necessary so that Lean can see that xs.map applies its argument only elements of the list xs. The usual idiom is to write xs.attach.map instead, where List.attach attaches to the list elements a proof that they are in that list. You can read more about this my Lean blog post on recursive definitions and our new shiny reference manual, look for Example Nested Recursion in Higher-order Functions . To make this step less tedious I taught Lean to automatically rewrite xs.map to xs.attach.map (where suitable) within the construction of well-founded recursion, so that nested recursion just works (issue #5471). We already do such a rewriting to change if c then else to the dependent if h : c then else , but the attach-introduction is much more ambitious (the rewrites are not definitionally equal, there are higher-order arguments etc.) Rewriting the terms in a way that we can still prove the connection later when creating the equational lemmas is hairy at best. Also, we want the whole machinery to be extensible by the user, setting up their own higher order functions to add more facts to the context of the termination proof. I implemented it like this (PR #6744) and it ships with 4.18.0, but in the course of this work I thought about a quite different and maybe better way to do this, and well-founded recursion in general:

A simpler fix Recall that to use WellFounded.fix

WellFounded.fix : (hwf : WellFounded r) (F : (x :  )   ((y :  )   r y x   C y)   C x) (x :  ) : C x

we have to rewrite the functorial of the recursive function, which naturally has type

F : ((y :  )    C y)   ((x :  )   C x)

to the one above, where all recursive calls take the termination proof r y x. This is a fairly hairy operation, mangling the type of matcher s motives and whatnot. Things are simpler for recursive definitions using the new partial_fixpoint machinery, where we use Lean.Order.fix

Lean.Order.fix : [CCPO  ] (F :      ) (hmono : monotone F) :  

so the functorial s type is unmodified (here will be ((x : ) C x)), and everything else is in the propositional side-condition montone F. For this predicate we have a syntax-guided compositional tactic, and it s easily extensible, e.g. by

theorem monotone_mapM (f :         m  ) (xs : List  ) (hmono : monotone f) :
    monotone (fun x => xs.mapM (f x)) 

Once given, we don t care about the content of that proof. In particular proving the unfolding theorem only deals with the unmodified F that closely matches the function definition as written by the user. Much simpler!

Isabelle has it easier Isabelle also supports well-founded recursion, and has great support for nested recursion. And it s much simpler! There, all you have to do to make nested recursion work is to define a congruence lemma of the form, for List.map something like our List.map_congr_left

List.map_congr_left : (h :   a   l, f a = g a) :
    List.map f l = List.map g l

This is because in Isabelle, too, the termination proofs is a side-condition that essentially states the functorial F calls its argument f only on smaller arguments .

Can we have it easy, too? I had wished we could do the same in Lean for a while, but that form of congruence lemma just isn t strong enough for us. But maybe there is a way to do it, using an existential to give a witness that F can alternatively implemented using the more restrictive argument. The following callsOn P F predicate can express that F calls its higher-order argument only on arguments that satisfy the predicate P:

section setup
variable   : Sort u 
variable   :     Sort v 
variable   : Sort w 
def callsOn (P :     Prop) (F : (  y,   y)    ) :=
    (F': (  y, P y     y)    ),   f, F' (fun y _ => f y) = F f
variable (R :         Prop)
variable (F : (  y,   y)   (  x,   x))
local infix:50 "   " => R
def recursesVia : Prop :=   x, callsOn (    x) (fun f => F f x)
noncomputable def fix (wf : WellFounded R) (h : recursesVia R F) : (  x,   x) :=
  wf.fix (fun x => (h x).choose)
def fix_eq (wf : WellFounded R) h x :
    fix R F wf h x = F (fix R F wf h) x := by
  unfold fix
  rw [wf.fix_eq]
  apply (h x).choose_spec

This allows nice compositional lemmas to discharge callsOn predicates:

theorem callsOn_base (y :  ) (hy : P y) :
    callsOn P (fun (f :   x,   x) => f y) := by
  exists fun f => f y hy
  intros; rfl
@[simp]
theorem callsOn_const (x :  ) :
    callsOn P (fun (_ :   x,   x) => x) :=
   fun _ => x, fun _ => rfl 
theorem callsOn_app
      : Sort uu    : Sort ww 
    (F  :  (  y,   y)        ) -- can this also support dependent types?
    (F  :  (  y,   y)    )
    (h  : callsOn P F )
    (h  : callsOn P F ) :
    callsOn P (fun f => F  f (F  f)) := by
  obtain  F ', h  := h 
  obtain  F ', h  := h 
  exists (fun f => F ' f (F ' f))
  intros; simp_all
theorem callsOn_lam
      : Sort uu 
    (F :     (  y,   y)    ) -- can this also support dependent types?
    (h :   x, callsOn P (F x)) :
    callsOn P (fun f x => F x f) := by
  exists (fun f x => (h x).choose f)
  intro f
  ext x
  apply (h x).choose_spec
theorem callsOn_app2
      : Sort uu    : Sort ww 
    (g :          )
    (F  :  (  y,   y)    ) -- can this also support dependent types?
    (F  :  (  y,   y)    )
    (h  : callsOn P F )
    (h  : callsOn P F ) :
    callsOn P (fun f => g (F  f) (F  f)) := by
  apply_rules [callsOn_app, callsOn_const]

With this setup, we can have the following, possibly user-defined, lemma expressing that List.map calls its arguments only on elements of the list:

theorem callsOn_map (  : Type uu) (  : Type ww)
    (P :     Prop) (F : (  y,   y)        ) (xs : List  )
    (h :   x, x   xs   callsOn P (fun f => F f x)) :
    callsOn P (fun f => xs.map (fun x => F f x)) := by
  suffices callsOn P (fun f => xs.attach.map (fun  x, h  => F f x)) by
    simpa
  apply callsOn_app
    apply callsOn_app
      apply callsOn_const
      apply callsOn_lam
      intro  x', hx' 
      dsimp
      exact (h x' hx')
    apply callsOn_const
end setup

So here is the (manual) construction of a nested map for trees:

section examples
structure Tree (  : Type u) where
  val :  
  cs : List (Tree  )
-- essentially
-- def Tree.map (f :      ) : Tree     Tree   :=
--   fun t =>  f t.val, t.cs.map Tree.map )
noncomputable def Tree.map (f :      ) : Tree     Tree   :=
  fix (sizeOf   < sizeOf  ) (fun map t =>  f t.val, t.cs.map map )
    (InvImage.wf (sizeOf  ) WellFoundedRelation.wf) <  by
  intro  v, cs 
  dsimp only
  apply callsOn_app2
    apply callsOn_const
    apply callsOn_map
    intro t' ht'
    apply callsOn_base
    -- ht' : t'   cs -- !
    --   sizeOf t' < sizeOf   val := v, cs := cs  
    decreasing_trivial
end examples

This makes me happy! All details of the construction are now contained in a proof that can proceed by a syntax-driven tactic and that s easily and (likely robustly) extensible by the user. It also means that we can share a lot of code paths (e.g. everything related to equational theorems) between well-founded recursion and partial_fixpoint. I wonder if this construction is really as powerful as our current one, or if there are certain (likely dependently typed) functions where this doesn t fit, but the above is dependent, so it looks good. With this construction, functions defined by well-founded recursion will reduce even worse in the kernel, I assume. This may be a good thing.

The cake is a lie What unfortunately kills this idea, though, is the generation of the functional induction principles, which I believe is not (easily) possible with this construction: The functional induction principle is proved by massaging F to return a proof, but since the extra assumptions (e.g. for ite or List.map) only exist in the termination proof, they are not available in F. Oh wey, how anticlimactic.

PS: Path dependencies Curiously, if we didn t have functional induction at this point yet, then very likely I d change Lean to use this construction, and then we d either not get functional induction, or it would be implemented very differently, maybe a more syntactic approach that would re-prove termination. I guess that s called path dependence.

• [DLA 4072-1] xorg-server security update to fix eight CVEs related to possible privilege escalation in X.
• [DLA 4073-1] ffmpeg security update to fix three CVEs related to out-of-bounds read, assert errors and NULL pointer dereferences. This was the second update that I announced last month.

• [ELA-1337-1] xorg-server security update to fix eight CVEs in Buster, Stretch and Jessie, related to possible privilege escalation in X.
• [ELA-882-2] amanda regression update to improve a fix for privilege escalation. This old regression was detected by Beuc during his work as FD and now finally fixed.

• hplip to fix some bugs and let hplip migrate to testing again.

• php-jshrink
• php-maxmind-web-service-common
• php-sparkline
• php-spyc

• osmocom-dahdi-linux fixing bugs
• libosmo-abis fixing more bugs

Changes in version 0.0.2 (2025-03-09)

• Updated tolerance in simple test as newer upstream nlopt change behaviour ever so slightly leading to an other spurious failure
• Numerous small and standard updates to DESCRIPTION, README.md, badges, and continuous integration setup

This post by Dirk Eddelbuettel originated on his Thinking inside the box blog. If you like this or other open-source work I do, you can now sponsor me at GitHub.

• El d a despu s de la cat strofe: Bah a volvi a amanecer destrozada, La Nueva.
• En 20 im genes, el inmenso da o que provoc el temporal en Bah a, La Nueva.
• Drone footage of the nearby stream, which now seems a river, Instagram.
• Drone footage of the same above stream nearer the golf club and entering the city - MP4. I do not know the author, happy to give the proper credits if contacted!!!

• 06 rooms in parallel on Saturday;
• 02 auditoriums in parallel on Monday and Tuesday;
• 30 talks/BoFs of all levels;
• 05 workshops for hands-on activities;
• 09 lightning talks on general topics;
• 01 Live Electronics performance with Free Software;
• Install fest to install Debian on attendees' laptops;
• BSP (Bug Squashing Party);
• Uploads of new or updated packages.

• Total people registered: 399
• Total attendees in the event: 224

• Food: 69
• Accommodation: 20
• Travel: 18

• Youtube - Peertube
• video.debian.net And see the photos taken by several collaborators in the links below:
• Google photos
• Nextcloud

• Collabora

• Jedai.ai
• Toradex Brasil
• Globo.com
• Policorp Tecnologia

• BRDSoft - Tecnologias para TI e Telecomunica es
• EITA - Cooperativa de Trabalho Educa o, Informa o e Tecnologia para Autogest o Supporters
• ICTL - Instituto para Conserva o de Tecnologias Livres - Nazinha Alimentos
• DACOMPSI

• Projeto Debian
• Comunidade Debian Brasil
• Comunidade Debian MG
• DCC/UFMG - Departamento de Ci ncia da Computa o da Universidade Federal de Minas Gerais

Changes in version 0.2.3 (2025-03-08)

• Correct the minimum version of Rcpp to 1.0.8 (Walter Somerville)
• The package now uses Authors@R as mandated by CRAN
• Updated 'whitespace in literal' issue upsetting clang++-20
• Continuous integration updates including simpler r-ci setup

This post by Dirk Eddelbuettel originated on his Thinking inside the box blog. If you like this or other open-source work I do, you can now sponsor me at GitHub.

Changes in version 0.1.13 (2025-03-07)

• A call to std::string::erase is now guarded (Daniel)
• The package now uses Authors@R as mandated by CRAN (Dirk)
• simdjson was upgraded to version 3.12.2 (Dirk)
• Continuous integration updated to more compilers and simpler setup
• Two demos are now in inst/examples to not inflate Suggests

This post by Dirk Eddelbuettel originated on his Thinking inside the box blog. If you like this or other open-source work I do, you can now sponsor me at GitHub.