Make a what?

Defining Lisp could be a long blog post in and of itself so for brevity…

Lisps are a family of programming languages / dialects that have a long history dating back the late 1950s. LISP is ancient in computer programming terms. The original idea of a LISP was part of a 1958 paper by John McCarthy and there is an implementation of LISP 1 from 1960 so we’re talking about as old as Fortran and COBOL.

Lisps are quite different from the typical C-style of programming languages but they have certain strengths and weakness over those languages too. Having another way to think about programming can’t hurt. There are many different implementations of Lisp, Clojure, Scheme, Common Lisp but they all have some common characteristics.

Lisps:

• have a very concise syntax
• use a prefix notation not infix
• are dynamically typed
• represent code as a native data structure - homoiconicity

# This is sudo code and # is supposed to be a comment 
# prefix notation means the operation comes first
# so addition looks like this

(+ 1 2 3 4) => 10

# interestingly + here isn’t an operator 
# like in C or Java but a function call
# an open paren marks the startof a function call so 
# finding the minimum number would look like this

(min 1 2 3 4) => 1

# Lisps use a similar syntax for data structures 
# a list in Lisp looks like this where ` specifies that the
# open parenthesis is a data structure not a function call

`(1 2 3 4 5) => (1 2 3 4 5)

Why make a Lisp?

So… I’ve wanted to do this for a while. I’ve actually started a couple of times in the past. However I’ve never seen an attempt through to completion. Building a little Lisp of my own as a learning exercise has always seemed the right kind of interesting.

I blame Clojure for this interest. Clojure changed the way I approach programming. Clojure strikes a great balance of pragmatism, using the JVM as a foundation to build an elegant functional language on top of. My Clojure experience left me interested in Lisps in general. Lisps are so syntactically simple that parsing them should be pretty straightforward right?

What makes you think you’ll finish this time?

Frankly I don’t know if I will but I’m going to document my journey this time and see how it goes. I’ve recently joined a team that mostly use Java and I thought this exercise would be a good way to revamp my Java knowledge / workflow.

Despite Java being the first “real” programming language I learnt, many, many years ago at University, I haven’t actually worked with the Java language that much. I’ve used the JVM a fair bit, two year long Clojure projects and another in Scala so I’m familiar with some parts of the eco system. I’d like to be able to say at the end of this project I’m confident with using modern Java features and tools.

Java has a reputation of being slow moving and extremely backwards compatible. Even the Java code I wrote during my CS degree should still work on the later JVMs. I haven’t really kept up-to-date with whats available in Java since… checks notes Java 1.6 so I’m keen to push for more exposure to newer language features.

Now I’m aware a lot of changes happened in Java 8. I’m most curious about Java’s Steams and how they might be a more functional way to write idiomatic Java. I’m also keen to try out lambdas and see what else I bump into along the way, a friend once described Java Optionals as sudo monads so maybe I’ll get to play with those… :-)

As for tools I’m going to be quite boring and use Gradle to do most of the heavy lifting. It is the build tool my team is using. This’ll be a two for one, learning / reinforcement of what I’m using in my day to day. I’m also going to try and TDD where it makes sense for this exercise.

How does one make a Lisp anyway?

Good question. In theory you could probably hack something together pretty quickly. The syntax of a Lisp is very lightweight so parsing should be a doddle. Most Lisps embrace using a REPL, (read, evaluate, print, loop) for development which means you can get very quick feedback while coding. It also means one can quickly get feedback on how the Lisp behaves without needing to move past an interpreter.

So I want to build a fairly simple system that takes input from the command line, parses it, then evaluates it and prints to standard out. This will be less work than compiling that input and outputting a standalone executable. Although it would be a great step toward building a complier… Maybe later? :-)

I’m going to use the MAL – make a Lisp project to help me. The project describes itself; “Mal is a Clojure inspired Lisp interpreter”, perfect! The project looks like a really helpful tool. MAL is also a learning too so it is intentionally designed for what I want to do.

Developing a Lisp with MAL is split into a series of 11 sequential stages with clearly defined end goals so while working I’ll be able to focus on a small part at a time.

There is also an extensive looking test suite for the project. The tests execute your Lisp via standard input and verify what is returned. There are already 82 separate language implementations of MAL all in the same repo. While I don’t want to copy from someone else it will be nice to know I can take a look at other folks approach to solving the same problems.

So why are you writing this?

Hopefully someone will find it interesting. ¯_(ツ)_/¯

Mostly to document somewhere what I did / learned and also keep myself accountable.

MAL Step 0 - Sticks and glue.

Okay, while I’m very excited to jump right in to building, step zero is mostly a series of house keeping tasks. That extensive test suite I mentioned is designed to work via Standard In / Standard Out which keeps the tests implementation and language agnostic. The first task is to do the legwork to enable the MAL project tools to build and run my Lisp implementation.

MAL uses a Makefile to run build and run the tests against a target implementation. Okay. I’ve used make files before but only very basic ones and, again, not since university. I know that Make is build tool like Gradle, SBT, Lein or whatever the cool kids are using in the Javascript world these days. Fun tangent the ruby tool rake is named because it is make for ruby or ruby-make -> rake.

However, knowing that doesn’t give me much to go on… I’m off to experiment a bit and find a crash course on make files.

some time later…

Okay I’ve set up my own little Lisp implementation skeleton. I’ve started with the following:

• I’ve created a new project, myjava - no points for original naming - via gradle init to generate an empty Java project with a sensible layout and basic dependancies included.
• I’ve added my new implementation / directory to the MAL Makefile like below:

# add my implementation to MAL 
IMPLS = … myjava …
# when I invoke the make file so:
# make "test^myjava^step0" 
# this line makes the following call to my own Makefile. Meta!
# make -C impls/myjava step0_repl 
myjava_STEP_TO_PROG =  impls/myjava/$($(1))

• Alongside my empty Java project I’ve created a Makefile for building the project. When the MAL Makefile is ran for a specific step it delegates to my own Makefile. My own Makefile delegates to gradle.

# this means match any input starting with step
step%:
	@echo "Building step: $@"
	@./gradlew build

• I’ve created a run script, which will be called when running the MAL test suite

#!/bin/bash

set -exo pipefail
# run the project and pass the target step as a command line argument 
exec ./gradlew run -q --console=plain --args="${STEP:-stepA_mal}" "${@}"

And that is all the project glue wired up! 🥳🥳🥳🥳🥳🥳

Okay now we can write a little bit of Java! To finish step Zero I need to build the start of a project REPL, read, evaluate, print, loop. I need to print a user prompt, read any input then print that input to stdout. When the user closes standard in the application should exit cleanly.

Awesome, so in the past I remember using Buffered Input Readers to read from stdin however nowadays Java provides a Scanner class to make reading lines of input easier. It also respects when standard input is closed such as a user pressing ctrl d.

// Easy!
Scanner scanner = new Scanner(System.in);
String line = scanner.nextLine();

The rest of the code can be found here if you’re curious but Scanner was they only interesting Java thing so far. :) Finally running the step zero tests and seeing it come together!

~> make "test^myjava^step0"

make -C impls/myjava step0_repl
Building step: step0_repl

BUILD SUCCESSFUL in 619ms

Testing test^myjava^step0; 

Started with:
+ exec ./gradlew run -q --console=plain --args=step0_repl
Welcome to MAL.

Testing basic string
TEST: 'abcABC123' -> ['',abcABC123] -> SUCCESS
Testing string containing spaces
TEST: 'hello mal world' -> ['',hello mal world] -> SUCCESS
Testing string containing symbols
TEST: '[]{}"\'* ;:()' -> ['',[]{}"'* ;:()] -> SUCCESS

… more tests here … 

TEST RESULTS (for ../tests/step0_repl.mal):
    0: soft failing tests
    0: failing tests
   24: passing tests
   24: total tests 

Yay!!! All the leg work is done and I have a basic REPL built! That concludes Step Zero of my journey through Making a Lisp with MAL. It was an interesting start and I’m glad I did it. Going forward with a prebuilt test suit will make my life much easier. Having the tests passing brings a smile to my face! :-)

Next time STEP 1: Reading and Printing

Thanks for reading!