Planet Scheme

January 17, 2017

GNU Guix

Meet Guix at FOSDEM

GNU Guix will be present at FOSDEM next month with talks on a number of areas of active development. The first one will be on Saturday, in the high-performance computing (HPC) track:

Of course, the GNU Guile track on Sunday will be like home, with a bunch of talks there: We&aposll end the day with a round table on the future of Guix.

FOSDEM takes place in Brussels, Belgium, on the 4th and 5th of February, with the Guile track all day long on Sunday 5th. Hope to see you there!

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 and armv7.

by Ludovic Courtès (guix-devel@gnu.org) at January 17, 2017 01:30 PM

Programming Praxis

Exercise 1-9

Sometimes it’s good to go back to basics. Here is Exercise 1-9 from The C Programming Language by Brian W. Kernighan and Dennis M. Ritchie:

Write a program to copy its input to its output, replacing each string of one or more blanks by a single blank.

Your task is to write a solution to Exercise 1-9. 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 January 17, 2017 09:00 AM

January 13, 2017

Programming Praxis

Words On A Telephone Keypad

The digits on a telephone keypad are associated with letters; for instance, the digit 2 is associated with the letters A, B and C, and the digit 7 is associated with the letters P, Q, R and S. Thus, a word can be converted to its numeric equivalent; for instance, PRAXIS can be converted to the number 772947. The conversion is not necessarily unique, so ACT, BAT and CAT all convert to 228.

Your task is to write a program that takes a number, such as 228, and returns a list of all the words in a dictionary that are represented by that number. 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 January 13, 2017 09:00 AM

January 10, 2017

Programming Praxis

Prime String

Today’s exercise is easy to describe, but has some tricky edge cases that make it hard to implement:

Given a string of the prime numbers appended sequentially — 2357111317192…. — and an index n, return the string of five digits beginning at index n. For instance, the five characters starting at index n = 50 are 03107. The first 61 characters of the prime string are shown below:

0         1         2         3         4         5         6
0123456789012345678901234567890123456789012345678901234567890

2357111317192329313741434753596167717379838997101103107109113

Your task is to write a program to find the substring of the string of all primes starting at the nth character. 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 January 10, 2017 09:00 AM

January 06, 2017

Programming Praxis

Fibonacho Numbers

ft090208

Mathematicians are strange people:

Two people are sharing a plate of nachos. They take turns dividing the nachos, each taking the nth Fibonacci number of nachos on the nth turn. When the number of nachos left is less than the next Fibonacci number, they start the sequence over. What number of nachos (less than 500) requires the most number of restarts?

For instance, if you start with n = 11 nachos, the first person takes 1 nacho (leaving 10), the second person takes 1 nacho (leaving 9), the first person takes 2 nachos (leaving 7), the second person takes 3 nachos (leaving 4), and the process restarts. Then the first person takes 1 nacho (leaving 3), the second person takes 1 nacho (leaving 2), and the first person takes 2 nachos (leaving none). There were two restarts, which we can notate as [1,1,2,3], [1,1,2].

The fibonacho numbers are those starting numbers n that require more restarts than any smaller number. Thus, the first fibonacho number is 1 from [1], the second fibonacho number is 3 from [1,1], [1], the third fibonacho number is 10 from [1,1,2,3], [1,1], [1], and so on.

Your task is to write programs that calculate the number of restarts for a given n, and the sequence of fibonacho 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 January 06, 2017 09:00 AM

December 25, 2016

Programming Praxis

Merry Christmas

Merry Christmas to all my readers, and thank you for staying with me for another year.

Your task is to turn off your computer and spend a week with family and friends.

I’ll see you in 2017!

christmas-nativity-scene_455966


by programmingpraxis at December 25, 2016 09:00 AM

December 23, 2016

Programming Praxis

A Partridge In A Pear Tree

You all know the old song:

On the first day of Christmas my true love gave to me a partridge in a pear tree.

On the second day of Christmas my true love gave to me two turtle doves and a partridge in a pear tree.

On the third day of Christmas my true love gave to me three French hens, two turtle doves and a partridge in a pear tree.

On the fourth day of Christmas my true love gave to me four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the fifth day of Christmas my true love gave to me five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the sixth day of Christmas my true love gave to me six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the seventh day of Christmas my true love gave to me seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the eighth day of Christmas my true love gave to me eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the ninth day of Christmas my true love gave to me nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the tenth day of Christmas my true love gave to me ten lords a-leaping, nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the eleventh day of Christmas my true love gave to me eleven pipers piping, ten lords a-leaping, nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

