Planet Scheme

December 10, 2019

Joe Marshall

(map append elements)

I can recall the difficulty I had understanding let expressions in Lisp.  I used to write out the equivalent lambda expression and then manually add the syntactic sugar to make it into a let.  And I don't recall having an easy time with the chapter on linked lists.  So I find it amusing to see what tortuous code students come up with when they are first introduced to linked lists. My favorite so far has been (map append elements), which looks like it might join the sublists in elements, but if you think about it, the arity is all wrong:  map doesn't apply its function, it calls it.   This had me scratching my head for several minutes until I realized you can call apply on a single argument.

So what little gems of code have you discovered that perform the most trivial of tasks in the most convoluted or obscure manner?

by Joe Marshall (noreply@blogger.com) at December 10, 2019 07:42 PM

“No ‘x’ in ‘Nixon’”

I just had a phone screen where they asked if I could write a palindrome detector. I wrote a recursive and an iterative version. I like the recursive solution because it is so simple. There are only three equations:

  • An empty string is a palindrome.
  • A string with one character is a palindrome.
  • If a string starts and ends with the same character, and the substring between them is a palindrome, then the entire string is a palindrome.
I wrote them the iterative version so I wouldn't look like an idiot.  The iterative version is generally faster with a standard compiler, but it is more complex.  Not much more complex, but still, you have to keep track of two indexes into the string and how close they've gotten to each other.

The recursive solution is just more elegant.

Apparently I cannot post comments on my own blog.  Well, I can edit the post.  "if s[pos] != s[-pos-1]" sure looks like two pointers, but to be fair, the recursive solution hides its pointers in the string structure or in the slices if it is using them.  As for "(string= x (string-reverse x))", there is something elegant in something that crude.

by Joe Marshall (noreply@blogger.com) at December 10, 2019 02:27 PM

Programming Praxis

Pseudoprimes To Bases 2 And 3

Regular readers know of my affinity for the Online Encyclopedia of Integer Sequences. I was browsing the other day and came across A052155, the sequence of pseudoprimes to both base2 and base3. This sequence is important because it forms the basis of a very fast primality test for numbers in the range 232 to 264, which is a very important range for some large factoring algorithms (particularly SIQS and NFS in their 2LP variants): a number n in range is prime if 2n-1 ≡ 1 (mod n), 3n-1 ≡ 1 (mod n), and n is not in a small list of known pseudoprimes to bases 2 and 3. The two modular exponentiations are reasonably quick, the lookup by binary search is even quicker, and the primality test is fully deterministic.

Your task is to calculate the pseudoprimes to bases 2 and 3 less than a million. 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 December 10, 2019 10:00 AM

December 06, 2019

Programming Praxis

Muenchhausen Numbers

A radix-10 number is a Muenchhausen number if it is equal to the sum of its digits, each digit raised to the power of itself. For instance, 3435 is a Muenchhausen number because 3**3 + 4**4 + 3**3 + 5**5 = 3435. Strict Muenchhausen numbers do not permit 0 as a digit, because 0**0 is undefined. Variant Muenchhausen numbers permit 0 as a digit, with 0**0 defined as 0. Muenchhausen numbers also exist with radices other than 10.

Your task is to find all the Muenchhausen numbers in radix-10. 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 December 06, 2019 01:51 PM

December 03, 2019

Programming Praxis

A Single Line Of Code

Today’s task challenges you write a useful program using only a single line of code. It is not fair to abuse the notion of a line. You can probably do more than you expect.

Your task is to write a useful program using only a single line of code. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at December 03, 2019 10:00 AM

November 27, 2019

GNU Guix

Guix on an ARM Board

Increasingly people discovering Guix want to try it on an ARM board, instead of their x86 computer. There might be various reasons for that, from power consumption to security. In my case, I found these ARM boards practical for self-hosting, and I think the unique properties of GNU Guix are making it very suitable for that purpose. I have installed GNU Guix on a Cubietruck, so my examples below will be about that board. However, you should be able to change the examples for your own use case.

