Today, I want to know some of the use of the Lisp language, including what it is used, what is the syntax, searched by Baidu, find an article, go http://blog.9cbs.net/windoze
Lisp is a historic language. The full name is List Processor, which is "table handling language", which is a language that begins in John McCarthy in 1958. Many languages and many languages such as Algo, such as Algo, such as Algo, such as Algo, have some slightly insignificant purposes, or only in some specific occasions, and now I am still known to have the remaining Fortran and Cobol. But LISP, not only did not recession over time, but in turn, once again, it has been glowing out of youth, SchEME, ML, ML, and other languages from Lisp, even more than many old stars. So where is this mysteriest in this evergreen?
If you have accessible C / C , Pascal these "process language", Lisp may make you feel very unusual, first attract you eyeball (or let you feel confusing) must be an abnormal bracket in the LISP program Of course, from now on the point of view, this design is indeed a lot of programs, but considering the computer handling capacity of the May 190s, the design of the simplified language itself is in the case.
The basic syntax of Lisp is very simple. It doesn't even reserve the word (some language may have any objection to this, don't be afraid, I listen to you), it only has two basic data, only one basic syntax structure is expressing The formula, and these expressions are the program structure, but as the simplest play of rules has the most complex changes, LISP uses the most basic language structure definition to complete other languages, the most complex functionality.
Less nonsense, now let's take a look at the basic elements in the Lisp language.
The expression of LISP is an atom (Atom) or a table (List), atom (Atom) is an alphanumeric sequence, such as ABC; Table is a sequence consisting of zero or more expressions, and the expression is separated between expressions. Open, put in a pair of parentheses, such as:
ABC () (ABC XYZ) (A b (c) d)
The last table is composed of four elements, where the third element itself is also a table.
As the calculation expression 1 1 value 2, the expression in the LISP also has a value, if the expression e is Valent V, we say that E returns V. If an expression is a table, then we call the first element in the table, and the rest of the elements are called arguments.
Just like five axioms in the geometric world of Ou Ri, we are here to give 7 axioms in the LISP world (basic operator):
(Quote X) Returns x, we are bused as' x (atom x) When X is an atom or empty table, returns atom T, otherwise it returns a blank table (). In the LISP, our habits are true with atom T true, while empty tables () indicate false. > (atom 'a) T> (atom' ()) (atom '()) T Now we have the first operator that needs to be required, let's take a look at the Quote operator. The role - A table in Quote (quote), we avoid it to be evaluated. An untruritable expression is used as an argument, and ATOM will treat it as code, for example:> (Atom 'a)) T Anti-one is referenced in the table is only considered to be a table> (atom' (atom 'a) () Quote It looks somewhat strange, because you are difficult to find similar concepts in other languages, but this feature is the most distinctive characteristic - code and data using the same structure, and We use quote to distinguish them. (eq xy) When the value of x and y is the same or the T, EQ '()> (EQ' a 'b) ()> (EQ' (EQ ') is returned when the value of X and Y is the empty list. ) '()) T Next chapter, we will explain the operators and conditional operators related to the table, and the basic element of the LISP program.
A episode we told the top three of the seven axioms of Lisp world. This episode went to the remaining four.
The first is three table operations
(Car X) Requirement X is a table that returns the first element in X, for example:> (CAR '(ab)) A (CDR X) also requires x being a table, it returns to X to remove the first one Meeting of all elements outside the element, for example:> (CDR '(abc)) (CONS XY) Requirements Y is a table, it returns a table, the first element of this table is X, after Yes, all elements in Y, for example:> (CONS 'A' (BC)) (ABC)> (CONS 'C ()))) (ABC)
Seeing this here, you may ask, why didn't get the operator of the elements in some other location outside the table, don't worry, wait until the function and recursive you know the people, you will know what to do, Maybe you have already thought about it now?
The next thing to introduce it to everyone is a basic function that constitutes program logic ... Condition branch, in Lisp, it is completed by the COND operator, Cond is the last one of the seven axioms is also the most complex one (European The last axiom of Reid is like it is:
(COND (P1 E1) (P2 E2) ... (PN EN))
The P1 to PN is the condition, E1 to EN is the result, and the COND operator requests the P1 to PN to the PN, until the first value is a PN PN (still remember?), at which time the corresponding E is used as the entire expression. The value of the formula is returned, for example:
> (((((EQ 'a' b) 'first) ((atom' a) 'second) Second
Ok, so, we already have all the basic actions in the LISP world, we can start building the rules of the whole world.
In these seven operators, in addition to Quote and Cond, the expression that starts with other five operators always wants to evaluate it, and then produces the result, we call such an expression to function. .
On the last episode, we talked about "functions". In fact, this concept has already been learned in junior high school mathematics, and a function is nothing more than the corresponding relationship of the argument to the value, the same in Lisp. The function in the LISP is defined in the previous section (fast answering: Who remembers please raise your hand), use the following form to describe a function in the LISP:
(Lambda (P1 P2 ... PN) E)
Among them, PI is atom, referred to as parameters in the function, E is an expression, which is a function body.
The way to call a function is as follows:
((Lambda (P1 P2 ... PN) E) A1 A2 ... AN)
Among them, AI is expressive, according to our conventions, called inform.
The calling process of the entire function is as follows: Each expression AI (inactive) first evaluates, and then evaluates these first paragraphs, and the final result is the return value of the entire expression.
If an expression of the first element is an atom, it is not a basic operator (that is, the 7 we have mentioned), such as:
(f A1 a2 ... an)
And the value of f is a function (lambda (p1 p2 ... pn) e), the above expression is equivalent to
((Lambda (P1 P2 ... PN) E) A1 A2 ... AN)
After reading this paragraph, you may have a little dizziness, go to the window to do a few deep breath, then come back to do this, see what the result of this expression is?
((Lambda (f) (f '(B C))) (Lambda (X) (CONS' A X)))
If you got out, then continue to see it down, otherwise you will read more than a few words, and enter the above practice to a text editor that can automatically match the braces.
Here I plan to insert a few sentences, there may be many people have already seen this lambda, but it is not too might be in the LISP (if such words, you should not use this "entry", isn't it?) In Python, in Python, the Python brochure is just a stroke. He probably said: "Use the lambda word because it is similar to a syntax structure in the Lisp language." Ok, we now Let's take a look at the true origin of Lambda's allusions.
The word Lambda comes from the Lambda calculation theory. What is lambda? For the present, this concept is just "function", but for the age of Lambda calculation theory, it is a revolutionary innovation. The Lambda calculation theory is too complicated, and as an introduction to LISP, it is discussed that it has been completely deviated from the subject, but another concept of it proposed - high order function - is important in Lisp language The status, even can be said to be the main reason for Lisp.
As the "high-order derivative" is the "derivative of the derivative", the so-called high-order function is actually a "function of the function" (high teacher, forgive me). That is, a function itself is used as an argument of another function ("Functor" in modern C is actually an implementation of high-order functions in C ). The appearance of the high-order function, enhances the "function" to the status of the programming language to a "first-class citizen", you can operate a function like any basic data type, transform it, pass, how to toss.
Let's go back to the topic and continue to discuss the functions in the LISP. We can see that, so far, our functions have no names, the function can have no name, that is, the anonymous function is another major feature of Lisp, Lisp can let The programmer peels the data and name, which is a luxury that is not allowed to enjoy many other programming languages. The function does not have a problem, that is, you can't call itself in the function (OK, I know there is Y combination, but this is a introduction article), so Lisp provides a form that allows you to use one Identifier to reference functions:
(Label F (lambda (p1 p2 ... pn) e))
This expression is equivalent to the previous simple lambda expression, but all f appearing in E will be replaced with the entire Lambda expression, which is recursive.
At the same time, LISP provides it with a simple form:
(Defun f (p1 p2 ... pn) e)
You can start writing your first useful Lisp program, what do you plan to write? (No matter what, as long as hello world is good)
Next episode, we will give some common functions.
Lisp's grammatical elements have been basically discussed in the first few episodes, compared to c # or java hundreds of Specification, it may be simple to make you surprised, but great things are always simple, isn't it? Now let's review the content mentioned in the previous episode, first mention a few questions:
Since the Cond is conceptually equivalent to the IF statement in the process language, how should I describe the ELSE branch relative to if in the COND expression? How to express "repetition" in Lisp in (we have learned)? Or can you write a Foreach loop function?
(Note: Don't ask where input and output functions or arithmetic logic, they are all incredible things ...)
This focus, we will describe several common functions and give their simple implementation
First, answer questions in the first episode: How to take the second, third or nth element in a table?
Some readers may have already thought that the second element can be used as the following form:
(Car (CDR X))
Similarly, take the third element is this:
(CAR (CDR (CDR X)))))
In fact, this combination is often used in LISP. For convenience, LISP provides a general mode - CXR, where x is a sequence of A or D, a combination of CAR and CDR, such as:
> (CADR '((A b) (C D) E)) (C D)> (CADDR' ((C D) E)) E> (CDAR '((A b) (C D) E)) (B)
In addition, use (List E1 E2 ... En) to represent (CONS E2 (CONS EN ') ...)))))
> (CONS 'A (CONS' C))))))) (A B C)> (List 'A' B 'C) (A B C)
Now we define some new common functions, I suggest you think about it, don't hurry to see the implementation I give.
(Note: Some functions already exist in the Common Lisp, so if you want to test, give them a name)
(NULL X), test whether X is empty. For example:> (NULL 'A) ()> (NULL') T (AND x y), logic, when and only when X and Y are not empty tables, returns to 't, otherwise returns a blank table. > (AND 'A' B) T> (AND (atom 'a) () (NOT X), logic is not, returns' t when X is empty, otherwise the empty table is returned. (Someone asked me where OR?), For example:> (NOT (NOT (EQ 'A' B)) T (Append XY), connects two tables x and y, pay attention to it with CONS and LIST The difference is different. For example:> (append '()' (xy)) (XY) (PAIR XY), the X and Y are the same tables as two lengths, PAIR generation One table, where each element is an element pair in the corresponding position in the X and Y, the return value of this function is similar to the concept of MAP or Dictionary in other languages. For example:> (Pair '(ABC)' ((AX) (BY) (CZ)) (Assoc XY), where x is an atom, Y is a table returned by Pair, Assoc in Y Find element pairs of the first left element X and return. For example:> (Assoc 'a' ((by))) x> (Assoc 'a' ((A (Foo Bar) (BY) (BY))) (Subst XYZ), The atoms Yes appearing at any level in Table Z are replaced with expressions X. For example:> (subst '(x y)' b '(A B (A B C) D)) (a (x y) (a (x y) (a (x y) c) D) The simple implementation of these common functions is given below:
(Defun NULL (X '))) (COND (Cond (' t '())))))))))))))))))))))))))))))))))) Defun not (x) ('t' t)))) (COND ((NULL X) Y) ('T (CAR X) (Append (CDR X) )))))))))))) (((NULL X) ((NULL Y) '()) ((NOT (NOTM Y)) (NOT (Atom Y))) CONS (CAR Y))))))))))))))))))))))))))))))))))) (Cond ((CAAR Y) (CADAR Y) T (ASSOC X (CDR Y)))))))) (COND (((((((((((((((((Subst XY (Subst XY (CAR (CAR) Z)))))))))))) If you see here, you haven't halo, indicating that your nerves are indeed strong. Note How to express "repetition" in these examples, in Lisp, the most common repetition is not true, but recursive, this is also a common feature of most functional languages - The nested and recursive of the function constitutes the entire program logic.
This part of the content allows you to truly feel the characteristics of Lisp, compared with procedure to write process language, write Lisp programs require a completely different way of thinking, perhaps this is the true truse in the Lisp language for decades. Reason.
Understand this part, the next episode we will take the power of LISP, we will write a LISP interpreter with LISP. If you haven't seen this program before, I guarantee that it will be surprised.
The last episode we have seen a rough appearance of a LISP program. In the end of the article, I mentioned that this episode will write a LISP interpreter with lisp, in fact, this interpreter is not too long, although it may be you The longest one has seen so far.
I have a bit can't wait, let us first look at the whole program, then explain:
(Cond (ASSOC EA) ((CAR E)) (Cond ((CAR E) 'Quote) ((CADR E)) ((EQ (CAR E) 'atom (EVAL (CADR E) a))))) ((EQ (CAR E)' EQ) (EQ (EVAL (CADDR E) a)))) ((EQ (EQ) e) 'car) ((EVAL (CADR E) a))))) ((EQ (CAR E)' CDR) (CDR (EVAL E) A))))))))))))) ((EVAL E) a)))))))))))))))))))) ((EVAL E) A))) ((EQ (Car E) 'CONS) CONS (EVAL (CADDR E) a))))))) ((EQ (CAR E) 'COND) (EVCON (CDR E) A)) (' T (EVAL (CAR E) ) a) (CDR E)) a)))))))))))))) (EQ (CAAR E) (CDR E)) (CAD (Cadar E) (CAR E)) A ))) ((CAAR E) 'LAMBDA (Defun Evcon (CA) (CAAR E))))))))))))))))) (EVAL (CAAR C) a)) ('T (EVCON (CDR C) a)))))))))))))))))))))))))))))))))))))))))))))) ((NULL M) '()) (' T (EVLIS (CDR M) A)))))))))))))))))))))))))))))))))))))))))))))))))))) (Note: There may be readers have found that Lisp is not Ask you to define it before using the function)
The entire program contains three functions, the main function we follow the practice of Lisp (and Python, Perl), called it Eval, which is the skeleton of the entire program. Eval definitions are longer than any of our previous functions, let us consider how it works.
EVAL has two independent variables: E is the expression of the required value, A is a table consisting of a value assigned to the atom, which is a bit icon function call in a bit. This form is called context, which is to construct and search for this table, we wrote Pair and Assoc in the previous chapter.
EVAL's skeleton is a COND expression with four clauses. How to evaluate the expression depends on its type, the first branch processing atom, if E is atom, we look for its value in the context:
> (EVAL 'X' ((x a) (y b))) a
The second branch is another COND that handles the expression of (a), where A is atom. This includes all basic operators, each corresponding branch.
> (EVAL '(EVAL' (CONS X ')' ((XA) (YB))) (ABC) These branches (except for quote) Call EVAL to find the value of the argument.
The last two branches are more complex. In order to seek the value of a COND expression we call a secondary function called EVCON. It recursively evaluates the COND branch and finds the first element returns the clause of T, if such a clause is found, it returns the second element of this branch.
> (EVAL '(COND ((Atom x)' Atom) '((x' (a b))))) List
The last part of the second branch handle function call. It replaces the atom as its value (it should be a lambda or label expression). The resulting result expression is then evaluated. then:
(Eval '(f' (b c)) '((F (CONS' A X))))))))
Change to:
(EVAL '((CONS' A X)) '((F (lambda (x))))))))
It returns (A b c)
The last two COND branches of EVAL process the first element is the function adjustment of Lambda or Label. In order to evaluate the Label expression, first press the function name and the function itself into the context, then call EVAL to evaluate the expression of lambda in an internal, namely:
(Eval '(Label Firstatom (Cond (ATOM X)))))))))))))))))))))))) ))
Become
(Eval '(Cond (atom x) x))))))))))))))))))))))))))))))) ((Label Firstatom (Lambda (x) (Cond ((Cond " x) x) ('T (FirstTAM (CAR X))))))))))))))))))))))))))))))))))))
Finally returned A.
Finally, the expression of EVLIS ((P1 P2 ... PN) E) A1 A2 ... AN) is adjusted to obtain the value corresponding to the variable (A1 A2 ... A). (V1 V2 ... VN), add (P1 V1) (P2 V2) ... (PN VN) to the context, then evaluate the E. then:
(EVAL '(Lambda (CDR Y))' A '(B C D))' ())
Change to:
(Eval ')' ((x a) (Y (B C D))))))))
Finally returned (a c d).
Telling such a large article, if you understand, you have understood the basic programming and ideas of Lisp or even FP, then we wrote a long program to do what?
We have got a very beautiful computing model here, and the EVAL function actually implements the entire language and uses it we can define any other functions required. In other words, we now have airs' Lisp.
(Note: It can be seen that the grammatical analysis of recursive decline is, because it means you can use dozens, up to one or two hundred lines of programs to get a complex analyzer, compare Lalr you will more experience)
What should we go below? This issue, please read the reader to find the answer. This series is finally written, very much, I have a lot of strength, because I have never been very good from the small language, sometimes it is difficult to express the meaning of yourself. This time, I am on my own duck.
The history of LISP is very long, it is said to be only the second ancient language only second only. For Fortran, the negative evaluation given by the language is much more than the frontal evaluation, even in many cases as a brightened textbook as a programming language; but lisp is just the opposite, it has been greatly praised by people as an excellent work. These people include famous computer scientists, inventors of Smalltalk --aran Kay.
There is a rumor, it is said that McCarthy wanted to drag the grammar design of this language. After he finished some interesting things, he went back to give this Lambda-based language-based atrial language plus some mathematicians. The familiar grammar, but his student discovered that writing a program in an abstract syntax that has not yet defined a formal syntax, and it feels very good, so McCarthy simply decided not to define the syntax of the Lisp. Until now, the rules worth mentioning in the "grammar" definition of Lisp seem to have only one "brackets to be paired", and others are all specified in "Semantic".
In this way, it is of course not a price, soon, Lisp appears the first branch scheme. This language is designed by Guy Steler, Jr. and his teacher Gerald Sussman. The two most beginning work is to improve Lisp, and they share the LISP by Dynamic Scope into Lexical Scope. All languages that are almost familiar with today are Lexical Scope. Later, they introduced the concept of Continuation into Lisp, so a new language was born.
Subsequently, SUSSMAN introduced some other concepts in Lexical Scope and Scheme, which established the standard of Common Lisp, and SUSSMAN I have always been the main force of Common Lisp.
As an earliest FP language, the LISP is of course its shortcomings. The most illness is parentheses, so many of the FP languages that appear appear attempt to use additional syntax to clearly describe the program, the most famous It is Haskell (maybe there is CAML?), Haskell is a "pure" FP language. In Haskell, variables cannot assign values, no loops, and no program flow, everything is a function.
(Note: I personally think that I want to understand the essence of FP, and I seem to be more suitable with Haskell.)
In recent years, with the further popularity of FP, many ordered languages have gradually joined FP components, typical as "functor" in C , if you have used STL or Boost, you will find that using functor can complete a lot of incredible Features. As far as my personal experience, Functor's most intensive application is in the Boost.Spirit library, which allows you to construct a complex syntax analyzer with a large Parse / Match functionor.
Familiar with a functional language and experience it with your heart. After you transform your way of thinking, you will find even if you are the original orientation you can play a bigger power.
references:
"Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part1." Communication of the ACM 3: 4, April 1960. "The Art of the Interpreter, or the Modularity Complex (Parts Zero, One, and Two)", Guy Lewis Steele, Jr. And Gerald Jay Susman, Mit Al Lab Memo 453, May 1978. "LISP 1.5 Programmer's Manual", John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, Michael I. Levin. Online Resources :
You can get a free WINDOWS version of the Common Lisp version seems not much, only one CLISP can be thought of: http://clisp.cons.org can be used for Linux's CommON Lisp I know CMUCL and SBCL, URLs : Cmucl: http://www.cons.org/cmucl/sbcl: http://sbcl. SourceForge.Net In addition, a scheme implementation that is widely used in GNOME - Guile is also included in most Linux release in. Friends who are interested in Haskell can go to http://www.haskell.org to find a lot of information about Haskell, at http://www.haskell.org/hugs/ You can download to Windows and Linux / UNIX version Haskell interpreter - HUGS98.
