Planet Scheme

October 17, 2017

GNU Guix

Coming events

Guix will be present on a few venues in the coming weeks:

  1. On October 23rd, I (Ludovic Courtès) will be at GPCE, an academic conference co-located with SPLASH in Vancouver, Canada. I will present the paper Code Staging in GNU Guix, which discusses the motivation for and genesis of G-expressions, as well as recent improvements. It’s an honor to be presenting before an audience of experts in the field!
  2. Christopher Baines will be at freenode #live in Bristol, UK, among well-known free software activists from a variety of organizations and projects. Christopher will give a talk on October 29th to give an overview of Guix and GuixSD.
  3. On October 31st, Ricardo Wurmus, Jan Nieuwenhuizen, and possibly more Guix hackers will join a dozen free software projects at the third Reproducible Build Summit in Berlin, Germany. As in previous years, we expect it to be a good time to share tips & tricks as well as a longer-term vision with our fellow hackers!

If you’re around in Vancouver, Bristol, or Berlin, let’s get in touch! :-)

About GNU Guix

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

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

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

by Ludovic Courtès (guix-devel@gnu.org) at October 17, 2017 10:00 AM

Programming Praxis

Zeros And Ones

Zeros And Ones

This is somebody’s homework problem:

Given an array containing only zeros and ones, find the index of the zero that, if converted to one, will make the longest sequence of ones. For instance, given the array [1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1], replacing the zero at index 10 (counting from 0) forms a sequence of 9 ones.

Your task is to write a program that determines where to replace a zero with a one to make the maximum length subsequence. 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 17, 2017 09:00 AM

October 13, 2017

Programming Praxis

Zero-Sum Sub-Arrays

This interesting little question comes from Career Cup:

Given an array that contains only the elements -1 and 1, find the number of sub-arrays with a sum of zero. For instance, given the array [-1, 1, -1, 1], there are four sub-arrays that sum to zero: [-1, 1], [1, -1], [-1, 1] and [-1, 1, -1, 1].

Your task is to count the sub-arrays of a -1/1 array that sum to zero. 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 13, 2017 09:00 AM

October 09, 2017

Programming Praxis

Day 280

Pat Ballew is a retired math teacher who writes a blog On This Day In Math that gives a day-by-day history of mathematics. The blog is odd, quirky, and unquestionably fun. On October 7th, Ballew wrote:

The 280th day of the year…. The sum of the first 280 consecutive primes, mod 280, is prime.

Since I like to play with prime numbers, that got my attention, and I quickly went to determine how many such days there are in a year.

Your task is to determine how many days in a year share the characteristic that on the nth day the sum of the first n primes, mod n, is prime. 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 09, 2017 05:17 PM

October 06, 2017

Programming Praxis

Two Palindrome Exercises

Many of the people who read my blog are programming students. It is October, about the middle of the Fall Semester at many universities, and my student readers need exercises to cement their understanding of their studies. Here are two exercises about palindromes.

  1. A number like 123454321 is palindromic; it decimal digits are the same left-to-right as they are right-to-left. Write a program that determines if a given input number is palindromic.
  2. Given a list of strings, for instance {“a” “bcd” “ef” “g” “f” “ed” “c” “ba”}, write a program to determine if the individual letters of the strings form a palindrome. Note that the letters might be distributed into the individual words differently when read in opposite directions.

Your task is to write two programs that recognize palindromes. 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, 2017 09:00 AM

October 03, 2017

Programming Praxis

Chez Scheme Setup

We continue today with the recent series of exercises about how I configured my new computer. Chez Scheme is a remarkable Scheme compiler/interpreter, very fast, and remarkably bug-free, but it includes limited libraries, so users must create their own. This note describes some of the libraries I use.

