Edit | Discuss | History

Lisp

Appeared in:

1958

Influenced:

Paradigm:

Typing discipline:

Dialects:

Versions and implementations (Collapse all | Expand all):

Programming language

Lisp (“LISt Processing”) is a high-level expression-oriented programming language.

The language was designed in 1958 as a practical mathematical notation for developing programs; its purpose was to show a way to build a Turing-complete language with as few tools as several basic operators and a notation to define functions.

Language design was theoretical one and wasn’t accompanied by language implementation created by its author. First Lisp interpreter that could evaluate Lisp expressions was written in 1959, and first complete Lisp compiler written in Lisp was implemented in 1962.

Since then, Lisp gave birth to lots of dialects, two most popular being Common Lisp and Scheme. Lisp itself has no official standard, but both “Common Lisp” and Scheme have been standardized (in 1994 and 1995, respectively).

Lisp is usually associated with artificial intelligence research, but it is actually a general-purpose language. Despite of being half a century-old, it is widely used in different areas of software development.

Lisp was somewhat influenced by IPL which included concepts of usage of lists and recursion, though in rather primitive form. Lisp was the very first language to use if-then-else control structure in general form of cond operator, and thus all subsequent languages which use it have inherited it from Lisp.

Lisp is homoiconic language: program code is written as a sequence of S-expressions, and the same data structure is used to represent native data structures of the language. S-expression (short for symbolic expression) is a way of representing tree-structured data in readable form. Individual S-expression is either an atom (a single object — number or symbol) or cons pair (x y), where x and y are S-expressions as well. This way each atom is a leaf of a tree, and each cons pair is a node. Most Lisp implementations use somewhat wider definition of expression, allowing expressions to be grouped not only in cons pairs but also in “cons lists” of atoms/expressions enclosed in parentheses. This feature of Lisp allows processing Lisp code in the same way as Lisp data and thus supports metaprogramming paradigm.

So, Lisp expressions are written as lists and use prefix notation: the first element of the list is operator, special operator (i.e., control structure) or function which is applied, and the rest of the list are its arguments (see examples for more details).

Originally Lisp had very few control flow structures, but more were added later, and some could be imitated using provided ones. Thus, if-then-else was provided initially, as an operator which takes three arguments and evaluates to second one if the first one is not nil and to third one otherwise. Loops were not provided initially and were imitated using recursion; later they were added as macros.

Elements of syntax:

Inline comments	;
Nestable comments	#\| ... \|#
Variable assignment	(setq variable value)
Physical (shallow) equality	(eq x y)
Deep equality	(equal x y)
Function definition	(defun f (a b ...) ...)
Function call	(function var1 var2 ... varn)
Function call with no parameters	(function)
Sequence	(progn <exp1> <exp2> ...)
If - then	(if <exp> <code>)
If - then - else	(if <exp> <code> <code>)
Loop forever	(loop <instructions>)
While condition do	(loop while <condition> do <instructions>)
Do until condition	(loop do <instructions> until <condition>)
For each value in a numeric range, 1 increment	(loop for i from <first> upto <last> do <instructions>)
For each value in a numeric range, 1 decrement	(loop for i from <first> downto <last> do <instructions>)

Examples:

Fibonacci numbers:

Example for versions Corman Common Lisp 3.0, SBCL 1.0.1, SBCL 1.0.29, clisp 2.47, gcl 2.6.6

This example uses recursive definition of Fibonacci numbers and expands use of loop macro to finally clause (expression evaluated after the loop is done).

(defun fibonacci (n)
  (if (< n 3)
      1
      (+ (fibonacci (- n 1)) (fibonacci (- n 2))) ) )

(loop for i from 1 to 16
   do (format t "~D, " (fibonacci i))
   finally (format t "...~%") )

Fibonacci numbers:

Example for versions Corman Common Lisp 3.0, clisp 2.47, gcl 2.6.6

This example uses iterative definition of Fibonacci numbers, though expressed through recursive calls of fib-iter.

(defun fibonacci (n)
  (defun fib-iter (a b count)
    (if (zerop count)
	b
	(fib-iter (+ a b) a (- count 1)) ) )
  (fib-iter 1 0 n) )

(loop for i from 1 to 16
   do (format t "~D, " (fibonacci i))
   finally (format t "...~%") )

Hello, World!:

Example for versions Corman Common Lisp 3.0, SBCL 1.0.1, SBCL 1.0.29, clisp 2.47, gcl 2.6.6

When executed in interactive mode, program output looks as follows:

Hello, World!
NIL

First line contains standard output, second — the result of expression evaluation (in this case there is none).

(format t "Hello, World!~%")

Factorial:

Example for versions Corman Common Lisp 3.0, SBCL 1.0.1, SBCL 1.0.29, clisp 2.47, gcl 2.6.6

This example uses recursive factorial definition (which is natural for Lisp). Features:

math operators: (- n 1) is prefix notation equivalent to n-1 in infix notation;
comparison operators: (= n 0) evaluates to T if n is zero, and to nil (used as false) otherwise;
conditional operator if: Lisp expressions are evaluated using brackets, so they can be written in several lines;
function definition using defun;
Common Lisp macro loop;
format specifiers in format: ~D corresponds to printing an integer, and ~% is end-of-line.

