Planet Scheme

August 17, 2018

Programming Praxis

Matrix Search

Today’s exercise is a simple task in matrix manipulation. Given a matrix in which the rows are ordered but the columns or not, efficiently search for a specific item in the matrix. For instance, given the matrix

2 5 8
1 4 7
3 6 9

 

a search for 6 finds it in row 2 column 1, a search for 8 finds it in row 0 column 2, and a search for 0 fails.

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

by programmingpraxis at August 17, 2018 09:00 AM

August 14, 2018

Programming Praxis

A Simple Interview Question

Today’s interview question comes from Apple:

Write a program to add two integers. You may not use the + (addition) operator, but may use the ++ (increment by 1) or -- (decrement by 1) operators. Be sure your solution works for both positive and negative inputs.

Your task is to write a program to add two integers. 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 14, 2018 01:00 PM

August 13, 2018

GNU Guix

GSoC 2018 report: Cuirass Web interface

For the last three months I have been working with the Guix team as a Google Summer of Code intern. The title of my project is "GNU Guix (Cuirass): Adding a web interface similar to the Hydra web interface".

Cuirass is a continuous integration system which monitors the Guix git repository, schedules builds of Guix packages, and presents the build status of all Guix packages. Before my project, Cuirass did not have a web interface. The goal of the project was to implement an interface for Cuirass which would allow a user to view the overall build progress, details about evaluations, build failures, etc. The web interface of Hydra is a good example of such a tool.

In this post, I present a final report on the project. The Cuirass repository with the changes made during the project is located at http://git.savannah.gnu.org/cgit/guix/guix-cuirass.git. A working instance of the implemented interface is available at https://berlin.guixsd.org/. You can find more examples and demonstrations of the achieved results below.

About Cuirass

Cuirass is designed to monitor a git repository containing Guix package definitions and build binaries from these package definitions. The state of planned builds is stored in a SQLite database. The key concepts of the Cuirass internal state are:

  • Job specification. Specifications state what has actually to be done by Cuirass. A specification is defined by a Scheme data structure (an association list) which includes a job name, repository URL, as well as the branch and a procedure proc that specifies how this is to be built.

  • Evaluation. An evaluation is a high-level build actcion related to a certain revision of a repository of a given specification. For each specification, Cuirass continuously produces new evaluations which build different versions of the project represented by revisions of the corresponding repository. Derivations and builds (see below) each belong to a specific evaluation.

  • Derivation. Derivations represent low-level build actions. They store such information as name of a build script and its arguments, input and output of a build action, target system type, and necessary environment variables.

  • Build. A build is a result of build actions that are prescribed by a derivation. This could be a failed build or a directory containing the files that were generated by compiling a package.

Besides the core which executes build actions and records their results in the database, Cuirass includes a web server which previously only responded to a handful of API requests with JSON containing information about the current status of builds.

Web interface

The Cuirass web interface implemented during the project is served by the Cuirass web server whose functionality has been extended to generating HTML responses and serving static files. General features of the interface are listed below.

  • The backend is written in Guile and implements request processing procedures which parse request parameters and extract specific data to be displayed from the database.

  • The frontend consists of HTML templates represented with Guile SXML and the Bootstrap 4 CSS library.

  • The appearance is minimalistic. Every page includes only specific content information and basic navigation tools.

  • The interface is lightweight and widely accessible. It does not use JavaScript which makes it available to users who do not want to have JavaScript running in the browser.

Structure

Let's review the structure of the interface and take a look at the information you can find in it. Note that the web-interface screenshots presented below were obtained with synthetic data loaded into Cuirass database.

Main page

The main page is accessible on the root request endpoint (/). The main page displays a list of all the specifications stored in the Cuirass database. Each entry of the list is a clickable link which leads to a page about the evaluations of the corresponding specification (see below).

Here is an example view of the main page.

Main page screenshot

Evaluations list

