# Planet Scheme

## Tuesday, September 21, 2021

### Idiomdrottning

#### Whitespace philosophy (for Lisp stuff)

Can people who put in a ton of whitespace in the middle of lines so that (on monospace) bindings or table values match up vertically please lay that off? Thank you.

• It looks messed up on proportional fonts and on screenreader.
• It’s difficult to extend; say you need to add a new line and it makes some of the “columns” now too narrow. Your diff now has to touch every line.
• It makes it fiddly to add code in that area and to use Paredit properly.
• You can’t string search for key/value pairs or name/binding pairs without a whitespace regex.

I don’t want my Lisp to be ASCII art. This isn’t Befunge.

(This isn’t refering to whitespace at the beginning of lines, a.k.a. indentation. That’s fine.)

## Tuesday, September 14, 2021

### Programming Praxis

#### Motzkin Numbers

[ I’ve had a couple of readers ask where I have been. I put in my retirement papers at work a few months ago, and will retire at the end of 2021. That sounds good, but setting up my post-retirement finances, learning about Medicare (it’s a huge mess) and deciding what to do with the rest of my life has been exhausting, and I still have a job to do. Here’s a simple exercise; I’ll try to be more regular about posting in future weeks. — Phil ]

Your task is to write a program to generate Motzkin Numbers (A001006). If you don’t like Motzkin numbers, pick any other sequence from the OEIS. 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.

# 2021-05-18 - Ruse Scheme shall be

Ruse Scheme, formely known as Arew Scheme, is at this stage, a collection of Scheme libraries for Chez Scheme. There is a grand scheme plan plot machination for it. Read on.

## What is a civilization kit?

A civilization kit is a software or set of software that ease the organization of life. So far, there is really one civkit that is mostly privateer that includes and is not limited to:

• Wikimedia project such as Wikipedia, Wikidata, Wiktionary...
• Android, iOS, Firefox, Chrome..
• MacOS, FreeBSD, NetBSD, Windows, Debian, Fedora, Ubuntu...
• Mastodon, and other projects that rely on activitypub...

And many more... that is only the visible part of Earth software system. They are software that aim to ease the the production of software or hardware. They are also software that helps with governance, provide tools to ease law making process, sustain production chain of food, energy, medecine, culture, education...

They are a lot of software, and that collection form a civkit.

## Is Ruse Scheme a new Scheme?

Yes, and no. It depends what is meant by a new Scheme.

Sometime a Scheme is a software that gathers many Scheme libraries, and rely on existing Scheme to execute their code. That is the case of Ruse.

Most of the time, a Scheme is a software that interpret and/or compile a lot of parentheses that is more or less compatible with RnRS. In this regard, Ruse is a Scheme, but it is not completly new. It rely on Chez Scheme to produce executables that can be run on a server or a desktop. Ruse will support Web Assembly and JavaScript to run Scheme in a Web browser.

Some Scheme implementation do a little of both, and also deliver features that go beyond past or current RnRS. Ruse does that, and shall reach beyond...

The main difference with existing Scheme implementations is not found at the programming language level. Ruse is and will stay a Scheme.

The main area Ruse try to innovate is the rest: whether it is the the production or sharing of code, Ruse aim to make it easier than sharing a meme. Another area Ruse try to innovate is to state upfront the scope of the project.

## What are the short term goal of Ruse Scheme?

The short term goal of Ruse Scheme is to build a scalable search engine: Babelia. Babelia will both scale-up and scale-down in terms of required hardware. In other words, it may run in the cloud or on a Raspberry Pi.

That first milestone will demonstrate how to build a distributed Von Neumann architecture that aim to be easier to work with than current approaches.

This is the first milestone because it is easier than going fully dencentralized first. It will deliver the necessary tools to work with the current Internet.

The plan is to deliver Babelia in 2022.

## What is the next Internet?

The next Internet is an Internet that is more open, more decentralized, more accessible, and resting upon the fundamental principle.

## What is the distributed Von Neumann architecture?

The distributed Von Neumann architecture is like a regular computer that rely on multiple commodity computers.

It is different from a compute grid, because it is not meant only for batch processing.

In Babelia, that distributed computer has volatile memory, non-volatile memory, possibly vectors or graphics processing units, and generic computation units.

