Lisp. Atom first
Hi, 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 the new school year, which means I will again have the opportunity to study and, for the second year already, teach LISP students. Another problem, apart from the traditional lack of interest in complex things, is the lack of literature. Anyway, the topic of LISP on the Internet, and even more so in Runet, is poorly covered. Here and on Habre publications quite a few.
I hope this article will appeal to the public and open a series telling about one of the most interesting and least understandable (although far from the brainfuck and far) programming languages - LISP. After all, as it is not banal, one more language - one more life
Let's start with the basic concepts of LISP-a - atoms and lists. A little later, if it is interesting, in the Atom Zero prequel, it will be possible to talk in more detail about the philosophy and causes of the emergence of LISP, as well as about the modern directions of its use.
LISP was invented by John McCarthy in 1958 to solve non-numerical problems and was based on three main pillars: the algebra of list structures, lambda calculus, 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 denote numbers, strings, complex structures, functions, and other objects. Restrictions on the names of characters depend on the dialect used, but most of them impose almost no restrictions on the characters used in the names. In addition, again in most dialects, character names are not case sensitive.
Some characters have a special purpose - they are constants, built-in functions, T (true, true) and NIL (false, false).
Numbers , unlike characters, cannot represent other objects, so a number is always a constant number. A little bit later we will look at the types of numbers in LISP.
Symbols and numbers are the simplest objects of LISP - atoms. The second main data type is point pairs, which are syntactically expressed as follows:
For example, dot pairs are expressions:
Atoms and point pairs are collectively called S-expressions (S-expression, symbolic expression). A special type 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 context list. 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 below.
An empty list is equivalent to a pair of empty brackets:
NIL <-> ().
A non-empty list consisting of the elements a1, a2, a3 ... in accordance with the rules for writing S-expressions can be written as follows:
In a LISP list, you can also write a sequence of elements enclosed in brackets and separated by spaces. By and large, the list is a multi-level data structure for which the sequence of opening and closing brackets is very important.
The elements of the list 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 S-expression syntax can be used along with the list syntax, for example, the following are equivalent:
If someone is interested, it will be possible to tell about the internal representation of lists in memory. This is a completely independent topic in terms of interest and volume.
In LISP, there is a rather small set of primitive functions, which provides a complete list processing capability. In the context of list structures, these functions are analogous to the basic arithmetic operations and form a certain system of rules to which absolutely all symbolic calculations are reduced.
The traditional basic functions include QUOTE, CAR, CDR, CONS, ATOM, EQ.
To begin, consider the function QUOTE, designed to block the calculation of the expression. The easiest way to demonstrate the operation of this function is by a simple example:
The QUOTE function can also be written shorter:
It is intended for receiving the first element of a point pair (or the head of the list). Using this function is possible only in list context; using an atom will result in an error.
car (list) -> S-expression.
A few examples:
For convenience, a head empty list is considered NIL.
Designed to get the second element of a point pair (or the tail of the list). Using this function is possible only in list context; using an atom will result in 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, the tail of the empty list is also considered to be nil.
A few examples:
The CAR and CDR functions are implemented in all LISP dialects, but some of them have synonyms for them (FIRST and REST, HEAD and TAIL).
It is intended to create a new list of the head and tail passed as arguments to it:
cons (s-expression, list) -> list
For example:
In fact, the CONS function is the antithesis of the CAR and CDR functions:
ATOM and EQ are predicates - i.e. functions that check the compliance of the argument with a certain property and return T or NIL depending on the success of the check.
The ATOM predicate checks whether the object passed as an argument is an atom:
atom (S-expression)
For example:
Predicate verifying the identity of two characters.
eq (atom, atom)
Examples:
It should be remembered that the predicate EQ applies only to atomic arguments and cannot be used for lists. Also, do not use EQ when comparing numbers.
More common than EQ is the EQL predicate, which allows you to compare numbers of the same type:
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 predicate EQUAL , which allows you to compare the identity of two lists:
The most common predicate is EQUALP , which allows 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, it can be concluded that the NULL function can also be used as a logical negation. For the same purpose, the NOT predicate exists in LISP.
Hope I could get interested. Next time I plan to talk about existing LISP dialects (although university XLisp will suffice at first), less frequently used basic 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 do not need - about functionals, macros, properties of symbols and closures. And of course, about what the public asks.
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 the new school year, which means I will again have the opportunity to study and, for the second year already, teach LISP students. Another problem, apart from the traditional lack of interest in complex things, is the lack of literature. Anyway, the topic of LISP on the Internet, and even more so in Runet, is poorly covered. Here and on Habre publications quite a few.
I hope this article will appeal to the public and open a series telling about one of the most interesting and least understandable (although far from the brainfuck and far) programming languages - LISP. After all, as it is not banal, one more language - one more life
Let's start with the basic concepts of LISP-a - atoms and lists. A little later, if it is interesting, in the Atom Zero prequel, it will be possible to talk in more detail about the philosophy and causes of the emergence of LISP, as well as about the modern directions of its use.
Short story
LISP was invented by John McCarthy in 1958 to solve non-numerical problems and was based on three main pillars: the algebra of list structures, lambda calculus, 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 :
- The presentation forms of the programs and the data being processed in the LISP are identical and are list structures. In connection with this, several interesting possibilities open up - for example, the processing of other programs by the program. Not to mention the universality, extensibility and scalability of the syntax itself. The LISP kernel written in LISP takes less than 200 lines, and the PROLOGUE interpreter takes just over 50 lines.
- The implementation of the lists allows you not to think about memory management, reserving and freeing 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 it will surprise no one, but it is worth recalling that at the initial stages this concept was opposed to the strictly typed Fortran. - Prefix notation provides ample opportunities for parsing expressions, as well as provides the ability to use a single list context for programs and data.
- Use a huge amount of brackets. That is why, along with the traditional LISP (LISt Processing) decoding, there is also a Lots of Idiotic Silly Parentheses.
- We should not forget about the existence of LISP-machines - computers, whose architecture is optimized for the effective execution of programs in the LISP language. LISP machines are not very common, according to some data, their number in the world does not exceed 10,000. . Xerox LISP machines became the ancestors of some common ideas and technologies: garbage collection, laser printing, multi-window systems, etc.). I hope I will have a chance to talk about this in more detail in one of the next releases.
Data types
Traditionally, LISP considers two types of atoms : symbols and numbers. Symbols can denote numbers, strings, complex structures, functions, and other objects. Restrictions on the names of characters depend on the dialect used, but most of them impose almost no restrictions on the characters used in the names. In addition, again in most dialects, character names are not case sensitive.
Some characters have a special purpose - they are constants, built-in functions, T (true, true) and NIL (false, false).
Numbers , unlike characters, cannot represent other objects, so a number is always a constant number. A little bit later we will look at the types of numbers in LISP.
Symbols and numbers are the simplest objects of LISP - atoms. The second main data type is point pairs, which are syntactically expressed as follows:
< > ::= (< | >.< | >)For example, dot pairs are expressions:
(ab), (a.(bc)), ((ab).(c.NIL)).Atoms and point pairs are collectively called S-expressions (S-expression, symbolic expression). A special type of S-expression is a list, expressed as follows:
<> ::= NIL | (<S->.<>)NIL in most cases is defined as an empty list, in which case the list definition can be rewritten as follows:
<> ::= < > | (<>.<>)
< > :: = NIL
<> ::= <S->
<> ::= <>.
Wings, legs ... Main tail
Both head and tail are key concepts in the LISP context list. 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 below.
An empty list is equivalent to a pair of empty brackets:
NIL <-> ().
A non-empty list consisting of the 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 a LISP list, you can also write a sequence of elements enclosed in brackets and separated by spaces. By and large, the list is a multi-level data structure for which the sequence of opening and closing brackets is very important.
The elements of the list 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 S-expression syntax can be used along with the list syntax, for example, the following are equivalent:
(a.(b.nil)), (a b.nil), (ab nil), (ab)If someone is interested, it will be possible to tell about the internal representation of lists in memory. This is a completely independent topic in terms of interest and volume.
Basic functions and predicates
In LISP, there is a rather small set of primitive functions, which provides a complete list processing capability. In the context of list structures, these functions are analogous to the basic arithmetic operations and form a certain system of rules to which absolutely all symbolic calculations are reduced.
The traditional basic functions include QUOTE, CAR, CDR, CONS, ATOM, EQ.
QUOTE function
To begin, consider the function QUOTE, designed to block the calculation of the expression. The easiest way to demonstrate the operation of this function is by a simple example:
(+ 5 10) -> 15 ; 5+10
(quote (+ 5 10)) -> (+5 10) ;
The QUOTE function can also be written shorter:
'(+ 5 10) -> (+ 5 10) ; ' – quote
CAR function
It is intended for receiving the first element of a point pair (or the head of the list). Using this function is possible only in list context; using an atom will result in an error.
car (list) -> S-expression.
A few examples:
(car '(abc)) -> a
(car '(a)) -> a
(car 'a) -> ERROR: a is not a list
(car '(nil)) -> nil
(car nil) -> nil
(car '(nil a)) -> nilFor convenience, a head empty list is considered NIL.
CDR function
Designed to get the second element of a point pair (or the tail of the list). Using this function is possible only in list context; using an atom will result in 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, the tail of the empty list is also considered to be nil.
A few examples:
(cdr '(abc)) -> (bc)
(cdr '(a)) -> nil
(cdr 'a) -> ERROR: a is not a list
(cdr '(a (bc))) -> ((bc))
(cdr '(nil a)) -> (a)
(cdr ()) -> nilThe CAR and CDR functions are implemented in all LISP dialects, but some of them have synonyms for them (FIRST and REST, HEAD and TAIL).
CONS function
It is intended to create a new list of the head and tail passed as arguments to it:
cons (s-expression, list) -> list
For example:
(cons 'a '(bc)) -> (abc)
(cons 'a nil) -> (a)
(cons nil '(bc)) ->(nil bc)
(cons nil nil) ->(nil)
(cons '(ab) '(c)) ->((ab) c)In fact, the CONS function is the antithesis of the CAR and CDR functions:
(cons (car '(abc)) (cdr '(abc))) -> (abc)ATOM function
ATOM and EQ are predicates - i.e. functions that check the compliance of the argument with a certain property and return T or NIL depending on the success of the check.
The ATOM predicate checks whether the object passed as an argument is an atom:
atom (S-expression)
For example:
(atom 'a) -> t
(atom '(abc)) -> nil
(atom ()) -> t ;.. nil,
EQ function
Predicate verifying the identity of two characters.
eq (atom, atom)
Examples:
(eq 'a 'b) -> nil
(eq 'a 'a) -> t
(eq 'a (car '(ab)) -> t
(eq () nil) -> t
It should be remembered that the predicate EQ applies only to atomic arguments and cannot be used for lists. Also, do not use EQ when comparing numbers.
More common than EQ is the EQL predicate, which allows you to compare numbers of the same type:
(eq 1.0 1.0) -> nil
(eql 1.0 1.0) -> t
Even more common for numbers is the predicate = , which allows you to compare the values of numbers of different types:
(eql 1 1.0) -> nil
(= 1 1.0) -> t
More common for lists is the predicate EQUAL , which allows you to compare the identity of two lists:
(equal 'a 'a) -> t
(equal '(ab) '(ab)) -> t
The most common predicate is EQUALP , which allows to compare arbitrary objects.
NULL function
NULL checks whether the object passed as an argument is an empty list:
For example:
(null '()) -> t
(null '(abc)) -> nil
(null nil) -> t
(null t) -> nil
Judging by the last two examples, it can be concluded that the NULL function can also be used as a logical negation. For the same purpose, the NOT predicate exists in LISP.
What's next?
Hope I could get interested. Next time I plan to talk about existing LISP dialects (although university XLisp will suffice at first), less frequently used basic 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 do not need - about functionals, macros, properties of symbols and closures. And of course, about what the public asks.
See you!
PS Criticize, but not too much, publish for the first time :)
Source: https://habr.com/ru/post/65791/
All Articles