Installing the Guix System on an ARM board is not as easy as installing it on an x86 desktop computer: there is no installation image. However, Guix supports ARM and can be installed on a foreign distribution running on that architecture. The trick is to use the Guix installed on that foreign distribution to initialize the Guix System. This article will show you how to install the Guix System on your board, without using an installer image. As we have previously mentioned it is possible to generate an installation image yourself, if your board is supported.

Most boards can be booted from an existing GNU+Linux distribution. You will need to install a distribution (any of them) and install GNU Guix on it, using e.g. the installer script. Then, my plan was to install the Guix System on an external SSD drive, instead of the SD card, but we will see that both are perfectly possible.

The first part of the article will focus on creating a proper u-boot configuration and an operating system declaration that suits your board. The second part of this article will focus on the installation procedure, when there is no installer working for your system.

Writing a configuration file for an ARM board

A configuration file for an ARM board is not very different from a configuration file for a desktop or a server running on another architecture. However, most boards use the u-boot bootloader and require some less common modules to be available at boot time.

The root file system

First of all, you should decide where your root file system is going to be installed. In my case, I wanted to install is on the external SSD, so I chose it:

(file-systems
  (cons* (file-system
           (mount-point "/")
           (device "/dev/sda1")
           (type "ext4"))
         %base-file-systems))

If you instead want to install the root file system on an SD card, you'll need to find its device name, usually /dev/mmcblk0 and the partition number. The device corresponding to the first partition should be /dev/mmcblk0p1. In that case, you would have:

(file-systems
  (cons* (file-system
           (mount-point "/")
           (device "/dev/mmcblk0p1")
           (type "ext4"))
         %base-file-systems))

The bootloader

Because of the way the Guix System is designed, you cannot use an already existing bootloader to boot your system: it wouldn't know where to look for the kernel, because it doesn't know its store path. It wouldn't be able to let you boot older generations either. Most boards use the u-boot bootloader, so we will focus on that bootloader here.

Contrary to grub, there are multiple variants of u-boot, one per board type. The installation procedure for u-boot is also somewhat specific to the board, so there are two things that you need to take care of: the u-boot package and the bootloader declaration.

Guix already define a few u-boot based bootloaders, such as u-boot-a20-olinuxino-lime-bootloader or u-boot-pine64-plus-bootloader among others. If your board already has a u-boot-*-bootloader defined in (gnu bootloader u-boot), you're lucky and you can skip this part of the article!

Otherwise, maybe the bootloader package is defined in (gnu packages bootloaders), such as the u-boot-cubietruck package. If so, you're a bit lucky and you can skip creating your own package definition.

If your board doesn't have a u-boot-* package defined, you can create one. It could be as simple as (make-u-boot-package "Cubietruck" "arm-linux-gnueabihf"). The first argument is the board name, as expected by the u-boot build sysetem. The second argument is the target triplet that corresponds to the architecture of the board. You should refer to the documentation of your board for selecting the correct values. If you're really unlucky, you'll need to do some extra work to make the u-boot package you just created work, as is the case for the u-boot-puma-rk3399 for instance: it needs additional phases to install firmware.

You can add the package definition to your operating system configuration file like so, before the operating-system declaration:

(use-modules (gnu packages bootloaders))

(define u-boot-my-board
  (make-u-boot-package "Myboard" "arm-linux-gnueabihf"))

(operating-system
  [...])

Then, you need to define the bootloader. A bootloader is a structure that has a name, a package, an installer, a configuration file and a configuration file generator. Fortunately, Guix already defines a base u-boot bootloader, so we can inherit from it and only redefine a few things.

The Cubietruck happens to be based on an allwinner core, for which there is already a u-boot bootloader definition u-boot-allwinner-bootloader. This bootloader is not usable as is for the Cubietruck, but it defines most of what we need. In order to get a proper bootloader for the Cubietruck, we define a new bootloader based on the Allwinner bootloader definition:

(define u-boot-cubietruck-bootloader
  (bootloader
    (inherit u-boot-allwinner-bootloader)
    (package u-boot-cubietruck)))

Now that we have our definitions, we can choose where to install the bootloader. In the case of the Cubietruck, I decided to install it on the SD card, because it cannot boot from the SSD directly. Refer to your board documentation to make sure you install u-boot on a bootable device. As we said earlier, the SD card is /dev/mmcblk0 on my device.