The goal is to make it easier to build software inside a trusted network of computers.

## What are the mid term goals of Ruse Scheme?

Mid term goals of Ruse Scheme are three folds:

• Offer enough tooling to make it easier to create, sell and make a living by producing Scheme code. This includes making it painless to interop with existing software.

• Implement a package manager inspired from Nix, and backed up by content-addressable code that can be translated into multiple natural languages with the help of a decentralized peer-to-peer network.

• Explore a new operating system desktop paradigm resting upon the fundamental principle.

## What is the goal of Ruse Scheme?

The goal of Ruse Scheme is to build a coherant bootstrapable whole-stack civkit for a sustainable civilization, resting upon the fundamental principle.

## What is whole-stack?

Whole-stack build upon the full-stack concept to include programming databases, and kernels.

## What is the fundamental principle?

If a system must serve the creative spirit, it must be entirely comprehensible by a single individual.

# 2021-09-02 - Let there be binary executables

I released ruse-exe. A Chez program that allows to create binary executables from Scheme programs.

Here is in full the usage documentation:

Usage:

ruse-exe [--dev] [--petite] [--optimize-level=0-3] [EXTENSIONS-OR-DIRECTORIES ...] program.scm [ -- ARGS ...]

Given a Scheme program inside the file program.scm, produce a
standalone executable inside the current directory called a.out.
ruse-exe will look for the necessary files inside
EXTENSIONS-OR-DIRECTORIES.  The arguments following two dashed
ARGS will passed to the underlying C compiler.

The flag --dev will enable generate allocation and instruction count.

The flag --petite will only build with petite scheme.

The arguments EXTENSIONS-OR-DIRECTORIES will replace the default
extensions, source and library directories. If you want to compile a
project that has both .ss and .scm with libraries in the current
directory, you need to use something along the line of:

ruse-exe .ss .scm . program.scm

Homepage: http://letloop.xyz

You can grab a ready to use on ubuntu 21.04 binary release at github.

# 2021-09-03 - Oops!

Sorry planet Scheme there was a bug in my blog engine. I hope it is fixed now...

# 2021-08-25 - Jack: One Thread Per Core

I have being making progress with Babelia on the web user interface, IRC interface, and also the backend.

Regarding the backend, even if Chez Scheme is fast, it is clear even on the small dataset I have put together, that is around eleven gigabytes without compression. I need something like map-reduce [1], in LISP world known under the name of for-each-parallel-map.

In full-text search, and in a search product like google, they are tips, and tricks to avoid to hit the worst case. The worst being a query where the least frequent word is also one of the most frequent in the index. Possible workarounds include 0) using AND as the default operator 1) eliminating most common word (also known as stop-words); 2) caching results; 3) approximating results with user profiling...

All those workarounds give rise to other problems, or they need a lot of work such as profiling users, which is in my opinion not a problem when that is limited to profiling users' data that are published in the open (unlike tracking search users via their queries, or mail, etc...).

Anyway, threads are difficult, so I wanted to give it try. The above is trying to explain from where my motivation stems from.

It is still unclear whether make-jack works reliably all the time. You tell me.

## (make-jack count) â†’ procedure?

make-jack initialize a pool of COUNT parallel threads, and return a possibly endless generator that produces jacks. A jack is made of two procedure:

1. The first procedure is an accumulator that will consume one or more thunks. That is how the user request the parallel execution of something.

2. The second procedure will generate the results of the thunks submitted with the associated accumulator in an unspecified order.

Example:

(call-with-values jack
(lambda (consumer producer)
;; submit some work to the pool, the consumer will block
;; if there is too much work already scheduled.
(consumer thunks)
;; pull results
(let loop ((count (length input)))
(unless (fxzero? count)
;; producer will block the current thread until there
;; is something to produce
(display (producer))
(newline)
(loop (fx- count 1))))))


Here are some numbers that backup the claim that it may work as expected, the tests were done with pool of size five. The work, called THUNKS in the above snippet, is the computation of one thousand times fibonacci of 40:

