<q66> everyone should have their toy lisp

I’ve somehow managed to get bored enough to implement a programming language. It’s inspired by Haskell where all the functions are curried, and also inspired by Lisp because it, um, has a lot of parentheses (also the interpreter design is in the classic Lisp eval-apply style).

The language is called Pollux (clicky for GitHub link), which was the first word that came to mind when I thought of “point-free”, and the language encourages a lot of point-free style, so I guess that’s okay.

Here are some of the features of Pollux that make it distinctly a perversion of Lisp (and Haskell):

• Functions have a fixed arity and are curried. For instance, x -> y -> x has an arity of two (the arguments x and y) and returns the first argument (x).

• No special forms (and no implicit “unevaluated arguments” like Lisp macros).

The following is a brain-dump of sorts regarding some of the features.

if-then-else Combinator

Since there are no special forms, conditionals are a bit wonky to handle. For instance, if we had and if-then-else function that took three arguments: we’ll call these p, t, f — hopefully you’ll be able to figure out what they mean.

(if-then-else (== x 1)
              (print "true")
              (print "false"))

Pollux doesn’t have unevaluated arguments, so both the branches will be executed (resulting in truefalse being printed):

• if-then-else is evaluated, causing its arguments to be applied.

• print is applied to "true", resulting true to be printed to the screen.

• print is applied to "false", resulting false to be printed to the screen.

• Oops.

However, we can make use of lambda functions to avoid evaluating arguments (or quoted expressions, but they’re not nearly as cool for a reason you’re going to see soon):

(if-then-else (_ -> == x 1)
              (_ -> print "true")
              (_ -> print "false"))

Now we can write a suitable implementation of if-then-else that’s guaranteed to only execute one of the two branches:

• if-then-else is evaluated, causing its arguments to be applied.

• The lambdas are evaluated in the environment but aren’t executed yet.

• We can then check if the first condition is true, then pick a branch to execute.

• Yay!

… though now it seems a bit silly to an unused argument for each of the lambdas. What about:

(if-then-else (== 1)
              (_ -> print "true")
              (_ -> print "false")
              x)

Pollux’s function calls are curried, so (== 1) is going to return a closure that compares a value against 1. We can also pass the value of x to the true and false branches. In this example, the benefits aren’t immediately obvious, but…:

; These functions aren't very exciting, but are kind of interesting, I guess.
(let! 'id (x -> x))
(let! 'const (x -> y -> x))
(let! 'flip (f -> x -> y -> f y x))

(let! 'filter (p -> foldr (if-then-else p
                                        cons
                                        (const id))
                          []))

(filter ((flip <) 3) [1 2 3 4 5 6]) ; returns [1 2]

This is an implementation of filter, which walks through a list and returns only the values that return true. There’s a fair bit of magic functions here, which I’m going to explain:

• foldr is a right-reduction of a list. I explained its left analog, foldl, in a previous article, and its semantics are roughly similar, with the exception that the fold proceeds from the right end of the list to the left, and the accumulator function has its arguments swapped (x -> acc instead of acc -> x).

• cons creates a list with two arguments: the head of the list and the rest of the list.

• const takes an argument and returns a “constant generation function”, e.g. for all values of y, (const 1 y) will always return 1.

• id just returns the argument it’s passed.

With that in mind, we can see how if-then-else lets us write stupidly cute point-free code. The filter function proceeds from the right of the list, checks if the current value is true when applied to p — if it is, then we append it to the accumulator, otherwise we keep the accumulator and — hey, that’s what we’re doing, but in stupidly point-free style!

AST Nodes as Types

Pollux doesn’t differentiate between AST nodes and value types. There are only a few fundamental AST nodes (functions, applications, symbols, various literals) which can be directly operated upon as values. The parser directly generates code objects, which are also data objects, which leads on to…

Kind-of Not Really Homoiconicity

This is a somewhat Lisp-y trait: all code is data. However, Pollux doesn’t really have S-expressions since a function placed adjacent to a value is just regarded as function application with no way to manipulate the expression. While Pollux does have quote/unquote, it’s not really that useful (presently only used to pass unevaluated symbol names to let!), but could probably be made better with a function manipulates quoted function applications.

Other Things on the Todo List

Conditions (nor exceptions) haven’t been implemented so if something goes wrong, a Python exception is thrown and everything just aborts. An actual type system should probably be implemented (with structs and stuff). call-with-current-continuation is a cool idea but I don’t know if I care enough about it.

Ending Remarks

Pollux is a silly toy language that I just wanted to get out of my head — determining whether it works well or not is an exercise for the reader, but I’d just like to post this article to get an opinion of what people might think of it — feel free to fork it on GitHub or take a gander at its source code.