Racket

How to Make Racket Go (Almost) As Fast As C

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.

...

Deriving Recursion from First Principles

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?

...

Writing Racket Macros: define-syntax and phases

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.

...

microKanren Reading

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!

...

A programmable programming language? I'll drink to that!

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!

A poorly-painted blue mug A passable freehanded Racket logo

...

Mastodon