Planet Scheme

February 19, 2019

Programming Praxis

The Trapped Knight

Over at Numberphile, Neil Sloane discusses a knight moving on an infinite chessboard with squares numbered in a square spiral (note that, starting from 1, the squares on the southeast diagonal are successive squares of odd numbers 1² = 1, 3² = 9, 5² = 25, 7² = 49, and so on):

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28 .
41 20  7   8 9 10 27 .
42 21 22 23 24 25 26 .
43 44 45 46 47 48 49 50

The knight starts from square 1 and always moves to the smallest-numbered square not previously visited. Thus, from 1, the knight can move to squares 10, 12, 14, 16, 18, 20, 22 or 24, of which the smallest unvisited square is 10. From 10, the knight can then move to squares 1, 3, 23, 29, 47, 49, 51 or 53; the smallest of those, 1, has already been visited, so the knight moves to square 3. And so on. The beginning of the knight’s tour visits squares 1, 10, 3, 6, 9, 4 and so on (A316667).

Your task is to write a program to determine if the knight’s tour is infinite or if the knight becomes trapped with no remaining unvisited squares; if the knight becomes trapped, determine the length of his tour and the square on which he remains. 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 February 19, 2019 10:00 AM

February 15, 2019

Programming Praxis

Peaks

Given an array of integers, a peak is a subarray of minimal length in which the integer values increase and then decrease. For instance, in the array [5,5,4,5,4] there is a peak [4,5,4] and in the array [6,5,4,4,4,4,4,5,6,7,7,7,7,7,6] there is a peak [6,7,7,7,7,7,6]. Note that [4,5,6,7,7,7,7,7,6] shows a pattern of increasing and decreasing values, but it is not minimal because the first two items can be removed and the remaining subarray remains a peak. The array [5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8] has two peaks, [4,5,4] and [8,9,9,8].

Your task is to write a program that finds all of the peaks in an array. 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 February 15, 2019 10:00 AM

February 12, 2019

Programming Praxis

Consecutive Sums

Given the positive integer 15, there are three ways to take consecutive positive integers that sum to 15: 1+2+3+4+5, 4+5+6 and 7+8.

Your task is to write a program that, given a positive integer, finds all the ways that consecutive positive integers can sum to the target 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 February 12, 2019 10:00 AM

February 07, 2019

GNU Guix

QA on non-Intel at Guix Days

During the second day of Guix Days (a FOSDEM fringe event) we split up into smaller working groups based on our areas of interest. I led a group which aimed to address some of the package issues which exist on non-Intel architectures. Of course not everyone has access to an ARM board, but with the qemu-binfmt-service service it is possible to use QEMU and the binfmt_misc functionality of the Linux kernel to emulate these systems. Many have reported that this system emulation is comparable in speed to many of the available ARM boards on the market. Yet another possibility would be to do the hacking on an x86_64 system and, when we had a working prototype, to test it with QEMU or on actual ARM hardware.

Our group decided to tackle Go, which was lacking support in Guix on armhf and aarch64. Upon checking the build logs from Cuirass and the source code for Go we determined that Go did indeed require the gold linker from the GNU Binutils. We didn't want to modify the copy of Binutils in Guix since it is part of our bootstrap story, so we quickly put together a new package definition which added the configure flag to enable gold.