We can now put everything together like so:

(use-modules (gnu packages bootloaders))

(define u-boot-cubietruck
  (make-u-boot-package "Cubietruck" "arm-linux-gnueabihf"))

;; u-boot-allwinner-bootloader is not exported by (gnu bootloader u-boot) so
;; we use @@ to get it.  (@ (module) variable) means: get the value of "variable"
;; as defined (and exported) in (module).  (@@ (module) variable) is the same, but
;; it doesn't care whether it is exported or not.
(define u-boot-allwinner-bootloader
  (@@ (gnu bootloader u-boot) u-boot-allwinner-bootloader))

(define u-boot-cubietruck-bootloader
  (bootloader
    (inherit u-boot-allwinner-bootloader)
    (package u-boot-cubietruck)))

(operating-system
  [...]
  (bootloader
    (bootloader-configuration
      (target "/dev/mmcblk0")
      (bootloader u-boot-cubietruck-bootloader)))
  [...])

The kernel modules

In order for Guix to be able to load the system from the initramfs, it will probably need to load some modules, especially to access the root file system. In my case, the SSD is on an ahci device, so I need a driver for it. The kernel defines ahci_sunxi for that device on any sunxi board. The SD card itself also requires two drivers: sunxi-mmc and sd_mod.

Your own board may need other kernel modules to boot properly, however it is hard to discover them. Guix can tell you when a module is missing in your configuration file if it is loaded as a module. Most distros however build these modules in the kernel directly, so Guix cannot detect them reliably. Another way to find what drivers might be needed is to look at the output of dmesg. You'll find messages such as:

[    5.193684] sunxi-mmc 1c0f000.mmc: Got CD GPIO
[    5.219697] sunxi-mmc 1c0f000.mmc: initialized, max. request size: 16384 KB
[    5.221819] sunxi-mmc 1c12000.mmc: allocated mmc-pwrseq
[    5.245620] sunxi-mmc 1c12000.mmc: initialized, max. request size: 16384 KB
[    5.255341] mmc0: host does not support reading read-only switch, assuming write-enable
[    5.265310] mmc0: new high speed SDHC card at address 0007
[    5.268723] mmcblk0: mmc0:0007 SD32G 29.9 GiB

or

[    5.614961] ahci-sunxi 1c18000.sata: controller can't do PMP, turning off CAP_PMP
[    5.614981] ahci-sunxi 1c18000.sata: forcing PORTS_IMPL to 0x1
[    5.615067] ahci-sunxi 1c18000.sata: AHCI 0001.0100 32 slots 1 ports 3 Gbps 0x1 impl platform mode
[    5.615083] ahci-sunxi 1c18000.sata: flags: ncq sntf pm led clo only pio slum part ccc 
[    5.616840] scsi host0: ahci-sunxi
[    5.617458] ata1: SATA max UDMA/133 mmio [mem 0x01c18000-0x01c18fff] port 0x100 irq 37
[    5.933494] ata1: SATA link up 3.0 Gbps (SStatus 123 SControl 300)

Also note that module names are not consistent between what Guix expects and what is printed by dmesg, especially when the contain a "-" or a "_". You will find the correct file name by building (or using a substitute for) linux-libre beforehand:

find `guix build linux-libre`/lib/modules -name '*mmc*'

Here, I could find a file named "kernel/drivers/mmc/host/sunxi-mmc.ko", hence the module name sunxi-mmc. For the other driver, I found a "kernel/drivers/ata/ahci_sunxi.ko", hence the name ahci_sunxi, even if dmesg suggested ahci-sunxi.

Once you have found the modules you want to load before mounting the root partition, you can add them to your operating-system declaration file:

(initrd-modules (cons* "sunxi-mmc" "sd_mod" "ahci_sunxi" %base-initrd-modules))

Installing the Guix System

Installing on another drive

In my case, I wanted to install the system on an external SSD, while the currently running foreign distribution was running from the SD card. What is nice with this setup is that, in case of real trouble (you SSD caught fire or broke), you can still boot from the old foreign system with an installed Guix and all your tools by re-flashing only the bootloader.