(defun factorial (n)
  (if (= n 0)
      1
      (* n (factorial (- n 1))) ) )

(loop for i from 0 to 16
   do (format t "~D! = ~D~%" i (factorial i)) )

Quadratic equation:

Example for versions Corman Common Lisp 3.0, SBCL 1.0.1, SBCL 1.0.29, clisp 2.47, gcl 2.6.6

Common Lisp provides complex numbers as datatype, printed as #C(real imag). write-to-string converts a number into a string.

Note that for interactive evaluation it’s enough to add (quadratic-roots-2 1 0 1) to see the result of calculation, while for compiled execution you’ll have to wrap call of this function in printing command, like (format t (quadratic-roots-2 1 0 1)).

(defun quadratic-roots-2 (A B C)
  (cond ((= A 0) (string "Not a quadratic equation."))
    (t
    (let ((D (- (* B B) (* 4 A C))))
      (cond ((= D 0) (concatenate 'string "x = " (write-to-string (/ (+ (- B) (sqrt D)) (* 2 A)))))
        (t
        (values (concatenate 'string "x1 = " (write-to-string (/ (+ (- B) (sqrt D)) (* 2 A))))
                (concatenate 'string "x2 = " (write-to-string (/ (- (- B) (sqrt D)) (* 2 A)))))))))))

CamelCase:

Example for versions Corman Common Lisp 3.0, SBCL 1.0.1, SBCL 1.0.29, clisp 2.47

(defun camel-case (s)
  (remove #\Space 
          (string-capitalize
           (substitute #\Space nil s :key #'alpha-char-p))))

(princ (camel-case (read-line)))

Factorial:

Example for versions Corman Common Lisp 3.0, SBCL 1.0.1, SBCL 1.0.29, clisp 2.47, gcl 2.6.6

In this example the inner loop with collect clause produces a list of numbers from 1 to n. After this operation * is applied to this list, and the product of the numbers is printed.

(loop for n from 0 to 16
   do (format t "~D! = ~D~%" n 
        (apply '* (loop for i from 1 to n 
                        collect i)) ) )

Hello, World!:

Example for versions JScheme 7.2, MIT/GNU Scheme 7.7.9, guile 1.8.5

Printing a message is a side effect of this command. Depending on the chosen implementation, the command will return either the message printed, or Unspecified return value.

(write "Hello, World!")

Factorial:

Example for versions JScheme 7.2, MIT/GNU Scheme 7.7.9, guile 1.8.5

This example uses tail-recursive factorial calculation. Note that GNU Guile and MIT/GNU Scheme print correct result, while JScheme has values of factorial starting with 13! wrong due to overflow.

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

(do ((i 0 (+ i 1)))
  ((> i 16))
    (display (string-append (number->string i) "! = "))
    (display (number->string (factorial i)))
    (newline))

Fibonacci numbers:

Example for versions JScheme 7.2, MIT/GNU Scheme 7.7.9, guile 1.8.5

This example uses recursive definition of Fibonacci numbers.

(define (fibonacci x)
  (if (< x 2)
    x
    (+ (fibonacci (- x 1)) (fibonacci (- x 2)))))

(do ((i 1 (+ i 1)))
  ((> i 16))
    (display (string-append (number->string (fibonacci i)) ", ")))
(display "...")
(newline)

Quadratic equation:

Example for versions guile 1.8.5

begin is used to execute several commands in row.

(define A (read))
(define B (read))
(define C (read))
(define D (- (* B B) (* 4 A C)))
(if (= A 0)
  (display "Not a quadratic equation.")
  (begin
   (define k1 (/ B -2 A))
   (define k2 (/ (sqrt (abs D)) 2 A))
   (if (= D 0)
    (begin (display "x = ") (display k1))
    (if (> D 0)
      (begin (display "x1 = ") (display (+ k1 k2)) (newline) (display "x2 = ") (display (- k1 k2)))
      (begin (display "x1 = (") (display k1) (display ", ") (display k2) (display ")") (newline)
             (display "x2 = (") (display k1) (display ", ") (display (- k2)) (display ")"))))))

CamelCase:

Example for versions guile 1.8.5

This program shows how to use regular expressions from regex module. First two commands load the necessary modules. The third one reads a line from input stream using read-line command (rdelim module) — unlike plain read, it consumes characters till the end of line, not till the first whitespace — and converts it to lowercase.

The fourth command finds all matches for a regexp which describes a sequence of lowercase letters. Then it replaces each match with a return of a certain function applied to it (bound using lambda). In this case the function is string-titlecase which converts the first character of the string to uppercase.

Finally, the fifth command removes all non-letter characters from the string.

(use-modules (ice-9 regex))
(use-modules (ice-9 rdelim))
(define text (string-downcase (read-line)))
(define text (regexp-substitute/global #f "[a-z]+"  text 'pre (lambda (m) (string-titlecase (match:substring m))) 'post))
(define text (regexp-substitute/global #f "[^a-zA-Z]+"  text 'pre 'post))
(display text)