Planet Scheme

October 20, 2020

Programming Praxis

Doubled Pairs

Today’s exercise is somebody’s homework problem:

You are given an array containing positive integers, all distinct. Write a program that determines if there exist in the array any numbers such that one is double the other. For instance, in the array [1,2,3,4], the pairs 1,2 and 2,4 are both doubles, so the program should return True; in the array [1,3,5,7,9] there is no such doubled pair, so the program should return False. For extra credit, return a pair that proves the result is True, if it exists. For extra-extra credit, return all such pairs. Your program must run in linear time.

The student who asked for help realized there was a simple nested-loop solution that runs in quadratic time, but that doesn’t meet the constraints of the homework problem.

Your task is to solve all three levels of the homework problem. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at October 20, 2020 09:00 AM

October 16, 2020

GNU Guix

Announcing the first online Guix Day Conference

The Guix hackers are very happy to announce the first online Guix Day Conference on Sunday November, 22nd. This conference is open to everyone and will be held entirely online. Want to speak? Submit your proposal!

Important dates:

  1. November 6th: Deadline for talks proposal.
  2. November 14th: Deadline for releasing your pre-recorded talks.
  3. November 16th: Release of the schedule.
  4. November 22nd: Conference day!

Guix Days logo

The agenda of the day is:

  • pre-recorded talks with live question and answer sessions
  • birds of a feather (BoF) sessions
  • lightning round talks, if possible
  • hack together

There will be no presentation on the 22nd! And no registration fee.

Until November 6th: talks proposal

Propose your talks by sending them to Feel free to drop in #guix on to discuss what you would like to talk about before submitting. :)

Please describe with 10 lines or more what your proposal is about. Even if it is a BoFs topic (smaller group who want to talk about specific topics).

Once you have sent your proposal, you will be notified in the coming days whether your talk be part of the Guix Day.

Good topics include your own experience with Guix and what you feel is important to share with your other fellows, for example a non-exhaustive topic list is: installer, Maven build system, Data Service, GNU Hurd and cross-compilation, Cuirass and continuous integration, authentication, secret services, website translation, translation infrastructure,… It is a single day so we won't be able to cover all. ;-)

November 9th-14th: prepare your talk

The aim of the pre-recorded talk is to demonstrate new features, what you are hacking on, introduce the subject for easing the live question and answer sessions or BoFs. These pre-recorded talks should be 15-45 minutes long. Feel free to ask if you need help with the recording.

You are free to choose whichever storage platform you want (e.g., your own website, a PeerTube instance, a Nextcloud instance, etc.), but we will need to have access to the original file so we can publish it later on Your video must be released under a license that at least allows anyone to copy and share it, for any purpose.

You will have to release the video publicly before November 14th, so everyone has a chance to see it before the conference. If you are not able to do so (for instance your server cannot handle a huge load), you can alternatively send us a private link to the video and we will upload it on If you decide to do so, you will need to have the video ready by November 12th.

November 16th-22nd: watch the talks

Be sure to watch the pre-recorded talks before the conference. There will be no presentation on the 22nd.

November 22nd: participate

Coming soon! Stay tuned.

Code of Conduct

This online conference is an official Guix event. Therefore, the Code of Conduct applies. Please be sure to read it beforehand!

About GNU Guix

GNU Guix is a transactional package manager and an advanced distribution of the GNU system that respects user freedom. Guix can be used on top of any system running the Hurd or the Linux kernel, or it can be used as a standalone operating system distribution for i686, x86_64, ARMv7, and AArch64 machines.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. When used as a standalone GNU/Linux distribution, Guix offers a declarative, stateless approach to operating system configuration management. Guix is highly customizable and hackable through Guile programming interfaces and extensions to the Scheme language.

by Guix Hackers at October 16, 2020 12:00 AM

October 15, 2020

Joe Marshall

Apropos of Nothing

Lisp programmers are of the opinion that [] and {} are just () with delusions of grandeur.