The evaluations list of a given specification with name <name> is located at /jobset/<name>/. On this page, you can see a list of evaluations of the given project starting from the most recent ones. You can navigate to older evaluations using the pagination buttons at the bottom of the page. In the table, you can find the following information:

  • The ID of the evaluation which is clickable and leads to a page with information about all builds of the evaluation (see below).

  • List of commits corresponding to the evaluation.

  • Build summary of the evaluation: number of succeeded (green), failed (red), and scheduled (grey) builds of this evaluation. You can open the list of builds with a certain status by clicking on one of these three links.

Here is a possible view of the evaluations list page:

Screenshoot of evaluations list

Builds list

The builds list of a evaluation with ID <id> is located at /eval/<id>/. On this page, you can see a list of builds of the given evaluation ordered by their stop time starting from the most recent one. Similarly to the evaluation list, there are pagination buttons located at the bottom of the page. For each build in the list, there is information about the build status (succeeded, failed, or scheduled), stop time, nixname (name of the derivation), system, and also a link to the corresponding build log. As said above, it is possible to filter builds with a certain status by clicking on the status link in the evaluations list.

Screenshot of builds list

Summary

Cuirass now has the web interface which makes it possible for users to get an overview on the status of Guix package builds in a user-friendly way. As the result of my GSoC internship, the core of the web interface was developed. Now there are several possibilities for future improvements and I would like to welcome everyone to contribute.

It was a pleasure for me to work with the Guix team. I would like to thank you all for this great experience! Special thanks to my GSoC mentors: Ricardo Wurmus, Ludovic Courtès, and Gábor Boskovits, and also to Clément Lassieur and Danny Milosavljevic for their guidance and help throughout the project.

by Tatiana Sholokhova at August 13, 2018 03:00 PM

August 11, 2018

Peter Bex

What to expect from CHICKEN 5

We're getting close to a CHICKEN 5 release, so let's take a look at the cool new stuff!

Overhaul of built-in modules

The biggest change you'll notice when you fire up CHICKEN and start to use it is that the modules that come shipped with core are completely different from CHICKEN 4. The functionality is mostly the same, but we moved things around (a lot!) to make things more logical.

This is also the main reason we decided to bump the major version number: the modules have different names, procedures have been renamed, merged or dropped.

You can take a look at the complete list in the CHICKEN 5 manual. We've taken the module layout from R7RS small as inspiration, but since CHICKEN is still an R5RS Scheme first (with r7rs being an optional extension) we had to make some changes.

So, we define a scheme module which contains the entire R5RS language. For everything that is a CHICKEN-specific extension to standard R5RS Scheme, we put it under a (chicken ...) name, which tries to follow the R7RS naming conventions.

For example, R7RS defines a (scheme process-context) module with the following procedures:

  • command-line
  • exit
  • emergency-exit
  • get-environment-variable
  • get-environment-variables

Likewise, CHICKEN defines a (chicken process-context) module, which is a superset of the corresponding R7RS module. Take a look at its manual page; you can see that it defines many more procedures, but it includes all the standard ones too.

By using the R7RS names but with scheme replaced by chicken, the new modules should be easy to remember for anyone used to R7RS. Of course, you can still write portable standard R7RS programs via the r7rs egg, which defines a 100% compatible (scheme process-context) module with only the R7RS identifiers.

There is one important caveat: Because our scheme modules exports everything from R5RS Scheme, we don't provide, say, a (chicken cxr) module for all the cadadr, caddar and so on, because those are all in scheme. This also means that the (chicken load) module does not export load; that's already in scheme. Instead, it defines various non-standard CHICKEN extensions like load-relative and such.

Saner module imports

Speaking of modules, we've improved the way modules are linked into user code. In CHICKEN 4, there's a very strict distinction between modules and (compilation) units. This was an endless source of confusion for beginners. For example, why did (import foo) give an error when you tried to actually refer to an identifier from the foo module? That's because import didn't actually load the code, just the import library. To actually load the code and import the library, you needed (use foo). You could also load the code without importing it via (require-library foo). This should help with cross-compilation. The idea was that you would only need to load the import library on the host, and have the library itself compiled for the target, but in practice you needed to compile the library twice anyway (once on the host, once for the target).

