logging in or signing up LISP AI zerohenyo Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 113 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: September 20, 2010 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... By: mashaelsaleh (12 month(s) ago) thank you Saving..... Post Reply Close Saving..... Edit Comment Close By: shilpasalgiya (15 month(s) ago) i want this presentation Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript The Roots of Lisp : The Roots of Lisp In 1960, John McCarthy published a remarkable paper in which he did for programming something like what Euclid did for geometry. He showed how, given a handful of simple operators and a notation for functions, you can build a whole programming language. He called this language Lisp, for “List Processing,” because one of his key ideas was to use a simple data structure called a list for both code and data. Slide 2: Lisp as a model for programming is tending to become in our own time. As computer have grown more powerful, the new languages being developed have been moving steadily toward the Lisp model. 1. Seven Primitive Operators : 1. Seven Primitive Operators An expression is either an atom, which is a sequence of letters (e.g. foo), or a list of zero or more expressions, separated by whitespace and enclosed by parentheses. foo () (foo) (foo bar) = list of one element (a b (c) d) = list of four elements Slide 4: In arithmetic the expression 1 + 1 has the value 2. Valid Lisp expressions also have values. If an expression e yield v we say that e returns v. Our next step is to define what kinds of expressions there can be, and what value each kind returns. Slide 5: If an expression is a list, we call the first element the operator and the remaining elements the arguments. We are going to define seven primitive (in the sense of axioms) operators: quote, atom, eq, car, cdr, cons, and cond. Quote : Quote 1. (quote x) returns x. For readability we will abbrebriate (quote x) as ‘x. > (quote a) a >’a a > (quote (a b c)) (a b c) Atom : Atom (atom x) returns the atom t if the value of x is an atom or the empty list. Otherwise it returns (). In Lisp we conventionally use the atom t to represent truth, and the empty list to represent falsity. > (atom ‘a) t > (atom’ (a b c )) () > (atom’( )) t Slide 8: Now that we have an operator whose argument is evaluated we can show what quote is for. By quoting a list we protect it from evaluation. An unquoted list given as an argument to an operator like atom is treated as code: > (atom (atom ‘a)) t Slide 9: Whereas a quoted list is treated as mere list, in this case a list of two elements: > (atom ‘ (atom ‘a)) ( ) This corresponds to the way we use quotes in English. Cambridge is a town in Massachusetts that contains about 90,000 people. “Cambridge” is a word that contains nine letters. Slide 10: Quote may seem a bit of a foreign concept, because a few other languages have anything like it. It’s closely tied to one of the most distinctive features of Lisp:code and data are made out of the same data structures, and the quote operator is the way we distinguish between them. eq : eq 3. (eq x y) returns t if the values of x and y are the same atom or both the empty list, and ( ) otherwise. > (eq 'a 'a) t > (eq 'a 'b) ( ) > (eq ' ( )' ( )) t car : car 4. (car x) expects the value of x to be a list, and returns its first element. > (car ' (a b c)) a cdr : cdr 5. (cdr x) expects the value of x to be a list, and returns everything after the first element. > (cdr ' (a b c)) ( b c) cons : cons 6. (cons x y) expects the value of y to be a list, and returns a list containing the value of x followed by the value of y. > (cons 'a '(b c)) (a b c) > (cons 'a (cons 'b (cons 'c ' ( )))) (a b c) > (car (cons 'a '(b c ))) a > (cdr (cons 'a '(b c))) (b c) cnd : cnd 7.(cond (p1 e1)...(pn en)) is evaluated as follows. The p expressions are evaluated in order until one returns t. When one is found, the value of the corresponding e expression is returned as the value of the whole cond expression. > (cond ((eq 'a 'b) 'first) ((atom 'a) 'second)) second Slide 16: In five of our seven primitive operators, the arguments are always evaluated when an expression beginning with that operator is evaluated. We will call an operator of that type a function. 2. Denoting Functions : 2. Denoting Functions A notation for describing functions. A function is expressed as (lambda (p1..pn) e), where p1...pn are atoms (called parameters) and e is an expression. An expression whose first element is such an expression Slide 18: ((lambda (p1...pn) a1...an) is called a function call and its value is computed as follows. Each expression ai is evaluated. Then e is evaluated. During the evaluation of e, the value of any occurrence of one of the pi is the value of the corresponding ai in the most recent function call. Slide 19: > ((lambda ( x) (cons x ‘ (b))) ‘a) (a b) > ((lambda (x y) (cons x (cdr y))) ‘z ‘(a b c)) (z b c) If an expression has as its first element an atom f that is not one of the primitive operators (f a1…an) and the value of f is a function (lambda (p1…pn) e) then the value of the expression is the value of ((lambda (p1…pn) e) a1…an) In other words, parameters can be used as operators in expressions as well as arguments: Slide 20: >((lambda (f) (f ‘ (b c))) ‘ (lambda (x) (cons ‘a x))) (a b c) There is another notation for functions that enables the function to refer to itself, thereby giving us a convenient way to define recursive functions. The notation (label f (lambda (p1…pn) e)) denotes a function that behaves like (lambda (p1…pn) e), with the additional property that an occurrence of f within e will evaluate to the label expression, as if f were a parameter of the function. Slide 21: Suppose we want to define a function (subst x y z), which takes an expression x, an atom y, and a list like z but with each instance of y (at any depth of nesting) in z replace by x. (subst ‘m ‘b ‘ (a b (a b c ) d)) (a m (a m c) d) We can denote this function as (label subst (lambda (x y z) (cond ((atom z) (cond ((eq z y ) x) (‘t z))) (‘t (cons (subst x y (car z)) (subst x y ( cdr z)))))) Slide 22: we will abbreviate f = (label f (lambda (p1…pn) e)) as (defun f (p1…pn) e) so (defun subst (x y z) (cond ((atom z) (cond ((eq z y) x) ( ‘t z))) ( ‘t (cons (subst x y (car z)) (subst x y (cdr z))))))) Slide 23: Incidentally, we see here how to get a default clause in a cond expression. A clause whose first element is ‘t will always succeed. So (cond ( x y) ( ‘t z)) is equivalent to what we might write in a language with syntax as if x then y else z Slide 35: THE END THANK YOU. You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
LISP AI zerohenyo Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 113 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: September 20, 2010 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... By: mashaelsaleh (12 month(s) ago) thank you Saving..... Post Reply Close Saving..... Edit Comment Close By: shilpasalgiya (15 month(s) ago) i want this presentation Saving..... Post Reply Close Saving..... Edit Comment Close Premium member Presentation Transcript The Roots of Lisp : The Roots of Lisp In 1960, John McCarthy published a remarkable paper in which he did for programming something like what Euclid did for geometry. He showed how, given a handful of simple operators and a notation for functions, you can build a whole programming language. He called this language Lisp, for “List Processing,” because one of his key ideas was to use a simple data structure called a list for both code and data. Slide 2: Lisp as a model for programming is tending to become in our own time. As computer have grown more powerful, the new languages being developed have been moving steadily toward the Lisp model. 1. Seven Primitive Operators : 1. Seven Primitive Operators An expression is either an atom, which is a sequence of letters (e.g. foo), or a list of zero or more expressions, separated by whitespace and enclosed by parentheses. foo () (foo) (foo bar) = list of one element (a b (c) d) = list of four elements Slide 4: In arithmetic the expression 1 + 1 has the value 2. Valid Lisp expressions also have values. If an expression e yield v we say that e returns v. Our next step is to define what kinds of expressions there can be, and what value each kind returns. Slide 5: If an expression is a list, we call the first element the operator and the remaining elements the arguments. We are going to define seven primitive (in the sense of axioms) operators: quote, atom, eq, car, cdr, cons, and cond. Quote : Quote 1. (quote x) returns x. For readability we will abbrebriate (quote x) as ‘x. > (quote a) a >’a a > (quote (a b c)) (a b c) Atom : Atom (atom x) returns the atom t if the value of x is an atom or the empty list. Otherwise it returns (). In Lisp we conventionally use the atom t to represent truth, and the empty list to represent falsity. > (atom ‘a) t > (atom’ (a b c )) () > (atom’( )) t Slide 8: Now that we have an operator whose argument is evaluated we can show what quote is for. By quoting a list we protect it from evaluation. An unquoted list given as an argument to an operator like atom is treated as code: > (atom (atom ‘a)) t Slide 9: Whereas a quoted list is treated as mere list, in this case a list of two elements: > (atom ‘ (atom ‘a)) ( ) This corresponds to the way we use quotes in English. Cambridge is a town in Massachusetts that contains about 90,000 people. “Cambridge” is a word that contains nine letters. Slide 10: Quote may seem a bit of a foreign concept, because a few other languages have anything like it. It’s closely tied to one of the most distinctive features of Lisp:code and data are made out of the same data structures, and the quote operator is the way we distinguish between them. eq : eq 3. (eq x y) returns t if the values of x and y are the same atom or both the empty list, and ( ) otherwise. > (eq 'a 'a) t > (eq 'a 'b) ( ) > (eq ' ( )' ( )) t car : car 4. (car x) expects the value of x to be a list, and returns its first element. > (car ' (a b c)) a cdr : cdr 5. (cdr x) expects the value of x to be a list, and returns everything after the first element. > (cdr ' (a b c)) ( b c) cons : cons 6. (cons x y) expects the value of y to be a list, and returns a list containing the value of x followed by the value of y. > (cons 'a '(b c)) (a b c) > (cons 'a (cons 'b (cons 'c ' ( )))) (a b c) > (car (cons 'a '(b c ))) a > (cdr (cons 'a '(b c))) (b c) cnd : cnd 7.(cond (p1 e1)...(pn en)) is evaluated as follows. The p expressions are evaluated in order until one returns t. When one is found, the value of the corresponding e expression is returned as the value of the whole cond expression. > (cond ((eq 'a 'b) 'first) ((atom 'a) 'second)) second Slide 16: In five of our seven primitive operators, the arguments are always evaluated when an expression beginning with that operator is evaluated. We will call an operator of that type a function. 2. Denoting Functions : 2. Denoting Functions A notation for describing functions. A function is expressed as (lambda (p1..pn) e), where p1...pn are atoms (called parameters) and e is an expression. An expression whose first element is such an expression Slide 18: ((lambda (p1...pn) a1...an) is called a function call and its value is computed as follows. Each expression ai is evaluated. Then e is evaluated. During the evaluation of e, the value of any occurrence of one of the pi is the value of the corresponding ai in the most recent function call. Slide 19: > ((lambda ( x) (cons x ‘ (b))) ‘a) (a b) > ((lambda (x y) (cons x (cdr y))) ‘z ‘(a b c)) (z b c) If an expression has as its first element an atom f that is not one of the primitive operators (f a1…an) and the value of f is a function (lambda (p1…pn) e) then the value of the expression is the value of ((lambda (p1…pn) e) a1…an) In other words, parameters can be used as operators in expressions as well as arguments: Slide 20: >((lambda (f) (f ‘ (b c))) ‘ (lambda (x) (cons ‘a x))) (a b c) There is another notation for functions that enables the function to refer to itself, thereby giving us a convenient way to define recursive functions. The notation (label f (lambda (p1…pn) e)) denotes a function that behaves like (lambda (p1…pn) e), with the additional property that an occurrence of f within e will evaluate to the label expression, as if f were a parameter of the function. Slide 21: Suppose we want to define a function (subst x y z), which takes an expression x, an atom y, and a list like z but with each instance of y (at any depth of nesting) in z replace by x. (subst ‘m ‘b ‘ (a b (a b c ) d)) (a m (a m c) d) We can denote this function as (label subst (lambda (x y z) (cond ((atom z) (cond ((eq z y ) x) (‘t z))) (‘t (cons (subst x y (car z)) (subst x y ( cdr z)))))) Slide 22: we will abbreviate f = (label f (lambda (p1…pn) e)) as (defun f (p1…pn) e) so (defun subst (x y z) (cond ((atom z) (cond ((eq z y) x) ( ‘t z))) ( ‘t (cons (subst x y (car z)) (subst x y (cdr z))))))) Slide 23: Incidentally, we see here how to get a default clause in a cond expression. A clause whose first element is ‘t will always succeed. So (cond ( x y) ( ‘t z)) is equivalent to what we might write in a language with syntax as if x then y else z Slide 35: THE END THANK YOU.