In this scenario, we use the foreign system as we would the installer iso, using the manual installation procedures described in the manual. Essentially, you have to partition your SSD to your liking, format your new partations and make sure to reference the correct partition for the root file system in your configuration file. Then, initialize the system with:

mount /dev/sda1 /mnt
mkdir /mnt/etc
$EDITOR /mnt/etc/config.scm # create the configuration file
guix system init /mnt/etc/config.scm /mnt

You can now reboot and enjoy your new Guix System!

Installing on the same drive

Another option is to install the Guix System over the existing foreign distribution, replacing it entirely. Note that the root filesystem for the new Guix System is the current root filesystem, so no need to mount it. The following will initialize your system:

$EDITOR /etc/config.scm # create the configuration file
guix system init /etc/config.scm /

Make sure to remove the files from the old system. You should at least get rid of the old /etc directory, like so:

mv /etc{,.bak}
mkdir /etc

Make sure there is an empty /etc, or the new system won't boot properly. You can copy your config.scm to the new /etc directory. You can now reboot and enjoy your new Guix System!

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 Julien Lepiller at November 27, 2019 12:00 PM

November 26, 2019

Programming Praxis

Happy Thanksgiving

My daughter is visiting this week, so there will be no exercises. The next exercise will be on Tuesday, December 3rd. Enjoy the time with your family.

by programmingpraxis at November 26, 2019 02:29 PM

November 22, 2019

Programming Praxis

Three-Way Minimum Sum Partitions

I had a lot of fun working on this problem:

Given n, find x, y and z such that x y z = n and x + y + z is minimal; for instance, given n = 1890, the correct answer is (9 14 15).

Your task is to write a program to find x, y and z. 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 November 22, 2019 10:00 AM

November 19, 2019

Programming Praxis

Modified Coin Change

We solved the standard coin change problem in two previous exercises. The particular problem given here is to find the minumum number of coins that can be used to create a target amount of money, given an unlimited number of coins of various denominations, and is normally solved by a dynamic programming algorithm.

Today’s task is a variant on that problem: find the minimum number of coins that can be used to create a target amount of money, given an unlimited number of coins of denomination that are powers of 5.

Your task is to write a program to solve the modified coin change 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 November 19, 2019 10:00 AM

November 17, 2019

GNU Guix

Running a Guix Xfce Desktop on CentOS 7

This tutorial will show how to run a fully fledged Xfce desktop environment installed with Guix on top of an existing GNU/Linux distribution. This guide uses CentOS 7 as the base operating system and assumes that Xorg is already configured and running on VT2 under a different user account.

We will borrow Xorg and xinit from the host distribution and run Guix Xfce on virtual terminal 4 as user alice. No system-wide configuration files need to be touched (apart from the Guix install), but we do make a couple of changes for convenience.

From scratch to Xfce

If Guix is not already installed, go grab the installation script and run it as sudo bash guix-install.sh.

The script creates /gnu/store/ and /var/guix/ and configures a system service for guix-daemon. By default the daemon runs from the root users Guix; we won't be using the root account in this guide, so let's start by making the guix-daemon service refer to our local user alice instead.

sudo sed -i 's/root/alice/' /etc/systemd/system/guix-daemon.service

Now every time Alice runs 'guix pull', the daemon gets updated too. If you installed Guix just now, make sure to run guix pull before proceeding further.

Next we'll add some lines to Alices .bash_profile to set up PATH and related variables:

~/.bash_profile:

GUIX_PROFILE="${HOME}/.guix-profile"
[[ -L "${GUIX_PROFILE}" ]] && . "${GUIX_PROFILE}/etc/profile"

export PATH="${HOME}/.config/guix/current/bin:${PATH}"
export INFOPATH="${HOME}/.config/guix/current/share/info:${INFOPATH}"
export MANPATH="${HOME}/.guix-profile/share/man:/usr/share/man"

export XDG_CONFIG_DIRS="${HOME}/.desktop-profile/etc/xdg:${HOME}/.guix-profile/etc/xdg"
export XDG_DATA_DIRS="${HOME}/.desktop-profile/share:${HOME}/.guix-profile/share"