We got rid of this mess: now the canonical way to import the foo library is simply (import foo). For more info, see this post by Felix outlining how to improve imports.

Full numeric tower

Of course, support for the full numeric tower is a personal favorite of mine, having spent a lot of time to perfect this stuff!

Most importantly, this means you no longer need to worry about integer computations over- or underflowing into a flonum and all the weird floating-point problems that entails. Bignums are also a necessity when dealing with 64-bit numeric C types in the FFI. For example, we finally support the size_t type correctly. To me, complex numbers and exact fractions (aka rational numbers) are a nice added bonus, as you could already get them before with the numbers egg. However, by having these types built-in, they're more efficient and you don't have to worry about passing these numbers to code that can't handle them because support happened not to be compiled in.

Take some time to read my blog series about the numeric tower if you're interested in the details.

Declarative egg description language

The chicken-install program to install eggs was rewritten along with all the surrounding tools. The main reason to do this was to make the life of package maintainers easier.

The old version of chicken-install would download, build, install and (optionally) run the unit tests as part of one command. If any dependencies were missing, it would also recursively download, build, install and run tests for those as well. The new version cleanly separates these steps, by generating shell scripts (batch files on Windows) that can do the necessary actions to build and install.

To make this easier, we also had to re-think the egg "language". In CHICKEN 4, a .setup-file was simply a Scheme program in which a few helper procedures were available for calling the compiler. This means it's impossible to create a simple shell script that will separate the build and install steps. That's why we now have a separate, declarative file which describes the components of an egg. See the .egg file documentation for a concrete example.

The rewritten chicken-install will now also cache eggs to avoid re-downloading the same eggs again and again. By default the cache is stored in a dot-directory under the user's home directory. This can be overridden with the CHICKEN_EGG_CACHE environment variable, which might also help package maintainers take the distributed files from another location.

See these design notes for more information about the goals and motivations behind the rewrite.

Improved support for static compilation

In principle, CHICKEN 4 has good support for static compilation. In practice, egg authors would not include the necessary commands for building their libraries statically. Most people don't have a real need for static linking, which means they tend not to make an effort to support it just in case someone else might need it.

The upshot of this was that you could only really compile programs statically when they didn't use any eggs, or if you created a custom build script that would compile the eggs manually with the required -static option. With the new chicken-install, you get static compilation support automatically, for free.

Note that in CHICKEN 4, you could also build eggs and programs using the so-called deployment mode. This allowed shipping a program with all its libraries in one directory. This worked quite well if your target platform supported it, but not all platforms did. Static compilation covers all the use cases that deployment supported and works reliably on all platforms, so we decided to drop deployment mode with all the complexity it brings.

Other noteworthy things

But wait, there's more!

  • Code generation is now fully deterministic, making builds reproducible. This allows you to verify that any given file of generated C code corresponds to the Scheme source code by recompiling it with the same CHICKEN version, both for user code and for CHICKEN core itself. As an added bonus, because the generated C output is deterministic, ccache can be used to get much faster builds (before, it would invalidate the cache as each file would be different).
  • We've improved how symbols are garbage collected, which was optional and somewhat broken in CHICKEN 4. This will speed up code that generates many symbols, and stops symbol table stuffing attacks from being a threat.
  • We have removed quite a bit of bloat: The srfi-1, srfi-13, srfi-14, srfi-69 and srfi-18 libraries have been removed from core! Not to worry though; they are now available as eggs. This will both allow faster development and encourage innovation and competition from alternatives to these non-essential libraries (especially R7RS-large seems to be geared towards renewal of some of these). We've also moved several non-SRFI procedures from core: object-evict, compile-file, binary-search, procedures for dealing with queues, scan-input-lines and POSIX group-information have all been moved to eggs. Support for SWIG has been removed, as it was bit-rotting and nobody seemed to be using it anyway.
  • Ports can now be bi-directional, so there's no more unnecessary distinction between input-ports and output ports. This maps more cleanly to file descriptor semantics, which can also be opened for both reading and writing.
  • Random number generation has been completely replaced. Before, we used libc's rand(), which produces very low quality random numbers. CHICKEN 5 uses the WELL512 PRNG to generate random integers, and it provides access to the system entropy pool for generating cryptographically secure streams of random bytes (using /dev/urandom on *nix, and RtlGenRandom on Windows).