(define-public binutils-gold
  (package
    (inherit binutils)
    (name "binutils-gold")
    (arguments
     (substitute-keyword-arguments (package-arguments binutils)
       ((#:configure-flags flags)
        `(cons "--enable-gold=default" ,flags))))))

This was an obvious first step, and one which we knew would fail. Had it been this easy gold would have been enabled back in 2012 when it was first added. Our error came in the form of one of the binaries not being able to link against libstdc++.so, which is in the gcc:lib output. This was quickly added and we were off and building again.

(define-public binutils-gold
  (package
    (inherit binutils)
    (name "binutils-gold")
    (arguments
     (substitute-keyword-arguments (package-arguments binutils)
       ((#:configure-flags flags)
        `(cons "--enable-gold=default" ,flags))))
    (inputs
     `(("gcc:lib" ,gcc "lib")))))

Once again this failed. What were we missing? The correct paths were included, the file was indeed in the gcc:lib output. We inspected the original binutils package again noticed that it was built against a static libgcc, so of course it wouldn't find the shared library. In order to work quickly we copied the configure flags rather than inheriting them from binutils and tried our build again.

(define-public binutils-gold
  (package
    (inherit binutils)
    (name "binutils-gold")
    (arguments
     (substitute-keyword-arguments (package-arguments binutils)
       ((#:configure-flags flags)
        `(cons* "--enable-gold=default"
                "--enable-new-dtags"
                "--with-lib-path=/no-ld-lib-path"
                "--enable-install-libbfd"
                "--enable-deterministic-archives"))))
    (inputs
     `(("gcc:lib" ,gcc "lib")))))

This time we made it through the full build phase and we knew we were almost there. Our enthusiasm was quickly dampened when we got the error during the tests: unable to find the 'dc' program. What is this dc program? This isn't any package any of us had heard of before. It definitely wasn't packaged in Guix. A quick apt-cache search dc search in Ubuntu showed they didn't have package either. A second search of Ubuntu, apt-file search dc | grep '/bin/dc' quickly showed us it was in the bc package, and soon we were building binutils-gold again.

(define-public binutils-gold
  (package
    (inherit binutils)
    (name "binutils-gold")
    (arguments
     (substitute-keyword-arguments (package-arguments binutils)
       ((#:configure-flags flags)
        `(cons* "--enable-gold=default"
                "--enable-new-dtags"
                "--with-lib-path=/no-ld-lib-path"
                "--enable-install-libbfd"
                "--enable-deterministic-archives"))))
    (native-inputs
     `(("bc" ,bc)))
    (inputs
     `(("gcc:lib" ,gcc "lib")))))

Approaching the end of the check phase we soon ran into another error, there was an unpatched /bin/sh somewhere in the source code which was generated during the check phase. Based on the build logs we were able to track down approximately where the code should be, so we downloaded the source tar xf $(guix build --source binutils) and started looking. There were many obvious /bin/sh calls which we cross-referenced with the build logs and the patch-source-shebangs phase, and this left us with some code in gold/Makefile.in, which by default is not included in the patch-source-shebangs and would need to be fixed manually.

(define-public binutils-gold
  (package
    (inherit binutils)
    (name "binutils-gold")
    (arguments
     `(#:phases
       (modify-phases %standard-phases
         (add-after 'patch-source-shebangs 'patch-more-shebangs
           (lambda _
             (substitute* "gold/Makefile.in"
               (("/bin/sh") (which "sh")))
             #t)))
       ,@(substitute-keyword-arguments (package-arguments binutils)
         ((#:configure-flags flags)
          `(cons* "--enable-gold=default"
                  "--enable-new-dtags"
                  "--with-lib-path=/no-ld-lib-path"
                  "--enable-install-libbfd"
                  "--enable-deterministic-archives")))))
    (native-inputs
     `(("bc" ,bc)))
    (inputs
     `(("gcc:lib" ,gcc "lib")))))

One more build cycle later and we did it! /gnu/store/…-binutils-gold-2.31.1 existed! We now did two things, we copied our patch over to an aarch64 build machine and we started cleaning up our package definition on our x86_64 build machine, where we knew we had a working package definition.

(define-public binutils-gold
  (package
    (inherit binutils)
    (name "binutils-gold")
    (arguments
     `(#:phases
       (modify-phases %standard-phases
         (add-after 'patch-source-shebangs 'patch-more-shebangs
           (lambda _
             (substitute* "gold/Makefile.in"
               (("/bin/sh") (which "sh")))
             #t)))
       ,@(substitute-keyword-arguments (package-arguments binutils)
         ((#:configure-flags flags)
          `(cons* "--enable-gold=default"
                  (delete "LDFLAGS=-static-libgcc" ,flags))))))
    (native-inputs
     `(("bc" ,bc)))
    (inputs
     `(("gcc:lib" ,gcc "lib")))))

Fortunately for us the changes in the code worked on x86_64 and we still got a working binutils-gold output. On our aarch64 side the build was progressing nicely and everything seemed fine... until we suddenly were presented with big red errors about unrelocatable code. How could it? Everything was working so well! Undeterred, we built the source again, this time targeting armhf and were unfortunately presented with similar errors. Deciding to address the test failures later (It's ARM! It's not as well tested as other architectures! Right?) we disabled the tests and unsurprisingly binutils-gold built on both aarch64 and armhf.

(define-public binutils-gold
  (package
    (inherit binutils)
    (name "binutils-gold")
    (arguments
     `(#:phases
       (modify-phases %standard-phases
         (add-after 'patch-source-shebangs 'patch-more-shebangs
           (lambda _
             (substitute* "gold/Makefile.in"
               (("/bin/sh") (which "sh")))
             #t)))
       ,@(substitute-keyword-arguments (package-arguments binutils)
         ((#:tests? _ #f) #f)
         ((#:configure-flags flags)
          `(cons* "--enable-gold=default"
                  (delete "LDFLAGS=-static-libgcc" ,flags))))))
    (native-inputs
     `(("bc" ,bc)))
    (inputs
     `(("gcc:lib" ,gcc "lib")))))

