LISP Programming
LISP is one of the simplest computer languages in terms of syntax and semantics, and also one of the most powerful. It was developed in the mid1950’s by John McCarthy at M.I.T. as a “LISt Processing language”. Today, it is used for virtually all Artificial Intelligence programs and is the environment of choice for applications which require a powerful interactive working environment. LISP presents a very different way to think about programming from the “algorithmic” languages, such as BASIC, Fortran and Pascal.
As its name implies, the basis of LISP is a list. One constructs a list by enumerating elements inside a pair of parentheses. For example, here is a list with four elements (the second element is also a list):
(23 (this is easy) hello 821)
The elements in the list, which are not lists, are called “atoms.” For example, the atoms in the list above are: 23, this, hello, 821, easy, and is. Everything in LISP is either an atom or a list (but not both). The only exception is “NIL,” which is both an atom and a list. It can also be written as “()” – a pair of parentheses with nothing inside.
All statements in LISP are function calls with the following syntax: (function arg_{1} arg_{2} arg_{3} … arg_{n}). To evaluate a LISP statement, each of the arguments (possibly functions themselves) are evaluated, and then the function is invoked with the arguments. For example, (MULT (ADD 2 3) (ADD 1 4 2)) has a value of 35, since (ADD 2 3) has a value of 5, (ADD 1 4 2) has a value of 7, and (MULT 5 7) has a value of 35. Some functions have an arbitrary number of arguments; others require a fixed number. All statements return a value, which is either an atom or a list.
We may assign values to variables using the function SET. For example, the statement (SET ’test ’6) would have a value of a 6, and (more importantly, however) would also cause the atom “test” to be bound to the atom “6”. The quote in front of the arguments indicates that the arguments should not be evaluated before the function is invoked. The quote in front of numbers is optional. Observe the following examples:
Statement

Value

Comment

(SET ’a ( MULT 2 3))

6

a is an atom with a vaue of 6

(SET ’a ’(MULT 2 3))

(MULT 2 3)

a is a list with 3 elements

(SET ’b ’a)

a

b is an atom with a value of the character a

(SET ’c a)

(MULT 2 3)

c is a list with 3 elements

(SET ’TEST (ADD 3 (MULT 2 5)))

13

test has a value of 13

(SETQ VOWELS ’(A E I O U))

(A E I O U)

VOWELS is a list of 5 elements

(SETQ x (SETQ y ’same))

same

both x and y are bound to value of “same”

(SETQ y ’diff)

diff

x is still “same”

(SETQ x y)

diff

x is now “diff”

The function SETQ is the same as SET, but it causes LISP to act as if the first argument was quoted. The function EVAL returns the value of its argument, after it has been evaluated. For example, (SETQ z ’(ADD 2 3)) has a value of the list (ADD 2 3); the function (EVAL ’z) has a value of (ADD 2 3); the function of (EVAL z) has a value of 5 (but the binding of the atom z has not changed). In this last example, you can think of z being “resolved” twice: once because it is an argument to a function and LISP evaluates all arguments to functions before the function is invoked, and once when the function EVAL is invoked to resolve arguments. The function ATOM can be used to tell whether an item is an atom or a list.
Statement

Value

Comment

(SETQ X (ADD 45 8))

53
 X is now 53 
(SETQ Y ’(ADD X 11))

(ADD X 11)

Y is now a list

(EVAL ’Y)

(ADD X 11)


(EVAL Y)

64


(ATOM 5)

true


(ATOM X)

true


(ATOM ’Y)

true


(ATOM Y)

NIL


(ATOM ’(8 7 6))

NIL


The two most famous LISP functions are CAR and CDR (pronounced: coulder), named after registers of a now longforgotten IBM machine on which LISP was first developed. The function (CAR x) returns the first item of the list x (and x must be a list or an error will occur); (CDR x) returns the list without its first element (again, x must be a list). The function CONS takes two arguments, of which the second must be a list. It returns a list which is composed by placing the first argument as the first element in the second argument’s list. The function REVERSE returns a list which is its arguments in reverse order. The following examples illustrate the use of CAR, CDR, and CONS:
Statement 
Value

(REVERSE ’(8 7 6))

(6 7 8)

(REVERSE ’(1 (2 3 4) 5 6))

(6 5 (2 3 4) 1)



(CAR ’(This is a list))

This

(CAR (CDR ’(This is a list)))

is

(SETQ x (CDR (CDR ’(a b c d))))

(c d)

(CDR ’(This is a list ))

(is a list)

(CAR ’(hi))

