Articles

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:

artificial intelligence lisp programming

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?

artificial intelligence lisp programming

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?

  1. 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.

REFERENCE BOOK

  1. 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.

REFERENCE BOOK

  1. 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.

REFERENCE BOOK

  1. 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.

REFERENCE BOOK

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

artificial intelligence lisp programming

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

artificial intelligence lisp programming

artificial intelligence lisp programming

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:

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:

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:

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:

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:

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:

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:

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.

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:


Symbols

No assignment operator

Setq does not evaluate the First Argument!  Special Function in Lisp

 However, the Second Argument is evaluated.

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

However, assigning values to known functions is generally bad programming practice.

Exiting Lisp and effect on Symbols

Start a new session of Lisp

Lists in common lisp language


To stop Lisp to evaluate a List as an S-Expression, we use quote

The quote is used so extensively in lisp, i.e. forcing lisp not to evaluate arg That a special format is provided to quote

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

Combination of cars and cdrs is used so frequently that Lisp provides a variety of combinations of cars and cdrs:

The Empty List

Cons

To construct a list, the basic function used is cons

Note that just like car and cdr, cons is also non-destructive, i.e. cons does not effect the values of symbols.



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.

Evaluation in Common Lisp

The algorithm employed by the Lisp interface or ‘listener’ can be simplified as:

The central step of this (evaluate L ) is performed by a system function called EVAL, which executes roughly the following (recursive) algorithm:

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.

artificial intelligence lisp programming

artificial intelligence lisp programming

artificial intelligence lisp programming

Functions in Common Lisp

Simple function definitions can be specified using the Lisp function DEFUN, the format followed by DEFUN is:

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:

This function returns the last name of a name given in a form of a list, so for the following case it returns:

Interestingly enough, we have also introduced an odd limitation to our function, as can be seen from the following examples:

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.

Some of the key predicates are mentioned below:

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:


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:

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.

The following example will demonstrate a default clause in cond plus multiple s-expressions in each clause.

It is legal to have only one S-expression in a condition clause

Let’s look at insert example, which inserts an element “e” into the list if it already not a member.



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:

Logical Operators in Artificial Intelligence lisp programming

In Lisp the logical operators “and”, “or”, “not” are implemented as functions:

Now lets look at a few examples to see how these logical operators can be used beneficially:

Can you tell what will happen if we write:

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:

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.

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*

Two other do functions are also available: dolist and dotimes, The formats of dolist and dotimes are:

The list-val is a list from which one item at a time is assigned to var for the iterations of the dolist loop.


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 :

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.

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:

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.

The above code’s output would be as follows:

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:

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:


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.

But does not work for

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:

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:

To handle embedded cases we need to slightly modify the function, only once:

 

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button