On the twelfth day of Christmas my true love gave to me twelve drummers drumming, eleven pipers piping, ten lords a-leaping, nine ladies dancing, eight maids a-milking, seven swans a-swimming, six geese a-laying, five golden rings, four calling birds, three French hens, two turtle doves and a partridge in a pear tree.

Your task is to write a program that prints the words of the song, as economically as possible. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at December 23, 2016 09:00 AM

December 20, 2016

GNU Guix

GNU Guix and GuixSD 0.12.0 released

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

The release comes with USB installation images to install the standalone 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 a little over 4 months since the previous release, during which 76 people contributed code and packages. The highlights include:

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 and armv7.

by Ricardo Wurmus (guix-devel@gnu.org) at December 20, 2016 10:00 PM

Programming Praxis

Highly Abundant Numbers

We studied highly composite numbers in a series of several previous exercises, and had a lot of fun. In today’s exercise we look at a related concept: highly abundant numbers (A002093).

Highly abundant numbers are those numbers n such that sigma(m) < sigma(n) for all m < n, where m and n are positive integers and sigma(n) is the sum of the divisors of n. For instance, 12 is a highly abundant number since the sum of its divisors is 1 + 2 + 3 + 4 + 6 + 12 = 28, and no number less than 12 has a greater sum of divisors.

Your task is to compute the sequence of highly abundant 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 December 20, 2016 09:00 AM

December 16, 2016

GNU Guix

Reproducible Build Summit, 2nd Edition

GNU Guix was present this week at the second Reproducible Build Summit in Berlin. Three of us were there. We happily joined a dozen of other free software projects, mostly distros, to discuss cross-cutting reproducibility issues going from outreach to hacking on a specific piece of software. This attempts to summarize important points that were discussed in some of the sessions we attended, and how Guix fits into that.

On reproducibility

What does it mean for a build process to be reproducible? That sounded obvious to many attendants, but experience has shown that many outside of the community needed clarifications. A group led by Ed Maste of FreeBSD worked hard to come up with a definition that is both concise, accurate, and generic. Impressive and useful work!

At the same time, another group worked on the other thankless task that consists in improving the reproducible build documentation. A big thanks to them!

Testing reproducibility

For a couple of years, Debian has had a dashboard that shows the progress that has been made. The result is impressive: 92% of its source packages are now bit-for-bit reproducible! During the meeting, Eelco Dolstra reported first results for NixOS, obtained thanks to an extension to the Hydra continuous integration tool: 77% of the packages are currently reproducible.

Our build farm in Guix doesn&apost yet have the resources to perform independent rebuilds of packages. We plan to use the shared resources at tests.reproducible-builds.org to achieve that soon. Since last year&aposs summit, our patch submission guidelines require submitters to check for reproducibility issues using guix build --rounds=N. This has already allowed us to fix lots of reproducibility issues in packages.

User-facing interfaces to reproducible builds

Reproducible builds should allow users to verify builds, and distributors to no longer be single points of failure. But how can we actually empower users with reproducible builds? Last year, we outlined that reproducible builds are a means to user empowerment. Thus it was great to brainstorm these issues with brilliant minds!

dkg of Debian and ACLU led a couple of sessions on this topic. Tools like guix challenge are one way to help users check whether their binaries are trustworthy, provided independent package builds are available. Some suggested that this could be used as an input for a more general kind of “system health” monitoring tool.

A large part of the discussion then focused on policies that users could select. For example, assuming several independent organizations provide binaries for a given distro, users could disallow installation of binaries for which providers disagree on the output. Worded like this, the policy could easily lead to denial of service should one of the providers be unavailable. A refinement of this policy is to install only packages for which k out of n known builders “agree” on what the package contents are.

Guix currently allows users to specify multiple binary providers through the --substitute-urls option. We hope we can extend it to support this “k out of n” policy by the next Reproducible Build Summit!

Bootstrapping

The Summit focuses on reproducible builds, but unfortunately, there are more and more situations where software is not built from source. In most cases, this is due to bootstrapping issues: a compiler is written in the language it compiles, and thus distributors have no choice but to start from an opaque pre-built binary provided by upstream. The problem also comes up when building a complete system “from nothing”. This situation prevents users from knowing what code they’re running, and it makes them vulnerable to trusting trust attacks.

In Guix, the debate came up every time we added one of these self-hosted compilers—Rust, OCaml, GHC, etc. This is not a comfortable situation. We led sessions on this topic with two goals: to try and make a specific package “bootstrappable”, and to raise awareness and come up with guidelines for compiler and tool writers. Together with other hackers, we drafted a manifesto that we hope to publish soon. Stay tuned!

