Planet Scheme

April 19, 2019

Programming Praxis

Almost Primes

Today’s exercise was inspired by a task at Rosetta Code:

An integer n > 1 is a k-almost-prime if it is the product of k primes. Further, a k-almost prime is squarefree if all k primes are distinct.

You can learn more about k-almost-primes and their uses in number theory at Wikipedia or MathWorld.

Your task is to write programs that calculate the first ten k-almost-primes and squarefree k-almost-primes for 1 ≤ k ≤ 5. 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 April 19, 2019 09:00 AM

April 16, 2019

Programming Praxis

The Last Prime Digit

Over at NumberPhile, Dr Grimes (can you look at him and not smile?) discusses the pattern in the last digits of successive prime numbers. It’s not what you think.

Your task is to write a program that mimics the calculations made by Dr Grimes. 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 April 16, 2019 09:00 AM

April 12, 2019

Programming Praxis

Three Simple Math Problems

Here are three simple math problems. They are intended to be solved analytically, with number theory, without using a computer or a calculator. But I cheated. All three problems come from the YouTube channel Mind Your Decisions, where you will find lots of similar problems.

  1. Solve for x and y where both are integers: 615 + x2 = 2y
  2. Find a three-digit number abc = 100a + 10b + c with none of the digits 0 such that abc = a! + b! + c!
  3. Find a three-digit number pie = 100p + 10i + e with none of the digits 0 such that √pi + e = √ pie

Your task is to solve the three problems; you can write programs to solve them, if you wish, but it is fun to solve them by hand. When you are finished, you are welcome to or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

by programmingpraxis at April 12, 2019 04:00 AM

April 09, 2019

Programming Praxis

Grep-CSV

Regular readers of this blog know that. in my day job, I frequently process input files from vendors; almost always, they were created in Excel and arrive in CSV format. Sometimes I have to peek inside the files, looking for invalid data, and I have commonly used grep for that task. Sometimes grep gives me unwanted records, because there is a match in some field that is not the field of interested, and I just ignore the extra records. But the other day I had a mess, with lots of unwanted records, so I used awk to parse out the fields and find the records of interest.

I realized as I was performing that task that it would be useful to have a version of grep that understood the CSV file format. So I wrote grep-csv that takes a field number (counting from 1, like awk) and a regular expression and returns the matching rows of a CSV file.

Your task is to write a grep-csv 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 April 09, 2019 09:00 AM

April 05, 2019

Programming Praxis

Destructuring-Bind

We implemented Chris Okasaki’s physicist’s queues in the previous exercise. As I implemented them in Scheme, I struggled to maintain Okasaki’s clear, consise coding style, which relies heavily on pattern matching. There are several pattern-matching libraries available for Scheme, but they are rather heavy (the one I use, by Friedman, Hilsdale and Dybvig, is over six hundred lines of code). Our Standard Prelude has a simple pattern matcher, but it doesn’t fit properly with a simple binding. I finally came up with a strange method using let-values ... apply values that makes the code concise at the cost of forcing readers to think through an uncommon idiom. What I wanted was something similar to the destructuring-bind macro of Common Lisp.

So I wrote one.

Your task is to write a macro similar to the destructuring-bind macro of Common Lisp and add it 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 in the comments below.

by programmingpraxis at April 05, 2019 04:00 AM

April 03, 2019

Greg Hendershott

Exploding Frog

Exploding Frog

:: Racket, Frog

I’m writing and publishing this post using something other than Frog.

Having said that, I’m not planning to abandon maintaining Frog.

Over the past week I explored doing something I’ve wanted to try for many years: “Exploding” Frog from an app that you run, into a set of little commands that you call from a Makefile.

I believe there’s a variation of Greenspun’s Tenth Rule:

Any sufficiently complicated static blog generator contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of make.

— Someone who has made a static blog generator

If you look at Frog’s code, by volume, an awful lot of it consists of:

  1. Figuring out what needs to be (re)built.
  2. “Path math”.
  3. Configuration, customization, templates.
  4. Support for Bootstrap or various surveillance capitalism gadgets.

On the one hand, it is certainly very “Rackety” to write this in Racket. On the other hand, Racket advocates language-oriented programming. Make is a language for expressing the first two things.

