# Planet Scheme

## May 23, 2017

### Programming Praxis

#### Matrix Determinant And Inverse

Today’s exercise is preliminary to the exercise we will have later this week. You are to write programs that calculate the determinant and inverse of a matrix. I won’t go into the math involved behind the matrix arithmetic, as there are many sources on the internet that know far more about the process than I. Google for “matrix determinant” or “matrix inverse”; I used YouTube for my instruction.

Your task is to write programs that calculate the determinant and inverse of a matrix. 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.

## May 22, 2017

### GNU Guix

#### GNU Guix and GuixSD 0.13.0 released

We are pleased to announce the new release of GNU Guix and GuixSD, version 0.13.0!

The release comes with GuixSD USB installation images, a virtual machine image of GuixSD, and with tarballs to install the package manager on top of your GNU/Linux distro, either from source or from binaries.

It’s been 5 months since the previous release, during which 83 people contribute code and packages. The highlights include:

• Guix now supports aarch64 (64-bit ARM processors). This release does not include a binary installation tarball though, and our build farm does not provide aarch64 substitutes yet. We are looking for aarch64 hardware to address this. Please get in touch with us if you can help!
• Likewise, this release no longer includes a mips64el tarball, though Guix still supports that platform. We do not know whether we will continue to support mips64el in the long run; if you’d like to weigh in, please email us on guix-devel@gnu.org!
• The GuixSD installation image now supports UEFI. GuixSD can also be installed on Btrfs now.
• GuixSD has support to run system services (daemons) in isolated containers as a way to mitigate the harm that can be done by vulnerabilities in those daemons. See this article from April.
• A new guix pack command to create standalone binary bundles is available. We presented it in March.
• Guix now runs on the brand-new 2.2 series of GNU Guile. The transition led to hiccups that we have been addressing, in particular for users of guix pull. Among other things though, the noticeable performance improvement that comes for free is welcome!
• guix publish, which is what we use to distribute binaries, has a new --cache operation mode that improves performance when distributing binaries to a large number of users, as is the case of our build farm.
• Many reproducibility issues found in packages have been addressed—more on that in a future post.
• 840 new packages, leading to a total of 5,400+, and many updates, including glibc 2.25, Linux-libre 4.11, and GCC 7.
• New system services for Redis, Exim, Open vSwitch, and more. The interface of existing services, notably that of the NGINX service, has been greatly improved.
• Many bug fixes!

See the release announcement for details.

#### About GNU Guix

GNU Guix is a transactional package manager for the GNU system. The Guix System Distribution or GuixSD is an advanced distribution of the GNU system that relies on GNU Guix and respects the user&aposs freedom.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. Guix uses low-level mechanisms from the Nix package manager, except that packages are defined as native Guile modules, using extensions to the Scheme language. GuixSD offers a declarative approach to operating system configuration management, and is highly customizable and hackable.

GuixSD can be used on an i686 or x86_64 machine. It is also possible to use Guix on top of an already installed GNU/Linux system, including on mips64el, armv7, and aarch64.

## May 19, 2017

### Programming Praxis

#### Just Showing Off

As I have mentioned on several previous occasions, I frequently receive email from students asking for homework help, which I routinely ignore. Less frequently, I receive email from someone who tells me that Scheme is a horrible programming language, they don’t understand it, it is unreadable, there are too many parentheses, blah, blah, blah, and wouldn’t it be better if I wrote my blog in C#. (I don’t know what’s wrong with C# people, but I get more of them than any other language zealots.) Usually I ignore them, too, but the other day I engaged one of those correspondents who singled out macros as a particular wart on the face of Scheme. So I wrote to him and gave him this macro, which I used to calculate fibonacci numbers; the whole story is on the next page:

(define-syntax define-memoized
(syntax-rules ()
((define-memoized (f arg ...) body ...)
(define f
(let ((cache (list)))
(lambda (arg ...)
(cond ((assoc (,arg ...) cache) => cdr)
(else (let ((val (begin body ...)))
(set! cache (cons (cons (,arg ...) val) cache))
val)))))))))

