Pollux, a Toy Programming Language Vaguely Inspired By Lisp and Haskell

<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):

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):

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:

… 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")

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
                                        (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:

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.

comments powered by Disqus