As for the third item: Originally, I thought it would be cool to write Frog as an app, thinking people might use it even if they weren’t particularly into Racket programming. In reality, of course approximately 103.8% of Frog users like to program in Racket. So maybe, call this crazy, programmers who want a blog generating program to work a little differently could, I don’t know, change the program a little. Maybe there need not be layers of configuration and customization.


And yet, I’ve never really known that much about GNU Make. Just enough to cargo cult. And the GNU Make documentation, although thorough, never really “clicked” for me. This time, though, I stuck with it. It helped to have a non-trivial project in mind.

The most confusing thing for me at first, was, Make seems oriented around defining targets and “pulling” those from sources. “This executable depends on linking these object files. These object files depend on these .c and .h files.” I didn’t really grok how to make it be “push”-driven: We have a bunch of (say) .md post sources. Yes those get built into .html files, but we also have tags, and feeds, and…?

In the end I made use of some variables to define the sources, intermediate build files, and final outputs:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
# Configure where are sources, build cache, and root of the web site
# output.
src   := src
cache := .cache
www   := www

# Make normally "pulls" targets from sources, but we want to "push"
# sources to targets. As a result, we need to build lists of sources
# and from those build lists of targets.

post-sources := $(shell find $(src)/posts -type f)
post-caches  := $(patsubst $(src)/posts/%.md,$(cache)/%.rktd,$(post-sources))
post-htmls   := $(patsubst $(cache)/%.rktd,$(www)/%.html,$(post-caches))

