Lambda Calculus: Represent in Clojure and Elixir

Lambda calculus is the main idea behind functional programming, a complete model for computation. There are a lot of documents and courses about lambda calculus on the Internet, so in this post, I'll not focus on lambda calculus in theory. I'll take a more practical approach - use specific languages to represent lambda expressions. Clojure and Elixir have been chosen due to their coherence and elegance of design.

Introduction

The λ-calculus is a language with three expression forms:

variable reference, e.g., v, foo;
function application, e.g., (f x), (f (g x)); and
function abstraction, e.g., (λ (v) (+ v 1)).

Function abstraction:

All functions of the lambda calculus are anonymous and only take one parameter. For example: λx.e function accepts an argument x and returns the value of e.
In Clojure, we'd write this as:

(fn [x] e)

Function application:

(f e) is the applied function f to e. Function application in Clojure is the same form as a lambda expression:

(f e)

The table below shows some basic lambda terms and equivalent code in Clojure and Elixir:

Lambda term	Clojure	Elixir
λx.x	`(fn [x] x)`	`fn x -> x end`
λx.λy.y	`(fn [x] (fn [y] y))`	`fn x -> (fn y -> y end) end`
(λx.x y)	`((fn [x] x) a)`	`(fn x -> x end).(a)`
(λ f. λ x. f x)	`(fn [f] (fn [x] (f x))`	`fn func -> (fn x -> func.(x) end) end`

More complex Lamda term

Pair

pair = λx. λy. λf. f xy

The pair function takes two arguments x and y and returns a function that contains x and y in its body.
In Clojure, this term is equivalent to:

(def pair (fn [a b]
  (fn [func] (func a b))))

Elixir:

pair = fn (a, b) -> (fn func -> func.(a, b) end) end

Given a pair, we can extract the first and second item using selection functions:
Selection

fst = λx. λy. x
snd = λx. λy. y

These functions take two variables and simply return one of them.
Clojure code:

(def fst (fn [a b] a))
(def snd (fn [a b] b))

((pair 3 5) fst))  ;; => 3
((pair 3 5) snd))  ;; => 5

Similar code in Elixir

fst = fn (a, b) -> a end
snd = fn (a, b) -> b end

pair.(3, 5).(fst)  # => 3
pair.(3, 5).(snd)  # => 5

Function composition

This function takes 2 arguments and returns a function that is the composition of those.

comp = λg. λf. λx. g (f x)

Now we'll write real code to represent comp function and define 2 functions add and subtract for testing. In Clojure:

(def comp
  (fn [f g]
    (fn [x] (f (g x)))))

(def add (fn [n] (+ n 2)))
(def subtract (fn [n] (- n 4)))

((comp add subtract) 8)
;; => 6

The equivalent in Elixir:

comp = fn(g, f) -> (fn x -> f.(g.(x)) end) end
add = fn a -> a + 2 end
subtract = fn a -> a - 4 end

comp.(add, subtract).(8)
# => 6