Conclusion

There's a lot to like about the new CHICKEN, so go ahead and give it a spin! Release candidate 1 was made available today for you to try. The full list of changes can of course be found in the NEWS file. If you're already a happy CHICKEN 4 user, we've created a porting guide for you, to make it easier to make the transition from 4 to 5. If you need more help, you can of course contact the always friendly CHICKEN community.

by Peter Bex at August 11, 2018 09:44 AM

August 10, 2018

Programming Praxis

Penniless Pilgrim

Today’s exercise comes to us courtesy of long-time reader and contributor Ben Simon; you might like to look at his version of the task:

You must travel from the top-left corner of a five-by-five grid of points to the bottom-right corner, stepping from one point to another without retracing any edge. The first two steps must be eastward through the grid. Each step has a cost. An eastward step adds 2 to the current accumulated cost (so you start with an accumulated cost of 4), a westward step subtracts 2 from the current accumulated cost, a northward step halves the current accumulated cost, and a southward step doubles the current accumulated cost. It is possible to reach the bottom-right corner with an accumulated cost of zero.

Ben’s version of the task has a pretty map of Duonia, and a story about a penniless pilgrim who longs to visit the temple.

Your task is to write a program to find the zero-cost path through the grid. 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 10, 2018 09:00 AM

August 03, 2018

Programming Praxis

Odometer

Today’s exercise is an Amazon interview question:

An odometer variously uses letters and digits in its reading; for instance, an odometer might have a reading of G7TS39. Incrementing the odometer means adding 1 to a digit or increasing to the next letter to the next letter, with a carry to the next column when appropriate. Thus, G7TS39 increments to G7TS40 and G7TZ99 increments to G7UA00. As a special case, the odometer never increases in size, but rolls over, so the next odometer reading after Z9ZZ99 is A0AA00. An odometer position that initially contains a digit always contains a digit, and an odometer position that initially contains a letter always contains a letter, so 1Z9 increments to 2A0.

Your task is to write a program to increment an odometer. 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 03, 2018 09:00 AM

July 31, 2018

Programming Praxis

Double Dabble

Over at ComputerPhile, Professor Brailsford gives a beautiful explanation of the double-dabble algorithm for converting a number from binary to binary-coded decimal. If you don’t want to watch the video — you should — there is also an explanation at Wikipedia, or you can read the original description by C. B. Falconer.

Your task is to implement the double-dabble algorithm as shown by Professor Brailsford. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at July 31, 2018 09:00 AM

July 27, 2018

Programming Praxis

Triple Or Add Five

By starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite set of numbers can be generated. For instance, starting from 1, you can triple to get 3, then add five to get 8, and finally triple to get 24, so 24 is reachable. On the other hand, 15 is not reachable, as a little thought will show.

Your task is to write a program that determines if a number n is reachable by tripling or adding five, and if the number is reachable to give the sequence of operations by which it can be reached. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at July 27, 2018 09:00 AM

July 24, 2018

GNU Guix

Multi-dimensional transactions and rollbacks, oh my!

One of the highlights of version 0.15.0 was the overhaul of guix pull, the command that updates Guix and its package collection. In Debian terms, you can think of guix pull as:

apt-get update && apt-get install apt

Let’s be frank, guix pull does not yet run as quickly as this apt-get command—in the “best case”, when pre-built binaries are available, it currently runs in about 1m30s on a recent laptop. More about the performance story in a future post…