Hacks!

During the hacking sessions, while Ricardo was busy working on the bootstrapping manifesto, John together with Pierre Pronchery of NetBSD tackled gettext reproducibility issues, and Ludovic picked up the work of others on fixing a longstanding reproducibility issue in Guile, the Scheme implementation used by Guix—“the shoemaker’s child always goes barefoot”, they say.

Thanks!

We would like to thank the sponsors who helped make the Reproducible Build Summit possible: Debian, Google, Linux Foundation, and Open Tech Fund. Special thanks to Beatrice and Gunner of Aspiration and to Holger of Debian for the perfect organization, and for the productive and friendly atmosphere they created!

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 and armv7.

by Ludovic Courtès, John Darrington, Ricardo Wurmus (guix-devel@gnu.org) at December 16, 2016 05:00 PM

Programming Praxis

SQL Insert Syntax

When I’m not writing exercises for Programming Praxis, my day job has me writing SQL and PL/SQL code for a large Oracle database. One task I frequently perform is inserting records into a table, using the following syntax:

insert into tablename (
    field_1,
    field_2,
    field_3,
    ...)
values (
    value_1,
    value_2,
    value_3,
    ...)

Here, tablename is replaced by the name of the database table into which records are being inserted, each field is the name of a field in the table, and each value is the value to be inserted. The correspondence between field name and value is positional.

I can’t tell you how many times over the years I wrote that wrong. When I inadvertently skip a field, an error message politely tells me of my mistake. But when I transpose two fields, both of the same type, there is no error message, and I happily go on my way with bad data in the database.

I finally decided to do something about the situation; I wrote a program that converts the syntax shown below, which makes it easy to see the correspondence between fields and values, to the Oracle syntax shown above:

insert into tablename (
    field_1 => value_1,
    field_2 => value_2,
    field_3 => value_3,
    ...)

That’s much better: Easy to get right, much harder to get wrong. A significant payback on a few minutes of effort. Why didn’t I do this years ago!?

Your task is to find something annoying in your programming environment, and fix it; you can borrow my annoyance in the unlikely event you have none of your own. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at December 16, 2016 09:00 AM

December 13, 2016

Programming Praxis

List Swap

We have today an exercise for students who work with linked lists:

Given a linked list and an integer k, swap the two list items that are at distance k from the beginning of the list and distance k from the end of the list. Be sure to consider the case where the k cross, so that the item k from the beginning of the list is after the item k from the end of the list. For instance, given the list (1 2 3 4 5 6 7) and k = 2, you should return the list (1 6 3 4 5 2 7), and likewise if k = 6. The solution must run in O(n) time, where n is the length of the list.

Your task is to write the list-swapping code 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 December 13, 2016 09:00 AM

December 09, 2016

Programming Praxis

Searching An Infinite Array

Given an array of positive integers in ascending order, of infinite size, find the index of an integer k in the array, or determine that it does not exist. Your solution must work in time logarithmic in the index of the requested integer.

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


by programmingpraxis at December 09, 2016 09:00 AM

December 06, 2016

Programming Praxis

Career Cup

Regular readers know that I sometimes find inspiration for these exercises at Career Cup:

Given two sorted arrays, efficiently find the median of the combined array.

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


by programmingpraxis at December 06, 2016 09:00 AM

December 02, 2016

Programming Praxis

Beale’s Cipher

In the early 1800, Thomas J. Beale mined a large quantity of gold and silver, secretly, some place in the American West, and brought the gold, silver, and some jewels purchased with the treasur to Virginia, where he buried it. He wrote three coded documents that described the location of the buried treasure, the nature of the treasure, and the names of the owners. He never came back to retrieve the treasure. Only the second of those documents has been decoded, and many people, even today, are scouring Bedford County, Virginia, looking for buried treasure. Or so the story goes.

Beale used a variant of a book cipher. He chose a long text as a key, numbered each of the words in the text sequentially, starting from 1, and formed a message by choosing from the key text a word for each character of plain text having the same initial letter as the plain text; the cipher text consists of a list of the sequence numbers of the chosen words. For instance, if the key text is “now is the time” and the plain text is “tin”, then either (3 2 1) or (4 2 1) are valid encipherments. If the key text is long, there will be many duplicates, as we saw with the letter “t”, and the resulting cipher will be reasonably secure. Beale used the 1322 words of the Declaration of Independence as the key text for the second document; the key texts associated with the first and third documents are unknown.

Your task is to write programs that encipher and decipher messages using the Beale cipher; use it to decode the second document. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at December 02, 2016 09:00 AM