Programming languages are too slow! I’m not talking about execution speed—I’m talking about evolution speed. Programmers are always building new libraries and embedded DSLs, but the host programming language—particularly its type system—doesn’t understand the domain-specific aspects of these things.
...Chorex is a brand-new Elixir library for choreographic programming [3]: Chorex provides a macro-based DSL that lets you describe how processes communicate to perform a computation. This top-down description of interacting processes is called a choreography. From this choreography, Chorex creates modules for each process that handle all the message-passing in the system. The interactions performed by the generated code will never deadlock by construction because the choreographic DSL ensures that no processes will be waiting on each other at the same time.
...This is the story of how I solved a problem (ugly, cumbersome boilerplate code) that I ran into while writing a program in a functional language (Elixir). Functional programming languages often pride themselves on expressiveness and elegance; but occasionally they are not amenable to the most obvious solutions to the problems we wish to solve. In this case, the simplest solution to my problem would have been to have a global mutable variable. But no one likes those.
...Macros are tricky beasts. Most languages—if they have macros at all—usually include a huge “here there be dragons” warning to warn curious would-be macro programmers of the dangers that lurk ahead.
What is it about macros that makes them so dangerous and unwieldy? That’s difficult to answer in general: there are many different macro systems with varying degrees of ease-of-use. Moreover, making macros easy to use safely is an open area of research—most languages that have macros don’t have features necessary to implement macros safely. Hence, most people steer clear of macros.
...There’s a neat paper Type Systems as Macros by Chang, Knauth, and Greenman [1] that describes how to implement a typed language using an untyped host language and macro expansion. The paper is neat, but I found the code hard to follow—the paper uses a compact notation that’s convenient for print, but not so much for reproducing on one’s own. This post is my attempt to implement and explain in more accessible terms what’s presented in the paper.
...This is a question I’ve been wrestling with for a little bit. My first experience with a type system was with Java, and I didn’t like it. It just felt like an annoying constraint on the kinds of programs I could write. I was coming from Perl, which sports weak dynamic typing, so Java’s rigidity came as a bit of a shock.
After Java I learned some C, which too has types. C’s types are different from Java’s in a big way: in C they’re really just directives to the compiler on how to interpret some bytes. “Everything is just void *” is kind of true. In C, bytes can be interpreted however you wish.
I had a friend ask me what continuations are, and why they're useful. There's a ton of literature about continuations; this is just a simple example meant to showcase something small and hopefully grokkable.
You will need to understand a little bit of Racket, but if you know any Scheme, that should be good enough. If you just want a quick primer, check out Learn X in Y minutes for Racket.
#lang racket
;;; Export these symbols
(provide fail pick non-deterministic-factor)
;;; Global stack of choices (only visible to this module)
(define *choices* '())
;;; Pop a value off of the alternate choices stack
(define (fail)
(if (null? *choices*)
#f
(let ([next-choice (car *choices*)])
(set! *choices* (cdr *choices*))
(next-choice))))
This next function pick is where we capture the continuation. I've named it
return-from-pick to illustrate that when you call this function, it
will jump back to the point in the code where pick returns.
However, this works even if you use the continuation after the
thing the called pick itself has returned.
All the source for this may be found on my Codeberg repository.
Experimental type checker/inferer for a simple lambda calculus
This is a type inference system for a little language. (Described below.) It uses a fusion of type inference algorithms from PLAI, ESP, and μKanren. (See Resources)
Broadly speaking, our type inference engine works by:
We’ll describe each of those in more detail.
...μ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!
...Last week I was studying outside of a lecture hall where someone was teaching an introductory course on computer programming. There was a lot that I overheard that I disagreed with; this essay is an attempt to help me crystallize what exactly I disagreed with.
...