Lisp

Lisp (historically LISP) is a family of multi-paradigm type computer programming languages with a long history and an unmistakable and useful homo-iconic syntax based on Polish notation.

Originally developed in 1959 by John McCarthy and his collaborators at the Massachusetts Institute of Technology, Lisp is the second oldest high-level programming language; it appeared a year after FORTRAN and a year before COBOL.

Like COBOL and FORTRAN, Lisp has changed a lot since its inception, and there have been a number of dialects throughout its history. Today, the most widely used Lisp dialects are Scheme (1975), Common Lisp (1984), Emacs Lisp (1985), and Clojure (2007).

Lisp was originally created as a handy mathematical notation for computer programs, based on Alonzo Church's lambda calculus. It quickly became the programming language of choice in artificial intelligence (AI) research. As precursor programming languages, Lisp pioneered many ideas in computer science, including tree data structures, automatic storage management, dynamic types, and the self-contained compiler.

The acronym LISP stands for "LISt Processor" ('List Processing'). Chained lists are one of the important data structures in Lisp, and the Lisp source code itself is made up of lists. As a result, Lisp programs can manipulate Lisp source code as if they were simple data, giving rise to macro systems that allow programmers to create domain-specific languages embedded in Lisp.

The interchangeability of code and data also gives Lisp its instantly recognizable syntax. All program code is written as S-expressions, or lists in parentheses. A function call or syntactic form is written as a list, with the function or operator name first, and the arguments following; for example, a function f that takes three arguments can be called using (f x y z).

History

Lisp was invented by John McCarthy in 1958 while he was at the Massachusetts Institute of Technology (MIT). McCarthy published his design in 1960 in a Communications of the ACM article titled & # 34; Recursive Functions of Symbolic Expressions and Their Machine Computation, Part I & # 34; (the & # 34; Part II & # 34; was never published). There he showed that with some simple operators and a notation for functions, one can build a complete Turing language for processing algorithms.

From 1955 or 1956, the Information Processing Language was the first AI language, and it had already included many of the concepts, such as list processing and recursion, that came to be used in Lisp.

McCarthy's original notation used "M expressions" in square brackets that would be translated into S expressions. As an example, the expression M car[cons[A,B]] is equivalent to the expression S (car (cons A B)). Once Lisp was implemented, programmers quickly chose to use S-expressions, and M-expressions were abandoned. M expressions resurfaced with the short-lived attempts of Horace Enea's MLISP and Vaughan Pratt's CGOL.

Lisp was first implemented by Steve Russell on an IBM 704 computer. Russell had read McCarthy's paper, and realized (to McCarthy's surprise) that Lisp's eval function could be implemented in machine code. The result was a working Lisp interpreter that could be used to run Lisp programs, or more correctly, "evaluate Lisp expressions".

Two assembly language routines for the IBM 704 became the primitive operations for decomposing lists: car (contents of the address register) and cdr (contents of the decrement register). Lisp dialects still use car and cdr (pronounced /ˈkɑr/ and /ˈkʊdər/) for operations that return the first element and the rest of the list respectively.

The first full Lisp compiler, written in Lisp, was implemented in 1962 by Tim Hart and Mike Levin at MIT. This compiler introduced the Lisp model of incremental compilation, in which compiled and interpreted functions can be freely intermixed. The language in Hart and Levin's memos is much closer to the modern style of Lisp than McCarthy's earlier code.

Genealogy and variants

Over its fifty-year history, Lisp has produced many variations on the base theme of an expression language S. On the other hand, each given dialect may have several implementations, for example, there are more than a dozen implementations of Common lisp.

Differences between dialects can be very visible, for example, Common Lisp and Scheme use different keywords to define functions. Within a dialect that is standardized, however, the conforming implementations support the same base language, but with different extensions and libraries.

Relationship with artificial intelligence

From its inception, Lisp was closely associated with the artificial intelligence research community, especially on PDP-10 systems. It was used as the implementation of the Micro Planner programming language that was the foundation for the famous AI system. SHRDLU. In the 1970s, as AI research spawned commercial offspring, the performance of existing Lisp systems became an increasing problem.

Lisp was a difficult system to implement with common hardware and compiler techniques of the 1970s. Garbage collection routines, developed by then-MIT graduate student Daniel Edwards, made it practical to run Lisp on computer systems. general purpose, but effectiveness was still a problem. This led to the creation of Lisp machines: dedicated hardware for running Lisp programs and environments. Advances in both computer hardware and compiler technology soon made Lisp machines obsolete, to the detriment of the Lisp market.

