# 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)))

;; => 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