tag-caches     := $(wildcard $(cache)/tags/*)
tag-htmls      := $(patsubst %,$(www)/tags/%.html,$(notdir $(tag-caches)))
tag-atom-feeds := $(patsubst %,$(www)/feeds/%.atom.xml,$(notdir $(tag-caches)))
tag-rss-feeds  := $(patsubst %,$(www)/feeds/%.rss.xml,$(notdir $(tag-caches)))

non-post-sources := $(wildcard $(src)/non-posts/*.md)
non-post-htmls   := $(patsubst %.md,$(www)/%.html,$(notdir $(non-post-sources)))

Then, for example, a rule like this is how we turn a .md source into an intermediate .rktd cached file:

1
2
$(cache)/%.rktd: $(src)/posts/%.md
	$(make-post-cache) $< $(abspath $(cache)/tags) $@

and that into an .html file:

1
2
$(www)/%.html: $(cache)/%.rktd rkt/page-xexpr.rkt
	$(make-post-html) $< $(www) $@

What is this business about an “intermediate post cached file”? Well, the overall model is a two-stage “compile and link” sort of metaphor, similar to Frog. Post .md sources only define the “body” of a post page, e.g. the <article> element that will go somewhere in a page. Building that can be semi-expensive when you do enhancements like syntax-highlighting and automatic links to Racket documentation. It’s nice not to need to redo that, simply because some other element on the containing page changes. Also, each post has one or more tags, so the first pass is a chance to build an index of tags to posts, which the second pass can use to make feed files and an index page for each tag.

The little commands that the Makefile calls are defined in in a rkt/ subdirectory. Some of them require modules from Frog. Others are copypasta with some adaptation. Any of these files that could be truly generic — i.e. won’t elicit a pull-request someday to get different blog behavior — I’d like to move eventually into a “tadpole” package. The remaining code should go in some repo — not a package — as example code. That is, you could copy it — probably not even fork it — and just hack away. It is your blog, so it is your program.

So far I’m enjoying this new approach.

Again, I still plan to maintain Frog, in terms of fixing bugs and keeping it working on newer versions of Racket. Already in the past couple years I’ve been super reluctant to add new features, and haven’t. All I’m saying here is that I plan to continue that not-doing.

by Greg Hendershott at April 03, 2019 12:00 AM

April 02, 2019

Programming Praxis

Okasaki’s Physicists Queues

One of my favorite programming textbooks is Chris Okasaki’s Purely Functional Data Structures, which I pick up and re-read every year or so. Today’s exercise asks you to
implement Okasaki’s physicist’s queues, which you can read about in either his book (Figure 6.3 on page 73) or his thesis (Figure 3.4 on page 31). Queues provide two constructors empty and snoc, two accessors head and tail, and a single predicate isEmpty; it is an error if either head or tail are applied to an empty queue. This version comes from the book:

structure PhysicistsQueue : QUEUE
struct
    type alpha Queue = α list × int × α list susp × int × α list

    val empty = ([], 0, $[], 0, [])
    fun isEmpty (_, lenf, _, _, _) = (lenf = 0)

    fun checkw ([], lenf, f, lenr, r) = (force f, lenf, f, lenr, r)
      | checkw q = q
    fun check (q as (w, lenf, f, lenr, r)) =
        if lenr < lenf then checkw q
        else let val f' = force f
             in  checkw (f', lenf + lenr, $(f' @ rev r), 0, []) end

    fun snoc ((w, lenf, f, lenr, r), x) =
        check (w, lenf, f, lenr + 1, x :: r)

    fun head ([], lenf, f, lenr, r) = raise EMPTY
      | head (x :: w, lenf, f, lenr, r) = x
    fun tail ([], lenf, f, lenr, r) = raise EMPTY
      | tail (x :: w, lenf, f, lenr, r) =
            check (w, lenf - 1, $tl (force f), lenr, r)
end

Your task is to implement Okasaki’s physicists queues. 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 April 02, 2019 09:00 AM

April 01, 2019

Adrien Ramos

Weekly log 2019, week 13

Life, anime and nature

My boyfriend Reptifur discovered a nice little indie game: Dig Deep. It started as a mobile game and is now available for free on computers. It reminded me a bit of Downwell, which I really like because it has very simple mechanics but they are used in very interesting ways. Dig Deep doesn’t seem as… deep, but quite fun still.

This week I played my cello for 7 hours and 30 minutes, that’s a great increase in stamina! I even practiced for 2:30 in one single day, that’s probably my personal best! I didn’t want to take a break this week because I’m not going to be able to play for a while, but I’m starting to feel a bit tired and achy.

Regarding our evening screenings, we finished watching The Legend of Korra… and we can now definitely say that it was crap. We both hated the whole series: the characters are uninteresting, never learn anything and never evolve. The scenario can fit on a stamp. It was a huge letdown compared to the original series The Last Airbender, which was just amazing.

Fortunately our friends introduced us to One Punch Man. We watched it in only two evenings with them and we all enjoyed it very much.

We also followed some of the The Legend of Zelda: Ocarina of Time Randomizer tournament. The matches were pretty tense and skills were really impressive, since most participants are speed runners of one kind or another.

This week I also planted some vegetables for the first time in my life, at a friend’s mother house. We planted onions, garlic, shallots and salads. It was a relaxing experience. I also spent some time outdoors at the local parks. I feel like spring is putting some life back into me as well as into the plants.

Lets’ talk about code now!

Code and CHICKEN Scheme news

Youbi found a crash in Ensemble that occurred when trying to send a message containing only a slash. I fixed it as soon as possible.

At first I planned on sharing a little CHICKEN trick with you: lint your code csc -A -m whatever your-file.scm but then I found out about the chicken-lint tool (from the beaker egg) which does the same and more. Among other things, it warns you about unused imports and possible problems in conditionals and mutation expressions. It found some unused imports and a few bugs in Ensemble that might have been hiding.

It doesn’t support generalized set! yet, I’ll try to make a patch later.

Hiro told me about FluidLite and I’m really interested in it! I might someday add it as an add-on module for the Hypergiant sound system I’m working on.

Lets talk about that sound system real quick, because I mentioned it in the last post already.

My plans for it are to make a very simple DSP (digital signal processing) library, a bit like PureData only not using a graphical language, but using s-expressions. It would sit on top of the Portaudio library for real-time sound input and output, and I want to ship it with useful primitives for games like sound file loading and streaming, most certainly using the Opus format and library. Some proofs-of-concept of these ideas are present in my Confiture de Fraises and Smlilme game jam games.

The DSP part of it would resemble what glls does for OpenGL shaders: it would translate a domain specific language into tight C code that can be fed to portaudio’s very restrictive callback system (you can’t allocate memory or do system calls in them, for example)

On the CHICKEN side of things, I wanted to talk a little bit about a new feature coming in 5.1: embedding C libraries into eggs.

It’s really easy to use, you just have to declare all the C files you want to link into your library as c-objects components, and declare that you want to link them into your library using the objects property.

For example, my gl-math egg is split into a pure C library doing all the calculations, called hypermath, and the gl-math Scheme module. Here is how this translates into the egg file:

(components
  (c-object hypermath
    (source "hypermath/src/hypermath.c")
    (csc-options -C "-Ihypermath/include -O3"))
  (extension gl-math
    (objects hypermath)
    (csc-options -d0 -O3 -C "-Ihypermath/include -O3"))))

These declarations make chicken-install create a gl-math.a archive and gl-math.so shared object for both static and dynamic linking support.

This feature still has a few little bugs but I patched some of them already.

I also sent a patch for set-file-position! that didn’t clear the end-of-file flag on ports.

Here are the eggs that got released this week:

SaarCHICKEN is only a few days away now!

by Kooda at April 01, 2019 03:33 PM

March 29, 2019

GNU Guix

Connecting reproducible deployment to a long-term source code archive

GNU Guix can be used as a “package manager” to install and upgrade software packages as is familiar to GNU/Linux users, or as an environment manager, but it can also provision containers or virtual machines, and manage the operating system running on your machine.

One foundation that sets it apart from other tools in these areas is reproducibility. From a high-level view, Guix allows users to declare complete software environments and instantiate them. They can share those environments with others, who can replicate them or adapt them to their needs. This aspect is key to reproducible computational experiments: scientists need to reproduce software environments before they can reproduce experimental results, and this is one of the things we are focusing on in the context of the Guix-HPC effort. At a lower level, the project, along with others in the Reproducible Builds community, is working to ensure that software build outputs are reproducible, bit for bit.

Work on reproducibility at all levels has been making great progress. Guix, for instance, allows you to travel back in time. That Guix can travel back in time and build software reproducibly is a great step forward. But there’s still an important piece that’s missing to make this viable: a stable source code archive. This is where Software Heritage (SWH for short) comes in.

When source code vanishes

Guix contains thousands of package definitions. Each package definition specifies the package’s source code URL and hash, the package’s dependencies, and its build procedure. Most of the time, the package’s source code is an archive (a “tarball”) fetched from a web site, but more and more frequently the source code is a specific revision checked out directly from a version control system.

The obvious question, then, is: what happens if the source code URL becomes unreachable? The whole reproducibility endeavor collapses when source code disappears. And source code does disappear, or, even worse, it can be modified in place. At GNU we’re doing a good job of having stable hosting that keeps releases around “forever”, unchanged (modulo rare exceptions). But a lot of free software out there is hosted on personal web pages with a short lifetime and on commercial hosting services that come and go.

By default Guix would look up source code by hash in the caches of our build farms. This comes for free: the “substitute” mechanism extends to all “build artifacts”, including downloads. However, with limited capacity, our build farms do not keep all the source code of all the packages for a long time. Thus, one could very well find oneself unable to rebuild a package months or years later, simply because its source code disappeared or moved to a different location.

Connecting to the archive

It quickly became clear that reproducible builds had “reproducible source code downloads”, so to speak, as a prerequisite. The Software Heritage archive is the missing piece that would finally allow us to reproduce software environments years later in spite of the volatility of code hosting sites. Software Heritage’s mission is to archive essentially “all” the source code ever published, including version control history. Its archive already periodically ingests release tarballs from the GNU servers, repositories from GitHub, packages from PyPI, and much more.

Software Heritage logo

We quickly settled on a scheme where Guix would fall back to the Software Heritage archive whenever it fails to download source code from its original location. That way, package definitions don’t need to be modified: they still refer to the original source code URL, but the downloading machinery transparently goes to Software Heritage when needed.

There are two types of source code downloads in Guix: tarball downloads, and version control checkouts. In the former case, resorting to Software Heritage is easy: Guix knows the SHA256 hash of the tarball so it can look it up by hash using the /content endpoint of the archive’s interface.

Fetching version control checkouts is more involved. In this case, the downloader would first resolve the commit identifier to obtain a Software Heritage revision. The actual code for that revision is then fetched through the vault.

The vault conveniently allows users to fetch the tarball corresponding to a revision. However, not all revisions are readily available as tarballs (understandably), so the vault has an interface that allows you to request the “cooking” of a specific revision. Cooking is asynchronous and can take some time. Currently, if a revision hasn’t been cooked yet, the Guix download machinery will request it and wait until it is available. The process can take some time but will eventually succeed.

Success! At this point, we have essentially bridged the gap between the stable archive that Software Heritage provides and the reproducible software deployment pipeline of Guix. This code was integrated in November 2018, making it the first free software distribution backed by a stable archive.

The challenges ahead

This milestone was encouraging: we had seemingly achieved our goal, but we also knew of several shortcomings. First, even though the software we package is still primarily distributed as tarballs, Software Heritage keeps relatively few of these tarballs. Software Heritage does ingest tarballs, notably those found on the GNU servers, but the primary focus is on preserving complete version control repositories rather than release tarballs.

It is not yet clear to us what to do with plain old tarballs. On one hand, they are here and cannot be ignored. Furthermore, some provide artifacts that are not in version control, such as configure scripts, and often enough they are accompanied by a cryptographic signature from the developers that allows recipients to authenticate the code—an important piece of information that’s often missing from version control history. On the other hand, version control tags are increasingly becoming the mechanism of choice to distribute software releases. It may be that tags will become the primary mechanism for software release distribution soon enough.

Version control tags turn out not to be ideal either, because they’re mutable and per-repository. Conversely, Git commit identifiers are unambiguous and repository-independent because they’re essentially content-addressed, but our package definitions often refer to tags, not commits, because that makes it clearer that we’re providing an actual release and not an arbitrary revision (this is another illustration of Zooko’s triangle).

This leads to another limitation that stems from the mismatch between the way Guix and Software Heritage compute hashes over version control checkouts: both compute a hash over a serialized representation of the directory, but they serialize the directory in a different way (SWH serializes directories as Git trees, while Guix uses “normalized archives” or Nars, the format the build daemon manipulates, which is inherited from Nix.) That prevents Guix from looking up revisions by content hash. The solution will probably involve changing Guix to support the same method as Software Heritage, and/or adding Guix’s method to Software Heritage.

Having to wait for “cooking” completion can also be problematic. The Software Heritage team is investigating the possibility to automatically cook all version control tags. That way, relevant revisions would almost always be readily available through the vault.

Similarly, we have no guarantee that software provided by Guix is available in the archive. Our plan is to extend Software Heritage such that it would periodically archive the source code of software packaged by Guix.

Going further

In the process of adding support for Software Heritage, Guix gained Guile bindings to the Software Heritage HTTP interface. Here’s a couple of things we can do:

(use-modules (guix swh))

;; Check whether SWH has ever crawled our repository.
(define o (lookup-origin "https://git.savannah.gnu.org/git/guix.git"))
⇒ #<<origin> id: 86312956 …>

;; It did! When was its last visit?
(define last-visit
  (first (origin-visits o)))

(date->string (visit-date last-visit))
⇒ "Fri Mar 29 10:07:45Z 2019"

;; Does it have our “v0.15.0” Git tag?
(lookup-origin-revision "https://git.savannah.gnu.org/git/guix.git" "v0.15.0")
⇒ #<<revision> id: "359fdda40f754bbf1b5dc261e7427b75463b59be" …>

Guix itself is a Guile library so when we combine the two, there are interesting things we can do:

(use-modules (guix) (guix swh)
             (gnu packages base)
             (gnu packages golang))

;; This is our GNU Coreutils package.
coreutils
⇒ #<package coreutils@8.30 gnu/packages/base.scm:342 1c67b40>

;; Does SWH have its tarball?
(lookup-content (origin-sha256 (package-source coreutils))
                "sha256")
⇒ #<<content> checksums: (("sha1" …)) data-url: …>

;; Our package for HashiCorp’s Configuration Language (HCL) is
;; built from a Git commit.
(define commit
  (git-reference-commit
    (origin-uri (package-source go-github-com-hashicorp-hcl))))

;; Is this particular commit available in the archive?
(lookup-revision commit)
⇒ #<<revision> id: "23c074d0eceb2b8a5bfdbb271ab780cde70f05a8" …>

We’re currently using a subset of this interface, but there’s certainly more we could do. For example, we can compute archive coverage of the Guix packages; we can also request the archival of each package’s source code via the “save code” interface—though all this is subject to rate limiting.

Wrap-up

Software Heritage support in Guix creates a bridge from the stable source code archive to reproducible software deployment with complete provenance tracking. For the first time it gives us a software package distribution that can be rebuilt months or years later. This is particularly beneficial in the context of reproducible science: finally we can describe reproducible software environments, a prerequisite for reproducible computational experiments.

Going further, we can provide a complete software supply tool chain with provenance tracking that links revisions in the archive to bit-reproducible build artifacts produced by Guix. Oh and Guix itself is archived, so we have this meta-level where we could link Guix revisions to the revisions of packages it provides… There are still technical challenges to overcome, but that vision is shaping up.

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 March 29, 2019 02:50 PM

Programming Praxis

Project Euler 12

When a question about Project Euler 12 came up today at Reddit, I came here to link my solution to the problem, only to find out that we have never done that problem. So today we will.

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Your task is to write a program to solve Project Euler 12. 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 March 29, 2019 04:00 AM

March 27, 2019

Arthur A. Gleckler

RnRS Gardening

Monet's garden at Giverny

RnRS Gardening

As long as the roots are not severed, all is well. And all will be well in the garden.

— Chance the Gardener

Programming language communities are like gardens. Often, we get to grow something new and beautiful. But sometimes, we have to collect our tools and do grunt work just to keep things alive. This is a story about recent grunt work on two web sites in the garden of Scheme. I learned a few lessons in the process.

small.r7rs.org

First, some background: The most recent round of Scheme standardization, known as R7RS, divided the language into two versions, Small and Large. In 2013, after several years of work, working group 1 finished the specification for R7RS Small, and it was approved. Now, working group 2, chaired by John Cowan, is working on R7RS Large. (This is all being done by volunteers, and you're welcome to participate.)

For our work on R7RS Small, WG1 used Trac, an open-source issue tracker and wiki, at the domain trac.sacrideo.us. In late 2018, the site was taken down because the hosting provider stopped supporting it. Fortunately, we had backups. John restored the wiki pages from a recent backup, then did a rough translation of each page's markup into HTML or Markdown. Those pages are now hosted by Bitbucket, and r7rs.org points to them. John continues to update those pages as part of his work leading R7RS Large.

So we had our wiki pages again. However, the Bitbucket site doesn't include any of the issue-tracking pages that WG1 used to track a total of 538 tickets covering topics like Make nested quasiquotes work properly and Extend finite? and nan? to non-real values. Also, since it's a living site, it doesn't represent a historical record of what went into R7RS Small. R7RS Small was a big effort, and the Scheme community has a long tradition of doing its work in the open, so it seemed important to preserve that work somehow.

However, none of us wanted to run a Trac site. For my part, I wasn't interested in installing Trac, keeping up with security updates, and expanding the attack surface of my personal web server in the process. Faced with this dilemma, I procrastinated for months, then did something that's normally a bad idea. I implemented, in Scheme, a nearly complete implementation of Trac's elaborate markup language (WikiFormatting) as well as a good part of its data model. Using that code, I generated a replica, as static HTML files, of our Trac site. That replica is now hosted, thanks to Jonathan Rees's DNS wizardy, at small.r7rs.org.

Reimplementing a system from scratch is generally not advisable. It almost always turns out to be a bigger project than planned. Getting all the corner cases right, and matching the detailed behavior of the existing system, which has benefited from the work of many contributors over years, is a big job. On the other hand, in this particular case, I only had to get it working well enough to match one set of input data, and that data would not change, since it was a historical record. The maintenance, performance, and security benefits of serving a static set of HTML files instead of running a Trac instance were just too good to pass up. And implementing WikiFormatting was a self-contained programming challenge with a quick feedback loop, so it was fun to work on.

Every page on small.r7rs.org has a banner at the top explaining that it comes from a static snapshot of our Trac instance. Any page that John and I thought might possibly have been updated as part of the R7RS Large work has a link to the Bitbucket version, too. And all pages have links to their source in case I've screwed up the formatting somehow in my translation. Both wiki pages and tickets have been preserved.

Thanks to Aaron Hsu, requests to the old trac.sacrideo.us are now forwarded to small.r7rs.org, which rewrites the URLs to match the new URL syntax. As a result, as far as I could manage, all links to the old pages still work. (Right now, I'm using HTTP 302 Found, i.e. temporary redirects, but if all goes well, I'll eventually switch to 301 Moved Permanently.)

scheme-reports.org

At the scheme-reports.org web site, the official home of the Scheme reports, more bit rot had set in. Sometime around 2016, the scheme-reports@scheme-reports.org mailing list, which was the place for discussion of all the RnRS standards, went down. Not only did mail serving stop, but the entire archive of messages to the mailing list was lost. No backups could be found. However, Jonathan has managed to recreate the archive by extracting scheme-reports messages from his personal email archive and feeding them to MHonArc. Unfortunately, we haven't been able to reproduce the old URLs, so old URLs will now break. We've added a landing page that explains the history of the new archive so that people understand why there might be discrepancies or broken links. Mailing list delivery has been restarted, but new messages are not automatically pushed to the archive. (Maybe someday.)

We've gone through all the links on scheme-reports.org pages and updated them to account for the new email archive, the new small.r7rs.org site, and the latest URLs for the various RnRS reports, including all the R7RS Small drafts, errata, overview, etc.

Lessons

I learned a few lessons from these projects:

  1. In many cases, reimplementing software is a bad idea. But not always. In this case, making the investment now in exchange for future simplicity was a good tradeoff.
  2. Always own the domain name. In this case, we got lucky because Aaron owned the domain, but it would have been even better to have started with r7rs.org. Then we wouldn't have to maintain redirects across domains, and our URLs wouldn't be vulnerable to either of two sites going down.
  3. Always make backups and check that they work. We were lucky to have them for trac.sacrideo.us, but we didn't have them for the scheme-reports mailing list.
  4. Be careful when choosing a piece of software as a platform. It's easy to become committed to a piece of software by accident, and disentangling oneself from it may be a lot of work. It may be practically impossible. We were lucky to be able to replace Trac, but keeping the old Pipermail URLs proved to be too much to do.
  5. There are fun projects to work on even when doing grunt work.

Acknowledgements

Many thanks to Aaron, John, and Jonathan for all their help on these two projects and for their contributions to the Scheme community. Thanks, too, to Alex Shinn, chair of WG1, and to the members of the Scheme Steering Committee. And thanks to the authors and maintainers of Trac, which was a great asset while we were working on R7RS Small.

by Arthur A. Gleckler at March 27, 2019 12:00 PM

March 26, 2019

Programming Praxis

Multiplicative Persistance

Over at NumberPhile, Matt and Brady are talking about multiplicative persistance:

Take a number. Multiply all its digits together. Repeat with the new number until it reaches a single digit. For instance, starting from 327, the product of the digits 3, 2 and 7 is 42, then recurring with 42 the product of the digits 4 and 2 is 8, which is the final answer; we say the sequence 327 → 42 → 8 finishes in 2 steps. What number leads to a sequence with the maximal number of steps?

The video includes some live-coding in Python by Matt.

Your task is to implement a function to compute the multiplicative persistance sequence starting from a given number, then “play with it” as Matt suggests. 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 March 26, 2019 04:00 AM

March 25, 2019

Adrien Ramos

Weekly log 2019, week 12

So yeah, I want to try to get myself to start a weekly series of tiny posts, because it takes too long to write very detailed posts, and I’m not good with “microbloging” either so it might be a nice middle ground.

I still want to try the longer format from time to time though, but I don’t want to pressure myself to only do that.

I’m not sure if it will last, I might skip some weeks, but I will try not to. I should probably write a bit every day. If you have advice on light bloging, send them my way!

This week I trained on my cello a lot, I got back in the habit on practicing every day! 4:12 of practice this week.

I’ve seen some friends I hadn’t seen in a long while, it was really nice. One of them showed me his gear for his new hobby: making beer. Pretty impressive stuff! He’s really serious about it!

On the CHICKEN Scheme side of things, this week has been really busy!

The readability improvement for type warnings patches, from Megane, have finally been merged! I think it’s more in line with what people expect from compiler warnings, even though I personally think it’s a bit too spaced out. Here’s an example showing the old and new messages for the same piece of code (car 42):

From this:

Warning: at toplevel:
  (example.scm:1) in procedure call to `car', expected argument #1 of type `pair' but was given an argument of type `fixnum'

To this:

Warning: Invalid argument
  In file `example.scm:1',
  At the toplevel,
  In procedure call:

    (scheme#car 42)

  Argument #1 to procedure `car' has an invalid type:

    fixnum

  The expected type is:

    pair

  This is the expression:

    42

  Procedure `car' from module `scheme' has this type:

    ((pair 'a19 *) -> 'a19)

An other great patch, again from Megane, was also merged. It changes an internal procedure that is related to module loading, that was previously quadratic and is now linear, thanks to the use of hash tables. In my tests, it reduced the compilation time of a very simple example from hypergiant (that is very module heavy) from 5 minutes to 20 seconds! Thanks Megane, you’ve removed quite a big pain! I also tried a follow-up change that reduces this even further, to 4 seconds, but I have to tidy things up before I submit it.

Apart from feature patches, we experienced a weird bug creeping up, that prevented a lot of eggs from compiling properly, but a bug fix was swiftly devised by Felix.

I also finished porting Hypergiant! We now have the full suite of OpenGL eggs available in CHICKEN 5! Perfect timing for the Lisp Game Jam next month.

A lot of CHICKEN eggs have been released this week! Awesome!

I finally took some time to setup salmonella on the broken Mac OS laptop a friend gave me. Results can be seen here and should soon appear in the official listing.

Oh and, SaarCHICKEN is in two weeks! I’m really excited!

That’s it for this week! Please let me know what you think of this new, more laid back format. It certainly is far easier for me to write, but I hope it’s still interesting.

by Kooda at March 25, 2019 01:58 PM

March 22, 2019

Programming Praxis

Data Laundry, Revisited

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. Some weeks, as this week, data laundry occupies a significant portion of my time at work, so it’s an exercise worth examining. We looked at data laundry in two previous exercises. Today’s exercise in data laundry comes to us from Stack Overflow:

I have a file like this:

AAKRKA HIST1H1B AAGAGAAKRKATGPP
AAKRKA HIST1H1E RKSAGAAKRKASGPP
AAKRLN ACAT1 LMTADAAKRLNVTPL
AAKRLN SUCLG2 NEALEAAKRLNAKEI
AAKRLR GTF2F1 VSEMPAAKRLRLDTG
AAKRMA VCL NDIIAAAKRMALLMA
AAKRPL WIZ YLGSVAAKRPLQEDR
AAKRQK MTA2 SSSQPAAKRQKLNPA

I would like to kind of merge 2 lines if they are exactly the same in the 1st column. The desired output is:

AAKRKA HIST1H1B,HIST1H1E AAGAGAAKRKATGPP,RKSAGAAKRKASGPP
AAKRLN ACAT1,SUCLG2 LMTADAAKRLNVTPL,NEALEAAKRLNAKEI
AAKRLR GTF2F1 VSEMPAAKRLRLDTG
AAKRMA VCL NDIIAAAKRMALLMA
AAKRPL WIZ YLGSVAAKRPLQEDR
AAKRQK MTA2 SSSQPAAKRQKLNPA

Sometimes there could be more than two lines starting with the same word. How could I reach the desired output with bash/awk?

Your task is to write a program to solve this simple task of data laundry. 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 March 22, 2019 04:00 AM

March 19, 2019

Programming Praxis

Target Sum Subarray

Given an array of non-negative integers, write a program that finds the contiguous portion of the array that sums to a given target, or report that there is no such subarray. For instance, in the array 1, 4, 20, 3, 10, 5, target 33 exists in the subarray 20, 3, 10, in the array 1, 4, 0, 0, 3, 10, 5, target 7 exists in the subarray 4, 0, 0, 3, and in the array 1, 4, target 3 does not exist in any subarray.

Your task is to write a program that finds a target sum 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 March 19, 2019 09:00 AM