When I showed him how to speed up the calculation of fibonacci numbers by memoizing sub-computations, he grudgingly agreed there might be something there, but it wouldn’t translate to C# (I didn’t disagree with that comment).

Your task is to write a program that shows off some special feature of your favorite programming language; tell the story how it makes your language better than any others, and give a real-life example. 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.

## May 16, 2017

### Programming Praxis

A license plate number has form ABC-123, three letters followed by three digits. You are to store the set of license plate numbers, assume you will have about a hundred thousand of them, and be able to answer queries like:

* Is license plate PLB-123 a member of the set?

* How many license plates begin with the letters PLB?

* What is the list of license plates that begin with the letters PLB?

Your task is to write programs to store and query a list of license plate 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.

## May 12, 2017

### Programming Praxis

#### Division By Repeated Subtraction

I traded several emails this week with a programming student who was having trouble with this assignment:

Write a function that divides two numbers and returns their quotient. Use recursive subtraction to find the quotient.

The student went on to explain that he thought he needed to use a counter variable that he incremented each time the function recurred, but he didn’t know how to do that because the function could only take two arguments; it had to be of the form (define (divide a b) ...).

Your task is to write the function, and explain to the student how it works. 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.

## May 09, 2017

### Programming Praxis

#### Distinct Characters

We’ve done similar exercises in the past:

Write a program to determine if all the characters in a string are distinct. For instance, the word “Programming” has two m and two g, so all the characters are not distinct, but the word “Praxis” has six distinct characters.

Your task is to write a program to determine if all the characters in a string are distinct; you should provide three solutions, one that takes time O(n²), one that takes time O(n log n), and one that takes time O(n). 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.

## May 05, 2017

### Programming Praxis

#### Calculating Derivatives

I’ve seen this before, and when I ran across it again a few days ago decided to share it with all of you. This is why I like Scheme so much:

In mathematics, the derivative of a function f(x) is $f'(x) = \lim_{dx \to 0} \frac{f(x+dx)-f(x)}{dx}$. Here’s a simple implementation in Scheme, with an example:

Petite Chez Scheme Version 8.4

> (define dx 0.0000001)
> (define (deriv f)
(define (f-prime x)
(/ (- (f (+ x dx)) (f x))
dx))
f-prime)
> (define (cube x) (* x x x))
> ((deriv cube) 2)
12.000000584322379
> ((deriv cube) 3)
27.000000848431682
> ((deriv cube) 4)
48.00000141358396

Those results are reasonably close to the actual derivative of $3x^2$. The code is identical to the math.

Your task is to write a function to calculate derivatives in your favorite language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution in the comments below.

## May 02, 2017

### Programming Praxis

#### Base Conversion

I continue cleaning out my list of saved homework questions:

Given a number represented as a string in base 2, convert the number to a string in base 4. For instance, the number 110110002 = 31204.

Your task is to write a program that converts numbers from base 2 to base 4; for extra credit, write a program that converts from any base to another. 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.

## April 28, 2017

### Programming Praxis

#### Abbreviated Sentences

Sometimes people send me their homework problems and expect me to write programs for them. I ignore such people, but I do collect the tasks and use them in the blog from time to time, always waiting several months until the term has ended. Today’s exercise comes by that route:

Write a program that takes as input a sentence (a sequence of characters) and abbreviates it by replacing each word (a maximal sequence of letters) with the first letter of the word, followed by the number of letters in the middle of the word, followed by the last letter of the word. For instance, Programming Praxis is abbreviated P9g P4s. Any non-letter characters in the input should be retained in their original position in the output.

Your task is to write a program that abbreviates sentences. 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.

## April 25, 2017

### Programming Praxis

#### Etude On A Binary Tree

We have today another in our occasional series of exercises on binary trees; the input tree need not necessarily be ordered or balanced:

Given a binary tree containing integers, find the sum of all nodes at an even distance from the root, less the sum of all nodes at an odd distance from the root.