One of the key features of the new guix pull is the ability to roll back to previous versions of Guix. That’s a distinguishing feature that opens up new possibilities.

“Profile generations”

Transactional upgrades and rollbacks have been a distinguishing feature of Guix since Day 1. They come for free as a consequence of the functional package management model inherited from the Nix package manager. To many users, this alone is enough to justify using a functional package manager: if an upgrade goes wrong, you can always roll back. Let’s recap how this all works.

As a user, you install packages in your own profile, which defaults to ~/.guix-profile. Then from time to time you update Guix and its package collection:

$ guix pull

This updates ~/.config/guix/current, giving you an updated guix executable along with an updated set of packages. You can now upgrade the packages that are in your profile:

$ guix package -u
The following packages will be upgraded:
   diffoscope   93 → 96     /gnu/store/…-diffoscope-96
   emacs    25.3 → 26.1     /gnu/store/…-emacs-26.1
   gimp     2.8.22 → 2.10.4 /gnu/store/…-gimp-2.10.4
   gnupg    2.2.7 → 2.2.9   /gnu/store/…-gnupg-2.2.9

The upgrade creates a new generation of your profile—the previous generation of your profile, with diffoscope 93, emacs 25.3, and so on is still around. You can list profile generations:

$ guix package --list-generations
Generation 1  Jun 08 2018 20:06:21
   diffoscope   93     out   /gnu/store/…-diffoscope-93
   emacs        25.3   out   /gnu/store/…-emacs-25.3
   gimp         2.8.22 out   /gnu/store/…-gimp-2.8.22
   gnupg        2.2.7  out   /gnu/store/…-gnupg-2.2.7
   python       3.6.5  out   /gnu/store/…-python-3.6.5

Generation 2  Jul 12 2018 12:42:08     (current)
-  diffoscope   93     out   /gnu/store/…-diffoscope-93
-  emacs        25.3   out   /gnu/store/…-emacs-25.3
-  gimp         2.8.22 out   /gnu/store/…-gimp-2.8.22
-  gnupg        2.2.7  out   /gnu/store/…-gnupg-2.2.7
+  diffoscope   96     out   /gnu/store/…-diffoscope-96
+  emacs        26.1   out   /gnu/store/…-emacs-26.1
+  gimp         2.10.4 out   /gnu/store/…-gimp-2.10.4
+  gnupg        2.2.9  out   /gnu/store/…-gnupg-2.2.9

That shows our two generations with the diff between Generation 1 and Generation 2. We can at any time run guix package --roll-back and get our previous versions of gimp, emacs, and so on. Each generation is just a bunch of symlinks to those packages, so what we have looks like this:

Image of the profile generations.

Notice that python was not updated, so it’s shared between both generations. And of course, all the dependencies that didn’t change in between—e.g., the C library—are shared among all packages.

guix pull generations

Like I wrote above, guix pull brings the latest set of package definitions from Git master. The Guix package collection usually contains only the latest version of each package; for example, current master only has version 26.1 of Emacs and version 2.10.4 of the GIMP (there are notable exceptions such as GCC or Python.) Thus, guix package -i gimp, from today’s master, can only install gimp 2.10.4. Often, that’s not a problem: you can keep old profile generations around, so if you really need that older version of Emacs, you can run it from your previous generation.

Still, having guix pull keep track of the changes to Guix and its package collection is useful. Starting from 0.15.0, guix pull creates a new generation, just like guix package does. After you’ve run guix pull, you can now list Guix generations as well:

$ guix pull -l
Generation 10   Jul 14 2018 00:02:03
  guix 27f7cbc
    repository URL: https://git.savannah.gnu.org/git/guix.git
    branch: origin/master
    commit: 27f7cbc91d1963118e44b14d04fcc669c9618176