(time (call-with-values jack ...))
no collections
0.029955076s elapsed cpu time
152.646622367s elapsed real time
592688 bytes allocated
Command being timed: "scheme --libdirs src/ --program main.scm"
User time (seconds): 761.84
System time (seconds): 0.04
Percent of CPU this job got: 498%
Elapsed (wall clock) time (h:mm:ss or m:ss): 2:32.71
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 49624
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 14194
Voluntary context switches: 1011
Involuntary context switches: 3646
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0

The code:

(define-record-type* <queue>
;; This is a fifo queue, that can signal when items are available
;; or space is available. Space is available when there is less
;; than MARK items inside the REST. It is used in jacks in both
;; accumulators and generators.
(make-queue% name head rest mark mutex item-available space-available)
queue?
(name queue-name)
(rest queue-rest queue-rest!)
;; mark is an integer that allows to keep the number of produced,
;; and accumulated values low; Tho, there is room for starvation.
(mark queue-mark)
(mutex queue-mutex)
(item-available queue-item-available)
(space-available queue-space-available))

(define (make-queue name mark)
(make-queue% name '() '() mark (make-mutex) (make-condition) (make-condition)))

(define (queue-pop! queue)
(mutex-acquire (queue-mutex queue))
(if (null? (queue-rest queue))
(begin
;; Wait for work...
(condition-wait (queue-item-available queue) (queue-mutex queue))
(mutex-release (queue-mutex queue))
;; recurse
(queue-pop! queue))
;; There is nothing in the head, but the rest has stuff
;; reverse the rest to keep it FIFO, and replace the
;; HEAD with it. Return the first item immediatly to
;; avoid to pressure the mutex, and best performance.
(queue-rest! queue '())
(condition-signal (queue-space-available queue))
(mutex-release (queue-mutex queue))
item))
;; There is work, all is well.
(mutex-release (queue-mutex queue))
item)))

(define (queue-push! queue . items)
(mutex-acquire (queue-mutex queue))
;; we only check that the rest is less than the mark. BUT the user
;; may append more than mark ITEMS.
(if (fx<? (length (queue-rest queue)) (queue-mark queue))
(begin
(queue-rest! queue (append items (queue-rest queue)))
;; TODO: It may not be necessary to wake up all waiting
;; threads, but only (length (queue-rest queue))?
(mutex-release (queue-mutex queue)))
(begin
;; Block until some work is done.
(condition-wait (queue-space-available queue) (queue-mutex queue))
(mutex-release (queue-mutex queue))
;; TODO: here it is possible to append the items without
;; recursing.
(apply queue-push! queue items))))

