9 files changed, 197 insertions, 0 deletions
diff --git a/elixir/.formatter.exs b/elixir/.formatter.exs
new file mode 100644
index 0000000..d2cda26
--- /dev/null
+++ b/elixir/.formatter.exs
@@ -0,0 +1,4 @@
+# Used by "mix format"
+[
+  inputs: ["{mix,.formatter}.exs", "{config,lib,test}/**/*.{ex,exs}"]
+]
diff --git a/elixir/.gitignore b/elixir/.gitignore
new file mode 100644
index 0000000..12fd196
--- /dev/null
+++ b/elixir/.gitignore
@@ -0,0 +1,26 @@
+# The directory Mix will write compiled artifacts to.
+/_build/
+
+# If you run "mix test --cover", coverage assets end up here.
+/cover/
+
+# The directory Mix downloads your dependencies sources to.
+/deps/
+
+# Where third-party dependencies like ExDoc output generated docs.
+/doc/
+
+# Ignore .fetch files in case you like to edit your project deps locally.
+/.fetch
+
+# If the VM crashes, it generates a dump, let's ignore it too.
+erl_crash.dump
+
+# Also ignore archive artifacts (built via "mix archive.build").
+*.ez
+
+# Ignore package tarball (built via "mix hex.build").
+workshop1-*.tar
+
+# Temporary files, for example, from tests.
+/tmp/
diff --git a/elixir/README.md b/elixir/README.md
new file mode 100644
index 0000000..fe5b773
--- /dev/null
+++ b/elixir/README.md
@@ -0,0 +1,21 @@
+# Workshop1
+
+**TODO: Add description**
+
+## Installation
+
+If [available in Hex](https://hex.pm/docs/publish), the package can be installed
+by adding `workshop1` to your list of dependencies in `mix.exs`:
+
+```elixir
+def deps do
+  [
+    {:workshop1, "~> 0.1.0"}
+  ]
+end
+```
+
+Documentation can be generated with [ExDoc](https://github.com/elixir-lang/ex_doc)
+and published on [HexDocs](https://hexdocs.pm). Once published, the docs can
+be found at <https://hexdocs.pm/workshop1>.
+
diff --git a/elixir/ast.ex b/elixir/ast.ex
new file mode 100644
index 0000000..4305b7b
--- /dev/null
+++ b/elixir/ast.ex
@@ -0,0 +1,34 @@
+defmodule Ast do
+  def var(name), do: {:var, name}
+  def abs(param, body), do: {:abs, param, body}
+  def app(func, param), do: {:app, func, param}
+
+  def pprint(expr) do
+    case expr do
+      {:var, name} -> name
+      {:abs, param, body} -> "(λ #{param} . #{pprint(body)})"
+      {:app, func, param} -> "#{pprint(func)} #{pprint(param)}"
+    end
+  end
+
+  def free_vars(expr) do
+    case expr do
+      {:var, name} -> MapSet.new([name])
+      {:abs, param, body} -> MapSet.delete(free_vars(body), param)
+      {:app, func, param} -> MapSet.union(free_vars(func), free_vars(param))
+    end
+  end
+
+  def subst(expr, old_var, new_expr) do
+    case expr do
+      {:var, name} ->
+        if name == old_var, do: new_expr, else: expr
+
+      {:abs, param, body} ->
+        if param == old_var, do: expr, else: {:abs, param, subst(body, old_var, new_expr)}
+
+      {:app, func, param} ->
+        {:app, subst(func, old_var, new_expr), subst(param, old_var, new_expr)}
+    end
+  end
+end
diff --git a/elixir/ast_test.exs b/elixir/ast_test.exs
new file mode 100644
index 0000000..b10c959
--- /dev/null
+++ b/elixir/ast_test.exs
@@ -0,0 +1,70 @@
+defmodule AstTest do
+  use ExUnit.Case
+
+  test "pprint/1" do
+    assert Ast.pprint(Ast.var("x")) == "x"
+    assert Ast.pprint(Ast.abs("x", Ast.var("x"))) == "(λ x . x)"
+    assert Ast.pprint(Ast.app(Ast.var("x"), Ast.var("y"))) == "x y"
+  end
+
+  test "pprint with if expression lambda calculus" do
+    assert Ast.pprint(Ast.abs("f", Ast.abs("y", Ast.app(Ast.var("f"), Ast.var("x"))))) ==
+             "(λ f . (λ y . f x))"
+  end
+
+  test "free_vars-1" do
+    program = Ast.var("x")
+    expected = MapSet.new(["x"])
+    repr_expected = "x"
+    repr_subs_expected = "y"
+
+    assert MapSet.equal?(Ast.free_vars(program), expected)
+    assert Ast.pprint(program) == repr_expected
+
+    assert Ast.pprint(Ast.subst(program, "x", Ast.var("y"))) == repr_subs_expected
+  end
+
+  test "free_vars-2" do
+    program = Ast.abs("x", Ast.var("x"))
+    expected = MapSet.new([])
+    repr_expected = "(λ x . x)"
+    repr_subs_expected = "(λ x . x)"
+
+    assert MapSet.equal?(Ast.free_vars(program), expected)
+    assert Ast.pprint(program) == repr_expected
+
+    assert Ast.pprint(Ast.subst(program, "x", Ast.var("y"))) == repr_subs_expected
+  end
+
+  test "free_vars-3" do
+    program = Ast.app(Ast.var("f"), Ast.var("x"))
+    expected = MapSet.new(["f", "x"])
+    repr_expected = "f x"
+
+    assert MapSet.equal?(Ast.free_vars(program), expected)
+    assert Ast.pprint(program) == repr_expected
+  end
+
+  test "free_vars-4" do
+    program =
+      Ast.abs(
+        "f",
+        Ast.app(Ast.var("x"), Ast.abs("x", Ast.app(Ast.var("f"), Ast.var("x"))))
+      )
+
+    expected = MapSet.new(["x"])
+    repr_expected = "(λ f . x (λ x . f x))"
+
+    assert MapSet.equal?(Ast.free_vars(program), expected)
+    assert Ast.pprint(program) == repr_expected
+  end
+
+  test "free_vars-5" do
+    program = Ast.abs("f", Ast.abs("y", Ast.app(Ast.var("f"), Ast.var("x"))))
+    expected = MapSet.new(["x"])
+    repr_expected = "(λ f . (λ y . f x))"
+
+    assert MapSet.equal?(Ast.free_vars(program), expected)
+    assert Ast.pprint(program) == repr_expected
+  end
+end
diff --git a/elixir/mix.exs b/elixir/mix.exs
new file mode 100644
index 0000000..df46a80
--- /dev/null
+++ b/elixir/mix.exs
@@ -0,0 +1,28 @@
+defmodule Workshop1.MixProject do
+  use Mix.Project
+
+  def project do
+    [
+      app: :workshop1,
+      version: "0.1.0",
+      elixir: "~> 1.17",
+      start_permanent: Mix.env() == :prod,
+      deps: deps()
+    ]
+  end
+
+  # Run "mix help compile.app" to learn about applications.
+  def application do
+    [
+      extra_applications: [:logger]
+    ]
+  end
+
+  # Run "mix help deps" to learn about dependencies.
+  defp deps do
+    [
+      # {:dep_from_hexpm, "~> 0.3.0"},
+      # {:dep_from_git, git: "https://github.com/elixir-lang/my_dep.git", tag: "0.1.0"}
+    ]
+  end
+end
diff --git a/elixir/test_helper.exs b/elixir/test_helper.exs
new file mode 100644
index 0000000..869559e
--- /dev/null
+++ b/elixir/test_helper.exs
@@ -0,0 +1 @@
+ExUnit.start()
diff --git a/elixir/workshop1.ex b/elixir/workshop1.ex
new file mode 100644
index 0000000..caf85d7
--- /dev/null
+++ b/elixir/workshop1.ex
@@ -0,0 +1,5 @@
+defmodule Workshop1 do
+  def hello do
+    :world
+  end
+end
diff --git a/elixir/workshop1_test.exs b/elixir/workshop1_test.exs
new file mode 100644
index 0000000..f0b4603
--- /dev/null
+++ b/elixir/workshop1_test.exs
@@ -0,0 +1,8 @@
+defmodule Workshop1Test do
+  use ExUnit.Case
+  doctest Workshop1
+
+  test "greets the world" do
+    assert Workshop1.hello() == :world
+  end
+end