Lisp in Elixir

lisp.ex

defmodule Lisp do

  @type ast :: [String.t | number | ast]
  @type token :: :lp | :rp | number | String.t

  @letters Enum.concat(?a..?z, ?A..?Z)
  @numbers ?0..?9
  @operators [?+]

  @doc """
  converts a string to a tuple of the first token, followed
  by leftovers in the string
  """
  @spec tokenize(String.t) :: {nil | token, String.t} | :done
  def tokenize(""), do: :done
  def tokenize("(" <> rest), do: {:lp, rest}
  def tokenize(")" <> rest), do: {:rp, rest}
  def tokenize(" " <> rest), do: {nil, rest}
  def tokenize(<<char::8>> <> rest) when char in @letters do
    tokenize_identifier(<<char::8>>, rest)
  end
  def tokenize(<<char::8>> <> rest) when char in @numbers do
    {number_str, rest} = tokenize_number(<<char::8>>, rest)
    {String.to_integer(number_str), rest}
  end
  def tokenize(<<char::8>> <> rest) when char in @operators do
    {<<char::8>>, rest}
  end

  defp tokenize_identifier(letter, <<char::8>> <> rest)
      when char in @letters or char in @numbers do
    {id, rest} = tokenize_identifier(<<char>>, rest)
    {letter <> id, rest}
  end
  defp tokenize_identifier(letter, other) do
    {letter, other}
  end

  defp tokenize_number(digit, <<char::8>> <> rest)
      when char in @numbers do
    {number_str, rest} = tokenize_number(<<char>>, rest)
    {digit <> number_str, rest}
  end
  defp tokenize_number(digit, rest) do
    {digit, rest}
  end

  @doc """
  converts a lisp code program string into a series of tokens.

  Tokens are:
  - parentheses
  - identifiers
  - operators
  - numbers
  """
  def string_to_tokens(string, so_far \\ []) do
    case tokenize(string) do
      # quit when there is nothing left
      :done -> so_far
      {nil, rest} ->
        # ignore spaces
        string_to_tokens(rest, so_far)
      {token, rest} ->
        string_to_tokens(rest, so_far ++ [token])
    end
  end

  @spec parse(program :: String.t) :: ast
  @doc """
  converts a lisp program string into lisp AST.

  raises syntax error when there's a syntax error
  """
  def parse(program) do
    program
    |> string_to_tokens
    |> parse_expr
    |> case do
      {ast, []} -> ast
      _ -> raise "syntax error"
    end
  end

  @spec parse_expr([token]) :: {ast, [token]}
  defp parse_expr([:lp | rest]) do
    parse_list(rest)
  end
  defp parse_expr([string | rest]) when is_binary(string) do
    {string, rest}
  end
  defp parse_expr([number | rest]) when is_number(number) do
    {number, rest}
  end
  defp parse_expr(_), do: raise "syntax error"

  @spec parse_list([token]) :: {ast, [token]}
  defp parse_list(terms, so_far \\ [])
  defp parse_list([:rp | rest], so_far), do: {so_far, rest}
  defp parse_list(expr_andmore, so_far) do
    {expr, rest} = parse_expr(expr_andmore)
    parse_list(rest, so_far ++ [expr])
  end

end

lisp_test.exs

defmodule LispTest do
  use ExUnit.Case

  describe "tokenize tokenizes" do
    test "left-paren" do
      assert {:lp, ""} = Lisp.tokenize("(")
      assert {:lp, " "} = Lisp.tokenize("( ")
      assert {:lp, "foo"} = Lisp.tokenize("(foo")
    end

    test "right-paren" do
      assert {:rp, ""} = Lisp.tokenize(")")
      assert {:rp, " "} = Lisp.tokenize(") ")
    end

    test "spaces are ignored" do
      assert {nil, ""} = Lisp.tokenize(" ")
      assert {nil, " "} = Lisp.tokenize("  ")
    end

    test "identifiers" do
      assert {"foo", ""} = Lisp.tokenize("foo")
      assert {"foo", " "} = Lisp.tokenize("foo ")
      assert {"foo", " bar"} = Lisp.tokenize("foo bar")
      assert {"foo", " 1"} = Lisp.tokenize("foo 1")
      assert {"foo2", ""} = Lisp.tokenize("foo2")
    end

    test "numbers" do
      assert {1, ""} = Lisp.tokenize("1")
      assert {1, " "} = Lisp.tokenize("1 ")
      assert {47, " foo"} = Lisp.tokenize("47 foo")
    end

    test "operators" do
      assert {"+", ""} = Lisp.tokenize("+")
      assert {"+", " "} = Lisp.tokenize("+ ")
      assert {"+", "foo"} = Lisp.tokenize("+foo")
      assert {"+", "47"} = Lisp.tokenize("+47")
    end
  end

  describe "string_to_tokens/1" do
    test "puts together the tokens" do
      assert [:lp, "foo", :rp] == Lisp.string_to_tokens("(foo)")
      assert [:lp, "foo", :rp] == Lisp.string_to_tokens("( foo )")
      assert [:lp, "foo", 47, :rp] == Lisp.string_to_tokens("(foo 47)")
      assert [:lp, "foo47", :rp] == Lisp.string_to_tokens("(foo47)")
    end

    test "syntax errors are not detected" do
      assert [:lp, :lp] == Lisp.string_to_tokens("((")
      assert [:rp, :lp] == Lisp.string_to_tokens(")(")
    end
  end

  describe "when sent through the parser" do
    test "empty list is empty list" do
      assert [] == Lisp.parse("()")
    end

    test "an basic token is a basic token" do
      assert 47 == Lisp.parse("47")
      assert "foo" == Lisp.parse("foo")
      assert "+" == Lisp.parse("+")
    end

    test "lists work" do
      assert [] == Lisp.parse("()")
      assert ["foo", "bar"] == Lisp.parse("(foo bar)")
    end

    test "nested lists work" do
      assert [["foo", "bar"], 3] == Lisp.parse("((foo bar) 3)")
    end

    test "wierd stuff causes syntax error" do
      assert_raise RuntimeError, fn -> Lisp.parse("(()") end
      assert_raise RuntimeError, fn -> Lisp.parse("())") end
      assert_raise RuntimeError, fn -> Lisp.parse("foo bar") end
    end

    test "the example parses" do
      assert ["first", ["list", 1, ["+", 2, 3], 9]] ==
        Lisp.parse("(first (list 1 (+ 2 3) 9))")
    end
  end
end