From Lisp to Clojure

!

Lisp

  • Inspired by $\lambda$-Calculus
  • Hyper-productive syntax

Clojure

  • Extension to Lisp
  • Supports a slightly richer set of syntactic sugars for readability
  • Runs on JVM

Lisp

Lisp

Lisp

Review of LC

!

Abstraction

$\lambda x. e$

Example:

$\lambda x.\lambda y. x+y$

$\lambda xy. x+y$ (with syntactic abbreviation)

!

Application

$(e_1 e_2)$

Example:

$(((\lambda xy. x+y)\ 1)\ 2)$

$((\lambda xy. x+y)\ 1\ 2)$ (abbreviation)

Observation:

Application is always a list of expressions. The first expression is the function, and the rest of the list is arguments.

Design of Lisp

LISP = LISt Processing


Results:

  1. The entire language only needs one data structure: lists.
  2. Simplicity kicks ass.

From Lisp to Clojure

Simplicity is hard work. But, there’s a huge payoff. The person who has a genuinely simpler system - a system made out of genuinely simple parts, is going to be able to [e]ffect the greatest change with the least work. He’s going to kick your ass. He’s gonna spend more time simplifying things up front and in the long haul he’s gonna wipe the plate with you because he’ll have that ability to change things when you’re struggling to push elephants around.

Rich Hickey, Inventor of Clojure

!

!

Why Clojure?

!

Homoiconic Languages

Every language must support data structures:


Data

Given a language $L$, let $\mathbf{D}(L)$ be all possible data structures that can be represented by the language.

Homoiconic Languages

Every language must support a (sometimes VAST) collection of programming constructs:


Program

Given a language $L$, let $\mathbf{P}(L)$ be all possible (valid) programs that can be constructed in the langauge.

Homoiconic Languages

Definition

!

A language $L$ is homoiconic if:

$$ \mathbf{P}(L) \subseteq \mathbf{D}(L) $$

!

Make sure you understand this property.

It means that a homoiconic language can always digest its own program as data, and treat its data as programs.

Backbone of Lisp: S-expressions

S-expressions can be two things:

  1. Nested lists, or
  2. A completely valid Lisp program.

Atoms:

Atoms are values such as strings, characters, numbers or symbols.

Lists:

A bracket enclosed, whitespace separated list of elements. Each element can be an atom or a list.

S-expression:

A s-exp is a list.

S-expression

s-expr    : '(' expr-list ')'

expr-list : elem expr-list
          | <Empty>

elem      : s-expr
          | <Atom>

! This summarizes the Lisp syntax.

S-expressions as syntax

S-expressions are so simple that designing programming constructs with with becomes obvious.

  • !
  • Declaring a function
  • Declaring a variable (this is done with a more general mechanism known as name binding).
  • Invoking (evaluating) a function with given parameters
  • When a list is just a list
  • Flow control

S-expressions as function declaration

!

Recall in LC:

$$\lambda xyz. \left<\mathrm{expression}\right>$$

Here, we need a function name.

$$\left<\mathrm{name}\right> := \lambda xyz. \left<\mathrm{expression}\right>$$

!

Turning it into a S-expression:

(defun <name> ...)

Treat the parameters as a list

(defun <name> (x y z) <body>)

This approach of encoding function declaration to s-expressions is used by Common Lisp.

Dialects

(define (<name> x y z) <body>

Note the function name is grouped together with the parameters. This approach is used by Racket (formerly known as Scheme).

Name binding

(define PI 3.1415)

Local name bindings

Create a scope with a new nested list:

(let ...)

Create additional “local” variables in the scope:

(let ((x <expression>)
      (y <expression>)) <body>)

! This is the syntax of Common Lisp.

Function invocation

Because this is considered to be the most frequently used programming construct, it is represented simply by a list.

(<name> <expression> <expression> ...)

When a list is just a list

What if we really mean to represent a list of elements?

(quote (<element> <element> ...))

! This suppresses the inner list as function evaluation.

Branching

(if <test> <when-true> <when-false>)

The if start of a list indicates that it is a branching form.

Rolling up the sleeves

Let’s flex the power of simplicity.

  1. We have only been dealing with lists.
  2. Some lists start with distinct names, like define, let, if.
  3. Some nesting of lists needs to be respected, like grouping the parameters as a nested list.

!

Challenge

Compute the factorial of 100.

Rolling up the sleeves

Challenge

Compute the factorial of 100.

!

(define (factorial n)
  (if (< n 2) 
    n 
    (* n (factorial (- n 1)))))

!

Moving on from Lisp to Clojure

Lisp is simple (and thus powerful) in syntax. At the same time, it’s also simple in terms of the data structure it can support. No native support for vectors (dynamic list with random access), hash-maps (associative collections), sets (list without order or multiplicity), …

!

!

Clojure is Lisp:

Clojure faithfully minimizes syntax by sticking with s-expressions for programming constructs, so it remains homoiconic.

!

Clojure extends Lisp:

It adds more syntax (YES…) to support a richer data constructors for vectors, hash-map etc… It also support even more succinct definition of functions.

Clojure at a glance

(defn f [n] (if (< n 2) n (* n (f (dec n)))))

! The dec function decreases an integer by 1. You might want to know about bigint function which converts an integer to a BigInteger, when computing the value (f 100).

Clojure at a glance

(import java.util.Vector)
(let [v (java.util.Vector. (quote (1 2 "blah")))]
  (println "Last element =" (.lastElement v)))

! Wow, we are converting a Lisp list (1 2 "blah") to a Java vector object, and using the method java.util.Vector.lastElement to access the last element. … And we are still just using nested lists.

Looking ahead

Summary

!

back
© KEN PU, 2016