The primary library is my Standard Prelude, described at https://programmingpraxis.com/standard-prelude, loaded each time Chez Scheme starts up. Chez Scheme resides in two executable files in /usr/local/bin called scheme and petite. I provide a shell script /usr/local/bin/chez that loads scheme (the full compiler) and the Standard Prelude as part of the interactive-system startup:

    #! /usr/local/bin/scheme

    ; standard prelude
    (load "~/scheme/lib/prelude.ss")

    ; literate programming
    (load "~/scheme/lib/tangle.ss")

    ; interactive editing
    (define *edfile* #f)
    (define (lload . args)
      (when (pair? args) (set! *edfile* (car args)))
      (when (not *edfile*) (error 'lload "file not found"))
      (when (not (file-exists? *edfile*) (error 'lload "file not found"))
      (let* ((ss (tangle *edfile*)) (i (open-input-string ss)))
        (let loop ((obj (read i)))
          (if (eof-object? obj) (close-input-port i)
            (begin (eval obj (interaction-environment))
                   (loop (read i))))))))
    (define (ed . args)
      (when (pair? args) (set! *edfile* (car args)))
      (when (not *edfile*) (error 'ed "file not found"))
      (system (string-append "ed " *edfile*))
      (lload *edfile*))
    (define (vi . args)
      (when (pair? args) (set! *edfile* (car args)))
      (when (not *edfile*) (error 'vi "file not found"))
      (system (string-append "vi " *edfile*))
      (lload *edfile*))
    (define (sh . args)
      (system (if (null? args) "sh -l" (string-join #\space args)))
      (if #f #f))

    ; go home
    (cd "~/scheme")

Documentation of the Standard Prelude is provided on the web page noted above. I defer to Chez Scheme for hash tables, structures and random numbers, rather than using the versions in my Standard Prelude, and also defer to Chez Scheme for the Standard Prelude functions that Chez Scheme provides natively. The only part of the Standard Prelude that is not loaded is avl trees, which are removed to their own library. Also loaded at each run of Chez Scheme are my literate programming environment described at https://programmingpraxis.com/2010/08/10/literate-programming and my interactive editing environment described at https://programmingpraxis.com/2017/04/07/edit-files-in-a-repl.

The only thing that hasn’t been discussed previously in my blog is the sh command. On my desktop computer, the screen is large enough that I can have both a Scheme REPL and a system shell window open at the same time, and move between them as needed. On my tablet, the screen is simply too small, so it is convenient to have a way to quickly exit to the system shell, execute some command, and return to the REPL. The sh command, called with no arguments, opens a login shell, and returns to the REPL when it is exited; called with arguments, it executes the command specified by the arguments, then returns to the REPL immediately. The (if #f #f) that ends the function is the standard way to return void from a function; it is used here to suppress the return code that sh normally returns.

Other libraries that I commonly use appear on the pages that follow; all are stored in ~/scheme/lib, and loaded by (load "~/scheme/lib/xxx.ss"):

    avl.ss      -- avl trees
    priqueue.ss -- priority queues
    textfile.ss -- input, processing and output of text file databases
    pregexp.ss  -- Dorai Sitaram's portable regular expression matcher
    streams.ss  -- SRFI-41 streams - lazy lists (I am the author)
    match.ss    -- Kent Dybvig's pattern matcher

My normal habit is to work in the interpreter with the current directory set to ~/scheme. I create a directory for each project, then use (lload "project/xxx.ss") to load project file xxx.ss into the interpreter and either (ed) or (vi) to edit the file. Directory ~/scheme has no files, only project directories.

Your task is to implement this environment on your system, if you are a Scheme user, or to describe your own programming environment. When you are finished, you are welcome to discuss the exercise in the comments below.


by programmingpraxis at October 03, 2017 09:00 AM

September 29, 2017

Programming Praxis

Three-Level Control-Break

In many data-processing shops it is standard practice to write programs that generate reports that summarize data in hierarchical groups, say a report of population by city nested within county nested within state nested with a grand total. The input data is a set of records, already sorted in the required order. The output is a printed report, often written on sprocket-fed green-bar paper (where I work, we had a high-speed line printer as late as about ten years ago). The trick, of course, is that you never know that a break has occurred until you read the record after the break, so you have to be careful to keep track of where you are in the hierarchy, and to properly initialize and complete each level of the hierarchy; the first and last records in the data set are always potential spots for error.

Your task is to write a program that produces a three-level control-break report; use any data set that interests you. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.


by programmingpraxis at September 29, 2017 09:00 AM

September 26, 2017

Programming Praxis

Data Laundry

We have a simple task today, converting a file from one format to another. Such tasks are often called data laundry, in the sense of washing or cleaning the data as it moves from one format to another. Here’s the input:

lo0: flags=8049<UP,LOOPBACK,RUNNING,MULTICAST> mtu 16384
	options=1203<RXCSUM,TXCSUM,TXSTATUS,SW_TIMESTAMP>
	inet 127.0.0.1 netmask 0xff000000 
	inet6 ::1 prefixlen 128 
	inet6 fe80::1%lo0 prefixlen 64 scopeid 0x1 
	nd6 options=201<PERFORMNUD,DAD>
gif0: flags=8010<POINTOPOINT,MULTICAST> mtu 1280
en0: flags=8863<UP,BROADCAST,SMART,RUNNING,SIMPLEX,MULTICAST> mtu 1500
	ether f4:0f:24:29:df:4d 
	inet6 fe80::1cb5:1689:1826:cc7b%en0 prefixlen 64 secured scopeid 0x4 
	inet 10.176.85.19 netmask 0xffffff00 broadcast 10.176.85.255
	nd6 options=201<PERFORMNUD,DAD>
	media: autoselect
	status: active
en1: flags=963<UP,BROADCAST,SMART,RUNNING,PROMISC,SIMPLEX> mtu 1500
	options=60<TSO4,TSO6>
	ether 06:00:58:62:a3:00 
	media: autoselect <full-duplex>
	status: inactive
p2p0: flags=8843<UP,BROADCAST,RUNNING,SIMPLEX,MULTICAST> mtu 2304
	ether 06:0f:24:29:df:4d 
	media: autoselect
	status: inactive

The desired output is a comma-separated values file with three fields:

interface,inet,status
lo0,127.0.0.1,
gif0,,
en0,10.176.85.19,active
en1,,inactive
p2p0,,inactive

Your task is to write a program that converts the input shown above to the desired output. 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 26, 2017 09:00 AM

September 22, 2017

Programming Praxis

Comma Quibbling

Eric Lippert, at his blog Fabulous Adventures in Coding, discusses the problem of comma quibbling, which turns a list of words like (“ABC” “DEF” “G” “H”) into the string “ABC, DEF, G and H” with commas between each pair of words except the last pair, which gets the word “and” (without a comma). Here are the rules:

  1. If the input is empty, so is the output.
  2. If the input has a single word, so does the output.
  3. If the input has two words, the output is the two words separated by “and”.
  4. If the input has more than two words, the output is all the words, separated by commas, but with the last comma replaced by “and”.

A word is a maximal sequence of characters not containing a comma or a space.

Your task is to write a function that adds commas to a list of words, using the rules 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 September 22, 2017 09:00 AM

September 19, 2017

Programming Praxis

Catalan’s Triangle

Since our exercise a week ago, I’ve been reading about Catalan numbers, primarily based on the references at OEIS. Catalan’s Triangle (A009766) is a number triangle

1
1 1
1 2  2
1 3  5  5
1 4  9 14 14
1 5 14 28 42  42
1 6 20 48 90 132 132

such that each element is equal to the one above plus the one to the left.

Your task is to write a program that calculates a Catalan triangle. 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 19, 2017 09:00 AM

September 15, 2017

Programming Praxis

Compile Chez Scheme On Android ARM

In a recent exercise I described my new tablet computer, and talked about installing Guile Scheme because I could not get Chez Scheme to compile. I have finally been able to compile my preferred Scheme interpreter, Chez Scheme, on my Android ARM tablet. This note describes how I did it.

Chez Scheme is written partly in C and partly in Scheme; as a consequence, it requires a working Scheme compiler to be compiled. For popular platforms, such as Linux, Chez Scheme is distributed with the Scheme portion of the compiler already compiled, but for the Android ARM platform, we have to compile the Scheme portion of the compiler ourselves. The procedure is to compile Chez Scheme on some available platform (we will use Linux), cross-compile the Scheme portion of the compiler for the Android ARM platform, compile the C portion of the compiler on Android ARM, and then complete the build on Android ARM. It’s easier than it sounds. First, if you don’t already have Chez Scheme running on your Linux platform, perform the following steps to obtain and compile Chez Scheme (similar instructions apply on other platforms, go to the Chez Scheme Project Page for assistance):

cd /usr/local/src
sudo wget https://github.com/cisco/ChezScheme/archive/v9.4.tar.gz
gunzip v9.4.tar.gz
tar -xvf v9.4.tar
sudo rm v9.4.tar
cd ChezScheme-9.4
sudo ./configure
sudo make install

At this point you should have a working Chez Scheme system on the Linux computer. You might want to stop and play with it to make sure it works. Assuming that you compiled on an Intel system, the machine type was a6le, so perform the following steps to cross-compile to machine type arm32le for the Android ARM:

sudo mkdir boot/arm32le
cd a6le
sudo make -f Mf-boot arm32le.boot
cd ..
sudo ./configure -m=arm32le
sudo ./configure --workarea=arm32le
cd arm32le/s
sudo make -f Mf-cross m=a6le xm=arm32le base=../../a6le

Now the cross-compilation is complete and you are ready to work on the Android ARM system. Still on the desktop, pack up the complete Chez Scheme system:

cd /usr/local/src
sudo tar -czvf ChezScheme-9.4.tar.gz ChezScheme-9.4

We look next at the Android ARM tablet. We will be running under GnuRoot, so that must first be installed and configured. On the tablet, go to the Google Play Store and install program GnuRoot Debian; it should take only a few minutes. The environment installed by GnuRoot is minimal, so perform the following steps to install some useful software on your system:

apt-get update && apt-get -y upgrade
apt-get install build-essential ed vim m4 gawk
apt-get install ssh guile-2.0 python wget curl

Depending on your aspirations, you might want to install some other packages, or omit some of those shown above. Next, copy the .gz file to directory /usr/local/src on an Android tablet running GnuRoot; I did it by performing the following commands on the tablet, which was connected to my local network, but they are unlikely to work unmodified on your machine:

cd /usr/local/src
sftp phil@192.168.1.65
     cd /usr/local/src
     get ChezScheme-9.4.tar.gz
     quit

Once you have copied the .gz file to the tablet, perform the following steps there. It is odd to install and then uninstall X-windows, but Chez Scheme requires X-windows to compile, and doesn’t require it to run, so this sequence is correct (that was the trick that took me so long to figure out, delaying the compilation by several weeks):

apt-get install libncurses5-dev libncursesw5-dev
gunzip ChezScheme-9.4.tar.gz
tar -xvf ChezScheme-9.4.tar
rm ChezScheme-9.4.tar
cd ChezScheme-9.4
apt-get x11-common libx11-dev
cd arm32le/c
make
apt-get purge x11-common libx11-dev
cd ../s
make allx
cd ../..

At this point the program is compiled and ready to use. However, the install script doesn’t work properly, for some reason, so the program must be installed manually with the following commands:

cp arm32le/bin/scheme /usr/local/bin
cp arm32le/bin/petite /usr/local/bin
chmod +x /usr/local/bin/scheme
chmod +x /usr/local/bin/petite
mkdir /usr/local/csv9.4/arm32le
cp boot/arm32le/scheme.boot /usr/local/csv9.4/arm32le
cp boot/arm32le/petite.boot /usr/local/csv9.4/arm32le

And that’s it. To test your installation, type scheme at the command-line prompt; you should be rewarded with the Chez Scheme welcome text followed by a Scheme prompt:

Chez Scheme Version 9.4
Copyright 1984-2016 Cisco Systems, Inc.

>

Your task is to get your preferred programming environment working on your mobile device, and let us know how it works. If anyone installs Chez Scheme, I would appreciate your feedback on the instructions given above, particularly if you find any errors.


by programmingpraxis at September 15, 2017 09:00 AM

September 12, 2017

Programming Praxis

Catalan Numbers

Today’s exercise is an Amazon interview question for software engineers and developers:

How many unique binary search trees can be made from a series of numbers 1, 2, 3, 4, …, n, for any given n?

Your task is to compute the number of unique binary search 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 September 12, 2017 09:00 AM

September 08, 2017

Programming Praxis

Linked List Palindrome

Today’s exercise is an Amazon interview question from Career Cup (this is the exact question asked):

There is a given linked list where each node can consist of any number of characters :- For example
a–>bcd–>ef–>g–>f–>ed–>c–>ba.
Now please write a function where the linked list will return true if it is a palindrome .
Like in above example the linked list should return true

Your task is to write a program to determine if a list of strings forms a palindrome. 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 08, 2017 09:00 AM

September 05, 2017

Programming Praxis

Three Bit Hacks

We have three problems today that involve twiddling bits. In all three cases you are not permitted to perform any branching operation (so no if-else statement) nor are you permitted to perform a loop; you must write a single statement that performs the requested task:

1) Determine the absolute value of an integer.

2) Determine if an integer is a power of 2.

3) Determine the minimum and maximum of two integers.

The restrictions on branching and loops are useful for modern CPUs that have instruction caches that you want to stay inside for speed.

Your task is to write the three bit hacks 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 September 05, 2017 02:00 PM

GNU Guix

Announcing Guix-HPC

Today, Inria, the Max Delbrück Center for Molecular Medicine (MDC), and the Utrecht Bioinformatics Center (UBC) are announcing a joint effort to consolidate GNU Guix for reproducible scientific workflows in high-performance computing (HPC). The three research institutes have been using Guix and contributing to it. The new effort, dubbed Guix-HPC, hopes to extend Guix functionality to better address the needs of HPC users, as well as augmenting its package collection.

Guix was not initially designed with HPC in mind. However, we believe it has many good properties both for flexible software deployment on clusters, and as a foundation for reproducible scientific workflows. The Guix-HPC blog will regularly feature articles with HPC “howtos” and stories about our achievements. We are thrilled by the opportunities this new effort offers!

To learn more, visit the Guix-HPC Web site.

About GNU Guix

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

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

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

by Ludovic Courtès, Roel Janssen, Pjotr Prins, Ricardo Wurmus (guix-devel@gnu.org) at September 05, 2017 10:00 AM