Lisp List Processing Language

John McCarthy - the creator of Lisp and the basics of artificial intelligence

Lisp is a multi-paradigm language: object-oriented, functional, procedural programming. Appeared in 1958. Author: John McCarthy. Data typing: strong, dynamic. Dialects: Common Lisp (CLOS), Scheme, Arc, Clojure, BEE Lisp, extension languages: AutoLisp and ELisp. Influenced Io, Nemerle, Python, Ruby, Smalltalk, Logo

Lisp (Lisp, from the English List Processing Language - “list processing language”; modern writing: Lisp) is a family of programming languages, programs and data in which are represented by systems of linear lists of symbols. Lisp is the second highest-level programming language used in history (after Fortran). The creator of Lisp, John McCarthy, was engaged in research in the field of artificial intelligence (hereinafter AI) and the language he created is still one of the main tools for modeling various aspects of AI.

Traditional Lisp has a dynamic type system. The language is functional, but many later versions also have features of imperativeness; moreover, having full-fledged means of symbolic processing, it becomes possible to implement object orientation, an example of such an implementation is the CLOS platform.

The Lisp language, along with the Ada language, underwent a process of fundamental standardization for use in military affairs and industry, with the result that the Common Lisp standard appeared. Its implementations exist for most platforms.

One of the basic ideas of Lisp is to represent each character as a node of a multi-coordinate symbol network; at the same time, coordinates, properties, network levels are recorded in the so-called symbol slots. Main slots:

- the name of the symbol (the fundamental Aristotelian A = A from which the lambda calculus grows),

- functional slot,

- slot value

- an expandable list of properties (you can freely expand the slot system in a convenient way to solve the problem).

Lisp is a system programming language for so-called Lisp machines produced in the 1980s, for example, by Symbolics.

Syntax

The main mechanism of Lisp is an encapsulated list that defines the head of the list and the tail of the list attached to it, which can also be a list recursively. A Lisp machine is capable of perceiving every list arriving at it at the most abstract level, for example, as a meta-Lisp machine that modifies a perceiving machine. In such a dynamic, highly abstract environment, it is possible to implement both strictly scientific systems and innumerable programming tricks and generators of various machines.

Any Lisp program consists of a sequence of expressions (forms). The result of the program is to calculate these expressions. All expressions are written as lists — one of the basic structures of Lisp, so they can easily be created by means of the language itself. This allows you to create programs that modify other programs or macros that can significantly expand the capabilities of the language.

Externally, the Lisp source code is distinguished by an abundance of parentheses; Editing programs is greatly simplified by using a text editor that supports automatic code alignment, highlighting corresponding pairs of brackets and special commands such as “close all open brackets”, “go through the list to the right”, etc.

A list is a sequence of elements of any kind, including other lists. For example, (1 3/7 'foo #' +) consists of an integer, a rational fraction, the symbol foo, and a pointer to the addition function. Expressions are represented by lists in a prefix notation: the first element must be a form, that is, a function, an operator, a macro, or a special operator; other elements are arguments of this form that are passed to the form for processing. The list function returns a list of its arguments: for example, (list 1 3/7 'foo #' +) returns the list mentioned earlier. If some elements are expressions, then their value is calculated first: (list 1 2 (list 1 2)) returns (1 2 (1 2)). Arithmetic operators are written according to the same principle, for example (+ 4 (* 2 3)) gives 10.

Special operators allow you to manage the sequence of calculations. With their help, branches and loops are implemented. The if statement allows you to calculate one of two expressions depending on the condition, which is also an expression. If its result is not FALSE (not nil), then the first argument is calculated, otherwise the second one. For example, (if nil (list 1 2 "foo") (list 3 4 "bar")) always returns (3 4 "bar").

Backus-Naur form:

  s_expression :: = atomic_symbol |  "(" s_expression "." s_expression ")" |  list
 list :: = "(" s_expression {s_expression} ")"
 atomic_symbol :: = letter atom_part
 atom_part :: = empty |  letter atom_part |  number atom_part
 letter :: = "a" |  "b" |  "..." |  "z"
 number :: = "1" |  "2" |  "..." |  "9"
 empty :: = ""

Examples

An example of a program that displays the message "Hello, world!":

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

An example of Quine (a program that outputs its source code) to Lisp:

((lambda (x) (list x (list 'quote x)))' (lambda (x) (list x (list 'quote x))))

This program should work in most Lisp dialects, including Scheme.

An iterative version of the function for determining the Nth Fibonacci number using the Loop macro:

  (defun fibonacci (n)
     (loop repeat (+ n 1)
           for a = 1 then b 
           and b = 1 then (+ ab)
           finally (return a)))

Recursive version of the Nth Fibonacci function:

  (defun fibonacci (n)
     (if (or (= n 0) (= n 1))
      one
      (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))

Application

The first applications of Lisp were symbolic data processing and decision-making processes.

Common Lisp, the most popular dialect today, is a universal programming language. It is widely used in various projects: Internet servers and services, application servers and clients interacting with relational and object databases, scientific calculations and game programs.

One of the uses of the Lisp language is to use it as a scripting language that automates the work of a number of application programs:

- Lisp language is used as a scripting language in AutoCAD CAD (AutoLISP dialect);

- its dialect - SKILL - is used to write scripts in the CAD system Virtuoso Platform by Cadence Design Systems;

- Lisp is one of the basic tools of the text editor Emacs (dialect EmacsLISP) [2];

- Lisp is used as a scripting language in the Interleaf / Quicksilver publishing software (Interleaf Lisp dialect);

- In the Sawfish window manager, a special Lisp Rep dialect is used, which largely follows the Emacs Lisp dialect;

- Scheme dialect is used as one of the scripting languages ​​in the Gimp graphics processor;

- GOAL dialect is used for high-dynamic three-dimensional games;

- Lisp can be used to write scripts in Audacity audio editor.

The uses of Lisp are diverse: science and industry, education and medicine, from the decoding of the human genome to the aircraft design system.

Morozov M.N. 10 lectures on Lisp