✓ From Lambda Calculus To Lisp

About the syntax of LC

Syntax is minimal

  • Application with multiple parameters: \((f a b c)\)

  • Abstraction of functions with multiple arguments: \(\lambda x.\lambda y.\lambda z. \dots\)

LC expressions are nested lists of names and \(\lambda\)

  • Names are elements

  • Applications are lists starting with a name:

    (f a b c)

  • Abstractions are lists starting with a \(\lambda\):

    (𝜆 (x y z) (...))

Fact

All of LC expressions can be represented as nested lists.

Rewriting rules

So, \(\alpha\)-conversion, \(\beta\)- and \(\eta\)-reduction are transformations of lists. Since, these rules are proven to be Turing-complete, we can perform arbitrary computation by just processing nested lists.

List Processing = Lisp

Introducing Clojure

About Clojure

  • The language is a Java Virtual Machine (JVM) backed Lisp language.

  • Clojure comes data values and data structures.

  • Clojure programs are LC expressions, and the execution model is based on LC rewriting rules.

  • Clojure binds expression to symbols that can be reused and can be recursive.

  • Clojure has advanced and modern computational models: asynchronous, concurrent and modular programming

Note

Clojure is a practical language.

From LC to Clojure

  • LC names are symbols.

  • Abstractions are function declarations (with possible recursion).

  • Applications are function invocations.

  • Programming constructs are called forms in Clojure.

Names are symbols

  • Clojure has very genereously relaxed convention for symbol names.

  • x, y, z, x', last-name, :x:, 𝜋, +, \(\dots\)

Function declaration form

  • \(\lambda\) becomes the keyword fn

  • Parameters are enclosed in [ ... ]

\[ \lambda x.\lambda y.\lambda z. \left<\mathrm{body}\right> \]
\[ \downarrow \]
\[ \underbrace{\lambda}_{\mathrm{fn}} \underbrace{x.y.z.}_{\mathrm{[x\ y\ z]}} \left<\mathrm{body}\right> \]

So, function declaration is:

(fn [...] body)

Function invocation form

  • Clojure copies LC exactly for function invocation.

(func-expression arguments...)

A Hello World in Clojure

  • println is a function with variadic arity.

  • All arguments are converted to strings.

  • The function prints the arguments with space separation.

(println "Hello" "World")
Hello World
nil

Greeting in Clojure

We can define a function that outputs a message with a greeting prefix.

(fn [message] (println "Hi there," message))
#function[user/eval3980/fn--3981]

We can use the function in a function invocation form.

((fn [message] (println "Hi there," message)) "my name is Ken.")
Hi there, my name is Ken.
nil

Be kind to your readers and learn about smart ways of indenting Clojure code.

  • Whitespace doesn’t matter

  • ; is the comment character

((fn [x]
     ; x is the message
     (println "Hi there," x))
  "my name is Ken.")
Hi there, my name is Ken.
nil

Symbol binding

We will talk a lot more about symbol bindings in Clojure, but for now, we will focus on the top-level symbol binding form:

(def <name> <value>)
(def greet (fn [x] (println "Hi there," x)))
#'user/greet

Now, we can use the function.

(greet "my name is Ken.")
Hi there, my name is Ken.
nil