Linus's stream

I found a startlingly simple and pretty efficient algorithm to approximate π today, on a web demo for Tabby. It was so interesting that I tried it myself. Here's the script:

n := 1000000
k := 1
x := 0
with std.loop(n) fn {
	x <- x + 1 / (k * k)
	k <- k + 2
}
fmt.printf('Almost π: {{0}}\t(at n = {{1}})', math.sqrt(x * 8), n)

Looks deceptively simple, right? Just a few additions and multiplications. For various values of n, here's the output:

Almost π: 2.8284271247461903  (at n = 1)
Almost π: 3.1096254579886478  (at n = 10)
Almost π: 3.1384079670670912  (at n = 100)
Almost π: 3.14127432760274    (at n = 1000)
Almost π: 3.1415608224399487  (at n = 10000)
Almost π: 3.141589470489344   (at n = 100000)
Almost π: 3.1415923352799697  (at n = 1000000)
Almost π: 3.1415926217577352  (at n = 10000000)

It looks like the formula is a variant of a Taylor series-like approximation of π, but written iteratively/imperatively rather than as a sum per se, and it comes out really clean. I like it.

The anticipation of knowing that something you're capable of building can solve a problem you've been struggling with for a long time, but you can't actually see it work until you build it.

A full file/object storage service in ~30 lines of Oak!

with server.route('/blob/:fileName') fn(params) fn(req, end) if req.method {
        'GET' -> with fs.readFile(path.join(BlobDir, params.fileName)) fn(file) if file {
                ? -> end(http.NotFound)
                _ -> end({
                        status: 200
                        headers: { 'Content-Type': http.mimeForPath(params.fileName) }
                        body: file
                })
        }
        'POST' -> if ext := params.fileName |> str.split('.') |> std.last() |> str.lower() {
                'jpg', 'jpeg', 'png', 'svg', 'gif', 'gifv' -> {
                        blobPath := crypto.uuid() + '.' + ext
                        with fs.writeFile(path.join(BlobDir, blobPath), req.body) fn(res) if res {
                                ? -> end({
                                        status: 500
                                        headers: { 'Content-Type': http.MimeTypes.txt }
                                        body: 'could not save blob'
                                })
                                _ -> end({
                                        status: 201
                                        headers: { 'Content-Type': http.MimeTypes.txt }
                                        body: blobPath
                                })
                        }
                }
                _ -> end({
                        status: 400
                        headers: { 'Content-Type': http.MimeTypes.txt }
                        body: 'unsupported file type'
                })
        }
        _ -> end(http.MethodNotAllowed)
}

I wrote this as a part of my work to add file upload/attachment support to Lig3, but I might pull this out as a separate cross-app service for my personal infrastructure because it's so simple and it's something every app needs at some point.

Doing some brainstorming today by:

• Having GPT-3 come up with creative inspirations/solutions to problem statements
• Feeding them into text-to-image models to visualize them in different styles and worlds
• Reading articles in an app that highlights key ideas and how they connect to each other within the page
• Collecting my notes in a document that highlights missed connections between my ideas old and new

Still a long road to go, but I'm optimistic we're still at the very beginning of how computers can change the way we read and write.

Today I learned while digging through my /usr/include that my local Fedora install comes with a whopping 1.2M lines of C headers in /usr/include. That seems like a lot? Yeah?

$ cat /usr/include/**/*.h | wc
1208974 4871654 44110606

44MB of source text!

Sorting in Lisp

As I've been porting Klisp to Oak for fun this week, I wrote a couple of sorting algorithms that I think came out very elegant in Lisp:

(defn quicksort (xs)
      (if (< (size xs) 2)
        xs
        (let (pivot (nth xs (int (/ (dec (size xs)) 2)))) ; heuristic: pick midpoint
          (-> (quicksort (filter xs (partial (< ? pivot))))
              (append (filter xs (is pivot)))
              (append (quicksort (filter xs (partial (> ? pivot)))))))))

(defn merge (left right)
      (cond ((empty? left) right)
            ((empty? right) left)
            ((do
               (def l (first left))
               (def r (first right))
               (if (<= l r)
                 (conj l (merge (rest left) right))
                 (conj r (merge left (rest right))))))))

(defn mergesort (xs)
      (if (< (size xs) 2)
        xs
        (let (split-at (int (/ (size xs) 2)))
          (merge (mergesort (take xs split-at))
                 (mergesort (drop xs split-at))))))

Code is a poor interface for interactivity

As I was building Oak Notebook, I thought a lot about interactive documents and what makes me excited about improving their state of the art.

An often-cited category of interactive documents is programming notebooks like Jupyter, Observable, and Nextjournal. They're very, very cool, and they've inspired me in my own work. But I think they share one big flaw in their underlying document model: code is a poor interface for interactivity.

What I mean is that programming notebooks like those use writing and executing code in a general-purpose language as the main way for the reader to control visualizations and data displays. This excludes non-programmers from being able to really understand and work with these documents, and more important, even for programmers, reading and understanding code takes effort. Code is poor notation for things that aren't software, and code as interface hides what's really going on.

Oak Notebook, despite its many flaws, uses well-known and simple interactive input widgets and avoids this pitfall, at least for the simplest 20% of needs that cover 80% of use cases. Kevin Kwok's Carbide is another workaround for this pitfall that I'm excited about — making code as notation easier to interact with by augmenting it with interactive widgets and autodiff.

Cute little command line one-liner to count the number of decimal digits in a number:

echo "9,223,372,036,854,775,807" | \
    oak eval "stdin |> std.filter(str.digit?) |> len()"

(That number is INT64_MAX, if you are curious.)

I had to write a DOM TreeWalker today for a personal project that was written in Oak, and it's surprising how pleasant it was to write. I'd say it was the same or better than using the same DOM API from JavaScript.

// headingsList takes some container <div> and returns a list of all headings
// within that section of the page, in order
fn headingsList(div) {
	walker := document.createTreeWalker(
		div
		NodeFilter.SHOW_ELEMENT
		{
			acceptNode: fn(el) if el.tagName {
				'H1', 'H2', 'H3', 'H4', 'H5', 'H6' -> NodeFilter.FILTER_ACCEPT
				_ -> NodeFilter.FILTER_SKIP
			}
		}
	)

	headings := []
	with loop() fn(_, break) if el := walker.nextNode() {
		? -> break(headings)
		_ -> headings << {
			level: int(el.tagName.1)
			text: el.textContent
		}
	}
}

This is mostly due to two things, I think:

1. The recently finalized std.loop API is really nice for generic unbounded loops.
2. This semi-recent change to oak build --web codegen made JS methods very nice to call from Oak.

Oak now has a blog! Huzzah!