Lisp: The Language That Shaped Early AI, Explained

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 8.3 Free with a free account

Lisp: The Language That Shaped Early AI

Introduction to Artificial Intelligence · Chapter 8: Perception, Robotics, and Hands-On AISection 8.3 · lesson 59 of 6917 min · free with a free account

← Teaching Machines to Recognize and Sort ImagesNext lesson: Mapping and Localization (SLAM) in Robotics →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

How Lisp's symbols, lists and recursion powered early AI programs.

  • Describe Lisp's origins with John McCarthy and the ideas it introduced or popularized
  • Evaluate Lisp S-expressions using prefix calls, quote, car, cdr, cons and append
  • Write recursive Lisp functions with a base case and a recursive case for lists and trees
  • Explain how symbolic programs such as deriv and forward chaining rewrite expressions by rule

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (2,364 words). Read along, or search it.

Opening Question

A Derivative Without a Value for x

Most programming languages were designed to make numbers do what you want. In 1958, John McCarthy set out to build one where symbols, and lists of symbols, were just as easy to handle. He called it Lisp, short for list processing. For about thirty years, it was the working language of artificial intelligence. Here's the kind of job it made easy: take the formula x times x, and work out its derivative, without ever giving x a value. How can a program do that?

History

McCarthy, Lambda Calculus and Lisp 1.5

In the mid-1950s, researchers who wanted programs to reason found that the languages of the day were built for arithmetic. IPL, from Allen Newell, Herbert Simon and Cliff Shaw, had introduced list processing for their Logic Theorist program. But it was low-level, and awkward. McCarthy, who had helped organize the 1956 Dartmouth workshop that named the field, wanted something cleaner. Working at MIT from 1958, he combined list processing with recursive functions, and with Alonzo Church's lambda calculus, a notation for defining functions. He published the design in a 1960 paper, and a widely used version, Lisp 1.5, followed in 1962. Lisp is the second-oldest high-level language still in wide use, after Fortran.

Lasting Ideas

Garbage Collection, Lambdas and Code as Data

Many ideas now taken for granted were introduced, or popularized, by Lisp. Conditional expressions: an if-then-else that produces a value, like Python's x if test else y. And recursion, as an everyday tool. Garbage collection, which reclaims unused memory automatically, as Python, Java and Go do. And functions as values, including nameless ones, called lambdas. The interactive loop: type an expression, and see its value at once. And code as data: programs are lists, so one program can build or change another.

Why AI Chose Lisp

Symbols, Trees and Recursion

Why did AI researchers choose it? Symbols are ordinary data. A formula like plus x three is a list, not a string to be parsed. Nested lists represent trees, which suit parse trees, game trees and logical formulas. And recursion fits the problems: searching a tree, or taking apart a formula. Programs are data, so a reasoning program can inspect and build other expressions. And the interactive loop let researchers test ideas one function at a time.

Legacy

From SHRDLU to Clojure

Many well-known early AI programs were written in Lisp, including Terry Winograd's SHRDLU, which understood English commands in a world of toy blocks. Companies even built Lisp machines, computers designed to run it fast. When the first wave of expert-system enthusiasm faded, that market faded too. Today, Python dominates AI practice, thanks to its machine-learning libraries. But Lisp lives on, in several dialects. Common Lisp is large, with an ANSI standard from 1994. Scheme, from 1975, is small and elegant. Emacs Lisp customizes a text editor. And Clojure, from 2007, is a modern Lisp that runs on the Java platform.

S-Expressions

Atoms and Lists in One Notation

Everything in Lisp is built from one structure: the symbolic expression, or S-expression. An S-expression is either an atom, like the number 42, the symbol square, or a string, or else a list: zero or more S-expressions inside parentheses. The definition is recursive, because a list can contain lists. And the same notation is used for data, and for code.

Evaluation

Prefix Calls, Quote, NIL and T

Lisp writes a function call in prefix form, function first. Plus, two, three means two plus three, and this call returns five. To evaluate a list, Lisp evaluates every argument, then applies the function to the values. Numbers evaluate to themselves. In the nested call, plus one two gives three, and minus ten four gives six. Then times returns eighteen. To treat a list as data instead of running it, put a quote mark in front. Quote a b c is just a list of three symbols. Without the quote, Lisp would try to call a function named a, and report an error. Two symbols are special. NIL is the empty list, and also means false. T means true, and anything other than NIL counts as true in a test.

List Operations

Cons Cells, Car and Cdr

Inside the computer, a list is a chain of cons cells. Each cell has two parts: the car holds an element, and the cdr points to the rest of the list. The odd names come from the IBM 704, the first machine that ran Lisp. Newer code often says first and rest instead. So car of a b c returns a, and cdr returns the list b c. Cons adds an element to the front: x onto a b gives x a b. Append joins lists end to end. Nth counts from zero, so nth two of a b c d is c. And member returns the list from the match onward.

Common Mistake

