Artificial Intelligence Using Lisp Programming And Examples
Description:
artificial intelligence lisp programming-“The Ultimate goal of Artificial Intelligence research (which we are very far from achieving) is to build an intelligent human being.” Science Fiction has also been exploring the ultimate goal of Artificial Intelligence (or highlighting the AI researchers dream), by producing novels, and movies, such as Star Wars, Terminator, and Short Circuit, which exhibit intelligent machines. Such endeavors predict to some extent the future of artificial intelligence lisp programming. This dream person can be hypothesized to have certain simple modules, as shown in the following model:
The overall structure of the model is INPUT -> INTERNALS -> OUTPUT, where the INPUT and the OUTPUT represent specialized areas of Artificial Intelligence which we will not be addressing in this course. Our main focus will be on how this information is processed internally, (i.e. INTERNALS) and how intelligent decisions are reached, which exhibit Intelligence.
For this course we will keep the INPUT and OUTPUT modules simply by replacing them with simple text-based inputs and outputs, allowing easy transfer of knowledge from one side to another. This would also relieve us from addressing difficult areas (Vision, Natural Language, Robotics, and Speech processing/generation) which themselves require (as pre-requisites) a thorough knowledge of AI fundamentals.
We can think of this approach as building a box (which includes all the internals) with a primitive form of inputs and outputs, and then later on adding more useful and productive inputs and outputs, which resemble the real humans we are trying to mimic or clone:
What Artificial Intelligence can allow computers to do?
Computers Can Help Planning
Planning systems: route planning, task planning, and of course Robotics:
Computers Can Help Experts Analyze, Diagnose and Design
Expert systems: MYCIN, PROSPECTOR, POEMS
Computers Can Solve Difficult Problems
Mathematical systems: ATLAS, POEMS, and MACSYMA
Computers Can Understand Simple English
Natural language systems: allowing friendly user interfaces.
Computers Can Understand Simple Images
Vision systems: medical image analysis, robots, security systems, satellite images
Computers Can Help Manufacture Products
Robotics: Assembly robots; are controlled and manipulated using AI techniques.
Computers Can Learn from Examples and Precedents
Learning systems: ID3, LEAP, ARM, POEMS
What is Artificial Intelligence?
-
The Handbook of AI, Barr, and Feigenbaum:
AI is the part of computer science concerned with designing intelligent computer systems, that is, systems that exhibit the characteristics we associate with intelligence in human behavior – understanding language, learning, reasoning, solving problems, and so on.
-
Artificial Intelligence and Natural Man, Boden:
Artificial Intelligence is not the study of computers, but of intelligence in thought and action. Computers are its tools because its theories are expressed as computer programs that enable machines to do things that would require intelligence if done by people.
-
Artificial Intelligence, An Introductory Course, Bundy (ed.):
What is AI? … Artificial Intelligence is the attempt to build computational models of cognitive processes, or, to put it another way: in Artificial Intelligence we make computers perform tasks that would be considered intelligent if done by a human.
-
An Introduction to Artificial Intelligence, Charniak and McDermott:
Artificial Intelligence is the study of mental faculties through the use of computational models… AI researchers are trying to create a computer, which thinks.
Artificial Intelligence & Expert Systems
The Goal of AI scientists has always been to develop computer programs that could in some sense THINK, i.e. solve problems that would be considered intelligent if done by a human.
- The major breakthrough in developing intelligent programs came through when the researchers discovered that the problem-solving power of a program comes from the knowledge it possesses, NOT just from the formalisms and the inference techniques.
- That knowledge led to the development of computer programs for special purposes, systems that were experts in some specific problem areas.
Artificial Intelligence Expert Systems
Advantages of Using Expert Systems
Expert Systems (or the general term Knowledge-Based Systems) can be distinguished from other kinds of AI programs:
- Expert Systems deal with domains, which require a considerable amount of human expertise.
- Expert Systems exhibit high performance in terms of speed and reliability in order to be useful tools.
- Expert Systems are capable of explaining and justifying their actions and solutions.
Development of Expert Systems is justified when:
- The task solution has a high payoff.
- Human expertise is being lost over time.
- Human expertise is scarce in a specific domain.
- Expertise is needed in many locations at one time.
- Expertise is needed in a hostile environment.
Life Cycle of Expert Systems
Introduction to Common Lisp
Lisp was originally developed in the early 1960s by John McCarthy and his students at MIT. It was one of the first languages to be aimed at non-numeric computation(i.e. handling symbols such as words, lists of symbols, and lists of lists), as opposed to the numerically-oriented scientific and engineering languages such as FORTRAN. It was also an early example of an interactive language, in which the user could type in program statements for immediate execution (BASIC, Prolog), instead of having to work through separate phases of editing, compiling and running (FORTRAN, Pascal, C). The former aspect made it an obvious candidate for use as an AI language, where arbitrary symbolic manipulations are needed, and the latter aspect led to a particular style of program development, in which programs are put together, tried out and debugged all within a single interactive environment.
List processing languages (LISP is an acronym for LISp Processing) has proved to be singularly appropriate to programming for problem-solving. Fundamental techniques like generate and test, constraint propagation and so on have all been developed within this computational framework. Indeed, there are certain kinds of architectures that would be hard to implement in any other way, because they require the manipulation of programs as if they were data. Such architectures seem to be essential for the design of intelligent systems. List processing languages appear to provide the most elegant and economical way of doing this. Such languages have also made modular and incremental programming far easier to do. Whether one is considering techniques associated with production systems or with the
It is worth pointing out that, though Lisp was aimed at non-numeric computations, the current Common Lisp standard is very strong in numeric computations.
This is another unique quality of Lisp that it allows no distinction between data and programs. That is to say, that data items or lists in Lisp could may as well be programs, which can be executed or evaluated.
quite a different approach of object-oriented schemes, it is hard to see how these would be implemented outside of the context of list processing.
We have used the terms “list processing languages” and Lisp interchangeably, though it is worth pointing out that there were and are other symbolic or list processing languages, such as POP-2, POP-11, Prolog, ML. They have all been used in AI to some extent, and Prolog being the most popular of them all. In fact, in Europe and Japan, Prolog has been as popular as Lisp for AI work.
Prolog shares most of the Lisp’s advanced features, such as interactive environment, programming flexibility, and garbage collection. But again, we need to stress, that if one is going to learn a language, it might as well be one with a growing literature, rather than a dead tongue or one which is just becoming popular. And it goes beyond saying, that Lisp is the most popular language for artificial intelligence programming.
Syntax in Artificial Intelligence lisp programming
S-Expressions
Syntactically, in Lisp, there is only one construct – the (symbolic) S-expression. An S-expression can either be an atom or a list. Examples of atomic (atoms) S-expressions are:
1 2 3 4 5 |
ABC 12 456.9 X1 THIS_IS_A_LONG_ATOM |
Historically, such items were known as “atoms”, but the terminology of Common Lisp (or “Lisp” for short from here on) refers to these as symbols. Lists or parenthesised S-expressions consist of a left-parenthesis, a sequence of zero or more S-expressions, and a right-parenthesis. This recursive definition essentially allows any mixture of atomic S-expressions and parentheses in which the parentheses are properly matched. Examples of lists are:
1 2 3 4 5 |
(A) (1 2 3 4) ( ) (( (A) (B) ) C) (((() () ()))) |
The empty list S-expression “()” is taken as the special atom NIL. This item can also act as the truth value “false” (where as the truth value “true” is represented by all other forms of non-nil S-expression). So all the following forms of NIL refer to the same S-expression (i.e. empty list), but suggest various notational conventions:
1 2 3 |
( ) is the empty list ‘NIL is the symbol named NIL NIL is the truth-value “false” |
All the three notations refer to the same unique internal Lisp item, but writing them in different ways depending on what they are being used for can add clarity to a program. The second one makes use of the extremely convenient quote symbol, which will be dealt with later and which can be seen as an abbreviatory convention.
Upper and Lower Case
Lisp can sometimes seem a little eccentric in its handling of the case of alphabetic symbols. The Steele standard attempts to define a simple consistent approach, based on the idea that the internally stored form of everything is in Upper-case. However, implementations may vary how exactly they let the user see or refer to symbols. This can become very confusing. The best strategy to protect your sanity is to:
- Never wRitE anyThiNg wHose mEANiNg dePends ON its CASE.
- Use quoted strings to refer to file-names or symbols with different cases, from within Lisp, as the original case is preserved. Though, in DOS all file names are taken in Upper-case characters.
Comments in Artificial Intelligence lisp programming
Comments in Lisp are started with a ; character (i.e. semicolon). So a statement of Lisp would be like:
1 |
(+ 5 10) ; sets the symbol a with value 10, this is a comment |
Another way of placing long sections of comments is to enclose lines of text with #| and |# characters. These are basically macro characters, which we will address later on in the course. So a large section of code can be commented out by placing these characters, such as:
1 2 3 4 5 |
#| (setq a 10) (setq b 20) .... other code |# |
Programming in Common Lisp
As mentioned previously, the only construct in Lisp is an S-expression, which can either be an atom or a list. The list S-expression is also used in defining and calling the main programming construct the function (remember the similarity between the data and the programs). The Lisp system has a vast number of built-in functions (system functions), and the Lisp programmer can call these functions directly or can incorporate them into definitions of new functions.
Simple Function Calls
The syntax (notation) for a function call (i.e. the application of a function to a set of arguments) is very simple; Lisp statements are, in general, of the following form:
1 |
function-name <argument-1> ... <argument-n>) |
That is, a left-parenthesis, the function to be used (or called), and various values for the parameters (separated by spaces), and a final right-parenthesis. For example, + and * are built-in functions for performing addition and multiplication respectively:
1 2 |
(+ 5 17) ; would evaluate to 22, and (* 3 4) ; would evaluate to 12. |
Notice that the placing of the brackets is different from that used in other languages, such as Pascal and C++, where the function is placed outside the brackets, and the arguments are separated with commas.
Lisp interpreter follows two simple rules:
1) If the S-expression to be evaluated is an atom then its value is returned. For example if we type in a numeral 7 to the Lisp interpreter’s prompt, we will get the value 7 back, since 7 evaluates to itself. On the other hand if we have a symbol X, with a value 123 assigned to it, then that value will be returned.
1 2 |
> 7 7 |
2) If the S-expression to be evaluated is a list then it is assumed to be a function call (or a macro call, which we will address later, but for the moment assume they are similar to functions). The function definition is recalled from the first item in the list (i.e. the function name), then all the arguments are evaluated, and the function is applied to the evaluated arguments.
For example, if we have:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
> (+ 2 4) ;Lisp will first extract the definition of the function + and 6 ;then evaluate 2 and 4, which return 2 and 4, and then + is > ;applied to 2 and 4. > (+ X Y) ;If we have two symbols X and Y, with values 12 and 22 34 ;respectively, then for the S-expression (+ X Y) we will get > ;34. In this case the function + was applied to the evaluated ;values of X and Y, which turned out to be 12 and 22. > (* 8 ( + 3 7) ) ;evaluates 8 and (+ 3 7), then evaluates * with arguments 80 ;8 and 10, to produce the result 80 > > (* (+ 8 3) (+ 4 ( * 9 2 ) ) ) 242 > |
Symbols
No assignment operator
1 2 3 4 5 6 7 8 9 10 |
> (setq x 10) ;in Lisp x = 10 is performed by setq 10 > x ;x evaluates to 10 10 > (+ x 8) 18 > x ;value of x remains same 10 > hello ;symbol hello being evaluated, has no value Error: Variable has no value. |
Setq does not evaluate the First Argument! Special Function in Lisp
However, the Second Argument is evaluated.
1 2 3 4 5 6 7 8 9 |
> (setq w 20) 20 > (setq z w) ;z is not evaluated, w is evaluated and returns 20 20 ;z is Assigned 20 > (+ 2 (setq x (* 3 4) ) ) ;x is not evaluated, 12 is assigned to x, then 14 ;+ s-expression is evaluated and 2 is added to 12 > x ;x still has value 12 12 |
Function Names and Symbols
The names used to denote functions are not a separate class. They are just Symbols! Like x, y, w, z
Symbols can have some or all of following
Name, a string of characters, such as “a”, “hello”
Value
Function
Property Lists
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
> (hello 2 3) Error: Symbol has no function definition: HELLO > (+ 2 3) 5 > (1+ 20) ;1+ function adds 1 to its argument 21 > (setq 1+ 30) ;setq assigns value 30 to symbol 1+ 30 > 1+ 30 > (1+ 25) ;1+ function adds 1 to 25 26 > (+ 5 1+) ;1+ symbol has value 30 so this S-exp adds 5 to it 35 |
However, assigning values to known functions is generally bad programming practice.
Exiting Lisp and effect on Symbols
1 2 3 4 5 |
> (setq x 20) ;assign x a value 20 20 > x ;x evaluates to its value 20 > (exit) ;exit from lisp environment (or session) |
Start a new session of Lisp
1 2 |
> x ;previous session’s symbols are deleted Error: Variable has no value. |
Lists in common lisp language
1 2 3 4 5 6 7 8 |
(a b c) is a list of three elements, symbols or atoms a, b, c (a (b c) d) is again a list of three elements: a, (b c), and d Symbol b is not element of list. However, (b c) is (((x))) is a list of one element: ((x)) ((a b)) is again a list of one element. > (a b c) ;Lisp tries to get function ‘a’ Error: Symbol has no function definition: A |
To stop Lisp to evaluate a List as an S-Expression, we use quote
1 |
> ( quote (a b c) ) ;Quote is a Special |
The quote is used so extensively in lisp, i.e. forcing lisp not to evaluate arg That a special format is provided to quote
1 2 3 4 5 6 7 8 9 10 11 |
> ‘(a b c) ;Special format of quote fun (A B C) > ‘a ;symbol a has no value a ;but quote returns a without ;evaluating > (setq x ‘(a b c) ) (A B C) ;setq assigns (A B C) to x > (setq x ‘(+ 3 4) ) ;setq assigns (+ 3 4) to x (+ 3 4) |
Car and Cdr
Lisp is a List Processing language, and one of the fundamental tasks that is performed in Lisp is managing/processing/manipulating lists. The Two most common functions used for this purpose are car and
cdr
car Returns first element of list; Current Address Register
cdr Returns rest of list; Current Data Register
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
> (car ‘(a b c) ) A > (cdr ‘(a b c) ) (B C) > (setq x ‘(a b c)) ;car and cdr do not effect the symbol’s values (A B C) ;i.e. they are non-destructive > (car x) A >(cdr x) (B C) > x (A B C) > (car (cdr ‘( a b) )) B > (car ‘((a b)) ) ;((a b)) is a list of one element (a b) (A B) > (car (car ‘((a b)) )) A > (cdr ‘((a b) (c d))) ((C D)) > (cdr ‘((a b) (c d) (e f))) ((C D) (E F)) > (cdr (car ‘((x y) (z d)) ) ) (Y) |
Combination of cars and cdrs is used so frequently that Lisp provides a variety of combinations of cars and cdrs:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
caar same as (car (car ‘((a b)) )) …. caaaar same as (car (car (car (car …. )))) cadadr same as (car (cdr (car (cdr …. )))) …. cddddr same as (cdr (cdr (cdr (cdr …. )))) Hence the following two s-expressions return the same result > (car (cdr (car (cdr ‘((a b c) (d e f)) )))) E > (cadadr ‘((x y z) (d e f)) ) E |
The Empty List
1 2 3 4 5 6 7 8 |
> (cdr ‘(c) ) ; cdr of a one element list in an empty list NIL >’( ) ; empty list is same as NIL NIL > ( ) ; empty list evaluates to NIL NIL |
Cons
To construct a list, the basic function used is cons
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
> (cons ‘a ‘(b c) ) ;cons concatenates first argument to second arg ( A B C) > (cons ‘a ‘(b) ) (A B) > (cons ‘a ‘( ) ) (A) > (cons ‘(a b) ‘(c d) ) ((A B) C D) > (cons ‘x (cons ‘ y‘(z d) ) ) (X Y Z D) > (setq x ‘(a b)) (A B) |
Note that just like car and cdr, cons is also non-destructive, i.e. cons does not effect the values of symbols.
1 2 3 4 5 6 7 8 9 10 11 |
>(setq x ‘a) A > (setq y ‘(b c)) (B C) > (cons x y) (A B C) > x A > y (B C) |
List Construction Functions
Cons is function of two arguments. The second argument should always be a list. Cons return as its value the list obtained by taking the second argument and sticking the first one in front of it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
> (cons ‘a ‘(b c)) (A B C) > (cons ‘x (cons ‘y (cons ‘z nil))) (XYZ) > (cons ‘x (cons (cons ‘y (cons ‘z nil)) (cons ‘d nil))) (X (Y Z) D) > (list ‘a ‘b ‘c) ;list makes list of all elements (A B C) > (list ‘a ‘(b c) ‘d) (A (B C) D) > (append ‘(a b) ‘( c d) ‘(e f)) ;append combines lists (A B C D E F) >(setq x ‘(a b c)) (A B C) >(setq y ‘(x y z)) (X Y Z) > (append x y) (A B C X Y Z) |
Evaluation in Common Lisp
The algorithm employed by the Lisp interface or ‘listener’ can be simplified as:
1 2 3 4 5 |
While not end-of-file do read an S-expression L evaluate L print the result |
The central step of this (evaluate L ) is performed by a system function called EVAL, which executes roughly the following (recursive) algorithm:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
If L is a symbol then If L is numeric then result is corresponding base-ten number else If L currently has value V then result is V else error - unbound variable else If L is a call from a known function F then determine which arguments are to be evaluated, apply EVAL to appropriate arguments, apply F to the accumulated results. else error - undefined function |
For some system functions, some of the arguments are not to be evaluated, (such as setq, quote) but for simple user-defined functions, there is only one option, i.e. EVAL all of them, (though there are ways to circumvent this restriction, and we will get to it later on in the course).
Quote
One function which is particularly useful to allow data items to be passed as arguments without being evaluated is the Quote function. This function take one argument and does not EVAL it, and passes the original item as its result. There is a handy shorthand for (quote …), namely the apostrophe sign. For example,
(Quote Y) is equivalent to ‘Y
(Quote (1 2 3 4)) is equivalent to ‘(1 2 3 4)
List Structures in Common Lisp
Atomic S-expressions are simple labels referring to atomic symbolic items (e.g. numbers, names). The symbol NIL has a special status – it is a symbolic name for the empty list (), and so is both a symbol and a list.
List S-expressions are simple binary trees in structure. Each left parenthesis indicates a level of branching to the left, and each adjacent pair of S-expressions between parentheses indicates a level of branching towards the right. The end of the parenthesized expression corresponds, in the tree, to a right branch pointing to special symbol NIL. The convention is to draw the tree-structures as linked pairs of boxes, where each box indicates one node of the tree, as in the following examples.
Functions in Common Lisp
Simple function definitions can be specified using the Lisp function DEFUN, the format followed by DEFUN is:
1 2 3 4 5 6 |
(DEFUN function-name (<parameter-1> .... <parameter-N> ) <S-expression-1> <S-expression-2> ... <S-expression-N> ) |
Where function-name is an alphanumeric atom, as are the various parameter-names. The sequence of S-expressions constitutes the body of the function. For example:
1 2 3 |
(DEFUN last-name (name) (first (last name)) ) |
This function returns the last name of a name given in a form of a list, so for the following case it returns:
1 2 |
> (last-name ‘(Shahzada fawad)) FAWAD |
Interestingly enough, we have also introduced an odd limitation to our function, as can be seen from the following examples:
1 2 3 4 |
> (last-name ‘(Shahzada fawad)) fawad > (last-name ‘(shahzada)) shahzada |
As is obvious our function is limited by the definition we gave for last-name, it is quite possible that we might change the definition to make it more intelligent by checking the three parts of the name and so on.
Lisp Programming Style
Plan before you program
Use diagrams, pseudo-programs, algorithmic notation, top-down designs, or simple English to organize your thoughts – do not rush straight into writing program text.
Structure your Program into parts
Use functions, procedures, subroutines, etc. not just as an abbreviation for commonly occurring computations – they are useful to structure the program in a readable, debuggable, and maintainable way, even if each such function is called only once.
Use Comments properly
Make comments clear, correct, carefully-phrased, and not just a re-statement of the individual program statements. Give each function a header which says what arguments it takes, what results it returns, and any side-effects it has, etc., plus any general remarks (e.g. it assumes some global variables, or that it cannot cope with certain special cases).
Layout the text
Indentation and well placed blank lines can make the structure (and hence the meaning) of the program more apparent.
Choose names carefully
Variable names, function names, and symbolic labels, etc. should be mnemonics which suggest their purpose (e.g. SUM rather than S), and should not be confusing (e.g. similar to other names, or liable to be mis-typed).
Aim for clarity, not efficiency
Making a program incomprehensible in the hope of saving a few micro-seconds or a small amount of space is rarely worth it. In a high-level language, you are unlikely to know the true effect of the “improvements” on the compiled version. A simpler program is less error-prone, easier to maintain, alter, and understand.
Use symbols, not values
If some particular value is used throughout the program (e.g. the number of data items being processed, the character code for “new-line”), give it a name at the start, and use this name in the program.
Initialize variables
Make sure that starting values are set up. Do not assume that variables will initially be set to some standard value (zero or nil) by the system.
Check input values
Work on the assumption that data will be fed to your program by a total incompetent person, and incorporate tests to see that incoming values are suitable (before they are used). This can avoid accidents like dividing by zero, etc.
Encapsulation and Implementation of hiding
If you have to implement some set of facilities, or some particular kind of data-structure, hide the actual representation behind a whole set of accessing and updating functions. Ask yourself, what does a program have to be able to do to this data-structure? Then implement a function to perform each of these operations. Include even the trivial ones, such as creating a new instance, accessing a field of, printing out, etc. Then the program/programmer using this facility does not need to know anything of how you have implemented the data-type; all that is needed is the name/names of the functions which form the interface, and a note of their individual behavior. This is also a partial answer to the problem of using unpleasant operations (e.g. destructive updates in Lisp, such as nconc etc.) where it seems necessary (for efficiency, or for simplicity of design). If you have to use these methods … hide them.
Structure and simplicity
Keep your functions fairly small. If it doesn’t fit on to a standard monitor screen (INCLUDING COMMENTS, so that you can inspect it all at once), it is too big. In fact, it should be nearer to half a screenful of actual function; that is, no more than about 10 lines of executable code in a function. Keep your functions simple and self-explanatory. Try not to be one of those programmers who have a need to produce large quantities of spaghetti code as a boost to their egos. This urge to establish grandiose pieces of code often manifests itself in students with computer science training who believe this to be a way to impress examiners This is Not. Admittedly, some of these programs actually work, but is it worth staying up all night to do a two-hour programming exercise?
Modularity and Locality
Ideally, a function should be like a separate unit that can be plugged into any program, able to perform exactly the same small task, to meet the same precise specification, in a wide variety of environments (such as managing tables).
All auxiliary variables (other than parameters) should be declared locally and you should not use assignments to global variables for this purpose (as in BASIC or Pascal). There are some cases where a global variable is natural and clear, but using them as all-purpose receptacles is sloppy since it means that there is a chance that the function has some effect on, or is affected by, some totally different function, in a manner which can be worked out only by considering the various possible scenarios involving those global variables.
If you have to use global variables mark them clearly, by putting asterisks around them as part of their name, such as **my-global**
Recursion vs. Iteration
Where a task is naturally recursive (e.g. working down a list doing something to each item) use recursion. Remember that lists have a recursive definition themselves, so the task decomposes immediately into
What to do to NIL
What to do to an atom (not appropriate in some cases)
What to do to the CAR of the list
What recursive call to apply to the CDR
Iteration is a better idea than recursion if there are a very large number of items to be processed (like reading a file of 10000 s-expressions), which might lead to stack overflow. A special case of this is where the repetition is genuinely some sort of top-level loop (like the Lisp listener) which should, after each command return to roughly the same state. Another situation where iteration is worth considering is when you are seriously worried about time and space (remember recursion uses stack space to store last recursive call, before it starts returning values, of course then it remove values from stack).
Avoid free variables if possible
Programmers are often tempted to write functions that consult or alter free (i.e. non-local) variables that are not assumed to be global. That is, the programmer assumed that the function (say G) will always be called from within a function F which has a particular variable X inside it, and so lets the function G access or update that copy of X. If you depend on a function being able to sneak a look at the outer calling environment, then you have to be very careful about the use of that function – it relies on the names used in the calling function, and must always be called from a function which has such variables. Hence, it is not very modular. Either G has no need to consult X, in which case it should not be passed as a parameter; of G does need to consult X, in which case X should be passed as one of its arguments. It is also worth pointing out that such a case will not work on Lisps with different conventions for free variables – for example, Franz Lisp uses a dynamic scoping, whereas Common Lisp uses static (lexical) scoping.
Predicates in Artificial Intelligence lisp programming
Functions which test for a particular property in S-Expressions are called predicates. For example, to check if an s-expression is an atom, we call the predicate atom.This behavior of encapsulation and implementation hiding will be illustrated by the Lisp exercises such as tables.lsp and the ones which follow it.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
> (atom ‘a) T > (atom 8) T > (atom ‘(a b c) ) NIL > (atom (car ‘(a b c) ) ) T We can also check if an s-expression is a list or not by using listp > (listp ‘a) NIL > (listp ‘(a b c) ) T > (listp nil) T > (atom nil) T > (null nil) T > (null (cdr ‘(a) ) ) T |
Some of the key predicates are mentioned below:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Predicate Remarks: Checks if Argument/s Calling S-Exp atom Is an atom (atom ‘a ) listp Is list, i.e. ends with a nil (listp ‘(a b c) ) consp Is dotted pair, does not end with nil (consp ‘(a.b) ) null Is NIL or an empty list (null ‘( ) ) equal Are equal (equal ‘a ‘a ) eq Are equal and at same location (eq x x) eql as eq plus numbers are always same (eql x x) numberp Is a number (numberp 5 ) zerop Is a number and zero “0” (zerop 0 ) oddp Is an odd number (oddp 7 ) evenp Is an even number (evenp 4 ) typep First arg is of second arg type (typep 6 ‘number) member First arg is member of second arg (member ‘a ‘(a b c) ) |
member is an interesting function used for finding out the membership of a list. Member takes two arguments, the second of which should return be a list.The general calling s-expressions are:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
> (member ‘c ‘(a b c d) ) (C D) ;returns the remaining list > (member ‘x ‘(a b c) ) NIL > (member ‘y ‘(x (y) z) ) NIL ;y is not in the top level list > (member ‘(a b) ‘(a b c) ) NIL ;(a b) is not one element of list (a b c) > (member ‘(b c) ‘(a (b c) d) ) ;here (b c) is one element of list NIL ;But it is still not equal. Since (b c) ;is not same as (b c) in (a (b c) d) ;even though symbols b c same but ;list (b c) has different cons cells ;member uses eql > (setq x ‘(a (b c) d) ) > (member (cadr x) x) ;here (b c) is checked in (a (b c) d) ((B C) D) ;Yes it is member here! Can you see why? |
Conditionals in Artificial Intelligence lisp programming
To make decisions and based on those decisions execute proper actions is one of the important aspects of programming languages. Lisp provides this functionality through the Cond function. Cond can have single clause (the simple format) and multiple clauses (the general format). The two formats are as follows:
1 2 3 4 5 6 7 8 |
Simple format (cond (test-S-exp action-S-exp-1 action-S-exp-2 …) ) General format (cond (test-S-exp-1 action-S-exp-11 action-S-exp-12 …) (test-S-exp-2 action-S-exp-21 action-S-exp-22 …) (test-S-exp-3 action-S-exp-31 action-S-exp-32 …) ….. (test-S-exp-n action-S-exp-n1 action-S-exp-n2 …) ) |
To evaluate a cond clause, Lisp evaluates its condition or the test-S-exp, i.e. the first element of the clause. If it evaluates to true, Lisp evaluates the rest of the S-expressions in the clause.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
> (cond ((listp x) (car x)) ;take car of x if it is a list > (defun car-atomp (x) ;lets define a function with cond (cond ((listp x) (atom (car x))) ;calls atom predicate on car of x )) > (car-atomp ‘(a b c)) T > (car-atomp ‘z) NIL > (defun cond-ex1 (x) ;complex cond examples (cond ((listp x) (cons ‘a x)) ((numberp x) (+ 7 x)) )) > (cond-ex1 ‘(b c)) (A B C) > (cond-ex1 12) 19 > (cond-ex1 ‘z) ; we can have default clause NIL |
The following example will demonstrate a default clause in cond plus multiple s-expressions in each clause.
1 2 3 4 5 6 7 8 9 10 |
> (defun cond-ex2 (x) (cond ((listp x) (setq flag ‘list) (cons ‘z x)) ((numberp x) (setq flag ‘number) (+ 7 x)) (T (setq flag ‘neither) nil) )) > (cond-ex2 ‘(b c)) (A B C) > flag LIST |
It is legal to have only one S-expression in a condition clause
1 2 3 4 5 6 7 8 |
> (defun cond-ex2 (x) (cond ((listp x) (setq flag ‘list) (cons ‘z x)) ((numberp x) (setq flag ‘number) (+ 7 x)) ((setq flag ‘neither)) ;Only one s-exp )) > (cond-ex2 ‘z) NEITHER |
Let’s look at insert example, which inserts an element “e” into the list if it already not a member.
1 2 3 |
> (defun insert-ex3 (e l) (cond ((member e l) l) ;if already a member don’t do anything (t (cons e l)))) ;else cons the element. |
If function in Artificial Intelligence lisp programming
A simplified version of cond as given in the insert-ex3 example above can also be written in if function, as:
1 2 3 4 5 6 7 8 9 |
> (defun insert-ex4 (e l) (if (member e l) l (cons e l))) The format of if is: (if test-S-expression then-S-expression else-S-expression) > (defun if-ex5 (x) (if (listp x) (cdr x) (cons x nil))) ;if list return cdr else make list |
Logical Operators in Artificial Intelligence lisp programming
In Lisp the logical operators “and”, “or”, “not” are implemented as functions:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
> (and (listp ‘(a b)) (atom ‘c)) T > (and (listp ‘(a b)) (atom ‘x) (oddp 7) (evenp 7) (listp ‘(a b c)) ) NIL > (or (listp ‘(a b)) (evenp 7) ) T > (or (listp ‘(a b)) (atom ‘x) (oddp 7) (evenp 7) (listp ‘(a b c)) ) T > (not (atom ‘(a b))) T |
Now lets look at a few examples to see how these logical operators can be used beneficially:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
> (defun even-50-100 (x) ;It checks number is even, > 49 (cond ((numberp x) ; and < 101 (cond ((evenp x) (cond ((> x 49) (< x 101)))))))) > (even-50-100 17) NIL > (even-50-100 88) T > (defun even-50-100-new (x) ;It delivers the same result as above (and (numberp x) (evenp x) (> x 49) (< x 101))) |
Can you tell what will happen if we write:
1 2 |
> (defun even-50-100-different (x) (and (and (numberp x) (evenp x)) (and (> x 49) (< x 101))))) |
Do, Prog, Let & Recursion:
Do structure Artificial Intelligence lisp programming
Besides decision making and testing for conditions, another important aspect of programming languages is iteration. Lisp provides iteration through do loops. The format for do loop is:
1 2 3 4 5 6 7 8 |
(do ( (var1 val1 rep1) ;local variables can also be (var2 val2 rep2) ;skipped, i.e. empty list … ) ( exit-condition return-value) ;exit-condition is an S-expression S-expression-1 ;body S-expression-2 ;just like the variables list the …. ;body can also be skippe ) |
To evaluate a do clause, Lisp initializes all the variables with values, then it checks the exit-condition if false, it proceeds with evaluating all the S-expressions in the body. The iteration is repeated, by assigning the repeat values to the variables. The exit-condition is checked again if false the body is executed again. The iterative process continues, till the exit-condition turns true. Once the exit-condition turns true, the S-expression of return-value is computed and returned as the return value of the do loop.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
> (defun length1 (m) (do ( (ll m) (sum 0) ) ((atom ll) sum ) ;Exit-condition (setq ll (cdr ll)) (setq sum (1+ sum)) )) > (length1 ‘(a b c) ) 3 > (length1 ‘(a b (c d e) f ) ) 4 > (defun length2 (m) (do ( (ll m (cdr ll) ) ;repeat value (sum 0 (1+ sum) ) ) ((atom ll) sum ) ;Exit-condition ;No body )) > (length2 ‘(a b c) ) 3 > (defun do-reverse1 (m) (do ( (x m (cdr x) ) ;repeat value (res nil (cons (car x) res) ) ) ((null x) res) ;Exit-condition ;No body )) > (defun do-reverse2 (m) (do ( (x m ) ;No repeat value (res nil ) ) ((null x) res) ;Exit-condition (setq res (cons (car x) res)) (setq x (cdr x)) )) > (defun factorial (num) (do ( (x num (1- x) ) ;repeat value (fact 1 ) ) ((equal x 1) fact ) ;Exit-condition (setq fact (* fact x)) )) > (factorial 4) 24 > (defun factorial (num) (do ( (x num (1- x) ) (fact 1 (* fact x)) ) ((equal x 1) fact ) )) |
In addition to the standard do function, where the variables are assigned values at the same time (in parallel). There are times when we want the variables to be assigned in a sequential way. Lisp provides do*
1 2 3 4 5 6 |
> (defun factorial (num) (do* ( (x num (1- x) ) (fact x (* fact x) ) ) ((equal x 1) fact ) )) |
Two other do functions are also available: dolist and dotimes, The formats of dolist and dotimes are:
1 |
(dolist (var list-val return-val) S-exp1 S-exp2 …) |
The list-val is a list from which one item at a time is assigned to var for the iterations of the dolist loop.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
> (dolist (x ‘(a b c) ‘done) (print x) ) A B C DONE (dotimes (var stop-val result-val) S-exp1 S-exp2 …) The var is initialized to 0 and the dotimes loops till var reaches stop-val > (dotimes (x 5 ‘done) (print x) ) 0 1 2 3 4 DONE |
Prog structure in Artificial Intelligence lisp programming
The do function is a structured iteration construct, which is based on the primitive lisp construct called prog. Prog function allows the programmer write a sequence of S-expressions with some local variables. The format of prog is :
1 2 3 4 5 6 7 |
(prog ( (var1 val1 ) ;local variables can also be (var2 val2 ) ;skipped, No repeat values … ) S-expression-1 ;body S-expression-2 …. ) |
prog has two special features, which allowed Lisp to implement do from it. (i) (go label): allows the program to jump to a label in the prog body,
(ii) (return return-value): allows the program to return a value from prog.
(iii) label: allows the user to place labels in the body, for jumping too.
Prog only has a historical interest and is not normally used in the new programming paradigm.
1 2 3 4 5 6 7 |
> (defun prog-length (m) (prog ((sum 0) ) ;local variables again ;labels (cond ((atom m) (return sum)) ) (setq sum ( 1+ sum)) (setq m (cdr m)) (go again))) |
There are other variants of progs: prog1, prog2, progn, which allow the programmer sequence a set of S-expressions. However, the return values vary, in prog1 the value of 1st S-expression is returned, in prog2 the value of 2nd S-expression is returned, and in progn the value of last S-expression is returned.
The LET Command in artificial intelligence lisp programming:
Although strict Functional Programming would not allow the use of local variables (and assignment to such variables), Common Lisp has a command which gives a limited (but very useful) kind of variable declaration and initialization. The LET command, it has the same syntax and functionality as a PROG command, it:
- declares one or more local variables
- (optionally) gives them initial values
- executes a sequence of S-expressions using these local variables.
The general format of LET is:
1 2 3 4 5 6 7 8 9 10 |
(LET ( ( <variable-1> <value-1>) ( <variable-2> <value-2>) .... (<variable-N> <value-N>) ) <S-expression-1> <S-expression-2> .... <S-expression-K> ) |
The effect of the LET statement is to declare all these variables, evaluate each of the values (if provided, else assign nil), assigning the results to the corresponding variables, and to evaluate the Body of the statement (i.e. S-expressions).Processing begins outside of the LET statement at the end of this review, and the variables declared within it are no longer available. That is, the LET statement body is the “field” of these variables. LET only performs the initialization of the local variables – it is not a way of changing the values of existing variables. The following example shows how LET can be used, and what happens to global variables outside the scope of LET.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
(Setq a ‘Hello) (Setq b ‘Fawad) (print a) (print b) (LET ( ( a ‘(1 2 3)) ( b ‘(x y z)) ) (print “In LET structure”) (print a) (print b) (print “Exiting LET structure”) ) (print a) (print b) |
The above code’s output would be as follows:
1 2 3 4 5 6 7 8 |
Hello Fawad In LET structure (1 2 3) (x y z) Exiting LET structure Hello Fawad |
This clearly shows that the local variables in LET structure are really local and have no side effects, even on global variables with the same names.
Notice that LET sets all the initial variables simultaneously so that bindings made early in the list are not available during the setting of the later values. There is a related command LET*, which sets the values of several local variables in turn, thereby allowing the earlier settings to be used in later ones (the pseudo parallel operation of LET would not permit this). For example:
1 2 3 4 5 6 |
(LET* ( (operator (choose plan context)) (op-type (get-type operator)) (pre-conditions (get-conds operator)) ) ..... ) |
In the above, the value of the variable operator is available when the next two variables are being initialized. Similar commands are also available in do*, Prog* and so on. But it is worth pointing out that certain follow up variable values do not need this special in turn handling. For example in the following do structure the variables are handled correctly:
1 2 3 4 |
(DO ( (l ‘(a b c) (cdr l)) (x ‘a (car l)) ) ((null l) (print “exiting”)) (print x) ) |
Artificial intelligence lisp programming Recursion
Iteration provides almost all the functionality required in programming to carry out repetitive tasks. However, lisp lends itself more naturally towards recursion, and that makes it easy to understand recursion, which is normally considered to be very complicated.
The basic steps in coming up with recursive problem solving are:
Breaking down the task in smaller tasks
Combining the smaller tasks to solve the original problem
Identifying the grounding situation (terminating situation) of recursion
Specifying checks for these grounding cases that need to be examined before the recursive steps are taken.
1 2 3 4 5 6 7 8 9 10 11 |
> (defun iterative-sum (m) (do ( (ll m (cdr ll)) (sum 0 (+ (car ll) sum)) ) ((null ll) sum) )) This function works for: > (iterative-sum ‘(2 3 4 10 12)) 31 |
But does not work for
1 |
> (iterative-sum ‘(2 (3 4 10) 12)) |
error is produced since car of ((3 4 10) 12) is not a number so function + will fail. We can re-write the function for this list as:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
> (defun iterative-sum (m) (do ( (ll m (cdr ll)) (sum 0 (+ (car ll) sum)) ) ((null ll) sum) (cond ((listp (car ll)) (setq sum (do ((lll (car ll) (cdr lll)) (sum1 sum (+ (car lll) sum1) ) ((null lll) sum1) )) (setq ll (cdr ll)) )) |
However, this function will again not work for (2 ( 3 4 (10)) 12) In other words, as we keep making the list more and more complex, the iterative function also needs to be modified. To overcome this problem, we can use a recursive function. First, let’s see a simple recursive function:
1 2 3 |
> (defun recursive-sum (m) (cond ((null m) 0) (t (+ (car m) (recursive-sum (cdr m))) ) ) |
To handle embedded cases we need to slightly modify the function, only once:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
> (defun recursive-sum2 (m) (cond ((null m) 0) ((listp (car m)) (+ (recursive-sum2 (car m)) (recursive-sum2 (cdr m)))) (t (+ (car m) (recursive-sum2 (cdr m))) ) ) > (defun recursive-length (m) (cond ((null m) 0) (t (1+ (recursive-length (cdr m))) ) ) > (defun recursive-member (e m) (or (equal e (car m)) ; has a bug for nil list (recursive-member e (cdr m)) )) > (defun recursive-member (e m) (and m (or (equal e (car m)) (recursive-member e (cdr m)) ))) > (defun recursive-member (e m) (cond ((null m) nil ) (t (or (equal e (car m)) (recursive-member e (cdr m)))))) > (defun recursive-member (e m) ;The final and better version (cond ((null m) nil ) ((equal e (car m)) m) (t (recursive-member e (cdr m))))) > (defun factorial (n) (cond ((zerop n) 1) (t (* n (factorial (1- n)))))) > (defun our-subst (in out struct) (cond ((atom struct) struct) ((equal out (car struct)) (cons in (our-subst in out (cdr struct)))) (t (cons (car struct) (our-subst in out (cdr struct)))))) If the struct is an embedded list then our-subst needs to recurse on car also > (defun our-subst (in out struct) (cond ((atom struct) struct) ((equal out (car struct)) (cons in (our-subst in out (cdr struct)))) (t (cons (our-subst in out (car struct)) (our-subst in out (cdr struct)))))) The final version of our-subst is as follows: > (defun our-subst (in out struct) (cond ((equal out struct) in) ((atom struct) struct) (t (cons (our-subst in out (car struct)) (our-subst in out (cdr struct)))))) |