Generation 11   Jul 20 2018 10:44:46
  guix 82549f2
    repository URL: https://git.savannah.gnu.org/git/guix.git
    branch: origin/master
    commit: 82549f2328c59525584b92565846217c288d8e85
  14 new packages: bsdiff, electron-cash, emacs-adoc-mode,
    emacs-markup-faces, emacs-rust-mode, inchi, luakit, monero-gui,
    nethack, openbabel, qhull, r-txtplot, stb-image, stb-image-write
  52 packages upgraded: angband@4.1.2, aspell-dict-en@2018.04.16-0,
    assimp@4.1.0, bitcoin-core@0.16.1, botan@2.7.0, busybox@1.29.1,
    …
Generation 12   Jul 23 2018 15:22:52    (current)
  guix fef7bab
    repository URL: https://git.savannah.gnu.org/git/guix.git
    branch: origin/master
    commit: fef7baba786a96b7a3100c9c7adf8b45782ced37
  20 new packages: ccrypt, demlo, emacs-dired-du,
    emacs-helm-org-contacts, emacs-ztree, ffmpegthumbnailer, 
    go-github-com-aarzilli-golua, go-github-com-kr-text, 
    go-github-com-mattn-go-colorable, go-github-com-mattn-go-isatty, 
    go-github-com-mgutz-ansi, go-github-com-michiwend-golang-pretty, 
    go-github-com-michiwend-gomusicbrainz, go-github-com-stevedonovan-luar, 
    go-github-com-wtolson-go-taglib, go-github-com-yookoala-realpath, 
    go-gitlab-com-ambrevar-damerau, go-gitlab-com-ambrevar-golua-unicode,
    guile-pfds, u-boot-cubietruck
  27 packages upgraded: c-toxcore@0.2.4, calibre@3.28.0,
    emacs-evil-collection@20180721-2.5d739f5, 
    …

The nice thing here is that guix pull provides high-level information about the differences between two subsequent generations of Guix.

In the end, Generation 1 of our profile was presumably built with Guix Generation 11, while Generation 2 of our profile was built with Guix Generation 12. We have a clear mapping between Guix generations as created by guix pull and profile generations as created with guix package:

Image of the Guix generations.

Each generation created by guix pull corresponds to one commit in the Guix repo. Thus, if I go to another machine and run:

$ guix pull --commit=fef7bab

then I know that I get the exact same Guix instance as my Generation 12 above. From there I can install diffoscope, emacs, etc. and I know I’ll get the exact same binaries as those I have above, thanks to reproducible builds.

These are very strong guarantees in terms of reproducibility and provenance tracking—properties that are typically missing from “applications bundles” à la Docker.

In addition, you can easily run an older Guix. For instance, this is how you would install the version of gimp that was current as of Generation 10:

$ ~/.config/guix/current-10-link/bin/guix package -i gimp

At this point your profile contains gimp coming from an old Guix along with packages installed from the latest Guix. Past and present coexist in the same profile. The historical dimension of the profile no longer matches exactly the history of Guix itself.

Composing Guix revisions

Some people have expressed interest in being able to compose packages coming from different revisions of Guix—say to create a profile containing old versions of Python and NumPy, but also the latest and greatest GCC. It may seem far-fetched but it has very real applications: there are large collections of scientific packages and in particular bioinformatics packages that don’t move as fast as our beloved flagship free software packages, and users may require ancient versions of some of the tools.

We could keep old versions of many packages but maintainability costs would grow exponentially. Instead, Guix users can take advantage of the version control history of Guix itself to mix and match packages coming from different revisions of Guix. As shown above, it’s already possible to achieve this by running the guix program off the generation of interest. It does the job, but can we do better?

In the process of enhancing guix pull we developed a high-level API that allows an instance of Guix to “talk” to a different instance of Guix—an “inferior”. It’s what allows guix pull to display the list of packages that were added or upgraded between two revisions. The next logical step will be to provide seamless integration of packages coming from an inferior. That way, users would be able to refer to “past” package graphs right from a profile manifest or from the command-line. Future work!

