15 Oct 2024
I recently wrote about using first-class functions to help make a BF interpreter. This is a follow-up post to describe a nifty solution to a tricky problem that made my program go 2–5× faster and put it about on-par with an interpreter written in pure C.
A basic interpreter works by walking down the AST and evaluating nodes recursively: when the interpreter encounters an expression, it dispatches on the type of expression to decide how to perform the evaluation. Here’s the key insight to get a massive speed bump with very little effort: that dispatch is expensive and can be performed ahead-of-time. We can walk through the code once and precompute all the dispatching work.
...
2 Oct 2023
Or: Approaching the Y Combinator
These are some of my class notes. Learning to derive the Y Combinator from first principles is something I’ve always wanted to do. This isn’t quite the Y Combinator, but it’s very close and it still gets you recursion without relying on recursive structures to begin with.
In the beginning, we write a recursive function to compute the length of a list:
(let* ([len (λ (lst)
(if (null? lst)
0
(+ 1 (len (cdr lst)))))])
(len '(1 2 3)))
The let* syntax allows us to create local variable bindings that can reference themselves. But let’s suppose we don’t have let*—what do we do?
...
19 May 2023
There are a bunch of different ways of writing a macro in Racket. There are also some tricky things around phases to keep in mind. This is to help me keep them all straight.
3+1 ways to make a macro
#
This form:
(define-syntax-rule (foo args ...) (use args ...))
is equivalent to:
(define-syntax foo
(syntax-rules ()
([foo args ...] (use args ...))))
Which, is in turn equivalent to:
(define-syntax foo
(λ (stx)
(syntax-case stx ()
[(gensymed-foo args ...) #'(use args ...)]))) ; gensymed-foo is like foo but doesn't match in the template
because syntax-rules expands to syntax-case with some fancy wrapping around it.
...
4 Jul 2022
μKanren (“micro-Kanren”) is a tiny, embeddable logic programming language. It’s easy to understand and implement in almost any language. It’s a great case study of an embedded language: unlike other common “embedded” languages like SQL or regex, which normally are represented as just plain-old strings, μKanren takes more advantage of the host language’s features.
I recommend reading the original paper: it’s short, well-written, and easy to understand.
I did a write-up which you can read on Codeberg. The README is my set of notes that I made while walking through the implementation of the paper, and the repository contains an implementation in Racket. I’ve included some fun use cases like a type checker/inference engine that takes up only 37 lines of code!
...
21 Aug 2021
My wife and I got a chance to go to a place that lets you paint pottery and then have it fired. The pottery is all pre-made; you just get to paint it.
It’s been a very long time since I’ve worked with a physical art medium, so the mug looks kinda dumpy. I did alright with the Racket logo on the bottom-inside of the mug though!
...