Lisp. First atom
Hello, Habr!
LISP has interested me for a long time, but, unfortunately, there was no chance to actively use my knowledge and aspirations in practice. Soon a new school year, which means I will again have the opportunity to study and, for the second year, teach LISP students. Another problem, in addition to the traditional lack of interest in complex things, seems to be a lack of literature. Anyway, the topic of LISP on the Internet, and even more so in RuNet, is poorly lit. Here and on Habré there are not enough publications.
I hope this article will appeal to the public and will open a series that tells about one of the most interesting and least understood (although far from brainfuck and far) programming languages - LISP. After all, as it is not trite, another language is another life
Let's start with the basic concepts of LISP - atoms and lists. A little later, if it is interesting, in the prequel “Atom Zero” it will be possible to talk in more detail about the philosophy and causes of LISP, as well as about modern directions for its use.
LISP was invented by John McCarthy in 1958 for solving non-numeric problems and was based on three main pillars: the algebra of list structures, lambda calculus, and the theory of recursive functions. For a long time, LISP was used exclusively by a narrow circle of specialists in artificial intelligence. But, starting from the 80s of the last century, LISP began to gain momentum and is now actively used, for example, in AutoCad and Emacs.
What is the difference between LISP and traditional programming languages? Consider the key features :
Traditionally, LISP considers two types of atoms : symbols and numbers. Symbols can indicate numbers, strings, complex structures, functions, and other objects. The restrictions on character names depend on the dialect used, but most of them impose virtually no restrictions on the characters used in the names. Also, again in most dialects, character names are not case sensitive.
Some characters have a special purpose - these are constants, built-in functions, T (true, true) and NIL (false, false).
Numbers , unlike symbols, cannot represent other objects, so a number is always a constant number. A bit later we will consider types of numbers in LISP.
Symbols and numbers represent the simplest LISP objects — atoms. The second main data type is point pairs, which are syntactically expressed as follows:
For example, point pairs are expressions:
Atoms and point pairs are combined under the general name S-expressions (S-expression, symbolic expression). A special kind of S-expression is a list, expressed as follows: NIL in most cases is defined as an empty list, in which case the list definition can be rewritten as follows:
Both head and tail are key concepts in the LISP list context. The first element of the list is called the head of the list, all other elements are called the tail. To work with the head and tail, there is a set of basic functions, discussed a little below.
An empty list is equivalent to a pair of empty brackets:
NIL <-> ().
A non-empty list consisting of elements a1, a2, a3 ... in accordance with the rules for writing S-expressions can be written as follows:
In LISP, a list can also be written with a sequence of elements enclosed in brackets and separated by spaces. By and large, a list is a multi-level data structure for which a sequence of opening and closing brackets is archived.
List items can be atoms and lists, including an empty list. For example, () is an empty list, and (NIL) is a list consisting of one NIL element - which is equivalent to (()).
It should be understood that the usual syntax of S-expressions can be used along with list syntax, for example, the following expressions are equivalent:
If anyone is interested, it will be possible to talk about the internal representation of lists in memory. This is a completely independent topic both in terms of interest and volume.
LISP has a fairly small set of primitive functions that provides full-featured list processing. In the context of list structures, these functions are analogous to basic arithmetic operations and form a certain system of rules to which absolutely all symbolic calculations are reduced.
Traditionally, the basic functions include QUOTE, CAR, CDR, CONS, ATOM, EQ.
First, consider the QUOTE function, which is designed to block the evaluation of an expression. The easiest way to demonstrate the operation of this function is with a simple example: The QUOTE function can be written shorter:
Designed to get the first element of a point pair (or the head of a list). Using this function is possible only in a list context, using for an atom will lead to an error.
car (list) -> S-expression.
A few examples: For convenience, the head of an empty list is NIL.
Designed to get the second element of a point pair (or the tail of a list). Using this function is possible only in a list context, using for an atom will lead to an error.
cdr (list) -> list The
tail of the list is the entire list without the first element. If the list consists of one element, the tail will be NIL. For convenience, nil is also considered the tail of an empty list.
Some examples: CAR and CDR functions are implemented in all LISP dialects, but in some synonyms have been created for them: FIRST and REST, HEAD and TAIL).
Designed to create a new list from the head and tail arguments passed to it:
cons (s-expression, list) -> list
For example: In fact, the CONS function is the antipode of the CAR and CDR functions:
ATOM and EQ are predicates - i.e. functions that check whether the argument matches a certain property and return T or NIL depending on the success of the check.
The ATOM predicate checks if the object passed as an argument is an atom:
atom (S-expression)
For example:
A predicate that verifies the identity of two characters.
eq (atom, atom)
Examples: Remember that the predicate EQ applies only to atomic arguments and cannot be used for lists. Also, do not use EQ when comparing numbers. More general than EQ is the EQL predicate , which allows you to compare the same type of numbers: Even more common for numbers is the predicate = , which allows you to compare the values of numbers of different types: More common for lists is the EQUAL predicate , which allows you to compare the identity of two lists: The most common predicate is EQUALP , allowing you to compare arbitrary objects.
NULL checks whether the object passed as an argument is an empty list:
For example: Judging by the last two examples, we can conclude that the NULL function can also be used as a logical negation. For the same purpose, the predicate NOT exists in LISP.
I hope I could be interested. Next time I plan to talk about existing LISP dialects (although university XLisp will be enough at first), less commonly used core functions, folding CAR and CDR into something like CAAAADDAAR, and defining your own functions. Later - recursion, control structures, scope, input-output. Even later - if we don’t get tired - about functionals, macros, character properties and closures. And of course, about what the public will ask.
See you!
PS Criticize, but not too much, publish for the first time :)
LISP has interested me for a long time, but, unfortunately, there was no chance to actively use my knowledge and aspirations in practice. Soon a new school year, which means I will again have the opportunity to study and, for the second year, teach LISP students. Another problem, in addition to the traditional lack of interest in complex things, seems to be a lack of literature. Anyway, the topic of LISP on the Internet, and even more so in RuNet, is poorly lit. Here and on Habré there are not enough publications.
I hope this article will appeal to the public and will open a series that tells about one of the most interesting and least understood (although far from brainfuck and far) programming languages - LISP. After all, as it is not trite, another language is another life
Let's start with the basic concepts of LISP - atoms and lists. A little later, if it is interesting, in the prequel “Atom Zero” it will be possible to talk in more detail about the philosophy and causes of LISP, as well as about modern directions for its use.
Short story
LISP was invented by John McCarthy in 1958 for solving non-numeric problems and was based on three main pillars: the algebra of list structures, lambda calculus, and the theory of recursive functions. For a long time, LISP was used exclusively by a narrow circle of specialists in artificial intelligence. But, starting from the 80s of the last century, LISP began to gain momentum and is now actively used, for example, in AutoCad and Emacs.
What is the difference between LISP and traditional programming languages? Consider the key features :
- Forms of representation of programs and processed data in LISP are identical and are list structures. In this connection, several interesting possibilities open up, for example, processing by a program of other programs. Not to mention the versatility, extensibility, and scalability of the syntax itself. The LISP kernel, written in LISP, takes up less than 200 lines, and the PROLOG interpreter takes up just over 50 lines.
- The implementation of lists allows you not to think about memory management, redundancy and the release of cells occurs dynamically. Thus, we can talk about the appearance of the garbage collector in the first versions of LISP.
LISP is not a strongly typed programming language. Today, this will not surprise anyone, but it is worth recalling that at the initial stages this concept was opposed to the strictly typified Fortran. - Prefix notation provides ample opportunities for parsing expressions, and also provides the ability to use a single list context for programs and data.
- Using a huge number of brackets. That is why, along with the traditional decoding LISP (LISt Processing), there is Lots of Idiotic Silly Parentheses.
- We should not forget about the existence of LISP-machines - computers, the architecture of which is optimized for the effective execution of programs in the LISP language. LISP-machines are not very common, according to some reports their number in the whole world does not exceed 10,000. (As far as I know, in Ukraine there is not one. Personally, I have seen only one in my life - at the University of Bucharest, actively used by students for laboratory work) . LISP machines from the Xerox Research Center have become the progenitors of some common ideas and technologies: garbage collection, laser printing, multi-window systems, etc.). I hope I have a chance to talk about this in more detail in one of the next issues.
Data types
Traditionally, LISP considers two types of atoms : symbols and numbers. Symbols can indicate numbers, strings, complex structures, functions, and other objects. The restrictions on character names depend on the dialect used, but most of them impose virtually no restrictions on the characters used in the names. Also, again in most dialects, character names are not case sensitive.
Some characters have a special purpose - these are constants, built-in functions, T (true, true) and NIL (false, false).
Numbers , unlike symbols, cannot represent other objects, so a number is always a constant number. A bit later we will consider types of numbers in LISP.
Symbols and numbers represent the simplest LISP objects — atoms. The second main data type is point pairs, which are syntactically expressed as follows:
<точечная пара> ::= (<атом | точечная пара>.<атом | точечная пара>)For example, point pairs are expressions:
(a.b), (a.(b.c)), ((a.b).(c.NIL)).Atoms and point pairs are combined under the general name S-expressions (S-expression, symbolic expression). A special kind of S-expression is a list, expressed as follows: NIL in most cases is defined as an empty list, in which case the list definition can be rewritten as follows:
<список> ::= NIL | (.<список>) <список> ::= <пустой список> | (<голова>.<хвост>)
<пустой список> :: = NIL
<голова> ::=
<хвост> ::= <список>.
Wings, legs ... Main tail
Both head and tail are key concepts in the LISP list context. The first element of the list is called the head of the list, all other elements are called the tail. To work with the head and tail, there is a set of basic functions, discussed a little below.
An empty list is equivalent to a pair of empty brackets:
NIL <-> ().
A non-empty list consisting of elements a1, a2, a3 ... in accordance with the rules for writing S-expressions can be written as follows:
(a1.(a2.(a3…))) <-> (a1,a2,a3…)In LISP, a list can also be written with a sequence of elements enclosed in brackets and separated by spaces. By and large, a list is a multi-level data structure for which a sequence of opening and closing brackets is archived.
List items can be atoms and lists, including an empty list. For example, () is an empty list, and (NIL) is a list consisting of one NIL element - which is equivalent to (()).
It should be understood that the usual syntax of S-expressions can be used along with list syntax, for example, the following expressions are equivalent:
(a.(b.nil)), (a b.nil), (a b nil), (a b)If anyone is interested, it will be possible to talk about the internal representation of lists in memory. This is a completely independent topic both in terms of interest and volume.
Key Functions and Predicates
LISP has a fairly small set of primitive functions that provides full-featured list processing. In the context of list structures, these functions are analogous to basic arithmetic operations and form a certain system of rules to which absolutely all symbolic calculations are reduced.
Traditionally, the basic functions include QUOTE, CAR, CDR, CONS, ATOM, EQ.
QUOTE function
First, consider the QUOTE function, which is designed to block the evaluation of an expression. The easiest way to demonstrate the operation of this function is with a simple example: The QUOTE function can be written shorter:
(+ 5 10) -> 15 ; происходит вычисления выражения 5+10 и вывод результата
(quote (+ 5 10)) -> (+5 10) ; вычисление блокируется
‘(+ 5 10) -> (+ 5 10) ; ‘ – равноценно quote
CAR function
Designed to get the first element of a point pair (or the head of a list). Using this function is possible only in a list context, using for an atom will lead to an error.
car (list) -> S-expression.
A few examples: For convenience, the head of an empty list is NIL.
(car ‘(a b c)) -> a
(car ‘(a)) -> a
(car ‘a) -> ERROR: a is not a list
(car ‘(nil)) -> nil
(car nil) -> nil
(car ‘(nil a)) -> nilFuntion CDR
Designed to get the second element of a point pair (or the tail of a list). Using this function is possible only in a list context, using for an atom will lead to an error.
cdr (list) -> list The
tail of the list is the entire list without the first element. If the list consists of one element, the tail will be NIL. For convenience, nil is also considered the tail of an empty list.
Some examples: CAR and CDR functions are implemented in all LISP dialects, but in some synonyms have been created for them: FIRST and REST, HEAD and TAIL).
(cdr ‘(a b c)) -> (b c)
(cdr ‘(a)) -> nil
(cdr ‘a) -> ERROR: a is not a list
(cdr ‘(a (b c))) -> ((b c))
(cdr ‘(nil a)) -> (a)
(cdr ()) -> nilCONS function
Designed to create a new list from the head and tail arguments passed to it:
cons (s-expression, list) -> list
For example: In fact, the CONS function is the antipode of the CAR and CDR functions:
(cons ‘a ‘(b c)) -> (a b c)
(cons ‘a nil) -> (a)
(cons nil ‘(b c)) ->(nil b c)
(cons nil nil) ->(nil)
(cons ‘(a b) ‘(c)) ->((a b) c)(cons (car '(a b c)) (cdr '(a b c))) -> (a b c)ATOM function
ATOM and EQ are predicates - i.e. functions that check whether the argument matches a certain property and return T or NIL depending on the success of the check.
The ATOM predicate checks if the object passed as an argument is an atom:
atom (S-expression)
For example:
(atom ‘a) -> t
(atom ‘(a b c)) -> nil
(atom ()) -> t ;Т.к. пустой список равен nil, а следовательно атомарен
EQ function
A predicate that verifies the identity of two characters.
eq (atom, atom)
Examples: Remember that the predicate EQ applies only to atomic arguments and cannot be used for lists. Also, do not use EQ when comparing numbers. More general than EQ is the EQL predicate , which allows you to compare the same type of numbers: Even more common for numbers is the predicate = , which allows you to compare the values of numbers of different types: More common for lists is the EQUAL predicate , which allows you to compare the identity of two lists: The most common predicate is EQUALP , allowing you to compare arbitrary objects.
(eq ‘a ‘b) -> nil
(eq ‘a ‘a) -> t
(eq ‘a (car ‘(a b)) -> t
(eq () nil) -> t
(eq 1.0 1.0) -> nil
(eql 1.0 1.0) -> t
(eql 1 1.0) -> nil
(= 1 1.0) -> t
(equal ‘a ‘a) -> t
(equal ‘(a b) ‘(a b)) -> t
Null function
NULL checks whether the object passed as an argument is an empty list:
For example: Judging by the last two examples, we can conclude that the NULL function can also be used as a logical negation. For the same purpose, the predicate NOT exists in LISP.
(null ‘()) -> t
(null ‘(a b c)) -> nil
(null nil) -> t
(null t) -> nil
What's next?
I hope I could be interested. Next time I plan to talk about existing LISP dialects (although university XLisp will be enough at first), less commonly used core functions, folding CAR and CDR into something like CAAAADDAAR, and defining your own functions. Later - recursion, control structures, scope, input-output. Even later - if we don’t get tired - about functionals, macros, character properties and closures. And of course, about what the public will ask.
See you!
PS Criticize, but not too much, publish for the first time :)