During the 1980s and 1990s, a great deal of effort was made to unify the many dialects of Lisp into a single language (most notably, InterLisp, Maclisp, ZetaLisp, MetaLisp, and Franz Lisp). The new language, Common Lisp, was essentially a compatible subset of the dialects it replaced. In 1994, ANSI published the Common Lisp standard, "ANSI X3.226-1994 Information Technology Programming Language Common Lisp". At that time the world market for Lisp was much smaller than it is today.^{[citation needed]}

Since 2000

Having declined somewhat in the 1990s, Lisp experienced a new heyday focused on open implementations of Common Lisp and the development of applications and new portable libraries. One sign of this interest was that the print version of Peter Seibel's Practical Common Lisp, a tutorial for new programmers published in 2004, was briefly on Amazon.com as the second most popular programming book. The book is accessible online at no cost.

Many new Lisp programmers were inspired by writers like Paul Graham and Eric S. Raymond fighting for a language that others consider outdated. New Lisp programmers frequently describe the language as an eye-opening experience and claim that it is substantially more productive than other languages. This rise in awareness can be contrasted with the "artificial intelligence winter" and the brief growth of Lisp in the mid-1990s.

In his survey of Common Lisp implementations, Dan Weinreb lists eleven actively maintained implementations. Scieneer Common Lisp is a new commercial implementation that forked from the CMUCL with a first release in 2002.

The open source community has created a new support infrastructure: Cliki is a Wiki that collects information related to Common Lisp, the Common Lisp directory lists resources, #lisp is a popular IRC channel (supported by a Bot written in Lisp), lisppaste supports sharing and sharing and commenting on snippets, Planet Lisp collects content from various Lisp-related blogs, LispForum users discuss Lisp topics, Lispjobs is a service to advertise job openings and there is a new weekly news service (Weekly Lisp News).

The 50 years of Lisp (1958-2008) have been celebrated at LISP50@OOPSLA. There are several regular local user meetings (Boston, Vancouver, Hamburg,…), Lisp Meetings (European Common Lisp Meeting, European Lisp Symposium) and an International Lisp Conference.

The Scheme community actively maintains over twenty implementations. Several significant new implementations have been developed in recent years (Chicken, Gauche, Ikarus, Larceny, Ypsilon). The Scheme standard Revised5 Report on the Algorithmic Language Scheme was widely accepted in the Scheme community. The Scheme Requests for Implementation process has created many near-standard libraries and extensions for the Scheme. The user communities of individual implementations of the Scheme continue to grow. In 2003 a new language standardization process was started and led to the standard R⁶RS of the Scheme in 2007. The academic use of the Scheme to teach computer science seems to have declined somewhat. Some universities are no longer using Scheme in their introductory computer science courses.

There are also some new Lisp dialects. Notably: Newlisp (a scripting language), Arc (developed by Paul Graham) and recently Clojure (developed by Rich Hickey) and NU for programming with Apple's Cocoa.

Important dialects

The two main dialects of Lisp used for general purpose programming today are Common Lisp and Scheme. These languages represent significantly different design options.

Common Lisp, descended primarily from MacLisp, Interlisp, and Lisp Machine Lisp, is an expanded superset of early Lisp dialects, with a large language standard including many built-in data types and syntactic forms, as well as a system of the object. The Scheme is a more minimalist design, with a much smaller set of standard features but with certain implementation features (such as tail call optimization and full continuation) not necessarily found in Common Lisp. Common Lisp also borrowed certain features from Scheme such as lexical scope and lexical closure.

Scheme is a dialect of the Lisp language with static scope and true recursive tail invented by Guy Lewis Steele Jr. and Gerald Jay Sussman. It was designed to have exceptionally clear and simple semantics and few different ways of forming expressions. A wide variety of programming paradigms find convenient expression in Scheme, including the imperative, functional, and message passing styles. The Scheme continues to evolve with a series of standards (Revisedⁿ Report on the Algorithmic Language Scheme) and a series of Scheme Requests for Implementation.

In addition, Lisp dialects are used as scripting languages in a number of applications, with the best known being Emacs Lisp in the Emacs editor, Visual Lisp in AutoCAD, Nyquist in Audacity.

Language innovations