Cons Nests While Append Flattens

One stumbling block. Cdr of a, b c, d returns b c, then d. The inner list stays one element. Cons puts its first argument in as one new element, even when that argument is a list. So cons of the list a, onto b c, keeps the list a whole. Append joins the elements of two lists. Append of the list a and the list b c gives the flat list a b c. So the choice comes down to this: do you want a nested list, or a flat one?

Quick Check

Consing a List Onto a List

Quick check, with new lists. This call conses the list x y onto the list z. What does it return? Pause, and decide. It returns a two-element list: the list x y, then z. Cons adds its first argument as one element, so x y stays nested. The flat x y z is what append would give. And x y followed by a nested z would need z wrapped in a second list.

Defining Functions

Defun, Mapcar, Lambda and Reduce

A function is defined with defun: its name, its parameter list, and its body. Square of x multiplies x by x, so square of five returns 25. Functions are values too. Mapcar applies a function to every element, so mapcar of square over one to four returns 1, 4, 9 and 16. Lambda makes a nameless function on the spot. This one adds one, so this mapcar returns two, three, four. Remove-if-not keeps the elements that pass a test, here the even ones. And reduce combines them all: plus over one to five gives 15. The mark sharp-quote, in front of square or plus, means the function named square, or plus.

Conditionals

Cond Tests Clauses in Order

For decisions, if chooses between two values, and cond tests several conditions in order. Sign of minus four fails the first test, passes the second, and returns negative. Sign of zero falls through to the last clause. That clause starts with T, which always matches, so it acts as the default, and returns zero. A long-looking Lisp program is mostly indentation. Editors match the parentheses, and Lisp programmers read the indentation, rather than counting brackets.

Code as Data

Editing a List Then Running It

Because a Lisp program is a list, a program can build code, and change it. Here, a variable holds a list: plus, two, three. Eval runs that list as code, and returns five. Now setf replaces its first element with times. Ask for the variable, and the list now reads times, two, three. Evaluate it again, and the same list returns six: code, edited as data, then run.

Recursion

Base Case and Recursive Case

Lisp has few loops in everyday use. Repetition is usually recursion: a function that calls itself on a smaller problem. The recipe for a list has two parts. A base case: what to return for the empty list. And a recursive case: handle the first element, then recurse on the rest. Fact of n is one when n is at most one, and otherwise n times the fact of one less than n. Fact of five returns 120. Fact of 25 returns a 26-digit number, exactly. Lisp integers grow as large as needed, so there's no overflow. Sum-list adds the first element to the sum of the rest, and returns zero for the empty list. Counting a list's length works the same way, adding one each time.

Worked Trace

Sum-List Unwinds to Six

Follow sum-list on one, two, three. Each call waits for the one below it: one two three, then two three, then just three, then the empty list. The empty-list call answers first, with zero. Then the answers rise back up: three, then five, then six. Written out, the work is one, plus two, plus three, plus zero, which is six.

Recursion on Trees

Flattening a Nested List

Recursion shines on nested lists, which are trees. Flatten turns a nested list into a flat one, with three cases. The empty list gives NIL. A single atom becomes a one-element list. And a list is flattened by flattening its first element and its rest, and appending the two. Flatten of a, b c, d inside a list, then e, returns a b c d e. All the structure is gone. Now change append to cons. Cons makes each piece one new element, instead of joining their elements. Flatten of a and b c now returns something even more nested than its input.

Cost of Recursion

Fibonacci Calls Explode

Recursion can be elegant, but wasteful. The textbook Fibonacci function calls itself twice at each step. Fib of ten returns 55, and fib of twenty returns 6,765. But the same sub-problems are solved again and again. Counting the calls: 177 for fib of ten, 21,891 for fib of twenty, and over 2.6 million for fib of thirty. Each step of ten multiplies the work by more than a hundred. Remembering earlier answers, or carrying running values forward, removes the waste. Many Lisp systems also optimize tail recursion, so it uses no extra memory.

Symbolic Versus Numeric

Substituting a Value for x

A numeric program works with values, like five or 3.14. A symbolic program works with the expressions themselves. Subst replaces one symbol with a value. Substituting five for x in x, plus x times two, returns a new expression: five, plus five times two. Only the eval turns it into a number: fifteen.

Symbolic Program

Differentiation by Sum and Product Rules

Now a real symbolic program: differentiation. Calculus has rules about expressions. The derivative of a sum is the sum of the derivatives. A product follows the product rule: f times g, differentiated, is f times g prime, plus f prime times g. Deriv takes an expression e and a variable v. A number has derivative zero. A symbol has derivative one if it's the variable, and zero otherwise. A sum applies the sum rule to its two parts. A product applies the product rule. Anything else is reported as an unknown operator. Two helpers, make-sum and make-product, tidy the results. They drop additions of zero, and multiplications by zero or one.

Worked Results

Derivatives Built as New Lists