This will look familiar if you have used Guix on a foreign distribution before. The XDG_ variables tell desktop environments where to look for installed programs and things like autostart files: we want minimal interference from the host system, so we "hard code" them to refer to just our Guix profiles.

We will install Xfce and related programs to a separate Guix profile that can be updated and rolled back independently of the main user profile. That allows us to distinguish between "stable desktop environment" and "end user packages". To keep things manageable, we create a manifest for the desktop profile that can be kept in version control, and which allows us to reproduce the exact same environment in the future (even on a different computer!).

~/desktop-manifest.scm:

(specifications->manifest
 '("xfce" "xfce4-session" "xfconf" "xfce4-battery-plugin"
   "pulseaudio" "xfce4-volumed-pulse" "xfce4-notifyd"
   ;; Helpful graphical programs.
   "mousepad" "orage"
   ;; System configuration utilities.
   "xbacklight" "pavucontrol" "stow"
   ;; For HTTPS access.
   "nss-certs"
   ;; These utilities are provided by the host, but we want the Guix versions
   ;; because they are likely better integrated and up to date.
   "fontconfig" "bash-completion" "gnupg" "man-db" "git"))

Create the initial profile generation:

guix package -p ~/.desktop-profile -m ~/desktop-manifest.scm

That installs a union of all packages listed in the manifest to ~/.desktop-profile, and creates a script we will use to "activate" it later. To update this profile, simply invoke the same command again after running guix pull or modifying the manifest.

Before Xfce can be started, we need to create a configuration file for the X server to ensure the host executable is used, and we will tell it to to stay on virtual terminal 4. We also create a .xinitrc script that automatically starts Xfce every time xinit is invoked.

~/.xserverrc:

exec /usr/bin/Xorg -novtswitch -nolisten tcp "$@" vt$XDG_VTNR

~/.xinitrc:

#!/bin/sh

# Get the default xinit configuration for CentOS.
. /etc/X11/xinit/xinitrc-common

exec startxfce4

.xinitrc needs to be executable:

chmod +x ~/.xinitrc

Now let's activate the desktop profile and start the X server, using ":1" as DISPLAY (remember that we have another X server running on VT2, occupying the default ":0" display).

GUIX_PROFILE=~/.desktop-profile
source ~/.desktop-profile/etc/profile
xinit -- :1

Cool, we're in Xfce! Let's open a terminal and install a browser & some fonts:

guix install icecat font-liberation font-dejavu

To make the newly installed fonts available right away we need to invoke fc-cache:

fc-cache -rv

Finally, we'll configure the shell to source scripts installed by Guix so that bash completions and similar work, by adding these lines at the end of .bashrc:

~/.bashrc:

# Source the Guix shell configuration directories, for vte.sh and bash completions.
GUIX_PROFILES=("${HOME}/.desktop-profile"
               "${HOME}/.guix-profile"
               "${HOME}/.config/guix/current")