It was in Lisp that many computer science ideas were born, including the tree data structure, automatic garbage collection, dynamic typing, conditionals, higher order functions like map and reduce, recursion, the self-contained compiler, and the REPL.

Lisp was the first homoiconic programming language: the entire source code of the program is at the same time a data structure of the language (nested lists or trees). As a result, metaprogramming in Lisp is relatively easy. Since Lisp source code has a direct correspondence to the abstract syntax tree of the program, Lisp code can be created to manipulate more Lisp code, or even created from scratch, without the need for extensive parsing or manipulation. binary machine code. This is generally considered one of the primary advantages of the language with respect to its expressive power, and makes the language favorable to metacircular evaluation.

The ubiquitous IF THEN ELSE structure, now recognized as an essential element of any programming language, was invented by McCarthy for use in Lisp, where it saw its first appearance in a more general form (the cond structure). It was inherited by ALGOL, which popularized it.

Lisp profoundly influenced [[of Smalltalk, and then Lisp in turn was influenced by Smalltalk, adopting the features of object-oriented programming (classes, instances, etc.) in the late 1970s.

Lisp introduced the concept of garbage collection, whereby the system searches the "heap" dynamic memory to remove obsolete objects without explicit programmer intervention.

In large part because of its resource requirements relative to early computing hardware (including early microprocessors), Lisp did not become as popular outside of the artificial intelligence community as did FORTRAN and the language descendant ALGOL., the C language. Newer languages such as Java and Python have incorporated some limited versions of some of Lisp's features, but cannot necessarily provide the consistency and synergy of the complete concepts found in Lisp. Due to its suitability for ill-defined, complex, and dynamic applications, Lisp is currently enjoying something of a revival of popular interest.

Lists

The fundamental element in Lisp is the list, in the broadest sense of the term, since both data and programs are lists. That's where its name comes from, as Lisp is an acronym for "ListProcessing".

Lists in LISP are delimited by parentheses. This is where the LISP meaning joke comes from: "LostInStupidParentheses" which although in good humor is completely fictional.

Some of Lisp's built-in functions have familiar symbols (+ for sum, * for product), but others are more exotic, especially two that serve precisely to manipulate lists, breaking them down into their components. Their names ("car" and "cdr") are a bit strange, relics of times gone by and the structure of second-generation computers, "car" returns the head of a list and "cdr" its tail or rest.

Lisp follows a philosophy of non-destructive treatment of parameters, in such a way that most functions return a list that is the result of performing some transformation on the one they received, but without altering the latter.

One of the reasons why Lisp is particularly well-suited for AI is the fact that code and data are treated in the same way (as lists); this makes it especially easy to write programs capable of writing other programs depending on the circumstances.

Lisp was one of the first programming languages to include exception handling with the catch and throw primitives.

Derived from Lisp is the Logo programming language. Without going into details, Logo could be said to be Lisp without parentheses and with infix arithmetic operators.

Origins of shell"car" y n#34;cdr"

• car: Content of Address part of Register
• cdr: Content of Decremental part of Register

These are operations of the IBM 704 instruction set

Examples

Hello world

(format t "Hello, world!")

Working with lists

*******************Definition of the function: (defun emptied (l) (cond (null l) 1) if the list is empty returns 1 (t 0()))) in another case (full list) returns 0Call a the function: (emptied '(1 3 4) The list is not empty, it would return 0 (emptied '()) The list is empty, it would return 1*******************(defun last (List) (cond (null (cdr List) (car List) (t (last (cdr List()))))(last '(1 2 3 4 5 6 7) returns the last of the list: 7*******************; Factorial(x) = 1 if x=0 base case; x*factorial(x-1) if x verbal0 recursive case;Function factorial made with non-final recursivity(defun factorial (n) (if (= 0 n) 1 base case (♪ n (factorial (- n 1())))) ; recursive case(factorial 4) this would return 24=4*3*2*1*******************

Large values of the Ackermann Function

 ;Proposed by Nikolai Coica (defun ackermann (m n) "The Ackermann Function" (cond (= m 0) (+ n 1) (= m 1) (+ n 2) (= m 2) (+ 3 (♪ n 2()))) (= m 3) (+ 5 (♪ 8 (- (expt 2 n) 1()))) (t (cond (= n 0) (ackermann (- m 1) 1) (t (ackermann (- m 1) (ackermann m (- n 1())))))))