196

I've been learning Lisp to expand my horizons because I have heard that it is used in AI programming. After doing some exploring, I have yet to find AI examples or anything in the language that would make it more inclined towards it.

Was Lisp used in the past because it was available, or is there something that I'm just missing?

Cristián Romo
  • 9,814
  • 12
  • 50
  • 50
  • 5
    > …Please don't assume Lisp is only useful for Animation and Graphics, > AI, Bioinformatics, B2B and E-Commerce, Data Mining, EDA/Semiconductor > applications, Expert Systems, Finance, Intelligent Agents, Knowledge > Management, Mechanical CAD, Modeling and Simulation, Natural Language, > Optimization, Research, Risk Analysis, Scheduling, Telecom, and Web > Authoring just because these are the only things they happened to > list. --Kent Pitman – Avi Sep 25 '08 at 06:28
  • 2
    I didn't think that Lisp is only useful for AI, I'm just wondering why it is used for it. – Cristián Romo Sep 25 '08 at 17:42
  • I would rephrase the question as "what features of a language are necessary for hard AI?" This is a valid and useful question, and the outcome will be that only Lisp Forth & assembler have what it takes to do hard AI. – Albert van der Horst Feb 17 '14 at 13:23

10 Answers10

133

Lisp WAS used in AI until the end of the 1980s. In the 80s, though, Common Lisp was oversold to the business world as the "AI language"; the backlash forced most AI programmers to C++ for a few years. These days, prototypes usually are written in a younger dynamic language (Perl, Python, Ruby, etc) and implementations of successful research is usually in C or C++ (sometimes Java).

If you're curious about the 70's...well, I wasn't there. But I think Lisp was successful in AI research for three reasons (in order of importance):

  1. Lisp is an excellent prototyping tool. It was the best for a very long time. Lisp is still great at tackling a problem you don't know how to solve yet. That description characterises AI perfectly.
  2. Lisp supports symbolic programming well. Old AI was also symbolic. It was also unique in this regard for a long time.
  3. Lisp is very powerful. The code/data distinction is weaker so it feels more extensible than other languages because your functions and macros look like the built-in stuff.

I do not have Peter Norvig's old AI book, but it is supposed to be a good way to learn to program AI algorithms in Lisp.

Disclaimer: I am a grad student in computational linguistics. I know the subfield of natural language processing a lot better than the other fields. Maybe Lisp is used more in other subfields.

Nathan Shively-Sanders
  • 18,329
  • 4
  • 46
  • 56
  • 35
    Lisp is definitely still alive and kicking in the Machine learning/ILP world – HasaniH Jul 20 '09 at 15:15
  • 14
    I had an undergraduate course in AI taught in C. I had a graduate-level course in AI taught from Norvig's book. The book in C focused on AI algorithms and structures. Norvig's book felt like: "let's learn LISP while we read about AI history." In my opinion, an utter time-waster. – San Jacinto May 22 '10 at 22:42
  • 10
    One reason everyone seems to miss is that John McCarthy wrote Lisp and was a very influential Computer Scientist, specifically in the field of AI. Naturally, a lot of his work was implemented in Lisp, and thus Lisp gained a foothold. – cha0site Apr 09 '12 at 18:30
  • 3
    Common Lisp was never intended to be *the AI language*, it was created to be used in the industry. For research, Scheme is usually used. And never, ever judge a language by its age - it just isn't proportional to coolness, and vice versa. C is old but cool, so why does Lisp's age matter? – Luka Ramishvili May 17 '12 at 19:51
  • 2
    I don't it's accurate to was that Lisp *WAS* used for AI until the end of the 1980's. **In the year 2016 MIT remains a fairly well-renowned institution in the field of AI.** The recommended textbook for MIT's undergrad robotics course is `Artificial Intelligence by Patrick Henry Winston`. By the 2nd edition the programming chapters of that book branched into their own, synchronized, book -- `Lisp`. As the name implies, the programming is *entirely* in `Lisp`. http://people.csail.mit.edu/phw/Books/LISPBACK.HTML – Hack-R Jan 15 '16 at 14:40
  • Lisp begat Python begat Tensorflow. :) – Will Ness Feb 17 '18 at 18:38
65

Lisp is used for AI because it supports the implementation of software that computes with symbols very well. Symbols, symbolic expressions and computing with those is at the core of Lisp.

Typical AI areas for computing with symbols were/are: computer algebra, theorem proving, planning systems, diagnosis, rewrite systems, knowledge representation and reasoning, logic languages, machine translation, expert systems, and more.