(define (make-jack count)

;; That is the queue for all work for the created thread pool.
;; The mark is an arbitrary number, it could be an argument.
(define input (make-queue 'input (fx* count 2)))

(define (worker-loop index input)
;; TODO: replace thunk+output with output+thunk, and avoid the
;; cdr before the car.
(let ((thunk+output (queue-pop! input)))
(queue-push! (cdr thunk+output) ((car thunk+output)))
(worker-loop index input)))

(define (worker-init count)
(let loop ((count count))
(unless (fxzero? count)
;; count is passed as the thread index for debugging
;; purpose
(fork-thread (lambda () (worker-loop count input)))
(loop (fx- count 1)))))

(define (input-consumer input output)
(lambda (thunks)
;; TODO: avoid the call to apply. The reverse is necessary, to
;; keep around the priority information FIFO.
(apply queue-push! input (reverse (map (lambda (thunk) (cons thunk output)) thunks)))))

(define (output-producer output)
(lambda ()
(queue-pop! output)))

;; Initialize thread pool at call site, that is somewhat unusual
;; for a generator to have side-effects outside producing values.
(worker-init count)

(lambda ()
;; again the mark is a clueless guess.
(define output (make-queue 'output (fx* count 2)))
(values (input-consumer input output) (output-producer output))))


## Wednesday, September 1, 2021

### Scheme Requests for Implementation

#### SRFI 230: Atomic Operations

SRFI 230 is now in draft status.

This SRFI defines atomic operations for the Scheme programming language. An atomic operation is an operation that, even in the presence of multiple threads, is either executed completely or not at all. Atomic operations can be used to implement mutexes and other synchronization primitives, and they can be used to make concurrent algorithms lock-free. For this, this SRFI defines two data types, atomic flags and atomic (fixnum) boxes, whose contents can be queried and mutated atomically. Moreover, each atomic operation comes with a memory order that defines the level of synchronization with other threads.

### Jeremy Kun

#### Carnival of Mathematics #197

Welcome to the 197th Carnival of Mathematics!

197 is an unseemly number, as you can tell by the Wikipedia page which currently says that it has “indiscriminate, excessive, or irrelevant examples.” How deviant. It’s also a Repfigit, which means if you start a fibonacci-type sequence with the digits 1, 9, 7, and then continue with $a_n = a_{i-3} + a_{i-2} + a_{i-1}$, then 197 shows up in the sequence. Indeed: 1, 9, 7, 17, 33, 57, 107, 197, …

## Untangling the unknot

Kennan Crane et al showcased a new paper that can untangle tangled curves quickly, and can do things like generate Hilbert-type space-filling curves on surfaces. It’s a long thread with tons of links to videos and reading materials, covering energy functions, functional analysis, Sobolev methods, and a custom inner product.

## Folding equilateral triangles without measuring

Dave Richeson shows off a neat technique for folding equilateral triangles using just paper and no measurements. Replies in the thread show the geometric series that converges to the right 60 degree angle.

## Shots fired at UMAP and t-SNE

Lior Pachter et al. study what sorts of structure are preserved by dimensionality reduction techniques like UMAP (which I have also used in a previous article) by comparing it against a genomics dataset with understood structure. They make some big claims about how UMAP and t-SNE destroy important structure, and they show how to contrive the dimensionality reduction plot to look like an elephant even when there’s no elephantine structure in the data.

I’m not expert, but perhaps one best case scenario for UMAP enthusiasts would be that their analysis only applies when you go from very high dimensions down to 2 just so you can plot a picture. But if you stop at, say, $\sqrt{n}$ dimensions, you might still preserve a lot of the meaningful structure. Either way, they make a convincing pitch for Johnson-Lindenstrauss’s random linear reductions, which I’ve also covered here. Their paper is on biorXiv.

## Studying the Sieve

Ben Peters Jones took up Grant Sanderson’s math video challenge and released a series of videos studying the Sieve of Eratosthenes.

Be sure to submit fun math you find in September to the next carvinal host!

## Monday, August 30, 2021

### Joe Marshall

#### Tail recursion and fold-left

fold-left has this basic recursion:

(fold-left f init ())      = init
(fold-left f init (a . d)) = (fold-left f (f init a) d)
A straightforward implementation of this is
(defun fold-left (f init list)
(if (null list)
init
(fold-left f (funcall f init (car list)) (cdr list))))
The straightforward implementation uses a slightly more space than necessary. The call to f occurs in a subproblem position, so there the stack frame for fold-left is preserved on each call and the result of the call is returned to that stack frame.

But the result of fold-left is the result of the last call to f, so we don't need to retain the stack frame for fold-left on the last call. We can end the iteration on a tail call to f on the final element by unrolling the loop once:

(defun fold-left (f init list)
(if (null list)
init
(fold-left-1 f init (car list) (cdr list))))

(defun fold-left-1 (f init head tail)
(if (null tail)
(fold-left-1 f (funcall f init head) (car tail) (cdr tail))))

There aren't many problems where this would make a difference (a challenge to readers is to come up with a program that runs fine with the unrolled loop but causes a stack overflow with the straightforward implementation), but depending on how extreme your position on tail recursion is, this might be worthwhile.

## Saturday, August 28, 2021

### Scheme Requests for Implementation

#### SRFI 228: A further comparator library

SRFI 228 is now in draft status.

Further procedures and syntax forms for defining SRFI 128 comparators, and for extracting comparison procedures similar to those defined for Schemeâ€™s built-in types using them.

Best enjoyed in combination with SRFI 162.

## Friday, August 27, 2021

### Joe Marshall

#### A Floating-point Problem

Here's a 2x2 matrix:

[64919121   -159018721]
[41869520.5 -102558961]
We can multiply it by a 2 element vector like this:
(defun mxv (a b
c d

x
y

(+ (* a x) (* b y))
(+ (* c x) (* d y))))

* (mxv 64919121     -159018721
41869520.5d0 -102558961

3
1

#'list)

(35738642 2.30496005d7)
Given a matrix and a result, we want to find the 2 element vector that produces that result. To do this, we compute the inverse of the matrix:
(defun m-inverse (a b
c d

(let ((det (- (* a d) (* b c))))
(/ d det) (/ (- b) det)
(/ (- c) det) (/ a det))))
and multiply the inverse matrix by the result:
(defun solve (a b
c d

x
y

(m-inverse a b
c d
(lambda (ia ib
ic id)
(mxv ia ib
ic id

x
y
receiver))))
So we can try this on our matrix
* (solve 64919121     -159018721
41869520.5d0 -102558961

1
0
#'list)

(1.02558961d8 4.18695205d7)
and we get the wrong answer.

* (solve 64919121         -159018721
(+ 41869520 1/2) -102558961

1
0
#'list)

(205117922 83739041)
If we use double precision floating point, we get the wrong answer by a considerable margin.

I'm used to floating point calculations being off a little in the least significant digits, and I've seen how the errors can accumulate in an iterative calculation, but here we've lost all the significant digits in a straightforward non-iterative calculation. Here's what happened: The determinant of our matrix is computed by subtracting the product of the two diagonals. One diagonal is (* 64919121 -102558961) = -6658037598793281, where the other diagonal is (* (+ 41869520 1/2) -159018721) = -6658037598793280.5 This second diagonal product cannot be represented in double precision floating point, so it is rounded down to -6658037598793280. This is where the error is introduced. An error of .5 in a quantity of -6658037598793281 is small indeed, but we amplify this error when we subtract out the other diagonal. We still have an absolute error of .5, but now it occurs within a quantity of 1, which makes it relatively huge. This is called “catastrophic cancellation” because the subtraction “cancelled” all the significant digits (the “catastrophe” is presumably the amplification of the error).

I don't care for the term “catastrophic cancellation” because it places the blame on the operation of subtraction. But the subtraction did nothing wrong. The difference betweeen -6658037598793280 and -6658037598793281 is 1 and that is the result we got. It was the rounding in the prior step that introduced an incorrect value into the calculation. The subtraction just exposed this and made it obvious.

One could be cynical and reject floating point operations as being too unreliable. When we used exact rationals, we got the exactly correct result. But rational numbers are much slower than floating point and they have a tendancy to occupy larger and larger amounts of memory as the computation continues. Floating point is fast and efficient, but you have to be careful when you use it.

## Negative zero

Gauche supports IEEE754 negative zero -0.0. It simply wraps an IEEE754 double as a scheme object, so mostly it just works as specified in IEEE754 (and as supported by the underlying math library). Or, so we thought.

Let's recap the behavior of -0.0. It's numerically indistinguishable from 0.0 (so, it is not "an infinitely small value less than zero"):

(= -0.0 0.0) ⇒ #t

(< -0.0 0.0) ⇒ #f

(zero? -0.0) ⇒ #t


But it can make a difference when there's a functon f(x) such that it is discontinuous at x = 0, and f(x) goes to different values when x approaches to zero from positive side or negative side.

(/ 0.0)  ⇒ +inf.0
(/ -0.0) ⇒ -inf.0


For arithmetic primitive procedures, we simply pass unboxed double to the underlying math functions, so we didn't think we need to handle -0.0 specially.

It talks about writing abs in Java, but every time I saw articles like this I just try it out on Gauche, and alas!

;; Gauche 0.9.10
(abs -0.0) ⇒ -0.0    ; Ouch!


Yeah, the culprit was the C implementation of abs, the gist of which was:

   if (x < 0.0) return -x;
else return x;


-0.0 doesn't satisfy x < 0.0 so it was returned without negation.

The easy fix is to use signbit.

   if (signbit(x)) return -x;


I reported the fix on Twitter, then somebody raised an issue: What about (eqv? -0.0 0.0)?

My initial reaction was that it should be #t, since (= -0.0 0.0) is #t. In fact, R5RS states this:

The eqv? procedure returns #t if: ... obj1 and obj2 are both numbers, are numerically equal (see = ...), and are either both exact or both inexact.

However, I realized that R7RS has more subtle definition.

The eqv? procedure returns #f if: ... obj1 and obj2 are both inexact numbers such that either they are numerically unequal (in the sense of =), or they do not yield the same results (...) when passed as arguments to any other procedure that can be defined as a finite composition of Scheme's standard arithmetic procedures, ...

Clearly, -0.0 and 0.0 don't yield the same results when passed to /, so it should return #f. (It is also mentioned in 6.2.4 that -0.0 is distinct from 0.0 in a sense of eqv?.)

Fix for this is a bit involved. When I fixed eqv?, a bunch of tests started failing. It looks like some inexact integer division routines in the tests yield -0.0, and are compared to 0.0 with equal?, which should follow eqv? if arguments are numbers.

It turned out that the root cause was rounding primitives returning -0.0:

;; Gauche 0.9.10
(ceiling -0.5) ⇒ -0.0


Although this itself is plausible, in most of the cases when you're thinking of integers (exact or inexact), you want to treat zero as zero. Certainly you don't want to deal with two distint zeros in quotients or remainders. The choices would be either leave the rounding primitives as are and fix the integer divisions, or change the rounding primitives altogether. I choose the latter.

The fixes are in the HEAD now.

;; Gauche 0.9.11
(eqv? -0.0 0.0) ⇒ #f
(ceiling -0.5) ⇒ 0.0


Tags: 0.9.11, Flonums

## Wednesday, August 25, 2021

### Scheme Requests for Implementation

#### SRFI 227: Optional Arguments

SRFI 227 is now in draft status.

This SRFI specifies the opt-lambda syntax, which generalizes lambda. An opt-lambda expression evaluates to a procedure that takes a number of required and a number of optional (positional) arguments, whose default values are determined by evaluating corresponding expressions when the procedure is called.

This SRFI also specifies a variation opt*-lambda, which is to opt-lambda as let* is to let and the related binding constructs let-optionals and let-optionals*.

## Saturday, August 21, 2021

### Idiomdrottning

#### gemrefinder

Usage:

gemrefinder -p gemini://your.own.domain/page-with-your-posts


gemrefinder checks Gemini space for replies to your posts.

The current version checks

• Antenna
• nytpu’s comitium subscriptions
• gmisub aggregate
• CAPCOM
• Nightfall City’s Main Street, Dusk’s End, and Writer’s Lane

It only checks titles of posts, and see if they start with “RE: something you’ve started a post title with”.

Your own posts are included, but you can pipe the output of gemrefinder through grep -v to get rid of those.

You can install it with

chicken-install gemrefinder


You also need to have gmni in your path.

For source code (AGPL),

git clone https://idiomdrottning.org/gemrefinder


## Update

m15o writes in:

I love how a simple convention (RE:) that’s been around for years with email can be leveraged with other tools to create a simple notification system.

Right? It’s not as fool proof as checking for actual backlinks would be, since some people do change the title somewhat, and in that case gemrefinder will miss them. But it worked for me finding your reply right now♥

(By the way, I only now realize your site is mirrored on the web and looks stunning!)

That’s very flattering, thank you♥

## More

jjm mentions:

and then, tracking who is replying to my posts? This is starting to sound a bit like Twitter… or Tumblr?

I don’t know about that. It’s just nice to be able to take a few days off from constant reloading and save up for a longer cozy reading session, knowing that I can get alerted ro any direct replies right away.

I know peeps hate notifications (not necessarily jjm) but there is something even worse out there: constant checking checking checking. That’s a bad habit I can fall into if I don’t automate.

### Göran Weinholt

#### Loko Scheme 0.9.0

Loko Scheme 0.9.0 is now available from:

A bootable disk image for 64-bit PCs is available from:

The signatures are made with the GnuPG key 0xE33E61A2E9B8C3A2.

Loko Scheme 0.9.0 fixes bugs, improves performance and adds features. See NEWS.md in the distribution for a more detailed summary of changes.

Loko Scheme is an optimizing Scheme compiler that builds statically linked binaries for bare metal, Linux and NetBSD/amd64. It supports the R6RS Scheme and R7RS Scheme standards.

Loko Schemeâ€™s web site is https://scheme.fail, where you can find the release tarballs and the manual.

Loko Scheme is available under GNU Affero GPL version 3 or later.