For instance, given the binary tree shown below, the requested sum is 1 – 2 – 3 + 4 + 5 + 6 + 7 – 8 – 9 – 10 – 11 – 12 – 13 – 14 – 15 = -74:

           1
2           3
4     5     6     7
8  9 10 11 12 13 14 15

(I’m not an artist; you’ll have to imagine the lines connecting the various levels.)

Your task is to write a program to compute alternate sums and differences of the nodes of a binary tree. 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.

## April 21, 2017

### Programming Praxis

#### Damsel And Suitor

Chris Smith tweets mathematical curiosities at @aap03102. This one caught my eye the other day:

This is from 1779: a time when puzzles were written in poetry, solutions were assumed to be integers and answers could be a bit creepy:

Questions proposed in 1779, and answered in 1780.

I. QUESTION 742, by Mr. John Penberthy.

I’m in love with a damsel, the pride of the plain,
Have courted and talk’d in Ovidian strain;
But vain is the rhetoric us’d by my tongue,
She says I’m too old and that she is too young:
From the foll’wing equations, dear ladies, unfold;
If she be too young, or if I be too old.

x3 + xy2 = 4640y
x2yy3 = 537.6x

Where x represents my age, and y the damsel’s.

Your task is to compute the ages of the damsel and her suitor. 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.

## April 18, 2017

### Greg Hendershott

#### Racket Makefiles

A few years ago I wrote about makefiles for Racket. Some things have changed.

1. The old makefile built and pushed documentation to a GitHub Pages branch of the repo. That’s no longer necessary: The Racket package catalog builds and hosts documentation.

2. The Racket package catalog puts a yellow badge of shame on packages with missing dependencies (deps and build-deps in the package’s info.rkt). I want the makefile to check this.

3. In .travis.yml files for Travis CI, I think the script section ought to simply invoke targets in the makefile — delegating details to the latter.

4. Likewise some details needn’t even be in the makefile — they can move to the collection’s info.rkt. Example: The list of directories to clean.

5. The old makefile had separate PACKAGENAME and COLLECTS variables; for single-collection packages they were the same value. I wanted to simplify this to just the package name and use the appropriate package variants of raco commands.

