Why in the burning ouchy heckfire did the Lisp community, for all its talk of “worse is better”, never actually roll up our sleeves and think of this!

I use and love the sexp output for the rare few apps that support it, like notmuch, and of course xmlstarlet is amazing, but we never did a large scale, ambitious, sexpify everything project like this. The JSON dorks beat us to the punch! We should just shame scoop on the spot.

I hate JSON and I’ve never even used my own xj filter.

When you just needs some nested alists JSON overkill and when you need the full schema and xpath rig it’s underkill compared to SXML but you know what they’ve got that we don’t?

It’s there. They actually delivered.

This “jc” is a killer app among killer apps. Holy smoke.

Why don’t you put the whole world in a serialized object notation, Superman? Well, they just up and did that.

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.)

[ 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.

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.

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 , 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.

New paper with Chris Yu & Henrik Schumacher: https://t.co/SDlisHgmXu

We model 2D & 3D curves while avoiding self-intersection—a natural requirement in graphics, simulation & visualization.

Our scheme also does an *amazingly* good job of unknotting highly-tangled curves!

[1/n] pic.twitter.com/lee4WmFyPT

— Keenan Crane (@keenanisalive) August 2, 2021

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.

TIL how to fold a row of equilateral triangles in a strip of paper. Start with any fold. Here I’ve done one that is nowhere near 60°. Open it and fold the paper so an edge follows the previous crease. Repeat. The triangles quickly become almost equilateral. Can you justify this? pic.twitter.com/ALUaiVgbXS

— Dave Richeson (@divbyzero) August 7, 2021

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, 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.

It's time to stop making t-SNE & UMAP plots. In a new preprint w/ Tara Chari we show that while they display some correlation with the underlying high-dimension data, they don't preserve local or global structure & are misleading. They're also arbitrary.https://t.co/XkAOTKlOcs pic.twitter.com/dmFzD5RR6R

— Lior Pachter (@lpachter) August 27, 2021

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.

Additional submissions

• Tanya Khovanova remarks on their Number Gossip, that 1331 is the only nontrivial cube that can be written as .
• Ganit Charcha explains the math behind Montgomery Multiplication, i.e., modular exponentiation without computing a division. Super useful in cryptography!
• Anne Schwartz asked about your favorite math teaching articles, and received a big response with lots of interesting articles.
• Colin Beveridge shows off how their favorite bag of tricks to determine which triangular numbers are also squares.
• An oldie, but new to me, was the series of computational notebooks, 12 Steps to Navier Stokes, which teaches the basics of Computational Fluid Dynamics.
• Nisar Khan has been drawing pictures of random number generators

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

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)
      (funcall f init head)
      (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.

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.

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

            receiver)
  (funcall receiver
           (+ (* 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

                  receiver)
  (let ((det (- (* a d) (* b c))))
    (funcall receiver
             (/ d det) (/ (- b) det)
             (/ (- c) det) (/ a det))))

and multiply the inverse matrix by the result:

(defun solve (a b
              c d

              x
              y

              receiver)
  (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.

What's the right 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.

---

The first wakeup call was this article via HackerNews:

One does not simply calculate the absolute value

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

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*.

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.

Using with Urlwatch

Urlwatch is a great match for gemrefinder.

Here is an example config entry that you can add with urlwatch --edit.

---
name: "replies on Gemini"
command: "gemrefinder -m 60 -p gemini://your.own.domain/page-with-your-posts|grep -v gemini://your.own.domain/"
---

Then run urlwatch by hand to see if it works, and then add it to your cron jobs.

Installation

You can install gemrefinder 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.