by Joe Marshall ( at October 15, 2020 10:18 PM

October 08, 2020

GNU Guix

Childhurds and GNU/Hurd substitutes

A lot has happened since our Hello Hurd post beginning of April. No, not nearly as much as we joked on April 1st , but more than enough to share and be proud of.

Building a Hurd virtual machine

As some of you noticed, the previous hacks to build a Hurd virtual machine (VM) were removed and no longer work; using Guix you can now build a GNU/Hurd VM just like you would build a GNU/Linux VM:

guix system disk-image -t hurd-raw bare-hurd.tmpl

This cross-compiles all the relevant packages for GNU/Hurd—specifically the i586-pc-gnu triplet—and produces a VM image:


You can build it and start it from your GNU/Linux machine with this command:

qemu-system-i386 -enable-kvm -m 512 -snapshot -hda \
  $(guix system disk-image -t hurd-raw bare-hurd.tmpl)

We are using this ready-made, minimal GNU/Hurd operating system description gnu/system/examples/bare-hurd.tmpl that looks suprisingly familiar:

(use-modules (gnu) (gnu system hurd) (guix utils))
(use-service-modules ssh)
(use-package-modules ssh)

(define %hurd-os
    (inherit %hurd-default-operating-system)
    (bootloader (bootloader-configuration
                 (bootloader grub-minimal-bootloader)
                 (target "/dev/sdX")))
    (file-systems (cons (file-system
                          (device (file-system-label "my-root"))
                          (mount-point "/")
                          (type "ext2"))
    (host-name "guixygnu")
    (timezone "Europe/Amsterdam")
    (packages (cons openssh-sans-x %base-packages/hurd))
    (services (cons (service openssh-service-type
                              (openssh openssh-sans-x)
                              (use-pam? #f)
                              (port-number 2222)
                              (permit-root-login #t)
                              (allow-empty-passwords? #t)
                              (password-authentication? #t)))


and it can be customized just like a GNU/Linux operating system description. The end result is a full-blown Guix System with the Shepherd managing system services and all that—finally we can run herd on the Hurd.

A lot of things had to be in place to support this, we worked on

counting some ~200 patches by ten people over six months; including generic cross-compilation fixes and support, and Hurd fixes and support.

Also, we finished the passive translator settings over extended attributes (xattrs) for the Hurd and for Linux.

You may notice that we are using the new disk-image command rather than the old vm-image. One of the big hurdles in producing a VM image was the way Guix produces VM images: it would run a target QEMU, e.g. qemu-arm. That does not work for the Hurd, as there is no qemu-hurd. Without going into the hairy details, when Ludo and Janneke were—three patch sets, 50 messages and 13 days later—almost ready to give up, Mathieu came to the rescue with his brand-new implementation of the disk-image command. At the time, Hurd work was done on the wip-hurd branch and the disk-image work on wip-disk-image. Soon after, Mathieu proposed an explosive mix of the two branches; we managed to create the first Hurd system that really felt like Guix System.

The new implementation of the disk-image command was followed by the introduction of an --image-type or -t option. This option allows to produce disk images targeting different supports. The hurd-raw and hurd-qcow2 image types, producing respectively a raw Hurd disk-image and a Hurd QCOW2 disk-image were introduced. They can be used this way:

guix system disk-image -t hurd-raw bare-hurd.tmpl
guix system disk-image -t hurd-qcow2 bare-hurd.tmpl

This mechanism providing much more flexibility in the Guix System image generation will be described in a future blog post.

We also offer downloads of continuously built (actually cross-built) Guix System on GNU/Hurd (~350 MiB).


While amazing to be able to just run the Hurd in a VM, development without substitutes is a real pain; a Guix system needs substitutes. How to go about that? We have a build farm but currently Hurd only runs on ancient hardware: not an option. We need a machine running Guix/Hurd to offload Hurd build jobs to.

The proposed solution was to automate the building and running of a Guix VM into a new Guix service: the so-called hurd-vm or childhurd service. We would add something like:

(service hurd-vm-service-type)

to a couple of our build nodes to add a hird of virtual Hurd machines to our build farm.

The Childhurd service

The Hurd—being based on a microkernel—has some beautiful built-in "virtualization" possibilites that have their own naming: neighborhurds, subhurds. Similarly, we are adding childhurds to this mix: a childhurd is a GNU/Hurd VM running on GNU/Linux and managed by Guix.

When you are running Guix System, building a Hurd VM manually is no longer necessary. Just add the hurd-vm service to your operating system description:

(service hurd-vm-service-type
          (disk-size (* 12 (expt 2 30))) ;12GiB
          (memory-size 1024)))           ; 1GiB

and this will build a childhurd for you when you reconfigure your system. This childhurd can be stopped and started just like any other service:

herd stop hurd-vm
herd start childhurd

(childhurd is an alias for hurd-vm).


This Hurd is fully operational

It is highly addictive.

Having shaved this yak, let’s not lose sight that our initial goal was to offload builds to those GNU/Hurd VMs. The childhurd service does all the heavy lifting. To offload from GNU/Linux to my childhurd, I added this to my /etc/guix/machines.scm:

  (name "localhost")
  (systems (list "i586-gnu"))
  (host-key "ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIHZsrZ63zs+AhWbVJgYq6j1h2rgQGrWKCokpR2/Q/Jzy root@guixygnu")
  (port 10022)  ;the Hurd VM has SSH listening on that port
  (user "root")
  (private-key "/home/janneke/.ssh/id_rsa_childhurd"))

That can be used to transparently offload builds from GNU/Linux to the childhurd:

$ uname -o
$ guix build hello -s i586-gnu
The following derivation will be built:
guix offload: sending 1 store item (12 MiB) to 'localhost'...
offloading '/gnu/store/jqdvjhcxxnbq370y8i2c973c9zfiqrgl-hello-2.10.drv' to 'localhost'...
$ file -L $(guix build hello -s i586-gnu)/bin/hello
/gnu/store/803q5wapfnmr91ag8d9dzwabkbdxz3ay-hello-2.10/bin/hello: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /gnu/store/9vs3gkp6svam82zw7vjlml7iiarcs11c-glibc-2.31/lib/, for GNU/Hurd 0.0.0, not stripped


Hurd substitutes

Last Friday we produced the very first GNU Hello substitute for the Hurd:

StorePath: /gnu/store/803q5wapfnmr91ag8d9dzwabkbdxz3ay-hello-2.10
URL: nar/gzip/803q5wapfnmr91ag8d9dzwabkbdxz3ay-hello-2.10
Compression: gzip
FileSize: 61822
URL: nar/lzip/803q5wapfnmr91ag8d9dzwabkbdxz3ay-hello-2.10
Compression: lzip
FileSize: 52887
NarHash: sha256:0g4k1kppjs5148ynm4zw4x1kpaby67npc3ws6s7y7hf0il1cgryk
NarSize: 204328
References: 803q5wapfnmr91ag8d9dzwabkbdxz3ay-hello-2.10 9vs3gkp6svam82zw7vjlml7iiarcs11c-glibc-2.31 bwvd5338kfm0vsc4i9xvh48vdxr5ywrz-gcc-7.5.0-lib
System: i586-gnu
Deriver: jqdvjhcxxnbq370y8i2c973c9zfiqrgl-hello-2.10.drv

For development, porting and fixing of packages, you can use a Childhurd configuration like this:

(use-modules (srfi srfi-1) (guix packages) (guix records))
(use-package-modules base compression file gawk gdb hurd less m4 package-management)

(define guix-packages
  (filter-map input->package
              (fold alist-delete (package-direct-inputs guix)
                    '("glibc-utf8-locales" "graphviz" "po4a"))))

  (inherit %hurd-vm-operating-system)
  (users ...)
    (cons* diffutils file findutils gawk gdb-minimal git-minimal
           gnu-make grep gzip less m4 openssh-sans-x tar xz
            (delete guile-3.0 %base-packages/hurd)))))

… which allows working from a Git clone:

15:51:05 janneke@dundal:~/src/guix/master [env]
$ ssh -A janneke@childhurd
Last login: Sat Oct  3 15:31:55 2020 from
  This is the GNU Hurd.  Welcome.

janneke@childhurd ~$ git config --global url."git+ssh://".insteadOf gnu:
janneke@childhurd ~$ git clone gnu:guix
Cloning into 'guix'...
remote: Counting objects: 394436, done.
remote: Compressing objects: 100% (85728/85728), done.
remote: Total 394436 (delta 309572), reused 392294 (delta 307893)
Receiving objects: 100% (394436/394436), 137.05 MiB | 1.18 MiB/s, done.
Resolving deltas: 100% (309572/309572), done.
Updating files: 100% (2199/2199), done.

but before we continue let's first check the weather:

janneke@childhurd ~$ guix weather
computing 11079 package derivations for i586-gnu...
looking for 11521 store items on
updating substitutes from ''... 100.0%
  1.5% substitutes available (169 out of 11521)
  at least 443.3 MiB of nars (compressed)
  966.7 MiB on disk (uncompressed)
  0.012 seconds per request (142.2 seconds in total)
  81.0 requests per second

this gives an idea of how young this project is. Any day now, more Hurd substitutes will follow. Now let's configure and build Guix:

janneke@childhurd ~$ cd guix
janneke@childhurd ~/guix$ guix environment --bootstrap \
  --ad-hoc gcc-toolchain@7 libgcrypt zlib
substitute: updating substitutes from ''... 100.0%
The following derivations will be built:

66.3 MB will be downloaded
building profile with 3 packages...
janneke@childhurd ~/guix [env]$ ./bootstrap
janneke@childhurd ~/guix [env]$ ./configure --with-courage\
  --localstatedir=/var --sysconfdir=/etc
janneke@childhurd ~/guix [env]$ make
janneke@childhurd ~/guix [env]$ ./pre-inst-env guix build hello
substitute: updating substitutes from ''... 100.0%
0.1 MB will be downloaded:
substituting /gnu/store/803q5wapfnmr91ag8d9dzwabkbdxz3ay-hello-2.10...
downloading from ...
 hello-2.10  52KiB                    258KiB/s 00:00 [##################] 100.0%


just like we are used to do…almost. We are using --bootstrap and a targeted --ad-hoc to avoid dependencies like libx11, python-minimal, and other packages that do not build yet.

Isolated build environments

To help achieve reproducible builds, Guix builds packages in isolated build environments: build environments contain nothing but the inputs explicitly declared in the package definition—not even /bin/sh. Build environments also lack network access. On GNU/Linux this is achieved by running builds in separate namespaces. Besides, the environment contains device nodes and “special” file systems that are usually expected to be available: /dev/null, /dev/pts, /dev/shm, /proc, the loopback networking device, and so on. (The exact contents are documented.)

On GNU/Linux, these special files and file systems are implemented by the kernel. Guix only cares about user-land software, meaning that these devices “leak” from the host kernel instead of being an explicit “input” of derivations, but that’s OK, that’s the deal: the kernel and hardware are considered outside of Guix’s control.

What about GNU/Hurd, though? In GNU/Hurd, /dev/null, a Linux-compatible /proc, the TCP/IP stack necessary to implement the loopback device, and even support for pipes are all implemented in user-land: writing to /dev/null amounts to talking to the /hurd/null service (or translator), operations on AF_INET sockets translate to remote procedure calls (RPCs) to /servers/socket/2, which the /hurd/pfinet program listens to, and so on.

That raises an interesting question: what should the build environment contain on GNU/Hurd? So far our GNU/Hurd builds were made in non-isolated environments; we have just started implementing support for isolated builds but we’ll have to answer that question first. If we stick to our approach—every piece of user-land software must be an explicit input of the build process—then code that implements TCP/IP, /dev/null, or even pipe should be an explicit input of any build process that needs those facilities.

This principled approach can push the notion of controlled, reproducible build environments to a whole new level. For example, we’ve had cases where the choice of the root file system—e.g., ext4 vs. Btrfs—has an observable effect on software behavior, leading to concrete issues such as test failures in one case and not in the other. On GNU/Hurd, build processes could run their own root file system, doing away with this kind of discrepancy.

On the other hand, there are practical issues that cannot be ignored: virtually all build processes need these facilities so they’ll need to be set up one way or another. Also, one could argue that things like /dev/null have a well-defined interface that’s set in stone and that, consequently, how they’re implemented does not matter at all. Can we say the same of the TCP/IP stack though? Maybe not. A line needs to be drawn somewhere.

We have yet to decide where to draw the line and to precisely define what the build environment contains on GNU/Hurd. These questions are closely related to bootstrapping issues we notably discussed at the 2019 Reproducible Builds Summit. Tricky, but exciting.

What's next?

In an earlier post we tried to answer the question “Why bother with the Hurd anyway?” An obvious question because it is all too easy to get discouraged, to downplay or underestimate the potential social impact of GNU and the Hurd.

We tried to make Hurd development as easy and as pleasant as we could. As you have seen, things start to work pretty nicely and there is still plenty of work to do in Guix. But in a way this is “merely packaging” the amazing work of others. Some of the real work that needs to be done and which is being discussed and is in progress right now includes:

All these tasks look daunting, and indeed that’s a lot of work ahead. But the development environment is certainly an advantage. Take an example: surely anyone who’s hacked on device drivers or file systems before would have loved to be able to GDB into the code, restart it, add breakpoints and so on—that’s exactly the experience that the Hurd offers. As for Guix, it will make it easy to test changes to the micro-kernel and to the Hurd servers, and that too has the potential to speed up development and make it a very nice experience.

Join #guix and #hurd on or the mailing lists and get involved!

About GNU Guix

GNU Guix is a transactional package manager and an advanced distribution of the GNU system that respects user freedom. Guix can be used on top of any system running the Hurd or the Linux kernel, or it can be used as a standalone operating system distribution for i686, x86_64, ARMv7, and AArch64 machines.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. When used as a standalone GNU/Linux distribution, Guix offers a declarative, stateless approach to operating system configuration management. Guix is highly customizable and hackable through Guile programming interfaces and extensions to the Scheme language.

About the GNU Hurd

The GNU Hurd is the GNU project's replacement for the Unix kernel. It is a collection of servers that run on the Mach microkernel to implement file systems, network protocols, file access control, and other features that are implemented by the Unix kernel or similar kernels (such as Linux). More info.

The mission of the GNU Hurd project is to create a general-purpose kernel suitable for the GNU operating system, which is viable for everyday use, and gives users and programs as much control over their computing environment as possible.

by Jan (janneke) Nieuwenhuizen, Ludovic Courtès, Mathieu Othacehe at October 08, 2020 02:15 PM

October 06, 2020

GNU Guix

Running Guix System on a Linode Server

Christopher Lemmer Webber recently discovered how to run Guix System on a Linode server. The below guide details how to set up your Linode server to run Guix System. We invite you to run your website using Guix system!

To run Guix on a server hosted by Linode, start with a recommended Debian server. We recommend using the default distro as a way to bootstrap Guix. Create your SSH keys.


Be sure to add your SSH key for easy login to the remote server. This is trivially done via Linode's graphical interface for adding SSH keys. Go to your profile and click add SSH Key. Copy into it the output of:

cat ~/.ssh/<username>

Power the Linode down. In the Linode's Disks/Configurations tab, resize the Debian disk to be smaller. 30 GB is recommended.

In the Linode settings, choose Add a disk with the following:

  • Label: Guix
  • Filesystem: ext4
  • Set it to the remaining size

On the configuration field that comes with the default image, press ... and select Edit, then on that menu add to /dev/sdc the Guix label.

Now select Add a Configuration, with the following:

  • Label: Guix
  • Kernel: GRUB 2 (it's at the bottom! This step is important!
  • Block device assignment:

    • /dev/sda: Guix
    • /dev/sdb: swap
  • Root device: /dev/sda
  • Turn off all the filesystem/boot helpers.

Now power it back up, picking the Debian configuration. Once it's booted up, ssh in your server via ssh root@<your-server-IP-here>. (You can find your server IP address in your Linode Summary section.) Now you can run the binary installation as explained in the manual:

sudo apt-get install gpg
wget -qO - | gpg --import -
chmod +x
guix pull

Now it's time to write out a config for the server. The key information is below. Save the resulting file as guix-config.scm.

(use-modules (gnu)
             (guix modules))
(use-service-modules networking
(use-package-modules admin

  (host-name "my-server")
  (timezone "America/New_York")
  (locale "en_US.UTF-8")
  ;; This goofy code will generate the grub.cfg
  ;; without installing the grub bootloader on disk.
  (bootloader (bootloader-configuration
                 (inherit grub-bootloader)
                 (installer #~(const #t))))))
  (file-systems (cons (file-system
                        (device "/dev/sda")
                        (mount-point "/")
                        (type "ext4"))
  (swap-devices (list "/dev/sdb"))

  (initrd-modules (cons "virtio_scsi"    ;needed to find the disk

  (users (cons (user-account
                (name "janedoe")
                (group "users")
                ;; Adding the account to the "wheel" group
                ;; makes it a sudoer.
                (supplementary-groups '("wheel"))
                (home-directory "/home/janedoe"))

  (packages (cons* nss-certs            ;for HTTPS access

  (services (cons*
             (service dhcp-client-service-type)
             (service openssh-service-type
                       (openssh openssh-sans-x)
                       (password-authentication? #f)
                        `(("janedoe" ,(local-file ""))
                          ("root" ,(local-file ""))))))

Replace the following fields in the above configuration:

(host-name "my-server")       ; replace with your server name
; if you chose a linode server outside the U.S., then
; use tzselect to find a correct timezone string
(timezone "America/New_York") ; if needed replace timezone
(name "janedoe")              ; replace with your username
("janedoe" ,(local-file "")) ; replace with your ssh key
("root" ,(local-file "")) ; replace with your ssh key

The last line in the above example lets you log into the server as root and set the initial root password. After you have done this, you may delete that line from your configuration and reconfigure to prevent root login.

Save your ssh public key (eg: ~/.ssh/ as <your-username-here> and your guix-config.scm in the same directory. In a new terminal run these commands.

sftp root@@<remote server ip address>
put /home/<username>/ssh/ .
put /path/to/linode/guix-config.scm .

In your first terminal, mount the guix drive:

mkdir /mnt/guix
mount /dev/sdc /mnt/guix

Due to the way we set things up above, we do not install GRUB completely. Instead we install only our grub configuration file. So we need to copy over some of the other GRUB stuff that is already there:

mkdir -p /mnt/guix/boot/grub
cp -r /boot/grub/* /mnt/guix/boot/grub/

Now initialize the Guix installation:

guix system init guix-config.scm /mnt/guix

Ok, power it down! Now from the Linode console, select boot and select Guix.

Once it boots, you should be able to log in via SSH! (The server config will have changed though.) You may encounter an error like:

$ ssh root@<server ip address>
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.
The fingerprint for the ECDSA key sent by the remote host is
Please contact your system administrator.
Add correct host key in /home/joshua/.ssh/known_hosts to get rid of this message.
Offending ECDSA key in /home/joshua/.ssh/known_hosts:3
ECDSA host key for has changed and you have requested strict checking.
Host key verification failed.

Either delete ~/.ssh/known_hosts file, or delete the offending line starting with your server IP address.

Be sure to set your password and root's password.

ssh root@<remote ip address>
passwd  ; for the root password
passwd <username> ; for the user password

You may not be able to run the above commands at this point. If you have issues remotely logging into your linode box via SSH, then you may still need to set your root and user password initially by clicking on the Launch Console option in your linode. Choose the Glish instead of Weblish. Now you should be able to ssh into the machine.

Hooray! At this point you can shut down the server, delete the Debian disk, and resize the Guix to the rest of the size. Congratulations!

By the way, if you save it as a disk image right at this point, you'll have an easy time spinning up new Guix images! You may need to down-size the Guix image to 6144 MB, to save it as an image. Then you can resize it again to the max size.

That's all for today! We hope you have fun playing with your brand new Guix System Server!

A variant of this guide is available in the Guix Cookbook.

About GNU Guix

GNU Guix is a transactional package manager and an advanced distribution of the GNU system that respects user freedom. Guix can be used on top of any system running the kernel Linux, or it can be used as a standalone operating system distribution for i686, x86_64, ARMv7, and AArch64 machines.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. When used as a standalone GNU/Linux distribution, Guix offers a declarative, stateless approach to operating system configuration management. Guix is highly customizable and hackable through Guile programming interfaces and extensions to the Scheme language.

by Joshua Branson, Christopher Lemmer Webber at October 06, 2020 02:30 PM

Programming Praxis

Pandigital Squares, Faster And Smaller

In a previous exercise, we wrote a program to compute pandigital squares, defined as ten-digit numbers with integral square roots in which each digit zero through nine appears exactly once. We remarked at the time that our solution, though not very fast, was fast enough.

Your task is to write a program that finds pandigital squares, reducing the time and space requirements of the naive solution. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at October 06, 2020 09:00 AM

October 02, 2020

Programming Praxis

Non-Breaking Hyphen

Today’s exercise tells the story of a problem I faced in my day job. A user apparently copy/pasted a field from Word, Excel or Outlook into our data processing system, which assumes plain ascii (the underlying database, Oracle, handles unicode properly, but the system on top of Oracle doesn’t). Unfortunately, although the field looked okay,


the dash was actually a non-breaking hyphen, unicode 201110, which broke the system in a rather large way. The field in question was the vendor invoice number in an accounts payable system, and when the check paying that invoice was written, the check-writing program dropped the remittance advice from that check, so every subsequent check had the wrong remittance advice attached. The error wasn’t discovered immediately, so some of the checks were already mailed, making recovery difficult (we couldn’t just void the check run and start over because some of the checks were already mailed, and restarting the check run meant the check numbers wouldn’t match). So it was a grand old mess. In case you’re curious, I demonstrated the error with this SQL statement

select asciistr(fabinvh_vend_inv_code)
from   fabinvh
where  fabinvh_code = 'I2104519'

which returned


Unicode is nearly thirty years old. Users have the right to expect that their systems handle unicode characters properly.

Your task is to write a program that detects unicode/ascii error; you might also tell us about any unicode horror stories you have faced. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at October 02, 2020 09:00 AM

September 29, 2020

Programming Praxis

Pandigital Squares

A pandigital number, like 4730825961, is a ten-digit number in which each digit from zero to nine appears exactly once. A square number, like 25² = 625, is a number with an integral square root.

Your task is to write a program that finds all of the pandigital square numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at September 29, 2020 09:00 AM

September 01, 2020

Programming Praxis


Regular readers know of my affinity for number theory. Today’s exercise is a reflection of that.

It is conjectured that the two numbers produced by the equations n17 + 9 and (n + 1)17 + 9 for a given n are always co-prime (that is, their greatest common divisor is 1). Is that conjecture correct?

Your task is to either prove that the greatest common divisor is always 1 or write a program that finds a case where the greatest common divisor is not 1. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at September 01, 2020 09:00 AM

August 29, 2020

Göran Weinholt

Loko Scheme 0.6.0

Loko Scheme 0.6.0 is now available from:

The release tarball is signed by the GnuPG key 0xE33E61A2E9B8C3A2.

Loko Scheme 0.6.0 introduces support for R7RS-small. The release tarballs now include a pre-built compiler and all dependencies needed for building Loko. See in the distribution for a more detailed summary of changes.

Loko Scheme is an optimizing Scheme compiler that builds statically linked binaries for bare metal, Linux and NetBSD/amd64. It supports the R6RS Scheme and R7RS Scheme standards.

Loko Scheme’s web site is, where you can find the release tarballs and the manual.

Loko Scheme is available under GNU Affero GPL version 3 or later.

by weinholt at August 29, 2020 12:00 AM

August 21, 2020

Programming Praxis

Approximate Median

[ I offer my apologies to my readers for my recent absence. My employer, a local community college, is struggling with this virus business, revising nearly all of its business practices, and my programmer colleagues and I have been very busy. The Fall semester starts next week (mostly on-line classes, some on-campus classes for science labs and the nursing students), so hopefully things on the virus front will get better soon. But we are also in the middle of changing our main computing system from running on HP-UX on fifteen-year old hardware to Linux on new hardware, and having all kinds of setup problems (all of the people who set up the current system twenty years ago are gone, and no one seems to know how to set up the new system), so maybe not too soon. I hope all is well with all of you. — Phil ]

We have previously studied algorithms for the streaming median and sliding median that calculate the median of a stream of numbers; the streaming median requires storage of all the numbers previously seen, and the sliding median requires storage of the last k numbers in the stream, for some k.

Today’s exercise estimates the median of a stream of numbers while storing only two numbers:

The idea is at each iteration the median inches toward the input signal at a constant rate. The rate depends on what magnitude you estimate the median to be. I use the average as an estimate of the magnitude of the median, to determines the size of each increment of the median. If you need your median accurate to about 1%, use a step-size of 0.01 * the average.

Your task is to write a program that estimates the streaming median according to the given algorithm. When you are finished, you are welcome to read or run the suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at August 21, 2020 09:00 AM

August 04, 2020

Programming Praxis


There are 19,055 distinct words in the Bible:

$ cat bible.txt | tr -cs A-Za-z ‘
‘ | sort -u | wc -w

It’s easy enough to count the number of distinct items in a set (its “cardinality”) when the set is small, but when the set is large, the intermediate storage required for the distinct items can be overwhelming.

Phillipe Flajolet and various co-authors wrote a series of papers in which they developed methods of estimating the cardinality of a set with only a small amount of auxiliary storage, using randomization; Flajolet’s algorithms can be seen as an improvement on Robert Morris’ counting algorithm that we studied in a previous exercise. We will study Flajolet’s loglog algorithm in today’s exercise and perhaps have a look at his other algorithms in future exercises.

The basic idea is to apply a hash function to each element of the set. The first bit of the hash value will be zero about half the time, the first two bits of the hash value will be zero about a quarter of the time, the first three bits of the hash value will be zero about an eighth of the time, and so on; by looking at the maximum number of leading zero-bits, we can estimate the cardinality of the set. Flajolet extends this algorithm by splitting the counts among 2k buckets and averaging the estimated cardinalities; the bucket is selected randomly by looking at the last k bits of the hash value.

Your task is to implement Flajolet’s loglog algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at August 04, 2020 09:00 AM

July 23, 2020

GNU Guix

Improve Internationalization Support for the Guix Data Service

The first half of my Outreachy internship is already over and I am really excited to share my experience. Over the past weeks I’ve had the opportunity to work on the Guix Data Service, watch myself change, and accomplish way more than I thought I would.

The Guix Data Service processes, stores and provides data about Guix over time. It provides a complementary interface to Guix itself by having a web interface and API to browse and access the data.

The work I have done so far revolves around storing translated lint checker descriptions as well as package synopsis and descriptions in the Guix Data Service PostgreSQL database and making them available through the Guix Data Service web interface.

Initially the Guix Data Service database had translated versions of lint warning messages available, but they were not accessible through the web interface, so I made that possible during the contribution period.

Working on making lint warning messages available on the web interface made it easier for me to understand how translations for lint checker descriptions and package synopsis and descriptions would be stored in the database and later on be made available through the Guix Data Service web interface. At this point, the Guix Data Service supports package synopsis and descriptions as well as lint checker descriptions in various locales.

Guix Data Service page for the audacity package, in the Spanishlocale

Hopefully these changes will provide the Guix Data Service users with a more feasible way to interact with Guix data.

I have to note that this is my first internship and I was initially reluctant to believe that I would be able to tackle or successfully accomplish the tasks I was assigned, but with my mentor’s help and guidance I managed to. So far it has been a rewarding experience because it has helped me make progress in so many aspects, whilst contributing to a project that will potentially increase inclusion.

While working on this project, I’ve significantly improved my Guile, SQL, and Git skills and I am now more aware of how software localization is achieved. In addition to getting more technically skilled, this internship has taught me how to manage time and emotions when dealing with more than one activity at a time.

Now that a good share of what was initially planned to be done is accomplished, my mentor suggested working on something using the Guix Data Service data and I will be engaged in that during the remaining half.

These first 7 weeks of my internship have gone by really fast, but I have enjoyed everything and I am so eager to experience what's to come.

by Danjela Lura at July 23, 2020 12:00 PM

July 21, 2020

Programming Praxis

Lost Boarding Pass

We have today a fun little problem from probability:

On a sold-out flight, 100 people line up to board the plane. The first passenger in the line has lost his boarding pass but was allowed in, regardless. He takes a random seat. Each subsequent passenger takes his or her assigned seat if available, or a random unoccupied seat, otherwise. What is the probability that the last passenger to board the plane finds his seat unoccupied?

Your task is to determine the requested probability, either by reasoning mathematically or by writing a program to demonstrate the probability. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at July 21, 2020 09:00 AM

July 18, 2020

Vladimir Nikishkin

Proposing programming language features

This blog hasn’t had enough attention for quite a while. This is not, however, because I have abandoned it, but rather because the original purpose of this blog, that is dumping essays regarding books I read, is still valid. It’s just that the most recent book has taken an order of magnitude more time than I had expected it to take.

Okay, I’m going to write a bigger and better review on the “Structure and Interpretation of Computer Programs”, but the book altogether took so much time, effort and emotions, that even writing the review is going to take a while.

Meanwhile, one of the by-products of my reading happened to be a proposal of a feature to be included into the Scheme Language, that is needed in order to support all the code examples in the book.

(Yes-yes, you’re not misreading it. The book published in 1996 is _still_ not covered by the existing language standard in full. Otoh, it means that there is a chance of achieving things.)

Now that the proposal has an official number, there is going to be a public discussion among the potential Language System providers, and maybe (if it passes the review), we will have this feature officially recognised.

Watching discussions of experts on what they may actually work themselves is a fascinating experience, and a chance to improve own skills too. In this case the discussion is not expected to be too heated, however, but anyway. — this is the link to my recent proposal.

It speaks about quite an interesting approach to generating computer images, that builds on top of the classical features present in most drawing languages, such as PostScript, TikZ, MetaPost or SVG. While the expressive power is largely the same, the degree of abstractness is greater, which leaves gives greater code reusability and flexibility.

Scheme is by not means the only language that has a community feature review process.

  • Python has Python Enhancement Proposals (PEP)
  • Java has Java Community Process (JCP)
  • Scheme has Scheme Requests For Implementation

The image in the header is a digital copy of a work of M. Escher, whose works have inspired the original author of the “Picture Language” Peter Henderson.

by lockywolf at July 18, 2020 03:00 PM