In that spirit, here’s an updated Makefile, which I recently started using in the rackjure, markdown, and frog projects.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 PACKAGE-NAME=rackjure # Racket 6.1 adds pkg dep checking. ifeq ($(findstring "$(RACKET_VERSION)", "6.0", "6.0.1"),) DEPS-FLAGS=--check-pkg-deps --unused-pkg-deps else DEPS-FLAGS= endif all: setup # Primarily for use by CI. # Installs dependencies as well as linking this as a package. install: raco pkg install --deps search-auto remove: raco pkg remove $(PACKAGE-NAME) # Primarily for day-to-day dev. # Note: Also builds docs (if any) and checks deps. setup: raco setup --tidy$(DEPS-FLAGS) --pkgs $(PACKAGE-NAME) # Note: Each collection's info.rkt can say what to clean, for example # (define clean '("compiled" "doc" "doc/")) to clean # generated docs, too. clean: raco setup --fast-clean --pkgs$(PACKAGE-NAME) # Primarily for use by CI, after make install -- since that already # does the equivalent of make setup, this tries to do as little as # possible except checking deps. check-deps: raco setup --no-docs $(DEPS-FLAGS)$(PACKAGE-NAME) # Suitable for both day-to-day dev and CI test: raco test -x -p $(PACKAGE-NAME)  The two main scenarios here: • Day-to-day development: make setup and make test. • CI: make install, make check-deps, and make test. I think you could probably use this as a template for any single-collection package project. Just change PACKAGE-NAME. Possibly append a target or two for something unique to your project. This Makefile is designed to work with Racket 6.0 or newer — because I have some existing packages that support Rackets that old. If you only care about Racket 6.1 or newer, then all this:  1 2 3 4 5 6 # Racket 6.1 adds pkg dep checking. ifeq ($(findstring "$(RACKET_VERSION)", "6.0", "6.0.1"),) DEPS-FLAGS=--check-pkg-deps --unused-pkg-deps else DEPS-FLAGS= endif  can become just this:  1 DEPS-FLAGS=--check-pkg-deps --unused-pkg-deps  By the way, I wouldn’t call myself a very experienced user of make. For example the way I check for Racket < 6.1 seems smelly — but it was the least-worst way I could figure out. So please feel free to share any suggestions or corrections in the comments. ### Programming Praxis #### Longest Line Today’s exercise is simple: Write a program that prints the longest line in a file. If there is a tie for the longest line, you may print any of the longest lines, or all of them, at your option. There are lots of ways to solve this problem, and I expect that my fun-loving readers will come up with some outlandish solutions, so to make this a sensible exercise we add two rules: First, if you comment you must provide at least two solutions. Second, at least one of your solutions must be “reasonable” in the sense that you would actually use it in a production environment. Your task is to write a program to find the longest line in a file. 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. ## April 14, 2017 ### GNU Guix #### Running system services in containers At FOSDEM, in the awesome Guile track, I briefly demoed a new experimental GuixSD feature as part my talk on system services: the ability to run system services in containers or “sandboxes”. This post discusses the rationale, status, and implementation of this feature. #### The problem Our computers run many programs that talk to the Internet, and the Internet is an unsafe place as we all know—with states and assorted organizations collecting “zero-day exploits” to exploit them as they see fit. One of the big tasks of operating system distributions has been to keep track of known software vulnerabilities and patch their packages as soon as possible. When we look closer, many vulnerabilities out there can be exploited because of a combination of two major weaknesses of GNU/Linux and similar Unix-like operating systems: lack of memory-safety in the C language family, and ambient authority in the operating system itself. The former leads to a huge class of bugs that become security issues: buffer overflows, use-after-free, and so on. The latter makes them more exploitable because processes have access to many resources beyond those they really need. Security-sensitive software is now increasingly written in memory-safe languages, as is the case for Guix and GuixSD. Projects that have been using C are even considering a complete rewrite, as is the case for Tor. Of course the switch away from memory-unsafe languages won’t happen overnight, but it’s good to see a consensus emerging. The operating system side of things is less bright. Although the principle of least authority (POLA) has been well-known in operating system circles for a long time, it remains foreign to Unix and GNU/Linux. Processes run with the full authority of their user. On top of that, until recent changes to the Linux kernel, resources were global and there was essentially a single view of the file system, of the process hierarchy, and so on. So when a remote-code-execution vulnerability affects a system service—like in the BitlBee instant messaging gateway (CVE-2016-10188) running on my laptop—an attacker could potentially do a lot on your machine. Fortunately, many daemons have built-in mechanisms to work around this operating system defect. For instance, BitlBee, and Tor can be told to switch to a separate unprivileged user, avahi-daemon and ntpd can do that and also change root. These techniques do reduce the privileges of those processes, but they are still imperfect and ad hoc. #### Increasing process isolation with containers The optimal solution to this problem would be to honor POLA in the first place. As an example, the venerable GNU/Hurd is a capability-based operating system. Thus, GNU/Hurd has supported fine-grained virtualization from the start: a newly-created process can be given a capability to its own proc server (which implements the POSIX notion of processes), to a specific TCP/IP server, etc. In addition, its POSIX personality offers interesting extensions, such as the fact that processes run with the authority of zero or more UIDs. For instance, the Hurd’s login program starts off with zero UIDs and gains a UID when someone has been authenticated. Back to GNU/Linux, “namespaces” have been introduced as a way to retrofit per-process views of the system resources, and thus improve isolation among processes. Each process can run in a separate namespace and thus have a different view of the file system, process tree, and so on (a process running in separate namespaces is often referred to as a “container”, although that term is sometimes used to denote much larger tooling and practices built around namespaces.) Why not use that to better isolate system services? Apparently this idea has been floating around. systemd has been considering to extend its “unit files” to include directives instructing systemd to run daemons in separate namespaces. GuixSD uses the Shepherd instead of systemd, but running system services in separate namespaces is something we had been considering for a while. In fact, adding the ability to run system services in containers was a low-hanging fruit: we already had call-with-container to run code in containers, so all we needed to do was to provide a containerized service starter that uses call-with-container. The Shepherd itself remains unaware of namespaces, it simply ends up calling make-forkexec-constructor/container instead of make-forkexec-constructor and that’s it. The changes to the service definitions of BitlBee and Tor are minimal. The end result, for Tor, looks like this: (let ((torrc (tor-configuration->torrc config))) (with-imported-modules (source-module-closure &apos((gnu build shepherd) (gnu system file-systems))) (list (shepherd-service (provision &apos(tor)) (requirement &apos(user-processes loopback syslogd)) (modules &apos((gnu build shepherd) (gnu system file-systems))) (start #~(make-forkexec-constructor/container (list #$(file-append tor "/bin/tor") "-f" #$torrc) #:mappings (list (file-system-mapping (source "/var/lib/tor") (target source) (writable? #t)) (file-system-mapping (source "/dev/log") ;for syslog (target source))))) (stop #~(make-kill-destructor)) (documentation "Run the Tor anonymous network overlay."))))) The with-imported-modules form above instructs Guix to import our (gnu build shepherd) library, which provides make-forkexec-constructor/container, into PID 1. The start method of the service specifies the command to start the daemon, as well as file systems to map in its mount name space (“bind mounts”). Here all we need is write access to /var/lib/tor and to /dev/log (for logging via syslogd). In addition to these two mappings, make-forkexec-constructor/container automatically adds /gnu/store and a bunch of files in /etc as we will see below. #### Containerized services in action So what do these containerized services look like when they’re running? When we run herd status bitblee, disappointingly, we don’t see anything special: charlie@guixsd ~$ sudo herd status bitlbee
Status of bitlbee:
It is started.
Running value is 487.
It is enabled.
Provides (bitlbee).
Requires (user-processes networking).
Conflicts with ().
Will be respawned.
charlie@guixsd ~$ps -f 487 UID PID PPID C STIME TTY STAT TIME CMD bitlbee 487 1 0 Apr11 ? Ss 0:00 /gnu/store/pm05bfywrj2k699qbxpjjqfyfk3grz2i-bitlbee-3.5.1/sbin/bitlbee -n -F -u bitlbee -c /gnu/store/y4jfxya56i1hl9z0a2h4hdar2wm Again this is because the Shepherd has no idea what a namespace is, so it just displays the daemon’s PID in the global namespace, 487. The process is running as user bitlbee, as requested by the -u bitlbee command-line option. We can invoke nsenter and take a look at what the BitlBee process “sees” in its namespace: charlie@guixsd ~$ sudo nsenter -t 487 -m -p -i -u $(readlink -f$(type -P bash))
root@guixsd /# echo /*
/dev /etc /gnu /proc /tmp /var
root@guixsd /# echo /proc/[0-9]*
/proc/1 /proc/5
root@guixsd /# read line < /proc/1/cmdline
root@guixsd /# echo $line /gnu/store/pm05bfywrj2k699qbxpjjqfyfk3grz2i-bitlbee-3.5.1/sbin/bitlbee-n-F-ubitlbee-c/gnu/store/y4jfxya56i1hl9z0a2h4hdar2wmivgbl-bitlbee.conf root@guixsd /# echo /etc/* /etc/hosts /etc/nsswitch.conf /etc/passwd /etc/resolv.conf /etc/services root@guixsd /# echo /var/* /var/lib /var/run root@guixsd /# echo /var/lib/* /var/lib/bitlbee root@guixsd /# echo /var/run/* /var/run/bitlbee.pid /var/run/nscd There’s no /home and generally very little in BitlBee’s mount namespace. Notably, the namespace lacks /run/setuid-programs, which is where setuid programs live in GuixSD. Its /etc directory contains the minimal set of files needed for proper operation rather than the complete /etc of the host. /var contains nothing but BitlBee’s own state files, as well as the socket to libc’s name service cache daemon (nscd), which runs in the host system and performs name lookups on behalf of applications. As can be seen in /proc, there’s only a couple of processes in there and “PID 1” in that namespace is the bitlbee daemon. Finally, the /tmp directory is a private tmpfs: root@guixsd /# : > /tmp/hello-bitlbee root@guixsd /# echo /tmp/* /tmp/hello-bitlbee root@guixsd /# exit charlie@guixsd ~$ ls /tmp/*bitlbee
ls: cannot access &apos/tmp/*bitlbee&apos: No such file or directory

Our bitlbee process runs in a separate mount, PID, and IPC namespace, but it runs in the global user namespace. The reason for this is that we want the -u bitlbee option (which instructs bitlbee to setuid to an unprivileged user at startup) to work as expected. It also shares the network namespace because obviously it needs to access the network.

A nice side-effect of these fully-specified execution environments for services is that it makes them more likely to behave in a reproducible fashion across machines—just like fully-specified build environments help achieve reproducible builds.

#### Conclusion

GuixSD master and its upcoming release include this feature and a couple of containerized services, and it works like a charm! Yet, there are still open questions as to the way forward.

First, we only looked at “simple” services so far, with simple static file system mappings. Good candidates for increased isolation are HTTP servers such as NGINX. However, for these, it’s more difficult to determine the set of file system mappings that must be made. GuixSD has the advantage that it knows how NGINX is configured and could potentially derive file system mappings from that information. Getting it right may be trickier than it seems, though, so this is something we’ll have to investigate.

Another open question is how the service isolation work should be split between the distro, the init system, and the upstream service author. Authors of daemons already do part of the work via setuid and sometimes chroot. Going beyond that would often hamper portability (the namespace interface is specific to the kernel Linux) or even functionality if the daemon ends up lacking access to resources it needs.

The init system alone also lacks information to decide what goes into the namespaces of the service. For instance, neither the upstream author nor the init system “knows” whether the distro is running nscd and thus they cannot tell whether the nscd socket should be bind-mounted in the service’s namespace. A similar issue is that of D-Bus policy files discussed in this LWN article. Moving D-Bus functionality into the init system itself to solve this problem, as the article suggests, seems questionable, notably because it would add more code to this critical process. Instead, on GuixSD, a service author can make the right policy files available in the sandbox; in fact, GuixSD already knows which policy files are needed thanks to its service framework so we might even be able to automate it.

At this point it seems that tight integration between the distro and the init system is the best way to precisely define system service sandboxes. GuixSD’s declarative approach to system services along with tight Shepherd integration help a lot here, but it remains to be seen how difficult it is to create sandboxes for complex system services such as NGINX.

#### About GNU Guix

GNU Guix is a transactional package manager for the GNU system. The Guix System Distribution or GuixSD is an advanced distribution of the GNU system that relies on GNU Guix and respects the user&aposs freedom.

In addition to standard package management features, Guix supports transactional upgrades and roll-backs, unprivileged package management, per-user profiles, and garbage collection. Guix uses low-level mechanisms from the Nix package manager, except that packages are defined as native Guile modules, using extensions to the Scheme language. GuixSD offers a declarative approach to operating system configuration management, and is highly customizable and hackable.

GuixSD can be used on an i686 or x86_64 machine. It is also possible to use Guix on top of an already installed GNU/Linux system, including on mips64el, armv7, and aarch64.

### Programming Praxis

#### Element Words

Today’s exercise is either an interview question or somebody’s homework, I’m not sure:

Given a list of all the symbols of the chemicals in the periodic table, and a list of all the words in the English language, find the longest word that can be made using symbols of the chemicals in the periodic table.

Your task is to write a program to find the longest word that can be formed from the periodic table. 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.