for profile in "${GUIX_PROFILES[@]}"; do
    for dir in "${profile}/etc/bash_completion.d" "${profile}/etc/profile.d"; do
        if [[ -d "${dir}" ]]; then
            for f in "${dir}"/*; do
                . $f
            done
        fi
    done
done

Phew! It took some work, but by now you should have a working Xfce desktop environment, with bash completions and all. If you are content with starting it manually, skip to "final tweaks" below. Otherwise, read on.

(If you do not have a working desktop after following these steps, please email guix-devel@gnu.org so we can adjust the tutorial!)

Starting Xfce automatically on boot

We can configure our login shell to run xinit every time we log in to VT4 by adding these lines at the end of ~/.bash_profile:

# Start Xorg on display :1 when logged in to VT4, unless DISPLAY is already set.
if [[ -z "${DISPLAY}" && "${XDG_VTNR}" == 4 ]]; then
    GUIX_PROFILE="${HOME}/.desktop-profile"
    source "${HOME}/.desktop-profile/etc/profile"
    exec xinit -- :1
fi

To avoid the need for typing username and password at the console, instruct the getty service for TTY4 to automatically log in user 'alice':

/etc/systemd/system/getty@tty4.service.d/override.conf:

[Unit]
After=graphical.target

[Service]
# Delay for a few seconds, to ensure the Xorg server on VT2 starts first.
ExecStartPre=/bin/sleep 3
ExecStart=
ExecStart=-/sbin/agetty --autologin alice --noclear %I $TERM
Restart=on-success

Now just switching to VT4 will start Xfce! To do this when the system boots, simply enable the getty@tty4 service:

sudo systemctl enable getty@tty4.service

Final tweaks

Some issues were found during usage of the Xfce environment. Launching programs from the file manager failed because gio-launch-desktop was unavailable, and xfce4-terminal complained that the shell function __vte_prompt_command was not found.

These problems will be fixed in Guix eventually, but for now we'll work around them by adding the glib:bin and vte packages to our manifest:

~/desktop-manifest.scm:

(specifications->manifest
 '("xfce" "xfce4-session" "xfconf" "xfce4-battery-plugin"
   ...
   "glib:bin"                  ;for 'gio-launch-desktop'
   "vte"))                     ;for vte.sh, required by xfce4-terminal

We also found that closing the lid would not send the system to sleep, even though xfce4-power-manager --dump showed no problems. To work around it, we told systemd to ignore any "inhibitors" and take care of lid handling itself:

/etc/systemd/logind.conf:

HandleLidSwitch=suspend
LidSwitchIgnoreInhibited=yes

Additionally it is strongly recommended to enable the name service cache daemon if not already running. On CentOS this can be done by:

sudo yum install nscd

Bonus section: Installing programs with a custom build of Qt

One additional issue was that Qt programs did not work due to the stock CentOS kernel being too old. Specifically it lacks the renameat2() system call. Luckily Qt can be configured not to use it. A patch has been submitted to Guix, but since we are in a hurry, we will add a procedure to our manifest so we can use Qt programs (here wpa-supplicant-gui) until the Guix fix is merged:

~/.desktop-manifest.scm:

(use-modules (guix packages)
             (guix utils)
             (gnu)
             (gnu packages admin)
             (gnu packages qt))

(define qtbase/fixed
  (package/inherit
   qtbase
   (arguments
    (substitute-keyword-arguments (package-arguments qtbase)
      ((#:phases phases)
       `(modify-phases ,phases
          (add-after 'unpack 'disable-renameat2
            (lambda _
              ;; Mimic the '-no-feature-renameat2' configure flag.
              (substitute* "src/corelib/configure.json"
                (("config\\.linux && tests\\.renameat2")
                 "false"))
              #t))))))))

(define with-fixed-qt
  ;; This procedure recursively rewrites any references to 'qtbase'
  ;; with our patched version.
  (package-input-rewriting `((,qtbase . ,qtbase/fixed))))

(packages->manifest
 (append (list (with-fixed-qt wpa-supplicant-gui))
         (map specification->package
              '("xfce" "xfce4-session" "xfconf" "xfce4-battery-plugin"
                ...))))

...and now wpa_gui works after installing the new manifest!

Acknowledgements

Special thanks to Ocean Space Acoustics AS for sponsoring this work.

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 Marius Bakke at November 17, 2019 07:00 PM

November 15, 2019

Programming Praxis

Tri-Partitions

We have a fun little task for your Friday lunch hour:

Given an array of integers, rearrange the integers so no two consecutive integers have a sum that is divisible by 3, or indicate that such an arrangement is not possible.

Your task is to write a program to rearrange an array of integers as described above. 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 November 15, 2019 10:00 AM

November 12, 2019

GNU Guix

Spreading the news

Like most free software projects, Guix has no shortage of communication channels: there’s this blog, the NEWS file for release notes, a bunch of mailing lists, an IRC channel, there’s also an unofficial sub-Reddit and certainly more. Yet, as developers, we often find it hard to communicate important changes to our users. Starting from a few weeks ago, guix pull --news tells users what’s new, and it already feels very helpful! This post is about our motivations and the implementation of this new feature.

Getting the word out

Developers keep adding crazy features, fixing bugs, and generally improving things. But how good is it if users aren’t aware of these new things? As an example, since June, our build farm has been offering lzip-compressed binaries, which results in better performance when installing software. But to take advantage of that, users need to be aware of its existence, and they need to upgrade their Guix daemon. Likewise, how do we get people to learn about the new guix deploy command that’s now available at their fingertips, about security issues that were fixed, about important infrastructure changes, new options added to existing commands, and so forth?

Our (frustrating!) experience has been that release notes, blog posts, and mailing list announcements aren’t quite enough to get the word out. There’s always people who’ll miss important info and realize when it’s already late, sometimes too late. Hence this simple idea: wouldn’t it be nice if important information would reach users right in their terminal?

guix pull news

Alright, that’s not exactly a novel idea! In Debian for example, apt-listchanges shows news at the level of individual packages, taken from the NEWS.Debian or changelog.Debian files that package maintainers update. In addition, apt dist-upgrade and similar commands typically display dialog boxes and menus when special actions need to be taken when upgrading. That’s more or less what we’re looking for.

The situation in Guix is a little different: all of it lives in a single Git repository that contains the core, the command-line interfaces, as well as package definitions and operating system service definitions. The guix pull command is sort-of equivalent to apt update, except that it updates not only the set of available packages but also the guix tools themselves and all the operating system interfaces. Under the hood, guix pull essentially does git pull and consequently updates all of this. Guix very much follows a “rolling release” model.

For some time already, guix pull has been able to extract information about new and upgraded packages and to present it to the user. Our goal was to complement it with high-level information about important changes written with users in mind. Clearly, showing the Git commit log is not an option: commit logs are meant for developers and there’s roughly a thousand commits per month—way too much information. We needed high-level news entries, explicitly written for users.

The end result is this: guix pull now displays, in addition to a summary of the new and upgraded packages, the headlines of applicable news entries contributed by developers. Users can view the details by running guix pull --news:

'guix pull' displaying news.

Users can no longer miss the news, for the benefit of both users and developers!

Under the hood

How does this all work? There were several goals and constraints. First, like commit logs, our high-level news entries should be anchored in the Git history. Second, unlike commit logs, it should be possible to amend them—to fix typos, provide additional info, and so on. Third, the project has been paying a lot of attention to internationalization, with translations available for user interface messages, for package descriptions, and for the user manual—it’s one of these things that helps free software reach out to more people; thus, we naturally wanted news to be internationalized. Last, since Guix supports third-party “channels”, which are extensions of the official guix channel, why not provide channel authors access to that news feature?

With all these things in mind, we designed a simple news format. In essence, channel authors, including Guix developers, can provide a news file that looks like this:

(channel-news
 (version 0)

 (entry (commit "3e962e59d849e4300e447d94487684102d9d412e")
        (title (en "@command{guix graph} now supports package
transformations")
               (de "@command{guix graph} unterstützt nun Paketumwandlungen"))
        (body
         (en "The @command{guix graph} command now supports the common package
transformation options (see @command{info \"(guix) Package Transformation
Options\"}).  This is useful in particular to see the effect of the
@option{--with-input} dependency graph rewriting option.")
         (de "Der Befehl @command{guix graph} unterstützt nun die mit anderen
Befehlen gemeinsamen Umwandlungsoptionen (siehe @command{info \"(guix.de)
Paketumwandlungsoptionen\"}).  Sie helfen insbesondere dabei, die Wirkung der
Befehlszeilenoption @option{--with-input} zum Umschreiben des
Abhängigkeitsgraphen zu sehen.")))

 (entry (commit "49af34cfac89d384c46269bfd9388b2c73b1220a")
        (title (en "@command{guix pull} now honors
@file{/etc/guix/channels.scm}")
               (es "Ahora @command{guix pull} tiene en cuenta
@file{/etc/guix/channels.scm}"))
        (body
         (en "The @command{guix pull} command will now read the
@file{/etc/guix/channels.scm} file if it exists and if the per-user
@file{~/.config/guix/channels.scm} is not present.  This allows administrators
of multi-user systems to define site-wide defaults.")
         (es "Ahora la orden @command{guix pull} lee el fichero
@file{/etc/guix/channels.scm} si existe y el fichero personalizable
@file{~/.config/guix/channels.scm} no está presente. Esto permite a quienes
administran sistemas con múltiples usuarias definir valores predeterminados
en el sistema."))))

Each news entry refers to a commit, the commit that introduced the change it documents, and it has a title and body. Those can use Texinfo markup for rich formatting, and translations can be provided directly within the news file.

When guix pull --news runs, it determines which news entries are applicable given the user’s previous Guix instance. The (guix channels) module provides a simple programming interface for that:

(use-modules (guix channels) (srfi srfi-1))

(channel-news-for-commit (first %default-channels)
                         "66b707a7d2325daadeed5ca913637eea3a2628e7"
                         "ac19950507e941b6263f62f4ee4e8934c1b1598e")
⇒ (#<<channel-news-entry> commit: "3e962e59d849e4300e447d94487684102d9d412e" tag: #f title: (("en" . "@command{guix graph} now supports package\ntransformations") …) body: …> #<<channel-news-entry> commit: "49af34cfac89d384c46269bfd9388b2c73b1220a" tag: #f title: (("en" . "@command{guix pull} now honors\n@file{/etc/guix/channels.scm}") …) body: …>)

One thing is quite unusual (one might say “weird” :-)) about this news format: it refers to commit IDs “in-band”. In other words, unlike Git commit logs, which are “out-of-band”, the news file is contained inside the repository that it refers to. Technically, it means that before pushing a news entry, one must make sure it refers to the right commit ID (the news format allows you to refer to tags as well, but one may not want to create tags for every “news-worthy” change). Likewise, rebasing might invalidate commit IDs that appear in the news file. So this whole “in-band” log has drawbacks, but the big win is that it allows us to amend news entries to fix typos, add translations, and so on.

In other news…

Since it was applied a bit more than a month ago, we’ve already put the news mechanism to good use on quite a few occasions: giving users instructions on how to deal with locales after the last glibc upgrade, giving them upgrade info for CVE-2019-18192, telling them about new command-line options, and more.

In parallel, given that reading the mailing lists is akin to “drinking from a fire hose” as they say, Christopher Baines has been thinking about how to provide regular development updates to interested users and developers. Chris announced last week a prototype of a “Guix Weekly News” web site that would aggregate information about package updates automatically extracted from the Guix Data Service, along with manually written updates. It would seem that this service could readily grab info from channel news as well.

What about you, what do you expect in terms of news distribution? Join us on the mailing list and on IRC and let us know!

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 Ludovic Courtès at November 12, 2019 02:00 PM

Programming Praxis

Reverse A Linked List

We’ve done this before, but I saw questions asked about this task on three different beginner-programming forums this weekend (it must that that time in the semester when teachers introduce linked lists), and it never hurts to do some basic drill.

Your task is to write a program that reverses a linked list. 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 November 12, 2019 10:00 AM

November 08, 2019

Programming Praxis

Union Of Two Bags

Today’s exercise is somebody’s homework:

A bag is a list of key/count pairs: for instance, a bag containing three of item E, three of item R, and three of item A can be written E3R3A3. The union of two bags is a single bag containing a list of key/count pairs in which each item in each of the two bags has its count combined in a single item: for instance, the union of bags E3R3A3 and B3R3F3 is E3R6A3B3F3. The order of items in the bags is not significant.

Your task is to write three programs to compute the union of two bags, with time complexities O(mn), O((m+n) log (m+n)), and O(m+n), where m and n are the sizes of the two bags. 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 November 08, 2019 10:00 AM

November 05, 2019

Programming Praxis

Encrypting Ed(1)

When I introduced the topic crypt(1) last week my actual goal was to write an editing script using ed on an encrypted file; that’s when I realized that crypt(1) was missing and that ed no longer had an -x flag. I didn’t want anything fancy, just basic encryption. I knew the old crypt(1) was no good (actually, it was no good when it was introduced forty years ago) but I was surprised that Unix and Linux had not kept up with some kind of encryption. Humbug!

Your task is to enhance ed by adding the -x encryption flag. 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 November 05, 2019 10:00 AM