lisp (programming language) lisp redirects here for the internet protocol see locatoridentifier separation protocol lisp historically lisp is a family of computer programming languages with a long history and a distinctive fully parenthesized prefix notation originally specified in 1958 lisp is the secondoldest highlevel programming language in widespread use today only fortran is older by one year lisp has changed since its early days and many dialects have existed over its history today the best known generalpurpose lisp dialects are common lisp and scheme lisp was originally created as a practical mathematical notation for computer program influenced by the notation of alonzo churchs lambda calculus it quickly became the favored programming language for artificial intelligence ai research as one of the earliest programming languages lisp pioneered many ideas in computer science including tree data structures automatic storage management dynamic typing conditionals higherorder functions recursion the selfhosting compiler the name lisp derives from list processor linked lists are one of lisps major data structures and lisp source code is made of lists thus lisp programs can manipulate source code as a data structure giving rise to the macro systems that allow programmers to create new syntax or new domainspecific languages embedded in lisp the interchangeability of code and data gives lisp its instantly recognizable syntax all program code is written as sexpressions or parenthesized lists a function call or syntactic form is written as a list with the function or operators name first and the arguments following for instance a function f that takes three arguments would be called as f arg1 arg2 arg3 history media all and maxwidth720pxmwparseroutput tmultithumbinnerwidth100importantmaxwidthnoneimportantmwparseroutput tmulti tsinglefloatnoneimportantmaxwidthnoneimportantwidth100importanttextaligncenterjohn mccarthy top and steve russell bottom lisp was invented by john mccarthy in 1958 while he was at the massachusetts institute of technology mit mccarthy published its design in a paper in communications of the acm in 1960 entitled recursive functions of symbolic expressions and their computation by machine part i he showed that with a few simple operators and a notation for functions one can build a turingcomplete language for algorithms information processing language was the first ai language from 1955 or 1956 and already included many of the concepts such as listprocessing and recursion which came to be used in lisp mccarthys original notation used bracketed mexpressions that would be translated into sexpressions as an example the mexpression car by horace enea and cgol by vaughan pratt lisp was first implemented by steve russell on an ibm 704 computer russell had read mccarthys paper and realized to mccarthys surprise that the lisp eval function could be implemented in machine code the result was a working lisp interpreter which could be used to run lisp programs or more properly evaluate lisp expressions two assembly language macros for the ibm 704 became the primitive operations for decomposing lists car contents of the address part of register number and cdr contents of the decrement part of register number where the term register is used to mean memory register nowadays called memory location see car and cdr for the etymology of the terms lisp dialects still use car and cdr kr and kdr for the operations that return the first item in a list and the rest of the list respectively the first complete 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 intermix freely the language used in hart and levins memo is much closer to modern lisp style than mccarthys earlier code lisp was a difficult system to implement with the compiler techniques and stock hardware of the 1970s garbage collection routines developed by mit graduate student daniel edwards made it practical to run lisp on generalpurpose computing systems but efficiency was still a problem this led to the creation of lisp machines dedicated hardware for running lisp environments and programs during the 1980s and 1990s a great effort was made to unify the work on new lisp dialects mostly successors to maclisp like zetalisp and nil new implementation of lisp into a single language the new language common lisp was somewhat compatible with the dialects it replaced the book common lisp the language notes the compatibility of various constructs in 1994 ansi published the common lisp standard ansi x32261994 information technology programming language common lisp timeline timeline of lisp dialectsedit 1955 1960 1965 1970 1975 1980 1985 1990 1995 2000 2005 2010 2015 2018 lisp 15 maclisp interlisp lisp machine lisp scheme nil common lisp le lisp t emacs lisp autolisp openlisp picolisp eulisp islisp newlisp racket gnu guile visual lisp clojure arc lfe hy connection to artificial intelligence since inception lisp was closely connected with the artificial intelligence research community especially on pdp10 genealogy and variants over its sixtyyear history lisp has spawned many variations on the core theme of an sexpression language moreover each given dialect may have several implementationsfor instance there are more than a dozen implementations of common lisp differences between dialects may be quite visiblefor instance common lisp uses the keyword defun to name a function but scheme uses define within a dialect that is standardized however conforming implementations support the same core language but with different extensions and libraries historically significant dialects a lisp machine in the mit museum 43 bsd from the university of wisconsin displaying the man page for franz lisp lisp 1 first implementation lisp 15 first widely distributed version developed by mccarthy and others at mit so named because it contained several improvements on the original lisp 1 interpreter but was not a major restructuring as the planned lisp 2 would be stanford lisp 16 this was a successor to lisp 15 developed at the stanford ai lab and widely distributed to pdp10 systems running the tops10 operating system it was rendered obsolete by maclisp and interlisp maclisp developed for mits project mac no relation to apples macintosh nor to mccarthy direct descendant of lisp 15 it ran on the pdp10 and multics systems maclisp would later come to be called maclisp and is often referred to as maclisp interlisp developed at bbn technologies for pdp10 systems running the tenex operating system later adopted as a west coast lisp for the xerox lisp machines as interlispd a small version called interlisp 65 was published for the 6502based atari 8bit family computer line for quite some time maclisp and interlisp were strong competitors franz lisp originally a university of california berkeley project later developed by franz inc the name is a humorous deformation of the name franz liszt and does not refer to allegro common lisp the dialect of common lisp sold by franz inc in more recent years xlisp which autolisp was based on standard lisp and portable standard lisp were widely used and ported especially with the computer algebra system reduce zetalisp also termed lisp machine lisp used on the lisp machines direct descendant of maclisp zetalisp had a big influence on common lisp lelisp is a french lisp dialect one of the first interface builders called sos interface was written in lelisp scheme 1975 common lisp 1984 as described by common lisp the language a consolidation of several divergent attempts zetalisp spice lisp nil and s1 lisp to create successor dialects until the publication of ansi common lisp ansi x32261994 among the most widespread subdialects of common lisp are steel bank common lisp sbcl cmu common lisp cmucl clozure openmcl not to be confused with clojure gnu clisp and later versions of franz lisp all of them adhere to the later ansi cl standard see below dylan was in its first version a mix of scheme with the common lisp object system eulisp attempt to develop a new efficient and cleanedup lisp islisp attempt to develop a new efficient and cleanedup lisp standardized as isoiec 138161997 information technology programming languages their environments and system software interfaces programming language islisp ieee scheme ieee standard 11781990 r1995 ansi common lisp an american national standards institute ansi standard for common lisp created by subcommittee x3j13 chartered to begin with common lisp the language as a base document and to work through a public consensus process to find solutions to shared issues of portability of programs and compatibility of common lisp implementations although formally an ansi standard the implementation sale use and influence of ansi common lisp has been and continues to be seen worldwide acl2 or a computational logic for applicative common lisp an applicative sideeffect free variant of common lisp acl2 is both a programming language which can model computer systems and a tool to help proving properties of those models clojure a recent dialect of lisp which compiles to the java virtual machine and has a particular focus on concurrency game oriented assembly lisp or goal is a video game programming language developed by andy gavin and the jak and daxter team at naughty dog it was written using allegro common lisp and used in the development of the entire jak and daxter series of games 2000 to present after having declined somewhat in the 1990s lisp has recently experienced a resurgence of interest most new activity is focused around implementations of common lisp scheme emacs lisp clojure and racket and includes development of new portable libraries and applications many new lisp programmers were inspired by writers such as paul graham and eric s raymond to pursue a language others considered antiquated new lisp programmers often describe the language as an eyeopening experience and claim to be substantially more productive than in other languages dan weinreb lists in his survey of common lisp implementations eleven actively maintained common lisp implementations scieneer common lisp is a new commercial implementation forked from cmucl with a first release in 2002 the open source community has created new supporting infrastructure cliki is a wiki that collects common lisp related information the common lisp directory lists resources lisp is a popular irc channel and allows the sharing and commenting of code snippets with support by lisppaste an irc bot written in lisp planet lisp collects the contents of various lisprelated blogs on lispforum users discuss lisp topics lispjobs is a service for announcing job offers and there is a weekly news service weekly lisp news commonlispnet is a hosting site for open source common lisp projects quicklisp is a library manager for common lisp 50 years of lisp 19582008 was celebrated at lisp50oopsla there are regular local user meetings in boston vancouver and hamburg other events include the european common lisp meeting the european lisp symposium and an international lisp conference the scheme community actively maintains over twenty implementations several significant new implementations chicken gambit gauche ikarus larceny ypsilon have been developed in the last few years the revised5 report on the algorithmic language scheme there are several new dialects of lisp arc hy nu liskell and lfe lisp flavored erlang the parser for julia is implemented in femtolisp a dialect of scheme julia is inspired by scheme and is often considered a lisp major dialects common lisp and scheme represent two major streams of lisp development these languages embody significantly different design choices common lisp is a successor to maclisp the primary influences were lisp machine lisp maclisp nil s1 lisp spice lisp and scheme x8664 powerpc alpha arm motorola 68000 and mips scheme is a statically scoped and properly tailrecursive dialect of the lisp programming language invented by guy l steele jr and gerald jay sussman it was designed to have exceptionally clear and simple semantics and few different ways to form expressions designed about a decade earlier than common lisp scheme is a more minimalist design it has a much smaller set of standard features but with certain implementation features such as tailcall optimization and full continuations not specified in common lisp a wide variety of programming paradigms including imperative functional and message passing styles find convenient expression in scheme scheme continues to evolve with a series of standards revisedn report on the algorithmic language scheme and a series of scheme requests for implementation clojure is a recent dialect of lisp that targets mainly the java virtual machine and the common language runtime clr the python vm the ruby vm yarv and compiling to javascript it is designed to be a pragmatic generalpurpose language clojure draws considerable influences from haskell and places a very strong emphasis on immutability clojure provides access to java frameworks and libraries with optional type hints and type inference so that calls to java can avoid reflection and enable fast primitive operations further lisp dialects are used as scripting languages in many applications with the bestknown being emacs lisp in the emacs editor autolisp and later visual lisp in autocad nyquist in audacity scheme in lilypond the potential small size of a useful scheme interpreter makes it particularly popular for embedded scripting examples include siod and tinyscheme both of which have been successfully embedded in the gimp image processor under the generic name scriptfu language innovations lisp was the first language where the structure of program code is represented faithfully and directly in a standard data structurea quality much later dubbed homoiconicity thus lisp functions can be manipulated altered or even created within a lisp program without lowerlevel manipulations this is generally considered one of the main advantages of the language with regard to its expressive power and makes the language suitable for syntactic macros and metacircular evaluation a conditional using an ifthenelse syntax was invented by mccarthy in a fortran context he proposed its inclusion in algol but it was not made part of the algol 58 specification for lisp mccarthy used the more general condstructure algol 60 took up ifthenelse and popularized it lisp deeply influenced alan kay the leader of the research team that developed smalltalk at xerox parc and in turn lisp was influenced by smalltalk with later dialects adopting objectoriented programming features inheritance classes encapsulating instances message passing etc in the 1970s the flavors object system introduced the concept of multiple inheritance and the mixin the common lisp object system provides multiple inheritance multimethods with multiple dispatch and firstclass generic functions yielding a flexible and powerful form of dynamic dispatch it has served as the template for many subsequent lisp including scheme object systems which are often implemented via a metaobject protocol a reflective metacircular design in which the object system is defined in terms of itself lisp was only the second language after smalltalk and is still one of the very few languages to possess such a metaobject system many years later alan kay suggested that as a result of the confluence of these features only smalltalk and lisp could be regarded as properly conceived objectoriented programming systems lisp introduced the concept of automatic garbage collection in which the system walks the heap looking for unused memory progress in modern sophisticated garbage collection algorithms such as generational garbage collection was stimulated by its use in lisp edsger w dijkstra in his 1972 turing award lecture said with a few very basic principles at its foundation it largely because of its resource requirements with respect to early computing hardware including early microprocessors lisp did not become as popular outside of the ai community as fortran and the algoldescended c language because of its suitability to complex and dynamic applications lisp is enjoying some resurgence of popular interest in the 2010s syntax and semantics note this articles examples are written in common lisp though most are also valid in scheme symbolic expressions sexpressions lisp is an expression oriented language unlike most other languages no distinction is made between expressions and statements all code and data are written as expressions when an expression is evaluated it produces a value in common lisp possibly multiple values which can then be embedded into other expressions each value can be any data type mccarthys 1958 paper introduced two types of syntax symbolic expressions sexpressions sexps which mirror the internal representation of code and data and meta expressions mexpressions which express functions of sexpressions mexpressions never found favor and almost all lisps today use sexpressions to manipulate both code and data the use of parentheses is lisps most immediately obvious difference from other programming language families as a result students have long given lisp nicknames such as lost in stupid parentheses or lots of irritating superfluous parentheses however the sexpression syntax is also responsible for much of lisps power the syntax is extremely regular which facilitates manipulation by computer however the syntax of lisp is not limited to traditional parentheses notation it can be extended to include alternative notations for example xmlisp is a common lisp extension that employs the metaobject protocol to integrate sexpressions with the extensible markup language xml the reliance on expressions gives the language great flexibility because lisp functions are written as lists they can be processed exactly like data this allows easy writing of programs which manipulate other programs metaprogramming many lisp dialects exploit this feature using macro systems which enables extension of the language almost without limit lists a lisp list is written with its elements separated by whitespace and surrounded by parentheses for example 1 2 foo is a list whose elements are the three atoms 1 2 and foo these values are implicitly typed they are respectively two integers and a lispspecific data type called a symbol and do not have to be declared as such the empty list is also represented as the special atom nil this is the only entity in lisp which is both an atom and a list expressions are written as lists using prefix notation the first element in the list is the name of a function the name of a macro a lambda expression or the name of a special operator see below the remainder of the list are the arguments for example the function list returns its arguments as a list so the expression list 1 2 quote foo evaluates to the list 1 2 foo the quote before the foo in the preceding example is a special operator which returns its argument without evaluating it any unquoted expressions are recursively evaluated before the enclosing expression is evaluated for example list 1 2 list 3 4 evaluates to the list 1 2 3 4 note that the third argument is a list lists can be nested operators arithmetic operators are treated similarly the expression 1 2 3 4 evaluates to 10 the equivalent under infix notation would be 1 2 3 4 lisp has no notion of operators as implemented in algolderived languages arithmetic operators in lisp are variadic functions or nary able to take any number of arguments a cstyle increment operator is sometimes implemented under the name incf giving syntax incf x equivalent to setq x x 1 returning the new value of x special operators sometimes called special forms provide lisps control structure for example the special operator if takes three arguments if the first argument is nonnil it evaluates to the second argument otherwise it evaluates to the third argument thus the expression if nil list 1 2 foo list 3 4 bar evaluates to 3 4 bar of course this would be more useful if a nontrivial expression had been substituted in place of nil lisp also provides logical operators and or and not the and and or operators do short circuit evaluation and will return their first nil and nonnil argument respectively or and zero nil never james task time will evaluate to james lambda expressions and function definition another special operator lambda is used to bind variables to values which are then evaluated within an expression this operator is also used to create functions the arguments to lambda are a list of arguments and the expression or expressions to which the function evaluates the returned value is the value of the last expression that is evaluated the expression lambda arg arg 1 evaluates to a function that when applied takes one argument binds it to arg and returns the number one greater than that argument lambda expressions are treated no differently from named functions they are invoked the same way therefore the expression lambda arg arg 1 5 evaluates to 6 here were doing a function application we execute the anonymous function by passing to it the value 5 named functions are created by storing a lambda expression in a symbol using the defun macro defun foo a b c d a b c d defun f a b defines a new function named f in the global environment it is conceptually similar to the expression setf fdefinition f lambda a block f b atoms in the original lisp there were two fundamental data types atoms and lists a list was a finite ordered sequence of elements where each element is either an atom or a list and an atom was a number or a symbol a symbol was essentially a unique named item written as an alphanumeric string in source code and used either as a variable name or as a data item in symbolic processing for example the list foo bar 1 2 contains three elements the symbol foo the list bar 1 and the number 2 the essential difference between atoms and lists was that atoms were immutable and unique two atoms that appeared in different places in source code but were written in exactly the same way represented the same object whereas each list was a separate object that could be altered independently of other lists and could be distinguished from other lists by comparison operators as more data types were introduced in later lisp dialects and programming styles evolved the concept of an atom lost importance defining it true for any object which is not a cons conses and lists cons boxandpointer diagram for the list 42 69 613 a lisp list is implemented as a singly linked list each cell of this list is called a cons in scheme a pair and is composed of two pointers called the car and cdr these are respectively equivalent to the data and next fields discussed in the article linked list of the many data structures that can be built out of cons cells one of the most basic is called a proper list a proper list is either the special nil empty list symbol or a cons in which the car points to a datum which may be another cons structure such as a list and the cdr points to another proper list if a given cons is taken to be the head of a linked list then its car points to the first element of the list and its cdr points to the rest of the list for this reason the car and cdr functions are also called first and rest when referring to conses which are part of a linked list rather than say a tree thus a lisp list is not an atomic object as an instance of a container class in c or java would be a list is nothing more than an aggregate of linked conses a variable which refers to a given list is simply a pointer to the first cons in the list traversal of a list can be done by cdring down the list that is taking successive cdrs to visit each cons of the list or by using any of several higherorder functions to map a function over a list because conses and lists are so universal in lisp systems it is a common misconception that they are lisps only data structures in fact all but the most simplistic lisps have other data structures such as vectors arrays hash tables structures and so forth sexpressions represent lists parenthesized sexpressions represent linked list structures there are several ways to represent the same list as an sexpression a cons can be written in dottedpair notation as a b where a is the car and b the cdr a longer proper list might be written a b c d nil in dottedpair notation this is conventionally abbreviated as a b c d in list notation an improper list may be written in a combination of the two as a b c d for the list of three conses whose last cdr is d ie the list a b c d in fully specified form listprocessing procedures lisp provides many builtin procedures for accessing and controlling lists lists can be created directly with the list procedure which takes any number of arguments and returns the list of these arguments list 1 2 a 3 output 1 2 a 3 list 1 2 3 4 output 1 2 3 4 because of the way that lists are constructed from cons pairs the cons procedure can be used to add an element to the front of a list note that the cons procedure is asymmetric in how it handles list arguments because of how lists are constructed cons 1 2 3 output 1 2 3 cons 1 2 3 4 output 1 2 3 4 the append procedure appends two or more lists to one another because lisp lists are linked lists appending two lists has asymptotic time complexity o n displaystyle on append 1 2 3 4 output 1 2 3 4 append 1 2 3 a 5 6 output 1 2 3 a 5 6 shared structure lisp lists being simple linked lists can share structure with one another that is to say two lists can have the same tail or final sequence of conses for instance after the execution of the following common lisp code setf foo list a b c setf bar cons x cdr foo the lists foo and bar are a b c and x b c respectively however the tail b c is the same structure in both lists it is not a copy the cons cells pointing to b and c are in the same memory locations for both lists sharing structure rather than copying can give a dramatic performance improvement however this technique can interact in undesired ways with functions that alter lists passed to them as arguments altering one list such as by replacing the c with a goose will affect the other setf third foo goose this changes foo to a b goose but thereby also changes bar to x b goose a possibly unexpected result this can be a source of bugs and functions which alter their arguments are documented as destructive for this very reason aficionados of functional programming avoid destructive functions in the scheme dialect which favors the functional style the names of destructive functions are marked with a cautionary exclamation point or bangsuch as setcar read set car bang which replaces the car of a cons in the common lisp dialect destructive functions are commonplace the equivalent of setcar is named rplaca for replace car this function is rarely seen however as common lisp includes a special facility setf to make it easier to define and use destructive functions a frequent style in common lisp is to write code functionally without destructive calls when prototyping then to add destructive calls as an optimization where it is safe to do so selfevaluating forms and quoting lisp evaluates expressions which are entered by the user symbols and lists evaluate to some other usually simpler expression for instance a symbol evaluates to the value of the variable it names 2 3 evaluates to 5 however most other forms evaluate to themselves if entering 5 into lisp it returns 5 any expression can also be marked to prevent it from being evaluated as is necessary for symbols and lists this is the role of the quote special operator or its abbreviation one quotation mark for instance usually if entering the symbol foo it returns the value of the corresponding variable or an error if there is no such variable to refer to the literal symbol enter quote foo or usually foo both common lisp and scheme also support the backquote operator termed quasiquote in scheme entered with the character grave accent this is almost the same as the plain quote except it allows expressions to be evaluated and their values interpolated into a quoted list with the comma unquote and commaat splice operators if the variable snue has the value bar baz then foo snue evaluates to foo bar baz while foo snue evaluates to foo bar baz the backquote is most often used in defining macro expansions selfevaluating forms and quoted forms are lisps equivalent of literals it may be possible to modify the values of mutable literals in program code for instance if a function returns a quoted form and the code that calls the function modifies the form this may alter the behavior of the function on subsequent iterations defun shouldbeconstant one two three let stuff shouldbeconstant setf third stuff bizarre bad shouldbeconstant returns one two bizarre modifying a quoted form like this is generally considered bad style and is defined by ansi common lisp as erroneous resulting in undefined behavior in compiled files because the filecompiler can coalesce similar constants put them in writeprotected memory etc lisps formalization of quotation has been noted by douglas hofstadter in gdel escher bach and others as an example of the philosophical idea of selfreference scope and closure the lisp family splits over the use of dynamic or static aka lexical scope clojure common lisp and scheme make use of static scoping by default while newlisp picolisp and the embedded languages in emacs and autocad use dynamic scoping since version 241 emacs uses both dynamic and lexical scoping list structure of program code exploitation by macros and compilers a fundamental distinction between lisp and other languages is that in lisp the textual representation of a program is simply a humanreadable description of the same internal data structures linked lists symbols number characters etc as would be used by the underlying lisp system lisp uses this to implement a very powerful macro system like other macro languages such as c a macro returns code that can then be compiled however unlike c macros the macros are lisp functions and so can exploit the full power of lisp further because lisp code has the same structure as lists macros can be built with any of the listprocessing functions in the language in short anything that lisp can do to a data structure lisp macros can do to code in contrast in most other languages the parsers output is purely internal to the language implementation and cannot be manipulated by the programmer this feature makes it easy to develop efficient languages within languages for example the common lisp object system can be implemented cleanly as a language extension using macros this means that if an application needs a different inheritance mechanism it can use a different object system this is in stark contrast to most other languages for example java does not support multiple inheritance and there is no reasonable way to add it in simplistic lisp implementations this list structure is directly interpreted to run the program a function is literally a piece of list structure which is traversed by the interpreter in executing it however most substantial lisp systems also include a compiler the compiler translates list structure into machine code or bytecode for execution this code can run as fast as code compiled in conventional languages such as c macros expand before the compilation step and thus offer some interesting options if a program needs a precomputed table then a macro might create the table at compile time so the compiler need only output the table and need not call code to create the table at run time some lisp implementations even have a mechanism evalwhen that allows code to be present during compile time when a macro would need it but not present in the emitted module evaluation and the readevalprint loop lisp languages are often used with an interactive command line which may be combined with an integrated development environment ide the user types in expressions at the command line or directs the ide to transmit them to the lisp system lisp reads the entered expressions evaluates them and prints the result for this reason the lisp command line is called a readevalprint loop repl the basic operation of the repl is as follows this is a simplistic description which omits many elements of a real lisp such as quoting and macros the read function accepts textual sexpressions as input and parses them into an internal data structure for instance if you type the text 1 2 at the prompt read translates this into a linked list with three elements the symbol the number 1 and the number 2 it so happens that this list is also a valid piece of lisp code that is it can be evaluated this is because the car of the list names a functionthe addition operation note that a foo will be read as a single symbol 123 will be read as the number one hundred and twentythree 123 will be read as the string 123 the eval function evaluates the data returning zero or more other lisp data as a result evaluation does not have to mean interpretation some lisp systems compile every expression to native machine code it is simple however to describe evaluation as interpretation to evaluate a list whose car names a function eval first evaluates each of the arguments given in its cdr then applies the function to the arguments in this case the function is addition and applying it to the argument list 1 2 yields the answer 3 this is the result of the evaluation the symbol foo evaluates to the value of the symbol foo data like the string 123 evaluates to the same string the list quote 1 2 3 evaluates to the list 1 2 3 it is the job of the print function to represent output to the user for a simple result such as 3 this is trivial an expression which evaluated to a piece of list structure would require that print traverse the list and print it out as an sexpression to implement a lisp repl it is necessary only to implement these three functions and an infiniteloop function naturally the implementation of eval will be complex since it must also implement all special operators like if or lambda this done a basic repl is one line of code loop print eval read the lisp repl typically also provides input editing an input history error handling and an interface to the debugger lisp is usually evaluated eagerly in common lisp arguments are evaluated in applicative order leftmost innermost while in scheme order of arguments is undefined leaving room for optimization by a compiler control structures lisp originally had very few control structures but many more were added during the languages evolution lisps original conditional operator cond is the precursor to later ifthenelse structures programmers in the scheme dialect often express loops using tail recursion schemes commonality in academic computer science has led some students to believe that tail recursion is the only or the most common way to write iterations in lisp but this is incorrect all oftseen lisp dialects have imperativestyle iteration constructs from schemes do loop to common lisps complex loop expressions moreover the key issue that makes this an objective rather than subjective matter is that scheme makes specific requirements for the handling of tail calls and thus the reason that the use of tail recursion is generally encouraged for scheme is that the practice is expressly supported by the language definition by contrast ansi common lisp does not require in common lisp is not just a matter of stylistic preference but potentially one of efficiency since an apparent tail call in common lisp may not compile as a simple jump and program correctness since tail recursion may increase stack use in common lisp risking stack overflow some lisp control structures are special operators equivalent to other languages syntactic keywords expressions using these operators have the same surface appearance as function calls but differ in that the arguments are not necessarily evaluatedor in the case of an iteration expression may be evaluated more than once in contrast to most other major programming languages lisp allows implementing control structures using the language several control structures are implemented as lisp macros and can even be macroexpanded by the programmer who wants to know how they work both common lisp and scheme have operators for nonlocal control flow the differences in these operators are some of the deepest differences between the two dialects scheme supports reentrant continuations using the callcc procedure which allows a program to save and later restore a particular place in execution common lisp does not support reentrant continuations but does support several ways of handling escape continuations often the same algorithm can be expressed in lisp in either an imperative or a functional style as noted above scheme tends to favor the functional style using tail recursion and continuations to express control flow however imperative style is still quite possible the style preferred by many common lisp programmers may seem more familiar to programmers used to structured languages such as c while that preferred by schemers more closely resembles purefunctional languages such as haskell because of lisps early heritage in list processing it has a wide array of higherorder functions relating to iteration over sequences in many cases where an explicit loop would be needed in other languages like a for loop in c in lisp the same task can be accomplished with a higherorder function the same is true of many functional programming languages a good example is a function which in scheme is called map and in common lisp is called mapcar given a function and one or more lists mapcar applies the function successively to the lists elements in order collecting the results in a new list mapcar 1 2 3 4 5 10 20 30 40 50 this applies the function to each corresponding pair of list elements yielding the result 11 22 33 44 55 examples here are examples of common lisp code the basic hello world program print hello world lisp syntax lends itself naturally to recursion mathematical problems such as the enumeration of recursively defined sets are simple to express in this notation evaluate a numbers factorial defun factorial n if n 0 1 n factorial n 1 an alternative implementation takes less stack space than the previous version if the underlying lisp system optimizes tail recursion defun factorial n optional acc 1 if n 0 acc factorial n 1 acc n contrast with an iterative version which uses common lisps loop macro defun factorial n loop for i from 1 to n for fac 1 then fac i finally return fac the following function reverses a list lisps builtin reverse function does the same thing defun reverse list let returnvalue dolist e list push e returnvalue returnvalue object systems various object systems and models have been built on top of alongside or into lisp including the common lisp object system clos is an integral part of ansi common lisp clos descended from new flavors and commonloops ansi common lisp was the first standardized objectoriented programming language 1994 ansi x3j13 objectlisp or object lisp used by lisp machines incorporated and early versions of macintosh common lisp loops lisp objectoriented programming system and the later commonloops flavors built at mit and its descendant new flavors developed by symbolics kr short for knowledge representation a constraintsbased object system developed to aid the writing of garnet a gui library for common lisp knowledge engineering environment kee used an object system called units and integrated it with an inference engine and a truth maintenance system atms selfmodifying code mwparseroutput refbeginfontsize90marginbottom05emmwparseroutput refbeginhangingindentsulliststyletypenonemarginleft0mwparseroutput refbeginhangingindentsullimwparseroutput refbeginhangingindentsdlddmarginleft0paddingleft32emtextindent32emliststylenonemwparseroutput refbegin100fontsize100 mccarthy john 19790212 the implementation of lisp history of lisp stanford university retrieved 20081017 steele jr guy l richard p gabriel 1993 the evolution of lisp pdf the second acm sigplan conference on history of programming languages new york ny acm pp231270 isbn0897915704 retrieved 20081017 veitch jim 1998 a history and description of clos in salus peter h handbook of programming languages volume iv functional and logic programming languages first ed indianapolis in macmillan technical publishing pp107158 isbn1578700116 abelson harold sussman gerald jay sussman julie 1996 structure and interpretation of computer programs 2nd ed mit press isbn0262011530 my lisp experiences and the development of gnu emacs transcript of richard stallmans speech 28 october 2002 at the international lisp conference graham paul 2004 hackers painters big ideas from the computer age oreilly isbn0596006624 berkeley edmund c bobrow daniel g eds march 1964 the programming language lisp its operation and applications pdf cambridge massachusetts mit press article largely based on the lisp a simple introduction chapter berkeley edmund c sep 1964 the programming language lisp an introduction and appraisal computers and automation 1623 weissman clark 1967 lisp 15 primer pdf belmont california dickenson publishing company inc lisp programming languageat wikipedias sister projects definitions from wiktionary media from wikimedia commons quotations from wikiquote texts from wikisource textbooks from wikibooks resources from wikiversity history history of lisp john mccarthys history of 12 february 1979 lisp history herbert stoyans history compiled from the documents acknowledged by mccarthy as more complete than his own see mccarthys history links history of lisp at the computer history museum associations and meetings association of lisp users european common lisp meeting european lisp symposium international lisp conference books and tutorials casting spels in lisp a comicbook style introductory tutorial on lisp a free book by paul graham practical common lisp freeware edition by peter seibel lisp for the web land of lisp let over lambda interviews oral history interview with john mccarthy at charles babbage institute university of minnesota minneapolis mccarthy discusses his role in the development of timesharing at the massachusetts institute of technology he also describes his work in artificial intelligence ai funded by the advanced research projects agency including logicbased ai lisp and robotics interview with richard p gabriel podcast resources cliki the common lisp wiki the common lisp directory via the wayback machine archived from the original lisp faq index lisppaste planet lisp weekly lisp news lisp at curlie vtelisp programming languagefeatures automatic storage management conditionals dynamic typing higherorder functions linked lists mexpressions deprecated readevalprint loop recursion sexpressions selfhosting compiler tree data structures object systems common lisp object system clos commonloops flavors implementationsmajor dialects common lisp scheme clojure minor dialects allegro common lisp apple dylan arc autolisp bbn lisp dylan emacs lisp eulisp franz lisp game oriented assembly lisp goal hy interlisp islisp kawa knowledge engineering environment lelisp lfe lisp machine lisp maclisp mdl mlisp newlisp nil picolisp portable standard lisp racket rpl s1 lisp scm siod skill spice lisp steel bank common lisp t tinyscheme zetalisp communitystandards scheme requests for implementation common lisp hyperspec education programbydesign developers apple computer bolt beranek and newman harlequin massachusetts institute of technology mit mit computer science and artificial intelligence laboratory csail stanford artificial intelligence laboratory university of california berkeley xanalys people harold abelson edmund berkeley daniel g bobrow scott fahlman matthias felleisen matthew flatt phyllis fox richard p gabriel paul graham richard greenblatt timothy p hart louis hodes mike levin david luckham john mccarthy david a moon robert tappan morris david park kent pitman steve russell richard stallman guy l steele jr gerald jay sussman julie sussman daniel weinreb category category vtejohn mccarthy artificial intelligence circumscription dartmouth workshop frame problem garbage collection lisp mccarthy formalism mccarthy 91 function situation calculus space fountain vteprogramming languages comparison timeline history apl assembly basic c c c cobol fortran go groovy haskell java javascript js kotlin lisp lua objectivec pascal perl php python ruby rust shell smalltalk swift visual basic net vbnet more category lists alphabetical categorical generational nonenglishbased authority control bne xx535292 bnf cb11934831x data gnd 40359189 lccn sh85077449 sudoc 027270394 