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 guix-devel@gnu.org. Feel free to drop in #guix on irc.freenode.net 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 audio-video.gnu.org. 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 audio-video.gnu.org. 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 (noreply@blogger.com) at October 15, 2020 10:18 PM

Vasilij Schneidermann

State of Emacs Lisp on Guile

Update: Factual corrections to Robin Templeton’s work.

Update: Added an extra set of benchmarks for Guile 3 in a Debian Sid Docker container.

Disclaimer: I don’t use Guile. I hardly know it. There are other Scheme implementations I know far better. But since Guile Emacs is a hot topic with much hopes and unproven claims, I experiment with it every now and then. All “benchmark” results here are to be taken with caution, they’ve been created using Guile 2.2.6 and Emacs 26.3 on a Thinkpad X230t running Arch Linux.

With that out of the way, laurus from #emacs[1] reminded me that one of the reasons why Guile Emacs was possible in the first place is Guile’s language tower, with Emacs Lisp being one of the supported languages. But what does that mean? How complete is the Emacs Lisp support? What can it be used for? These and a few other questions are the topic of this blog post.

In need of a spec

Standardized programming languages have the great benefit of being based on a specification one can consult whenever in doubt of how things are supposed to behave. This allows several competing implementations to be developed, with their own unique strengths and benefits. if you adhere to the standard, switching between implementations isn’t hard and can help shaking out bugs, for example when compiling your C programs with different compilers.

Things get considerably harder if your chosen language decided to forego this approach and the correct behavior is defined by it, yet this didn’t stop people from writing alternative implementations for programming languages such as Python and Ruby. Emacs Lisp got into a similar situation ever since Guile was extended to the degree of supporting Emacs Lisp as an additional language. Provided your version of Guile is new enough, you can evaluate trivial code in the REPL:

scheme@(guile-user)> (define foo 1)
scheme@(guile-user)> foo
$1 = 1
scheme@(guile-user)> ,L elisp
Happy hacking with Emacs Lisp!  To switch back, type `,L scheme'.
elisp@(guile-user)> (defvar bar 2)
$2 = bar
elisp@(guile-user)> bar
$3 = 2

So far so good. But how much of Emacs Lisp is supported? Not much apparently, many common functions like message and error are unbound. It doesn’t seem possible to do anything with buffers or files either. This greatly limits the possibilities of writing useful scripts in Emacs Lisp[2]. One way of determining what exactly is supported would be consulting the source code, but where’s the fun in that when you could instead test it programmatically, thereby creating an executable spec…

Generating the spec

The usual test approaches fail me. Reading test inputs via stdin with read-string? Accessing the arguments with argv? Reading from a file with insert-file-contents? Obtaining an environment variable with getenv? None of that is supported. At least you can print to stdout with princ. I went for a slightly different approach instead, obtain a list of functions/variables[3] in a minimal Emacs environment, then generating a test file that checks their existence and prints a test summary. Here’s the code generation part:

(defun printf (fmt &rest args)
  (princ (apply 'format fmt args)))

(printf ";; elisp spec adherence test
(defvar passed 0)
(defvar failed 0)
(defun test-sym (pred sym)
  (if (funcall pred sym)
      (setq passed (1+ passed))
    (setq failed (1+ failed))))
(defun test-fun (sym) (test-sym 'fboundp sym))
(defun test-var (sym) (test-sym 'boundp sym))\n\n")

(mapatoms
 (lambda (atom)
   (when (fboundp atom)
     (printf "(test-fun '%S)\n" atom))
   (when (and (not (keywordp atom)) (boundp atom))
     (printf "(test-var '%S)\n" atom))))

(printf "\n")
(printf "(princ \"Passed: \")\n")
(printf "(princ passed)\n")
(printf "(terpri)\n")
(printf "\n")
(printf "(princ \"Failed: \")\n")
(printf "(princ failed)\n")
(printf "(terpri)\n")

Assuming it’s been saved as gen-elisp-spec.el, the executable spec itself is generated with emacs -Q --batch --script gen-elisp-spec.el > elisp-spec.el. Here’s a test session using Emacs and Guile:

[wasa@box ~]$ time emacs -Q --batch --script elisp-spec.el
Passed: 9567
Failed: 2
emacs -Q --batch --script elisp-spec.el  0.10s user 0.02s system 99% cpu 0.117 total
[wasa@box ~]$ time guile --language=elisp elisp-spec.el
Passed: 137
Failed: 9432
guile --language=elisp elisp-spec.el  77.62s user 0.27s system 103% cpu 1:15.04 total

This is kind of surprising. I didn’t expect Emacs to fail its own test and didn’t expect Guile to implement this little either. Most surprising is the abysmal speed of the test[4], I’m looking forward to anyone being able to explain that part to me. Here’s one more test using the official Debian Sid Docker image with Emacs 26.3 and Guile 3.0.2:

root@d27668492764:/# time emacs -Q --batch --script elisp-spec.el
Passed: 9108
Failed: 2

real    0m0.104s
user    0m0.097s
sys     0m0.007s
root@d27668492764:/# time guile --language=elisp elisp-spec.el
Passed: 137
Failed: 8973

real    6m20.950s
user    10m32.294s
sys     0m7.846s

This is not exactly an improvement. At least the numbers are small enough to print out the offending symbols, for Emacs it’s atom and printf (which polluted the test environment), for Guile I’ve taken the liberty of annotating the list:

;; binding
let let*
;; functions
lambda apply funcall
;; evaluation
eval load eval-and-compile eval-when-compile
;; sequences
aref aset make-vector nth
;; sequencing
progn prog2 prog1
;; iteration
dolist while
;; control flow
if when unless cond
;; short-circuiting
or and not
;; explicit nonlocal exit
throw catch
;; exceptions
signal condition-case unwind-protect
;; input
read-from-minibuffer
;; output
prin1-to-string print princ send-string-to-terminal terpri
;; cxr
car cdr caar cadr cdar cddr
car-safe cdr-safe
nthcdr
;; associations
assoc assq
;; search
member memql memq
;; destructive list processing
nreverse setcar setcdr rplaca rplacd
;; other list processing
cons list make-list `
mapcar mapc
append concat
reverse
length
;; symbols
defconst defvar defun defmacro
get put
fset set setq setplist
symbol-function symbol-name symbol-plist symbol-value
intern make-symbol
fmakunbound makunbound
quote function
;; plist
plist-get plist-put
lax-plist-get lax-plist-put
plist-member
;; strings
string string-match substring
upcase downcase
;; predicates
zerop floatp stringp numberp integerp wholenump
boundp fboundp functionp symbolp
consp listp nlistp
atom null
;; math
1+ 1-
fceiling ffloor ftruncate fround float
abs
min max
;; comparators
> < >= <= /= =
eq eql equal
string-equal string=
;; numerical operators
+ - * %
;; misc
random