Now for the real test. Due to bootstrapping issues with Go and aarch64, aarch64 uses Go@1.4 built for armhf. Go@1.11 failed to build until now because it was missing the gold linker. Surely using the gold linker would be a good test if our package worked. Since Go for aarch64 is 'more complex' due to the bootstrapping using armhf's Go, we decided to test armhf first. binutils-gold was added and our build started.

    (native-inputs
     `(("go" ,go-1.4)
+      ,@(match (%current-system)
+          ((or "armhf-linux" "aarch64-linux")
+           `(("gold" ,binutils-gold)))
+          (_ `()))
       ,@(package-native-inputs go-1.4)))

First build, success! /gnu/store/…-go-1.11.5 exists! OK, but does it actually work? guix build syncthing --system=armhf-linux. /gnu/store/…-syncthing-1.0.0 exists too! A quick check of guix refresh --list-dependent go@1.4 showed that we had unlocked 176 new packages for armhf. Even better, since they had all failed by default due to go@1.11 failing to build, for each package that did build meant one fewer package which failed to build which should take a big bite out of our build failures.

Our next test was syncthing for aarch64. /gnu/store/…-go-1.11.5 exists! /gnu/store/…-syncthing-1.0.0 ... does not. "unknown architecture 'armv7-a'." It seems that Go is confused which architecture it is building for. Unfortunately we were reaching the end of our time for hacking, so that will have to wait for another day. All that was left now was the test failures on binutils-gold for the ARM systems. Some attempts at cargo-culting other code failed (per-architecture tests we had and overriding flags in substitute-keyword-arguments we had, but not together), but after some attempts we were able to create a working package definition we were happy with.

(define-public binutils-gold
  (package
    (inherit binutils)
    (name "binutils-gold")
    (arguments
     `(#:phases
       (modify-phases %standard-phases
         (add-after 'patch-source-shebangs 'patch-more-shebangs
           (lambda _
             (substitute* "gold/Makefile.in"
               (("/bin/sh") (which "sh")))
             #t)))
       ,@(substitute-keyword-arguments (package-arguments binutils)
         ; Upstream is aware of unrelocatable test failures on arm*.
         ((#:tests? _ #f)
          (if (any (cute string-prefix? <> (or (%current-target-system)
                                               (%current-system)))
                   '("i686" "x86_64"))
              '#t '#f))
         ((#:configure-flags flags)
          `(cons* "--enable-gold=default"
                 (delete "LDFLAGS=-static-libgcc" ,flags))))))
     (native-inputs
      `(("bc" ,bc)))
     (inputs
      `(("gcc:lib" ,gcc "lib")))))

This patch was pushed to the master branch as 28317d499034b00cf1f08a9efd39bd2bc3425b19, and the commit following uses it as a native-input for Go@1.9 and Go@1.11. Go@1.4 was added in June 2016 and Go@1.6 that August, with our first go packages being added in October 2017. That same October Go@1.4 had support limited to Intel and armhf and in October 2018, in an effort to work toward a resolution, a patch was added to have aarch64 use Go@1.4 built for armhf for it's bootstrap path. Basically since the addition of the Go language support into Guix there was not a time when it was usable on armhf or aarch64. Hopefully we will soon finish getting full Go support on aarch64 and we can move all 352 dependents of Go@1.4 from "failing" to "succeeding" and have these architectures better supported.

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 Efraim Flashner at February 07, 2019 08:30 AM

February 06, 2019

Arthur A. Gleckler

Lisp in Person

Lisp in Person

The Bay Area Lisp and Scheme Users Group meets a few times every year to discuss computer science, design, human-computer interaction, complex systems development, programming languages, compiler optimization, cryptography, computer music, artificial intelligence, and other topics from a Lisp and Scheme point of view. I'm a member and co-organizer of the group.

Our meetings are typically organized around one long-form talk and a few five-minute lightning talks, followed by snacks and chatting. I've learned a lot about many interesting projects by attending.

I've been video-recording many of the talks and putting them on YouTube. To date, we have thirty-two talks on our playlist, including these long-form talks:

If you're in the San Francisco Bay Area, please join us for our next meeting. We're a friendly group, and we'd love to meet you and hear about your Lisp and Scheme projects, too. And if you'd like to give a talk, please send me a note.

(By the way, I've automated much of the video post-production work in Scheme. I wrote a wrapper around FFmpeg that takes much of the complexity out of using it. I plan to write about that in a future blog post.)

by Arthur A. Gleckler at February 06, 2019 12:00 PM

February 05, 2019

Programming Praxis

String Data Type

Different programming languages handle strings differently. In C, for instance, strings are null-terminated arrays of characters, so the \0 character is not permitted in strings; other langauges permit any character in a string. Some languages are limited to ascii, others admit unicode. Some languages allow strings to be mutated, while others make strings immutable. Some languages number the characters in a string starting from 0, others from 1. If you’re porting a program from one language to another, dealing with strings can be a headache. (You can probably guess accurately at the motivation for today’s exercise.)

Today’s exercise calls for you to write a portable string data type that can be easily moved language to another. You are free to define strings as you wish — not everyone will have the same needs. Whatever you decide, you should provide conversions to and from the strings in your native language, as well as some basic operations on strings: determine their length, find the character at a particular position, modify a character if you decide strings should be mutable, extract a substring, concatenate two strings, perhaps others. Make your data type as simple or as elaborate as you wish.

Your task is to write a portable string data type that can be easily moved from one language to another. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at February 05, 2019 10:00 AM

February 01, 2019

Programming Praxis

Alternating Lists

Today’s exercise is a simple task in list manipulation:

Write a program that takes one or more lists and returns a single list containing the elements of the input lists, taken alternately from the lists. If the lists are of different lengths, continue taking items from the lists that remain.

For instance, given the inputs (1 2 3 4 5), (a b c) and (w x y z), the desired output is (1 a w 2 b x 3 c y 4 z 5).

Your task is to write a program to take items alternately from multiple lists. 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 February 01, 2019 10:00 AM

January 29, 2019

Programming Praxis

Marsaglia’s Mental RNG

We saw an “in-your-head” random number generator in a previous exercise, but I found it hard to operate. Today’s exercise, due to George Marsaglia is a random number generator that even a dummy like me can work in his head:

Choose a two-digit number as a seed. Then form a new two-digit number by adding the ten’s digit and six times the unit digit. For instance, if you start from 23, the sequence is 23 → 20 → 02 → 12 → 13 → 19 → 55 → 35 …. Then the sequence of random digits is the unit digit of each two-digit number. This operation produces the numbers 1 through 58 as seeds; the ten digits each occur six times, except that nine and zero occur five times (because 59 and 60 are not part of the sequence).

Your task is to implement Marsaglia’s mental RNG, and experiment with it to determine its effectiveness. 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 29, 2019 10:00 AM

January 28, 2019

GNU Guix

Meet Guix at FOSDEM

As usual, GNU Guix will be present at FOSDEM in the coming days with a couple of talks:

The minimalist languages track will also feature talks about GNU Guile and about Racket that you should not miss under any circumstances!

Guix Days logo.

For the second time, we are also organizing the Guix Days as a FOSDEM fringe event, a two-day Guix workshop where contributors and enthusiasts will meet. The workshop takes place on Thursday Jan. 31st and Friday Feb. 1st at the Institute of Cultural Affairs (ICAB) in Brussels.

This year there will be few talks; instead, the event will consist primarily of “unconference-style” sessions focused on specific hot topics about Guix, the Shepherd, continuous integration, and related tools and workflows. We are also happy to welcome fellow Nix hackers, which should allow us to develop cross-distro cooperation.

Attendance to the workshop is free and open to everyone, though you are invited to register (there are only a few seats left!). Check out the workshop’s wiki page for registration and practical info. Hope to see you in Brussels!

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 Ludovic Courtès at January 28, 2019 11:00 AM

January 25, 2019

Programming Praxis

First Word

We have a simple exercise today, inspired a co-worker. Where I work, we have a reporting tool that permits a “hook” to the underlying SQL in some places. My co-worker asked me how to write an SQL statement that extracts the first word (a maximal sequence of non-spaces) from the beginning of a string (assume there are no leading spaces). For instance, given the string “abcdefg hijklmnop qrs tuv wxyz” the first word is “abcdefg”. Here’s the SQL expression, wrapped in a select statement, with &&STR representing the string:

select substr('&&STR', 1, instr('&&STR', ' ') - 1) from dual

Your task is to write a program to extract the first word from a string. 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 25, 2019 10:00 AM

January 22, 2019

Programming Praxis

Lunar Arithmetic

Over at Numberphile, Neil Sloane (yes, that Neil Sloane), talks about lunar arithmetic, an “other-worldly” way of doing simple math:

Lunar addition and multiplication work digit by digit, the same as terrestrial addition and multiplication, except that the plus and times tables are unusual. Addition is done by taking the larger of the two digits, so 1 + 3 = 3 and 7 + 4 = 7. Multiplication is done by taking the smaller of the two digits, so 1 * 3 = 1 and 7 * 4 = 4. Thus:

      3 5 7        3 5 7
    +   6 4      *   6 4
    -------      -------
      3 6 7        3 4 4
                 3 5 6
                 -------
                 3 5 6 4

There are no carries. There is no subtraction or division, since the results would not be unique.

Your task is to write programs that perform lunar addition and multiplication. 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 22, 2019 02:12 PM

January 19, 2019

Arthur A. Gleckler

Growing Schemes

Growing Schemes

My favorite dialect of Lisp, Scheme, first appeared in 1975. The Revised Reports on Scheme (RnRS) are the official standards[footnotes] for the language. In 1998, however, a second, parallel standards effort began: SRFI, the Scheme Requests for Implementation.

The purpose of the Scheme Requests for Implementation (SRFI) process is to help Scheme users write portable, useful code. We write concrete, detailed proposals and sample implementations for libraries and other additions to the Scheme language, and we encourage Scheme implementors to adopt them.

As of this writing, 165 Scheme standards documents have been produced by the volunteers who contribute to SRFI. Many of those documents have influenced, or have been incorporated into, the RnRS standards.

I took over as SRFI editor in April, 2015. In 2018, I realized that SRFI had been running for twenty years, so it was a natural point to write a history of the process. I submitted a paper about it (PDF) to the Scheme Workshop 2018 and gave a talk at the workshop, too (YouTube, slides). It was great fun to summarize the work that so many people have done over the years to help the language evolve, and to talk about my modest plans for improving the SRFI process.

YouTube thumbnail

This chart shows how the number of new SRFIs has grown over the years:

If you're a Scheme user or implementer, please join us and help prepare Scheme for the next twenty years!

Footnotes

Below are all of the RnRS and IEEE standards documents for Scheme. The SRFI documents are all available at srfi.schemers.org.

  • 1975: R0RS (PDF)
  • 1978: R1RS (PDF)
  • 1985: R2RS (PDF)
  • 1986: R3RS (PDF)
  • 1990: IEEE 1178-1990 (Available for purchase through IEEE.)
    IEEE Standard for the Scheme Programming Language. Reaffirmed 2008.
  • 1991: R4RS (PDF)
  • 1998: R5RS (PDF)
  • 2007: R6RS
    • base (PDF)
    • libraries (PDF)
    • appendices (PDF)
    • rationale (PDF)
  • 2013: R7RS-small (PDF)
  • in progress (as of this writing): R7RS-large

by Arthur A. Gleckler at January 19, 2019 12:00 PM

January 18, 2019

Programming Praxis

Extract Number From String

We have another string-handling exercise today:

Given a string containing a number, extract the number from the string. For instance, the strings “-123”, “-123junk”, “junk-123”, “junk-123junk” and “junk-123junk456” should all evaluate to the number -123.

Your task is to write a program to extract a number from a string. 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 18, 2019 10:00 AM

January 15, 2019

Programming Praxis

Find The Difference

Today’s question comes from a programming student:

You are given two strings s and t that consist only of lower-case letters. String t was created by adding one letter chosen at random to string s, then shuffling the resulting string. Find the letter that was added to t. For instance, the difference between the two strings “abcdef” and “bfxdeac” is the character “x”.

Your task is to write a program to find the random letter that was added to the string. 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 15, 2019 10:00 AM

January 11, 2019

Programming Praxis

Parallel Assignment

Recently, I was writing a program where I needed parallel assignment; the details of my program don’t matter. Some languages provide parallel assignment natively; for instance, Python:

Python 2.7.13 (default, Mar 13 2017, 20:56:15)
[GCC 5.4.0] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> a,b,c = 1,2,3
>>> print a,b,c
1 2 3
>>> a,b,c = b,c,a
>>> print a,b,c
2 3 1

You can do something similar in C (I think — I’m not sufficiently expert in C to be certain this works):

#define SWAP(x, y) { typeof(x) t = x; x = y; y = t }

Your task is to add parallel assignment to your favorite programming language. 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 11, 2019 10:00 AM