On coupling

The time traveler in you might be wondering: Why are package definitions coupled with the package manager, doesn’t it make it harder to compose packages coming from different revisions? Good point!

Tight coupling certainly complicates this kind of composition: we can’t just have any revision of Guix load package definitions from any other revision; this could fail altogether, or it could provide a different build result. Another potential issue is that guix pulling an older revision not only gives you an older set of packages, it also gives you older tools, bug-for-bug.

The reason for this coupling is that a package definition like this one doesn’t exist in a vacuum. Its meaning is defined by the implementation of package objects, by gnu-build-system, by a number of lower-level abstractions that are all defined as extensions of the Scheme language in Guix itself, and ultimately by Guile, which implements the language Guix is written in. Each instance created by guix pull brings all these components. Because Guix is implemented as a set of programming language extensions and libraries, that package definitions depend on all these parts becomes manifest. Instead of being frozen, the APIs and package definitions evolve together, which gives us developers a lot of freedom on the changes we can make.

Nix results from a different design choice. Nix-the-package-manager implements the Nix language, which acts as a “frozen” interface. Package definitions in Nixpkgs are written in that language, and a given version of Nix can possibly interpret both current and past package definitions without further ado. The Nix language does evolve though, so at one point an old Nix inevitably becomes unable to evaluate a new Nixpkgs, and vice versa.

These two approaches make different tradeoffs. Nix’ loose coupling simplifies the implementation and makes it easy to compose old and new package definitions, to some extent; Guix’ tight coupling makes such composition more difficult to implement, but it leaves developers more freedom and, we hope, may support “time travels” over longer period of times. Time will tell!

It’s like driving a DeLorean

Inside the cabin of the DeLorean time machine in “Back to the Future.”

Picture of a DeLorean cabin by Oto Godfrey and Justin Morton, under CC-BY-SA 4.0.

That profile generations are kept around already gave users a time machine of sorts—you can always roll back to a previous state of your software environment. With the addition of roll-back support for guix pull, this adds another dimension to the time machine: you can roll-back to a previous state of Guix itself and from there create alternative futures or even mix bits from the past with bits from the present. We hope you’ll enjoy it!

by Ludovic Courtès at July 24, 2018 12:30 PM

July 20, 2018

Programming Praxis

Fenwick Trees

There are some algorithms in coding theory where cumulative frequency tables must be maintained. This requires two tasks to be performed on an array of integers:

1) Calculate the cumulative sum of the first n elements of the array.

2) Modify the value of an element of the array.

One approach is to maintain an array of the elements, so that an element can be modified in O(1) time but calculating the cumulative sum requires O(n)time. Another approach is maintain an array of the cumulative sumes, so that a cumulative sum can be calculated in O(1) time but modifying a single element of the array takes O(n) time.

A Fenwick tree performs both operations in O(log n) time. The tree is normally embedded in a 1-based array, with the children of node i at nodes 2i and 2i + 1. Each element with index i a power of 2 contains the sum of the first i elements. Each element with index i a sum of two powers of 2 contains the sum of the elements since the preceding power of 2. In general, each element contains the sum of the values since its parent in the tree, found by clearing the least-significant bit in the index. Wikipedia has a good description of Fenwick trees.

For example, to find the sum of the first 1110 = 10112 items in the array, note that 11 has three bits set, so add elements 10002, 10102, and 10112. To modify the 11th element, modify 10112, 11002, 100002, and all higher powers of 2 up to the size of the array.

Your task is to implement Fenwick trees. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at July 20, 2018 09:00 AM

July 17, 2018

Programming Praxis

Top Heavy Perfect Powers

Over at his blog, Ken is investigating top-heavy perfect powers to investigate increasing the breadth of the Cunningham project. He makes a list of 2413 perfect powers bn with bn in increasing order, up to a googol, omitting bases that are themselves perfect powers (for instance, 4n, 8n or 9n).