Some notable omissions and differences:

  • No division. Most likely incompatible with Scheme’s numeric tower.
  • Input is read with read-from-minibuffer, not read-string.
  • send-string-to-terminal is unusual to have, but most likely the primitive output function.
  • string-match is nice to have, but of limited use without match-string.
  • prin1-to-string exists, prin1 doesn’t.
  • print doesn’t add newlines and behaves like prin1 should.

To do anything outside of textbook exercises you’d need to define extra primitives. Guile’s module/language/elisp/boot.el shows how to apply a band-aid on some of the previous shortcomings:

(fset '/ (@ (guile) /))
(fset 'read-string 'read-from-minibuffer)
(fset 'prin1 (@ (guile) write))
(defun print (object) (prin1 object) (terpri))

You could write more of it to reach that goal of using Emacs Lisp as scripting language outside of Emacs, but need to write Scheme to get there. Why not just use Scheme? Why invent a new runtime? The effort would be comparable to what node.js did for Chrome’s JavaScript engine, except with a far weaker sales-pitch.

What does this mean for Guile Emacs?

What I’ve shown above is barely sufficient to bootstrap an Emacs on top of it. Guile Emacs requires a customized version of Guile and Emacs, then loads up the supporting Emacs Lisp files to do the rest. There are more incompatibilities, like called-interactively-p being stubbed out. Extending the presented rudimentary spec to contain actual tests would help with tracking progress and usability. It might even improve the overall quality of GNU Emacs itself, provided that the core developers are on board and believe in the idea. I’ve briefly searched emacs-devel for previous discussion on the topic, but only found bikeshedding about Guile Emacs itself, so anyone who feels strongly about the subject, feel free to start a discussion there!

With regards to Guile Emacs itself, the situation is trickier. The above repositories have not been touched for five years, with Robin Templeton being the sole contributor for five Google Summer of Code events. Even though the work is far from complete, it is impressive what a college student managed to do under supervision of Guile’s maintainer Andy Wingo and Ludovic Courtès. Further advancements require similarly motivated individuals to participate in the Guile community and become part of the effort, much like with other free software projects. It’s tempting to take a shortcut like donating to other developers, but unless they’ve figured out a way of converting that money into equivalent work, there will be little connection between what you give away and what they do in return. This again is a topic worth discussing, preferably with the people that can make a change.

[1]laurus did some research as well, you can find an interesting discussion on the #guile channel: http://logs.guix.gnu.org/guile/2020-05-16.log
[2]At least you could now solve SICP in Emacs Lisp with less footguns: You have bignums, lexical scoping by default and TCO!
[3]This isn’t exactly correct, what’s tested for is whether the symbol has its function/value slot bound which may contain other things, for example macros and keywords.
[4]Consider that people like to advocate for Guile Emacs with the argument that it will make for a faster Emacs. While this may hold true in the long term, it’s nowhere near close to that yet. Here’s hoping that Guile 3 will alleviate some of the pain…

by Vasilij Schneidermann at October 15, 2020 07:58 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:

/gnu/store/n7jkfajw0fzp975hv0b9v18r9bbr961q-disk-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
  (operating-system
    (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"))
                        %base-file-systems))
    (host-name "guixygnu")
    (timezone "Europe/Amsterdam")
    (packages (cons openssh-sans-x %base-packages/hurd))
    (services (cons (service openssh-service-type
                             (openssh-configuration
                              (openssh openssh-sans-x)
                              (use-pam? #f)
                              (port-number 2222)
                              (permit-root-login #t)
                              (allow-empty-passwords? #t)
                              (password-authentication? #t)))
               %base-services/hurd))))

%hurd-os

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).

Substitutes

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
         (hurd-vm-configuration
          (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).

WARNING

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:

 (build-machine
  (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
GNU/Linux
$ guix build hello -s i586-gnu
The following derivation will be built:
   /gnu/store/jqdvjhcxxnbq370y8i2c973c9zfiqrgl-hello-2.10.drv
[…]
guix offload: sending 1 store item (12 MiB) to 'localhost'...
offloading '/gnu/store/jqdvjhcxxnbq370y8i2c973c9zfiqrgl-hello-2.10.drv' to 'localhost'...
[…]
/gnu/store/803q5wapfnmr91ag8d9dzwabkbdxz3ay-hello-2.10
$ 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/ld.so.1, for GNU/Hurd 0.0.0, not stripped

Hurrah!

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
Signature: 1;berlin.guix.gnu.org;KHNpZ25hdHVyZSAKIChkYXRhIAogIChmbGFncyByZmM2OTc5KQogIChoYXNoIHNoYTI1NiAjMDVGOEY5NjMxRUU5QzcxM0REQUNBRTYwNUNCNjJBNzlDNUY4NEVFQTIwMjc5OERBNTQ3NURCOUU2Q0FBRDMwMSMpCiAgKQogKHNpZy12YWwgCiAgKGVjZHNhIAogICAociAjMDVBMzkzMTgwOUY1RkQyMTdGMDM4MUVDMTJEODYyNzIyOEYyNjJGRDA4MTcxQjREMzZBNEM0RjBBNjZEQkY4NSMpCiAgIChzICMwQTc2RjZGNENCOTMzQTczNzA4QkNGMzRGREExMzkyOTRGQTQxREQzQTUwQkEwOUE0ODRCQUQyOTA4MjQ5ODIxIykKICAgKQogICkKIChwdWJsaWMta2V5IAogIChlY2MgCiAgIChjdXJ2ZSBFZDI1NTE5KQogICAocSAjOEQxNTZGMjk1RDI0QjBEOUE4NkZBNTc0MUE4NDBGRjJEMjRGNjBGN0I2QzQxMzQ4MTRBRDU1NjI1OTcxQjM5NCMpCiAgICkKICApCiApCg==

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"))))

(operating-system
  (inherit %hurd-vm-operating-system)
  (users ...)
  (packages
    (cons* diffutils file findutils gawk gdb-minimal git-minimal
           gnu-make grep gzip less m4 openssh-sans-x tar xz
           (append
            guix-packages
            (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 10.0.2.2


  This is the GNU Hurd.  Welcome.

janneke@childhurd ~$ git config --global url."git+ssh://git.sv.gnu.org/srv/git/".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 https://ci.guix.gnu.org...
updating substitutes from 'https://ci.guix.gnu.org'... 100.0%
https://ci.guix.gnu.org
  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 'https://ci.guix.gnu.org'... 100.0%
The following derivations will be built:
   /gnu/store/gxq5flc8kwpn999dw9xxvldy9xfd0q2x-profile.drv
   /gnu/store/vfkjnwgl4ckyklrl2z4q8x2vnlrwwyfr-gcc-toolchain-7.5.0.drv
   /gnu/store/zh6snj49ayrpw24jn7whpzygj1fpy9cm-module-import-compiled.drv

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 'https://ci.guix.gnu.org'... 100.0%
0.1 MB will be downloaded:
   /gnu/store/803q5wapfnmr91ag8d9dzwabkbdxz3ay-hello-2.10
substituting /gnu/store/803q5wapfnmr91ag8d9dzwabkbdxz3ay-hello-2.10...
downloading from https://ci.guix.gnu.org/nar/lzip/803q5wapfnmr91ag8d9dzwabkbdxz3ay-hello-2.10 ...
 hello-2.10  52KiB                    258KiB/s 00:00 [##################] 100.0%

/gnu/store/803q5wapfnmr91ag8d9dzwabkbdxz3ay-hello-2.10

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 irc.freenode.net 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.

ssh-keygen

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>_rsa.pub

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 https://sv.gnu.org/people/viewgpg.php?user_id=15145 -qO - | gpg --import -
wget https://git.savannah.gnu.org/cgit/guix.git/plain/etc/guix-install.sh
chmod +x guix-install.sh
./guix-install.sh
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
                     ssh)
(use-package-modules admin
                     certs
                     package-management
                     ssh
                     tls)

(operating-system
  (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
               (bootloader
                (bootloader
                 (inherit grub-bootloader)
                 (installer #~(const #t))))))
  (file-systems (cons (file-system
                        (device "/dev/sda")
                        (mount-point "/")
                        (type "ext4"))
                      %base-file-systems))
  (swap-devices (list "/dev/sdb"))

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

  (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"))
               %base-user-accounts))

  (packages (cons* nss-certs            ;for HTTPS access
                   openssh-sans-x
                   %base-packages))

  (services (cons*
             (service dhcp-client-service-type)
             (service openssh-service-type
                      (openssh-configuration
                       (openssh openssh-sans-x)
                       (password-authentication? #f)
                       (authorized-keys
                        `(("janedoe" ,(local-file "janedoe_rsa.pub"))
                          ("root" ,(local-file "janedoe_rsa.pub"))))))
             %base-services)))

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 "janedoe_rsa.pub")) ; replace with your ssh key
("root" ,(local-file "janedoe_rsa.pub")) ; 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/id_rsa.pub) as <your-username-here>_rsa.pub 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/id_rsa.pub .
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>
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
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
SHA256:0B+wp33w57AnKQuHCvQP0+ZdKaqYrI/kyU7CfVbS7R4.
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 198.58.98.76 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,

10001366650-1

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

1000136650\20111

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

8424432925592889329288197322308900672459420460792433

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 NEWS.md 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 https://scheme.fail, 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 20, 2020

Mark Damon Hughes

August 04, 2020

Programming Praxis

Loglog

There are 19,055 distinct words in the Bible:

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

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

Mark Damon Hughes

Racket CS 7.8

Big plus: ARM64 support!

Big minus: Neither DRRacket nor any built .app launches on the Mac, you have to call them from command line. Gross incompetence & zero testing.

My basic gridtest.rkt demo still takes 100ms to render a frame, needs to be <16ms. But that's interpreting from the shell, and I may look and see if they have a more efficient graphics API.

The bigger problem is that compiling doesn't work with packages, or at least I don't have the right magic invocations:

% cat build.zsh
#!/bin/zsh

rm -rf build
mkdir build
# Windows: --ico foo.ico
# Mac: --icns foo.icns
time raco exe --cs --gui ++lib memoize ++lib rsound ++lib portaudio -o build/gridtest gridtest.rkt

% ./build.zsh && ./build/gridtest.app/Contents/MacOS/gridtest
raco exe --cs --gui ++lib memoize ++lib rsound ++lib portaudio -o    39.14s user 2.40s system 87% cpu 47.390 total
ffi-lib: could not load foreign library
  path: libportaudio.2.dylib
  system error: dlopen(libportaudio.2.dylib, 6): image not found
  context...:
   raise-dll-error
   .../ffi/unsafe.rkt:131:0: get-ffi-lib
   call-in-empty-metacontinuation-frame
   proc
   call-in-empty-metacontinuation-frame
   body of '#%embedded:portaudio/portaudio:
   temp35_0
   run-module-instance!
   [repeats 6 more times]
   perform-require!
   call-in-empty-metacontinuation-frame
   eval-one-top
   eval-compiled-parts
   embedded-load
   proc
   call-in-empty-metacontinuation-frame

Well, that's fucked. 40 seconds and a fuck you because it doesn't bring in the dylib it needs.

Obviously I could just say "install Racket, run this script", but that's lame and distributes source, which in a real game I don't want to do.

by mdhughes at August 04, 2020 04:34 AM