computer

artificial intelligence using lisp programming & examples

Description:

“The Ultimate goal of AI 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 AI (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 AI. This dream person can be hypothesized to have certain simple modules, as shown in the following model:

artificial intelligence lisp programming language

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 simple 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) thorough knowledge of AI fundamental.

We can think of this approach as building a box (which includes all the internals) with 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:


Amazon Purchase Links:

Top Gaming Computers

Best Laptops

Best Graphic Cards

Portable Hard Drives

Best Keyboards

Best High Quality PC Mic

Computer Accessories

*Please Note: These are affiliate links. I may make a commission if you buy the components through these links. I would appreciate your support in this way!

What AI can allow computers to do?

artificial intelligence lisp programming language

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 expert in some specific problem area.

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 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 the specific domain.
  • Expertise is needed in many locations at one time.
  • Expertise is needed in hostile environment.

Life Cycle of Expert Systems

artificial intelligence lisp programming language

artificial intelligence lisp programming language

Introduction to Common Lisp

Lisp was originally developed in 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) have 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 which 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 quite 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 AI programming.



Syntax in Common Lisp

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:

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:

 

(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:

 

( )                     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 conventions.

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

Comments in Lisp are started with a ; character (i.e. semicolon). So a statement of Lisp would be like:

(+ 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:

 

#|

(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:

 

(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:

 

(+ 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.

 

Every Thing in Lisp is Evaluated

As the title states, in Lisp every thing is evaluated.

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.

>  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:

 

> (+ 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

 

> (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 First Argument!  Special Function in Lisp

However, Second Argument is evaluated.

 

> (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

 

> (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

 

> (setq x 20)                            ;assign x a value 20

            20

            > x                                                       ;x evaluates to its value

            20

            > (exit)                                                ;exit from lisp environment (or session)

            start new session of Lisp

> x                                                       ;previous session’s symbols are deleted

Error: Variable has no value.

 

Lists

(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

 

> ( quote (a b c) )                                                        ;Quote is a Special Function

(A B C)                                                                        ;does not evaluate argument

;returns argument as value

Quote is used so extensively in lisp, i.e. forcing lisp not to evaluate arg

That a special format is provided to quote

 

> ‘(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)                                                             ;without evaluating (+ 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

 

> (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:

 

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

 

> (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

 

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

 

>(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 returns as its value the list obtained by taking the second argument and sticking the first one in front of it.

 

>  (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:

 

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:

 

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 right. The end of the parenthesised 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.

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.

artificial intelligence lisp programming language

artificial intelligence lisp programming language

artificial intelligence lisp programming language

Functions in Common Lisp

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

(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:

 

(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:

 

(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:

 

(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).

Lay out 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 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 behaviour[1]. 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 which can be plugged into any program, able to perform exactly the same small task, to meet 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 affect 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 which consult or alter free (i.e. non-local) variables which 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 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

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.

 

(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:

 

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:

 

(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

 

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:

 

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.

 

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

 

(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

 

(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

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

 

(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

 

A simplified version of cond as given in insert-ex3 example above can also be written in if function, as:

 

(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 Lisp the logical operators “and”, “or”, “not” are implemented as functions:

 

(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:

 

(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:

 

(defun even-50-100-different (x)

(and (and (numberp x) (evenp x)) (and (> x 49) (< x 101)))))

 

Do, Prog, Let & Recursion:

 

Do structure

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:

 

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

 

(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*

 

(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:

 

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

 

(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

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  ( (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 jump to a label in the prog body,

(ii) (return return-value): allows the program return a value from prog.

(iii) label: allows the user place labels in the body, for jumping to.

 

Prog only has historical interest, and is not normally used in the new programming paradigm.

 

(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

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:

 

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

(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:

 

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:

 

(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:

(DO  (  (l  ‘(a b c) (cdr l))

(x  ‘a        (car l))   )

((null l) (print “exiting”))

(print x)  )

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.

 

(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

 

(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:

 

 

(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 lets see a simple recursive function:

 

(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:

 

(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))))))

This behaviour of encapsulation and implementation hiding will be illustrated by the Lisp exercises such as tables.lsp and the ones which follow it.

 

Engr Fahad

My name is Shahzada Fahad and I am an Electrical Engineer. I have been doing Job in UAE as a site engineer in an Electrical Construction Company. Currently, I am running my own YouTube channel "Electronic Clinic", and managing this Website. My Hobbies are * Watching Movies * Music * Martial Arts * Photography * Travelling * Make Sketches and so on...

Leave a Reply

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

Back to top button