Lisp - a syntax free programming language

Extensions to $\lambda$-Calculus

• $\lambda$-calculus is all about syntax.

  • names are expressions

  • $(f\ e_2)$ is an expression

    where $f$ is the function expression, and $e_2$ is the argument.

  • $\lambda x.\ e$ is an expression

• Generalize $\lambda$-calculus to support multiple arguments.

  • We can apply functions with multiple arguments:

    $(f\ e_1\ e_2\ e_3\ \dots)$

  • We can also extend the $\lambda$ notation with multiple argument names.

    $\lambda x.y.z.\ \dots$

Lists

• Lists are a really simple data structure:

  • A list of integers: (1,2,3,4)
  • A list of strings: ("hello", "world", "again")
  • Lists can be nested and heterogeneous: (1, 2, ("hello", "world"), 3, 4)

• $\lambda$-calculus expressions are (nested) lists!

  $\lambda$-calculus	List representation
  $(+\ 1\ 2\ 3)$	(+ 1 2 3)
  $\lambda x.y.\ (+\ x\ y\ 10)$	($\lambda$ (x y) (+ x y 10))

• Code can be expressed as lists.

  • $\lambda$-calculus is Turing Complete.
  • $\lambda$-calculus can be encoded as lists.

  ---

  Therefore:

  • Any code can be expressed as lists.

Lisp

• Lisp (list-processing) is one of the oldest programming language designed to rely on list-based representation of $\lambda$-calculus.

• Expressions are exclusively expressed as nested lists.

  split=8

  (define (fibo n) 
    (cond ((= n 0) 1)
          ((= n 1) 1)
          (true (+ (fibo (- n 1) (fibo (- n 2)))))))
  

  Look: there is no syntax - just nested lists.

  This is valid Racket code.

The magic of Lisp

• Learning a Lisp-based language requires:

  1. Little time to learn the syntax. Learning syntax is fun, but often does not yield immediate productivity.

  2. A lot more times to learn the semantics of functions. Learning what functions are available leads to productivity immediately.

• Lisp code is data.

  box

  Definition: Homoiconic languages

  Suppose that a programming language $L$ can describe data as well as code. Let $L^\mathrm{data}$ be the sub-language that describes data. We say that $L$ is homoiconic if all programs in $L$ can be described by $L^\mathrm{data}$.

• Programming Languages

  box

  Generally speaking $$ L = L^\mathrm{code} \cup L^\mathrm{data} $$

  Homoiconic languages have the property of: $$ L\subseteq L^\mathrm{data}$$

  Therefore:

  $$ L = L^\mathrm{data} $$

• Macros

  We can generate lisp code easily programmatically. So, Lisp code can generate Lisp code. This leads to the possibility of macro programming.

About Clojure

• Clojure is a Lisp.

  Clojure is a homoiconic dialet of Lisp. It provides a rich set of data structures going well beyond nested lists.

• Clojure is Java.

  Clojure runs on top of the Java Virtual Machine (JVM). Clojure code is compiled into JVM bytecode, and can interoperate with Java code natively.

• Clojure is industrial.

  Many companies rely on Clojure in production.