programming-languages

Functional Languages Need Not Be Slow

20 Dec 2023
programming-languages

Somewhere in my adolescence I got stuck with the notion that functional languages were slow while languages like C were fast. Now, a good C programmer can eke more performance out of their code than probably anyone else, but the cost you pay to keep your code correct goes exponential as you get closer and closer to the machine. Functional languages abstract a lot away from the machine. Higher languages in general abstract away the machine and make code easier to maintain. ...

Towards Fearless Macros

13 Nov 2023
featured
programming-languages, macros

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

Why Don't More Languages Have a call/cc Operator?

30 Oct 2023
programming-languages, computer-science

Something I’ve wondered about for a little while: why don’t more languages have a call/cc operator? Having first-class continuations in your programming language gives your programmers a powerful construct. So why do only a handful of languages have it? The short answer is: it’s tricky to implement efficiently. One way to get call/cc is to convert your code into continuation-passing style. Then, call/cc simply takes the continuation in that representation and binds it to a variable. ...

Deriving Recursion from First Principles

2 Oct 2023
computer-science, programming-languages, racket

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

Implementing Type Systems as Macros

14 Aug 2023
featured
computer-science, programming-languages, macros, type-checking

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

What is a type system, really?

23 Jan 2023
featured
computer-science, programming-languages, type-checking

Background # 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. ...

Continuations—what are they?

17 Nov 2022
tutorials, featured
programming, programming-languages

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

How to write a type checker/type inferrer with good error messages

27 Jul 2022
featured, tutorials
programming-languages, type-checking, computer-science

All the source for this may be found on my SourceHut repository. Synopsis # Experimental type checker/inferer for a simple lambda calculus Description # 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: generating typing constraints from the program solving those constraints We’ll describe each of those in more detail. ...

microKanren Reading

4 Jul 2022
tutorials, featured
programming-languages, racket

μ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 Sourcehut. ...

Complete and Liveness, Safe and Sound

2 Mar 2022
programming-languages, computer-science

I have a hard time keeping these terms straight: liveness vs. safety soundness vs. completeness This is intended as a short guide for myself; maybe someone else will find it useful too! Note that this is all to the best of my knowledge and understanding at the present time; if there be faults, they be the faults of myself. I welcome correction and clarification if I am wrong. Liveness vs. Safety # Liveness and safety deal with properties of a system. ...

Mastodon