Your task is to make a list of the 2413 top-heavy perfect powers less than a googol. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at July 17, 2018 09:00 AM

July 13, 2018

Programming Praxis

Data Laundry, Again

Data laundry is the act of cleaning data, as when it arrives in one format and must be translated to another, or when external data must be checked for validity. We looked at data laundry in a previous exercise. We return to it today because I have been doing data laundry all week, handling data from a new vendor. Today’s task is similar to one I have been doing this week; convert the input to the output shown below, changing all appearances of the string ABCDE to an incrementally-numbered string with a prefix:

ABCDE This is some text.
This is more text. ABCDE, ABCDE.
ABCDE And this is [ABCDE] still more text.
X1 This is some text.
This is more text. X2, X3.
X4 And this is [X5] still more text.

Your task is to write a program to perform the data laundry shown 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 July 13, 2018 09:00 AM

July 10, 2018

Programming Praxis

8/10 Palindromes

Sometimes I enjoy browsing oeis.org (I might be a little bit weird). While browsing the other day, I found A029804, the sequence of numbers that are palindromes in both decimal and octal.

Your task is to write a program that writes the sequence of numbers that are palindromes in both decimal and octal. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at July 10, 2018 09:00 AM

July 06, 2018

GNU Guix

GNU Guix and GuixSD 0.15.0 released

We are pleased to announce the new release of GNU Guix and GuixSD, version 0.15.0! This release brings us close to what we wanted to have for 1.0, so it’s probably one of the last zero-dot-something releases.

The release comes with GuixSD ISO-9660 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 7 months (much too long!) since the previous release, during which 100 people contributed code and packages. The highlights include:

  • The unloved guix pull command, which allows users to upgrade Guix and its package collection, has been overhauled and we hope you will like it. We’ll discuss these enhancements in another post soon but suffice to say that the new guix pull now supports rollbacks (just like guix package) and that the new --list-generations option allows you to visualize past upgrades. It’s also faster, not as fast as we’d like though, so we plan to optimize it further in the near future.
  • guix pack can now produce relocatable binaries. With -f squashfs it can now produce images stored as SquashFS file systems. These images can then be executed by Singularity, a “container engine” deployed on some high-performance computing clusters.
  • GuixSD now runs on ARMv7 and AArch64 boxes! We do not provide an installation image though because the details depend on the board you’re targeting, so you’ll have to build the image yourself following the instructions. On ARMv7 it typically uses U-Boot, while AArch64 boxes such as the OverDrive rely on the EFI-enabled GRUB. Bootloader definitions are available for many boards—Novena, A20 OLinuXino, BeagleBone, and even NES.
  • We further improved error-reporting and hints provided by guix system. For instance, it will now suggest upfront kernel modules that should be added to the initrd—previously, you could install a system that would fail to boot simply because the initrd lacked drivers for your hard disk.
  • OS configuration has been simplified with the introduction of things like the initrd-modules field and the file-system-label construct.
  • There’s a new guix system docker-image command that does exactly what you’d expect. :-)
  • There’s a dozen new GuixSD services: the Enlightenment and MATE desktops, Apache httpd, support for transparent emulation with QEMU through the qemu-binfmt service, OpenNTPD, and more.
  • There were 1,200 new packages, so we’re now close to 8,000 packages.
  • Many bug fixes!
  • The manual is now partially translated into French and you can help translate it into your native language by joining the Translation Project.

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's 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, x86_64, ARMv7, and AArch64 machines. It is also possible to use Guix on top of an already installed GNU/Linux system, including on mips64el and aarch64.

by Ludovic Courtès at July 06, 2018 12:00 PM

July 03, 2018

Programming Praxis

Top Five Test Scores

We frequently base exercises on student assignments. Today we have something for the teachers:

A student’s final store is the average of the five best test scores the student achieved during the school term. Given a list of student name/score pairs, determine the final score for each student. You may assume each student has at least five scores.

Your task is to write a program to determine each student’s final score, 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 July 03, 2018 09:00 AM