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.
The λ-calculus is a language with three expression forms:
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)
(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 |
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
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