Doldrums

“You can swim all day in the Sea of Knowledge and not get wet.”

– Norton Juster, The Phantom Tollbooth

About

Doldrums is a small, purely functional programming language with an emphasis on ease of top-to-bottom understanding. It's like a tiny Haskell. It's been a great way for me to learn about Haskell, compilers, parsing, typechecking, runtime evaluation, and more.

The compiler is written in Haskell. Use cabal run doldrums -- tour.dol to run an example program, or cabal run doldrums-test to see what programs are currently working. cabal haddock --open will show the documentation.

There are many examples of working programs in test/expect/*.dol (and expectedly broken ones in test/broken/*.dol).

Structure

Compilation is split into several stages, and the code is split as well. The AST definition of the language lives in the Language module. Parsing happens in Parse, that syntax tree is fixed by FixAst and typechecking happens in Typecheck. The Interpret module actually evaluates the program (if the --compile flag is not on).

The Graphviz module produces visualizations of Expr syntax trees, useful for debugging or inspection. For compilation, STG lowers Doldrums Expr to the spineless tagless G-machine, which is what Haskell does with its Core (before Cmm and LLVM). LLVM produces LLVM IR as text in a .ll file, and links against the runtime.rs Doldrums runtime library.

The execute function in Lib performs each stage of the compilation pipeline. In order, it parses a small prelude (written in Doldrums), reads an input file, parses, typechecks, evaluates, and shows the program's result.

The Doldrums language

Comments

-- Line comments look like this

{- Block comments
   look like this -}

Writing a program

A program is a list of functions. A function has a name, a list of arguments, a body, and optionally a type signature.

id :: a -> a
id x = x

const :: a -> b -> a
const x y = x

Define constants using a "function" with no arguments.

seven :: Int
seven = 7

Every program has a main function. This is what runs when the program starts.

main :: IO ()
main = print $ const 6 7

The $ operator

Because it has the lowest precedence, we can use $ to replace parentheses in certain situations, for cleaner code. For example,

main = f (g (h x))

is equivalent to

main = f $ g $ h x

which is also equivalent to using . for function composition

main = f . g $ h x

Let and where expressions

Define variables to be used in an expression with let...in

let
  n = 0
in n

Multiple definitions are allowed. Thanks to non-strict evaluation, they can be defined "out of order" or even be mutually recursive.

let
  a = 1
  d = c * 2
  b = 2
  c = 3
in
  a - b * c + d

Use the where keyword for definitions that come after an expression.

f = x + y
  where
    x = y * 2
    y = 7

Algebraic datatypes

Introduce user-defined types and values with data declarations. These are "sum of products" algebraic types, allowing type variables.

data Bool = True | False

data List a = Nil | Cons a (List a)

data Either a b = Left a | Right b

deriving clauses are supported for some common typeclasses. They do code generation to write the instance declaration automatically.

data Color = Red | Green | Blue
  deriving (Eq, Ord, Show)

Case expressions

Use case to pattern match on variables, literals, and user-defined constructors. The wildcard pattern _ matches anything. (Note that hanging indentation is supported here, and on other syntax like let binding blocks.)

fib :: Int -> Int
fib n = case n of
  0 -> 1
  1 -> 1
  _ -> fib (n - 1) + fib (n - 2)

Alternatively, use multiple top-level definitions with different pattern matches:

fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

LambdaCase is supported as well. These are equivalent:

f x = case x of ...

f = \case ...

Guards

Guard clauses provide a convenient way to evaluate multiple boolean conditions. otherwise is a synonym for True, defined in the Doldrums Prelude.

abs n :: Num a => a -> a
abs n
  | n > 0 = n
  | n < 0 = -n
  | otherwise = 0

Typeclasses

User-defined typeclasses and instances of those classes are supported. Basic classes like Eq, Ord, Num, Semigroup, and Show come pre-defined in Prelude.dol, with primitive operations supported by the parser and interpreter.

class Equal a where
  eq :: a -> a -> Bool

instance Equal Int where
  eq x y = x == y

instance Equal Bool where
  eq True  True  = True
  eq False False = True
  eq _     _     = False

Constraint syntax allows building typeclass hierarchies and reusing methods on subexpressions.

class Semigroup a => Monoid a where
  mempty :: a

instance Eq a => Eq (Pair a) where
  ...

Lexical negation

For ease of dealing with numeric values, lexical negation is supported.

f -7   -- applies f to negative seven
f - 7  -- subtracts seven from f

List syntax

Square bracket list syntax is supported for expressions, pattern matches, and type signatures. : is equivalent to Cons. The .. syntax allows for list ranges.

[]
(x:xs)
[Int]
[1,3..10]

Records

Record syntax is supported in data declarations, producing accessor functions.

data Person = Person { name :: String, age :: Int }

Record fields can be accessed with OverloadedRecordDot-style dot notation, or with RecordWildCards-style expansions.

somePerson.name
Person{..}

Record update syntax works too:

somePerson { age = age + 1 }

Typed holes

Variable names starting with _ are typed holes. The typechecker will call out their locations and possible types. These can be useful when writing programs as a way to make partial progress.

_
_myTypedHole
x + _y

Backticks for infix functions

Backticks let us use normal prefix functions as infix operators.

x = 10 `mod` 2

Operator sections

Operator sections let us apply any combination of the arguments to an infix operator.

(1+)  -- left
(+1)  -- right
(1+1) -- both
(+)   -- neither

Do notation

Use the do keyword for multi-line expressions that desugar to usage of the (>>=) bind operator.

main :: IO ()
main = do
  putStrLn "Hello, what's your name?"
  name <- getLine
  putStrLn $ "Nice to meet you, " <> name

Main differences from Haskell

• Haskell's String type is a singly-linked linked list of characters ([Char]). Doldrums uses Haskell's Text as its representation for String in the interpreter, and allocates a *const u8 with a specified length in the compiler.
• Haskell has an intermediate language between STG and LLVM called "C minus minus" (Cmm). Doldrums goes straight from STG lowering to LLVM generation.
• Doldrums does not have a garbage collector.
• Doldrums programs are single-threaded.
• Haskell typeclasses use dictionary passing. Doldrums uses "type tags" to decorate each method name.
• The Doldrums runtime is written in Rust.
• In Doldrums' compiled mode, every value is a fixed-length struct. There is no unboxing.
• Doldrums lacks all of Haskell's "advanced" features:
  • type system shenanigans
  • Template Haskell (compile-time metaprogramming)
  • FFI

Parsing

The parser uses Megaparsec and makeExprParser from parser-combinators.

Here's a simplified call graph of the parsing code, showing its structure:

Typechecking

The list of built-in Doldrums types is short: Int, Double, String, Tagged (for user-defined datatypes), TypeVariable, and :-> (the function type).

Prelude.dol defines Bool, Ordering, Unit, Maybe, Either, List, and TupleN (with N from 2 to 5) types.

Doldrums uses Hindley-Milner style type inference to ensure that certain kinds of invalid programs aren't allowed. For example, this program will fail to typecheck:

func x = x + 7

main = func "hello"

So will this one, since integer literals can't be applied as functions:

main = 1 2 3

Operator Fixities

Higher numbers mean higher precedence.

Precedence	Associativity	Operator
10	left	function application
9	right	.
7	left	*
7	left	/
6	left	+
6	left	-
5	right	:
5	right	<>
4	none	==
4	none	/=
4	none	>
4	none	>=
4	none	<
4	none	<=
3	right	&&
2	right	||
0	right	$

Some helpful resources if you want to do something like this

I'd recommend using Megaparsec or another parsing library to make that part easier to write. I learned a lot of this from Implementing Functional Languages: a tutorial. The talk Statically Typed Interpreters was helpful when figuring out how to add the initial typechecking. Some issues were debugged more quickly thanks to help from friends. Algorithm W Step by Step helped me upgrade the typechecking to Hindley-Milner style inference.