It is then no surprise that many famous AI applications in these domains were written in Lisp:

  • Macsyma as the first large computer algebra system.
  • ACL2 as a widely used theorem prover, for example used by AMD.
  • DART as the logistics planner used during the first Gulf war by the US military. This Lisp application alone is said to have paid back for all US investments in AI research at that time.
  • SPIKE, the planning and scheduling application for the Hubble Space Telescope. Also used by several other large telescopes.
  • CYC, one of the largest software systems written. Representation and reasoning in the domain of human common sense knowledge.
  • METAL, one of the first commercially used natural language translation systems.
  • American Express' Authorizer's Assistant, which checks credit card transactions.

There are thousands of applications in these areas that are written in Lisp. Very common for those is that they need special capabilities in the area of symbolic processing. One implements special languages that have special interpreters/compilers in these domains on top of Lisp. Lisp allows one to create representations for symbolic data and programs and can implement all kinds of machinery to manipulate these expressions (math formulas, logic formulas, plans, ...).

(Note that lots of other general purpose programming languages are used in AI, too. I have tried to answer why especially Lisp is used in AI.)

Rainer Joswig
  • 136,269
  • 10
  • 221
  • 346
  • 13
    Yes, historically AI was more about symbolic computation than anything else. The "*AI winter*" in the 80's was probably more a crisis of **symbolic** AI - in that time there was a resurgence of interest in sub-symbolic methods (neural networks, machine learning and so on). Lisp implementations were usually quite weak at numeric computing. I don't know if they improved on this front. – MaD70 Oct 17 '09 at 02:13
  • 2
    @MaD70: the AI winter in the 80s was about AI in general. The military stopped much of the funding and AI mostly failed in the commercial market. Even the neural network stuff that existed at that time. If one sees that AI then as 'novel software development methods' (using rules, logic, neural networks, garbage collection, ...) - that also failed. Much of that isn't even widely used/liked today. – Rainer Joswig Aug 20 '10 at 08:40
  • My impression at the time and in retrospect was/is different: I clearly remember resurgence of interest, both in research and in the market (there were even dedicated neural processors), in sub-symbolic methods in the second half of the '80s/early '90s, after decades of ostracism (see my answer, where I mention the influence of Minsky&Papert criticism of perceptrons: http://stackoverflow.com/questions/683124/neural-networks-obsolete/1581071#1581071). – MaD70 Oct 02 '10 at 12:43
  • 1
    Symbolic AI failed, IMO, because of hardware of the time (not powerful/cheap enough) AND because such harsh contrast between symbolic vs sub-symbolic camps precluded any synergy. W.r.t. "even widely used/liked today": I suspect that some of the techniques developed in AI (in both camps) are much more in use than one can think (no more hyped, fortunately). – MaD70 Oct 02 '10 at 12:43
  • Just an example: at the end of the '90s some of my acquaintances asked me about the feasibility of a project for quality control in the textile field. Off the top of my head I mentioned neural networks as a promising approach for such discrimination problem (essentially image classification). With only such suggestion, in some weeks they found an already developed software, using neural networks, and they acquired its distribution rights - much more sensible than embarking in a project involving R&D. – MaD70 Oct 02 '10 at 12:44
  • @MaD70: is QA in textiles with NN and image processing really AI? It does useful work, no doubt... – Rainer Joswig Nov 20 '13 at 10:04
  • How can Lisp be bad at numeric computing? Its very easy to translate S-expressions to compile to Fortran / C code in a Lisp program. Garbage Collection is much more popular today than it was back in the day. CSS, SQL, Project Dependency managers(make) are relational logic / constraint languages that are popular today, Excel is a dataflow language thats popular. – aoeu256 Jul 27 '19 at 20:16
23

One reason is that it allows you to extend the language with constructs specific for your domain, making it, effectively, a domain specific language. This technique is incredibly powerful as it allows you to reason about the problem you are solving, rather than about shuffling bits.

dsm
  • 10,263
  • 1
  • 38
  • 72
  • Can you provide or link to an example of this? – DuckMaestro Oct 25 '11 at 01:38
  • 10
    @DuckMaestro: In about 30 minutes of macro work this week, I implemented an ad-hoc buggy version of SQL Select. It goes like this: (query SELECT * FROM dataset WHERE expr). – Paul Nathan Nov 12 '11 at 20:08
  • Embedding an algebra solver in Lisp https://www.youtube.com/watch?v=X21cKVtGvYk&list=PL3E830012680E1B5C&index=6 Embedding a circuit language in Lisp https://www.youtube.com/watch?v=SsBxcpkyMMw&list=PL3E830012680E1B5C&index=10 Embedding Lisp into Lisp https://www.youtube.com/watch?v=0m6hoOelZH8&list=PL3E830012680E1B5C&index=13 Embedding Prolog in Lisp - Just watch the whole series – aoeu256 Sep 25 '19 at 23:13
  • https://www.youtube.com/watch?v=SLcZXbyGC3E <- This one is good – aoeu256 Sep 25 '19 at 23:24
11

My guess has always been that, being a functional language, it doesn't differentiate between code and data. Everything, including function definitions and function calls can be treated as lists and modified like any other piece of data.

So self-inspecting, self-modifying code could be written easily.

aib
  • 45,516
  • 10
  • 73
  • 79
  • 10
    That's not because it's functional. Prolog has the same property - everything is a "term" and terms are data as well as code. (Prolog is a logic programming language and also used a lot for AI) – Hugh Allen Sep 24 '08 at 23:25
  • 1
    The fancy term for this is called Homoiconicity - https://en.wikipedia.org/wiki/Homoiconicity – Morten Jensen Jan 13 '19 at 15:43
10

One possible answer is that AI is a collection of very hard problems, and Lisp is a good language for solving hard problems, not just AI.

As to why that is: macros, generic functions, and rich introspection allow for concise code and easy introduction of domain abstractions — it's a language that you can make more powerful. For a lot of problems that's unnecessary, and it comes with its own costs, but for other problems that power is needed to make any headway.

Rich
  • 2,853
  • 1
  • 20
  • 20
7

I think it's wrong to think about this in terms of AI only. Things like the AI-winter and commercial effects on common lisp are distracting if you're asking why it was used for AI, not why it's not often used now ...

Anyway, I think it's because most of the AI code was essentially research code. Lisp is a great language for exploratory programming, for implementing difficult algorithms, for self-modifying and often modified code. In other words, for research code.

I use lisp today for some of my research code (mathematics, signal processing) because it's more flexible and powerful than most languages while still generating more efficient code than most languages. I can typically get performance within a factor of +/- 2 of say c++ speed, but I can implement things much faster, and deal with complexity that would take me far more time than I have if I used c++, java, c#.

That's wandering off topic though. I think AI code was primarily written in common lisp for a while because it is a powerful approach to research code. It still is; but as `AI' algorithms became better understood and explored, parts of them were much easier to teach and use, so they showed up in flavor-of-the-year languages in undergrad courses. From there, it becomes an issue of what people already know, what libraries are available, and what works well for large groups.

simon
  • 7,044
  • 2
  • 28
  • 30
6

I'd guess that a big reason was the flexibility of lists as a basic data structure.

at the time, being able to turn them into all kind of composite objects, and new things as message passings and polimorphism, made it the language of choice; not specifically for AI, but for big, complex, tasks. especially when they were experimenting with concepts.

Javier
  • 60,510
  • 8
  • 78
  • 126
4

I think you're right: Lisp was a handy tool for hacking things up. This is because it didn't distinguish much between program and data. This allowed hackers to manipulate functions very easily, just like data.

But lisp is quite difficult for humans to read, with its braces and non-distinction between data and program. Today, I won't use lisp for any production AI code (or perhaps even prototyping) but would much prefer python for scripting.

Another thing to consider is the existing libraries/tools in/related to the language. I am not in a position to compare lisp libraries with python libraries, but I guess libraries and open source matter a lot more now than before.

This answer was inspired by the following comparison between lisp and python: http://amitp.blogspot.com/2007/04/lisp-vs-python-syntax.html

amit kumar
  • 20,438
  • 23
  • 90
  • 126
  • 3
    I personally find Lisp easier to read than most languages, and I only learned it a few weeks ago. Python is especially clean compared to most languages, yes, but if you compare lisp to something like C++ it is far cleaner and easier to read. In my experience anyway. – Zeusoflightning125 Jul 23 '14 at 21:24
4

I remember hearing that, being a functional language, Lisp was a very good choice for implementing recursive algorithms. Being able to track down a tree and work your way back is essential when considering the decision making processes (traversal) and end result (leaf node).

This was told to me during an AI course at university where we studied Lisp.

mlambie
  • 7,467
  • 6
  • 34
  • 41
  • 1
    Macros in Lisp are more powerful than anything else, letting you implement OOP in only 50 lines of Lisp code and the REPL lets you edit your program while its still running... Only Lisp can edit its own source code easily... – aoeu256 Sep 25 '19 at 22:56
3

A more cynical answer might be "because it lost a political AI war between Japan and the USA in the 1980s". There is an fun blog post that speculates about the impact of the Fifth-Generation Computer System demise on the Prolog.

Anon
  • 41
  • 1