hi

(CDR ’(one))

NIL

(CAR ’((1) (2 3) (4 5 6)))

(1)

(CONS 32 ’(22 12))

(32 22 12)

(CONS ’first ’(last))

(first last)

(CONS ’(one) ’(two three))

((one) two three)

(CDR (CAR ’((red white) blue)))

(white)

(CONS (CAR ’(red green blue)) (CDR ’(brown tan gold)))

(red tan gold)

(CAR ’hi)

error

(CAR ())

error

(CAR ’(ADD 2 2))

ADD

(CONS 78 NIL)

(78)

(CDR ’((red green) (blue white))

((blue white))



(SETQ a ’(orange black))

(orange black)

(ATOM (SETQ b (CONS ’red a)))

NIL

(ATOM b)

NIL

(ATOM (CAR b))

true

(ATOM NIL)

true



(SETQ fruit ’(apple orange))

(apple orange)

(SETQ more (CONS ’grape fruit))

(grape apple orange)

(CDR (CDR (REVERSE more)))

(grape)

(SETQ colors ’(red green yellow))

(red green yellow)

(SETQ area (MULT 2 3))

6

(SETQ A (CONS area ’(CDR colors)))

(6 CDR colors)

(SETQ B (CONS ’area (CDR colors)))

(area green yellow)

(SETQ C (REVERSE colors))

(yellow green red)

(CAR (CDR C))

green

(CONS ’pink (CONS ’orange (CONS C NIL)))

(pink orange (yellow green red))

As you have probably deduced, the function ADD simply summed its arguments. We’ll also be using the following arithmetic functions:
FUNCTION

RESULT

(ADD x_{1} x_{2} …)

sum of all arguments

(MULT x_{1} x_{2} …)

product of all arguments

(SUB a b)

ab

(DIV a b)

a/b

(SQUARE a)

a*a

(EXP a n)

a^{n}

(EQ a b)

true if a and b are equal, NIL otherwise

(POS a)

true if a is positive, NIL otherwise

(NEG a)

true if a is negative, NIL otherwise

Some examples of these functions are as follows:
STATEMENT

VALUE

(ADD (EXP 2 3) (SUB 4 1) (DIV 54 4))

24.5

(SUB (MULT 3 2) (SUB 12 (ADD 2 2)))

2

(ADD (SQUARE 3) (SQUARE 4))

25

LISP also allows us to create our own functions using the DEF function. For example,
(DEF SECOND(parms) (CAR (CDR parms)))
defines a new function called SECOND which operates on a single parameter named “parms”. SECOND will take the CDR of the parameter and then the CAR of that result. So, for example:
(SECOND ’(a b c d e))
would first CDR the list (yielding (b c d e)) and then CAR the result. So the value would be the single character “b”. Consider the following program fragment:
(SETQ X ’(a c s l))
(DEF WHAT(parms) (CONS parms (REVERSE (CDR parms))))
(DEF SECOND(parms) (CONS (CAR (CDR parms)) NIL))
The following chart illustrates the use of the userdefined functions WHAT and SECOND:
STATEMENT

VALUE

(WHAT X)

((a c s l) l s c)

(SECOND X)

(c)

(SECOND (WHAT X))

(l)

(WHAT (SECOND X))

((c))

Questions in this round will typically present a line of LISP code or a short sequence of statements and ask what is the value of the (final) statement.
Sample Problems
Evaluate: (CDR ’((2 (3))(4 (5 6) 7)))
Consider the following program fragment:
(SETQ X ’(RI VA FL CA TX)) (CAR (CDR (REVERSE X)))
What is the value of the CAR expression?
Given the function definitions for HY and FY as follows:
(DEF HY(PARMS) (REVERSE (CDR PARMS))) (DEF FY(PARMS) (CAR (HY (CDR PARMS))))
What is the value of the following?
(FY ’(DO RE (MI FA) SO))
Evaluate the following expression.
(EXP (MULT 2 (SUB 5 (DIV (ADD 5 3 4) 2)) 3) 3)
BitString Flicking
Bit strings (binary numbers) are frequently manipulated using logical operators, shifts, and circulates. Mastering this topic is essential for systems programming, programming in assembly language and optimizing code.
A typical use of bit string is to maintain a set of flags. Suppose that associated with a data structure in a program are 10 “options”, each of which can be either “on” or “off”. One could maintain this information using an array of size 10, or one could use a single variable (if it is internally stored using at least 10 bits, which is usually the case) and use 10 bits to record each option. In addition to saving space  a significant consideration if enough data structures and options are involved  the program is often cleaner if a single variable is involved rather than an array. Incidentally, bit strings are usually used to maintain Pascal “sets”.
The logical operators which will be used are: AND(&), OR(), XOR() and NOT(~). These operators examine the operand(s) on a bit by bit basis. For example, (10110 AND 01111) has a value of 00110. The AND, OR and XOR are binary operators; the NOT is a unary operator. The category description of Boolean Algebra/Digital Electronics has a complete description of each logical function. The following chart summarizes this information:
p

q

p AND q

p OR q

p XOR q

NOT p

0

0

0

0

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

1

1

1

0

0

Logical shifts (LSHIFTx and RSHIFTx) “ripple” the bit string x positions in the indicated direction. Bits shifted out are lost; zeros are shifted in at the other end. Circulates (RCIRCx and LCIRCx) “ripple” the bit string x positions in the specified direction. As each bit is shifted out one end, it is shifted in at the other end. Thus, for this category, the size of a bit string is fixed; it cannot be lengthened or shortened by any of the logical operators, shifts or circulates. If any bit strings are initially of different lengths, all shorter ones are padded with zeros in the left bits until all strings are of the same length. The following table gives some examples of these operations:
p

LSHIFT2 p

RSHIFT2 p

LCIRC3 p

RCIRC3 p

01101

10100

00011

01011

10101

10

00

00

01

01

1110

1000

0011

0111

1101

1011011

1101100

0010110

1011101

0111011

The order of precedence (from highest to lowest) is: NOT; SHIFT and CIRC; AND; XOR; and finally, OR. Operators with equal precedence are evaluated left to right; all operators bind from left to right.
Sample Problems
Evaluate the following expression:
(RSHIFT1 (LCIRC4 (RCIRC2 01101)))
List all possible values of x (5 bits long) that solve the following equation.
(LSHIFT1 (10110 XOR (RCIRC3 x) AND 11011)) = 01100
Evaluate the following expression:
((LCIRC3 (10110 XOR 11010)) AND (RSHIFT1 10111))
Evaluate the following expression:
((RCIRC14 (LCIRC23 01101))  (LSHIFT1 10011) & (RSHIFT2 10111))
Find all possible values of x for which the following expression has a value of 10100.
(LSHIFT2 (RCIRC3 (NOT x)))
Prefix/Infix/Postfix Notation
One commonly writes mathematical expressions, such as in infix notation: AB/(C+D). In this example, one must first evaluate C+D (call the result X), then B/X (call the result Y), and finally AY. The order of evaluation is not simply “go from left to right, evaluating on the fly.” Rather, evaluation is dependent on the precedence of the operators and the location of parentheses. Two alternative formats, prefix and postfix, have been developed to make evaluation more mechanical (and hence, solvable by a simple computer program).
Prefix notation places each operator before its operands, and postfix places each operator after its operands. The example above becomes –A/B+CD in prefix notation, and ABCD+/ in postfix notation. In all notations, the relative order of the operands is the same.
A simple algorithm for converting from infix to prefix (postfix) is as follows: (i) Fully parenthesize the infix expression. It should now consist solely of “terms”: a binary operator sandwiched between two operands. (ii) Write down the operands in the same order that they appear in the infix expression. (iii) Look at each term in the infix expression in the order that one would evaluate them, i.e., inner most parenthesis to outer most and left to right among terms of the same depth. (iv) For each term, write down the operand before (after) the operators. The following sequence of steps illustrates converting X=(A*BC/D)E from infix to postfix:
(X=(((A*B)(C/D))E))
XABCDE
XAB*CDE
XAB*CD/E
XAB*CD/E
XAB*CD/E
XAB*CD/E=
This equation has a prefix value of =X*AB/CDE. A quick check for determining whether a conversion is correct is to convert the result back into the original format.
The area of computer science that uses prefix and postfix notation (also known as “Polish” and “Reverse Polish” notation for the Polish logician Jan Lukasiewicz) most frequently is compiler design. Typically, expressions (as well as statements) are translated into an intermediate representation, known as a “syntax tree,” which is equivalent to either prefix or postfix notation. The intermediate representation can then be easily executed.
Sample Problems
Translate the following infix expression into postfix.
Given A=4, B=14 and C=2, evaluate the following prefix expression:
* /  + A B C * A C B
Evaluate the following prefix expression, when A=10, B=2, C=12 and D=2.
+ / ↑  A B 2 ↑ /  C D / A B 3 / + AC B
Share with your friends: 