1 of 34

Write yourself a compiler in Clojure: Dhall edition

Fabrizio Ferrai

​

@fabferrai

2 of 34

3 of 34

Let’s use Dhall to make something

Let’s talk about Dhall

Let’s talk about a Dhall compiler

Small FP Talk

META

META META TODAY

4 of 34

Story of me learning that making a compiler is not that bad

5 of 34

Dhall

JSON

  • Types
  • Imports
  • Functions

Functional, non-Turing-complete, strongly typed language

6 of 34

Not-Turing-Complete is a feature

Data Code

Turing

Completeness

Border

Dhall

Abstraction power

.

Dangers:

- Security

- Bad abstraction

- Non-termination

7 of 34

What is this useful for

“Like, it’s another language, better be revolutionary”

  • typed configurations: your configuration in a precise type
  • templating: template things in a sane but powerful way
  • send code on the wire in safe and efficient way
    1. safe because the language is not Turing complete
    2. efficient because defines binary encoding to serialize/deserialize

8 of 34

Can I try it?

dhall-lang.org

Install the “dhall” cli

NEW: Clojars → [dhall-clj “0.2.0”]

9 of 34

dhall-lang.org

10 of 34

Poll:

Dhall tutorial now or later?

11 of 34

Dhall shines when native in langs

​

​

Problem: no integrations yet

(only Haskell)

12 of 34

“Alright, I’ll make one for Clojure”

13 of 34

Great news #1

​

There is a Language Standard!

​

​

(this is actually not common, reasons later)

14 of 34

Great news #2

​

The language is tiny, so implementing it looked easy

​

(turns out this pretty much holds)

15 of 34

..6 months later

16 of 34

f-f/dhall-clj

17 of 34

Making a compiler in Clojure is fun+easy+useful

Why?

  • Somewhat restricted problem, “closed universe”
  • Great example where sane design is paramount
  • Best place to apply TDD
  • Really nice to manipulate data-structures in Clj
  • Helps to understand why/how the tools work

18 of 34

I almost forgot the definition

(sorry Rich!)

19 of 34

20 of 34

Compiler definition is a bit broader now

Generically “source string to executable”

​

See also “transpiler”

→ “source string to other language source string”

21 of 34

String → Executable

Cannot do it in one shot, as e.g. gcc realized

Compilers should be modular and make use of “phases”

And often different representations of ASTs

→ ~ “more types” is “good”

22 of 34

Source: The ClojureScript Compiler - A Look Behind the Curtains - Maria Geller

​

CLJS

23 of 34

https://blog.rust-lang.org/2016/04/19/MIR.html

Rust

24 of 34

https://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/HscPipe

Haskell (GHC)

25 of 34

Dhall Compiler Phases

Parse

Resolve Imports

Typecheck

Normalize

Emit

Source

AST

Import-free AST

Clojure data/code

Valid AST

Evaluated AST

MOST IMPORTANT SLIDE

26 of 34

DEMO

​

Let’s compile some Dhall

and go through the phases

27 of 34

Takeaways

28 of 34

Instaparse is really great and unique

github.com/Engelberg/instaparse

​

Main reason for quick bootstrap

​

Dhall grammar ~700 LOC

29 of 34

Maintainability needs super much attention

  • Dynamic typing, hard to:
    • Refactor - names, keywords, macros...
    • Keep track of data-structures flowing through phases
  • 100% test coverage is a MUST to know we don’t break stuff
    • Untested → Broken.
  • DO DIFFERENT KINDS OF TESTS
    • Mostly single-phase tests (“integration tests”?)
    • Property-based testing for serialization/deserialization
    • End-to-end testing can never be enough

30 of 34

Having a Language Standard is NICE a

  • For Dhall it’s composed by:
    • Grammar
    • Logic rules for transformations
    • Informal specification
    • Acceptance tests
  • TDD is natural and actually pleasurable here
  • Insight: not all languages can/should have specs
    • Tradeoff between speed and correctness (as usual?)
    • Standards fossilize innovation in general
    • Standards provide assurance on behaviour and replicability
    • Also reduce “vendor lock-in”

31 of 34

Making a (typed) language is not that hard

As in: there’s no special magic

Rough TODO list:

  • Make a grammar
  • Define you AST
  • Do you want a typechecker? Pick a typesystem
  • Read up on lambda calculus and dependent types: andres-loeh.de/LambdaPi
  • Define how you’re going to reduce/execute/normalize

32 of 34

Things to remember

Making a compiler in Clojure is nice

Dhall is awesome

Language Standards are really nice

100% test coverage is necessary*

More maintainability, less pasta!

*for compilers at least. Your PM might not agree :)

33 of 34

Thanks! Questions?

​

​

@fabferrai

f-f

github.com/f-f/dhall-clj

github.com/dhall-lang/dhall-lang

dhall-lang.org

34 of 34

More links

en.wikipedia.org/wiki/Lambda_calculus

andres-loeh.de/LambdaPi

youtube.com/watch?v=Elg17s_nwDg

github.com/Engelberg/instaparse