Deriv of x plus three, with respect to x, returns one. Deriv of three times x returns three. Deriv of x times x returns plus x x: two x, written as x plus x. Deriv of x times the sum x plus two returns x, plus x plus two: two x plus two. And deriv of y times x, with respect to y, returns x, because x is a constant there. x never gets a number. The program matches the shape of a list, applies a rule, and builds a new list, so the recursion follows the expression tree.

Quick Check

Differentiating Two x Plus Five

Quick check. Differentiate two times x, plus five, with respect to x. What exactly does deriv return? Pause, and predict. It returns just two. For two times x, the product rule gives two times one, plus zero times x. Make-product tidies those to two and zero, and make-sum drops the zero. The five's derivative is another zero, dropped too. The other two answers are only partly tidied. The helpers simplify all the way.

Rule-Based Reasoning

Forward Chaining Over Rain Rules

Second program: rule-based reasoning, with the rain, wet grass and slippery path rules from the earlier lessons on logic. Each rule is a pair: a list of premises, and the fact it produces. Rain gives wet, a sprinkler gives wet, and wet gives slippery. A rule fires when every one of its premises is among the known facts. Forward-chain adds the conclusion of every rule that fires, and calls itself again, until a pass adds nothing new.

Worked Trace

From Rain to Slippery in Three Passes

Start from rain. Pass one: the rain rule fires, and wet is added. Pass two: the wet rule fires, and slippery is added. Pass three adds nothing new, so the call returns rain, wet, slippery. From a sprinkler, it returns sprinkler, wet, slippery. From sun, no rule fires, and it returns just sun. The program is about a dozen lines, because lists and recursion do most of the work. A real rule engine adds variables, certainty values and explanations.

Lisp Ideas in Python

Comprehensions, Sum and Exact Factorials

Python borrowed several of these ideas. Here are the same tasks in Python, and this time we can run them. A list comprehension plays the role of mapcar. An if inside it does remove-if-not's job. And sum does the reduce. The factorial is the same recursion, written with Python's conditional expression, which Lisp pioneered. Run it. Python prints the squares, the even numbers, and fifteen. Then factorial of 25, also exact, because Python's integers grow as needed too.

Lisp Today

Strengths and Limits

Lisp today. Its strengths: programs and data share one notation, so tools that build or inspect programs are easy to write. It's excellent for symbolic work, like logic, rules, language and algebra. And good compilers, such as SBCL, make fast programs. Its limits: the parentheses take getting used to, machine-learning libraries mostly target Python, and fewer programmers know it.

Back to the Question

The Formula Is Just a List

Back to the opening question: how can a program find the derivative of x times x, without ever giving x a value? Because in Lisp, the formula is just a list. The program matches its shape, applies the product rule, and builds a new list: plus x x. That's symbolic AI in miniature: knowledge written as symbols, and reasoning done by rearranging them.

Key Takeaways

Lisp in Summary

To sum up. Lisp, from 1958, made symbols and lists as easy as numbers, and gave us recursion, garbage collection, lambdas and the interactive loop. Code and data are both S-expressions, evaluated in prefix form. Car and cdr take lists apart, and cons and append build them. Recursion handles lists and trees with a base case and a recursive case, and symbolic programs, like deriv, rewrite expressions by rule.

Think About It

Counting Atoms in a Nested List

Here's something to think about. Picture a function that counts the atoms in a nested list, like a, b c, then d e. What's its base case? And what should it do with the first element, when that element is itself a list?

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Lisp: The Language That Shaped Early AI

Who created Lisp and why was it used for AI?
John McCarthy designed Lisp, short for list processing, starting in 1958 at MIT, and published the design in a 1960 paper. AI researchers adopted it because symbols and nested lists are ordinary data, which suits formulas, parse trees and game trees. Recursion fits searching trees, programs are themselves lists that other programs can build or inspect, and the interactive loop let researchers test ideas one function at a time.
What is the difference between cons and append in Lisp?
Cons adds its first argument to the front of a list as one new element, while append joins the elements of lists end to end. So (cons '(a) '(b c)) returns ((a) b c), keeping the list (a) nested, but (append '(a) '(b c)) returns the flat list (a b c). Use cons when the result should stay nested and append when it should be flat.
What do car and cdr mean in Lisp?
Car returns the first element of a list, and cdr returns the rest of the list. A Lisp list is a chain of cons cells, each holding an element in its car part and a pointer to the remaining list in its cdr part. The odd names come from the IBM 704, the first machine to run Lisp, and newer code often says first and rest. For example, (cdr '(a b c)) returns (b c).
How does symbolic differentiation work in Lisp?
Symbolic differentiation treats a formula as a list and rewrites it by calculus rules, without ever giving the variable a value. A deriv function returns zero for a number, one for the variable itself and zero for other symbols, applies the sum rule to sums and the product rule to products, and recurses through the expression tree. Differentiating (* x x) with respect to x yields (+ x x), which means 2x.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.

69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →