Friday, May 17, 2013

LISP Prolog and Evolution

I just saw David Nolen give a talk at a LispNYC Meetup called:


LISP is Too Powerful

It was a provocative and humorous talk. David showed all the powerful features of LISP and said that the reason why LISP is not more adapted is that it is too powerful. Everybody laughed but it made me think. LISP was decades ahead of other languages, why did it not become a mainstream language?

David Nolen is a contributor to Clojure and ClojureScript.
He is the creator of Core Logic a port of miniKanren. Core Logic is a Prolog like system for doing logic programming.

When I went to university my two favorite languages were LISP and Prolog. There was a big debate weather LISP or Prolog would win dominance. LISP and Prolog were miles ahead of everything else back then. To my surprise they were both surpassed by imperative and object oriented languages, like: Visual Basic, C, C++ and Java.

What happened? What went wrong for LISP?

Prolog

Prolog is a declarative or logic language created in 1972.

It works a little like SQL: You give it some facts and ask a question, and, without specifying how, prolog will find the results for you. It can express a lot of things that you cannot express in SQL.

A relational database that can run SQL is a complicated program, but Prolog is very simple and works using 2 simple principles:

  • Unification
  • Backtracking

The Japanese Fifth Generation Program was built in Prolog. That was a big deal and scared many people in the West in the 1980s.

LISP

LISP was created by John McCarthy in 1958, only one year after Fortran, the first computer language. It introduced so many brilliant ideas:

  • Garbage collection
  • Functional programming
  • Homoiconicity code is just a form of data
  • REPL
  • Minimal syntax, you program in abstract syntax trees

It took other languages decades to catch up, partly by borrowing ideas from LISP.

Causes for LISP Losing Ground

I discussed this with friends. Their views varied, but here are some of the explanations that came up:

  • Better marketing budget for other languages
  • Start of the AI winter
  • DARPA stopped funding LISP projects in the 1990s
  • LISP was too big and too complicated and Scheme was too small
  • Too many factions in the LISP world
  • LISP programmers are too elitist
  • LISP on early computers was too slow
  • An evolutionary accident
  • Lowest common denominator wins

LISP vs. Haskell

I felt it was a horrible loss that the great ideas of LISP and Prolog were lost. Recently I realized:

Haskell programs use many of the same functional programming techniques as LISP programs. If you ignore the parenthesis they are similar.

On top of the program Haskell has a very powerful type system. That is based on unification of types and backtracking, so Haskell's type system is basically Prolog.

You can argue that Haskell is the illegitimate child of LISP and Prolog.

Similarity between Haskell and LISP

Haskell and LISP both have minimal syntax compared to C++, C# and Java.
LISP is more minimal, you work directly in AST.
In Haskell you write small snippets of simple code that Haskell will combine.

A few Haskell and LISP differences

  • LISP is homoiconic, Haskell is not
  • LISP has a very advanced object system CLOS
  • Haskell uses monadic computations

Evolution and the Selfish Gene

In the book The Selfish Gene, evolutionary biologist Richard Dawkins makes an argument that genes are much more fundamental than humans. Humans have a short lifespan while genes live for 10,000s of years. Humans are vessels for powerful genes to propagate themselves, and combine with other powerful genes.

If you apply his ideas to computer science, languages, like humans, have a relatively short lifespan; ideas, on the other hand, live on and combine freely. LISP introduced more great ideas than any other language.

Open source software has sped up evolution in computer languages. Now languages can inherit from other languages at a much faster rate. A new language comes along and people start porting libraries.

John McCarthy's legacy is not LISP but: Garbage collection, functional programming, homoiconicity, REPL and programming in AST.

The Sudden Rise of Clojure

A few years back I had finally written LISP off as dead. Then out of nowhere Rich Hickey single-handed wrote Clojure.

Features of Clojure

  • Run on the JVM
  • Run under JavaScript
  • Used in industry
  • Strong thriving community
  • Immutable data structures
  • Lock free concurrency

Clojure proves that it does not take an Google, Microsoft or Oracle to create a language. It just takes a good programmer with a good idea.

Typed LISP

I have done a lot of work in both strongly typed and dynamic languages.

Dynamic languages give you speed of development and are better suited for loosely structured data.
After working with Scala and Haskell I realized that you can have a less obtrusive type system. This gives stability for large applications.

There is no reason why you cannot combine strong types or optional types with LISP, in fact, there are already LISP dialects out there that did this. Let me briefly mention a few typed LISPs that I find interesting:

Typed Racket and Typed Clojure do not have as powerful types systems as Haskell. None of these languages have the momentum of Haskell, but Clojure showed us how fast a language can grow.

LISP can learn a lesson from all the languages that borrowed ideas from LISP.
It is nature's way.

25 comments:

Anonymous said...

I enjoyed reading this. It was informative, especially your comments on Prolog and Haskell.

Unknown said...
This comment has been removed by the author.
Unknown said...

It might seem like a banality, but actually Lisp is written "Lisp", not all capital "LISP". Just saying, since I think some people who read this post never really heard of Lisp before and will then think it's written "LISP".

Also, little typo: "Partly by borrowing ideas from LIPS."

Other than that, great post. I often wonder why there aren't more people using Lisp.
Funny is how people "decide" not to use Lisp because of it's syntax - whereas Lisp actually lacks syntax.

People should stop judging things by its cover, so they can clearly see its power.

Anonymous said...

Typos just kill the reading pleasure
s/LIPS/LISP/g

Cheers

grant rettke said...

Another reason might be that Haskell crystallized around 1998, and .... the Internet was well and thriving (what ever happened to the ML family???). Reminds me of FreeBSD fading into oblivion vs Linux.

Sami Badawi said...

s/LIPS/LISP/g
I had fixed a couple manually.
I usually spend more time proofreading. I wanted to get this post out close to the meetup.

Sami Badawi said...

Hi Manuel,

Thanks for all the spelling tips.
Of course the one post I rushed out the door is the one that gets picked up by Reddit while I am without internet connection for 3 days.
I was horrified when I read my abysmal English, which of course is not my first language.


I am old school. Writing it like John McCarthy and David Nolen. :-)

Jeff Caldwell said...

s/Dawkings/Dawkins/g

Sami Badawi said...

s/Dawkings/Dawkins/g
done.
Thanks AndroidStudent

Sami Badawi said...

This post has been proof read by crowd sourcing.

Slobodan Blazeski said...

Lisp failed because it didn't became default language for popular platform, http://slobodanblazeski.blogspot.com/2010/05/becoming-popular.html

hasknewbie said...


I think part of C/C++ success vs Lisp is that a lot of graduates students in the 70's and 80's were funded by ATT ( Berkeley Year on Campus program for example). So not to bight the hand the feeds a lot of them ended up using C and C++ at Berkeley and at other schools. Then they migrated in Silicon Valley and companies like Sun, Apple and HP.
Also, the West coast C users had more successful companies than the ones back in Boston that favored Lisp, Scheme etc. Intel and Sun succeeded while Symbolics etc failed.

Morten Brodersen said...

In the early days, vastly more people were financially successful with Fortran and C than with Lisp.

Newcomers copied what others did successfully before, including the languages they used. Rince repeat, and you have exponential growth. Game Over for Lisp.

It has nothing to do with the language. Case in point: the sudden popularity of Objective-C because of early financial success with iPhone application. Before then close to nobody used Objective-C. Now it is in the top 5 according to some measures.

Again, it has nothing to do with the quality/features of the language.

Another example: the sudden popularity of Javascript the moment a few successful websites started using it for "desktop like" applications.

Not to mention PHP. Same thing.

What it takes Lisp/Clojure to "win": write financially successful software using those languages. Make it will known that those application were written in Lisp/Clojure. Do it a lot. Game Won.

Unknown said...

AutoCAD was Lisp. I speculate it was changes to C for lack of programmers.

Unknown said...

Great article!

@ Mg Zuil:
Nope AutoCAD *used* Lisp as its macro language, it still does. Interpreted at first and later a compiler added. The built-in Lisp interpreted was actually stolen from XLisp 1.0 in the early 80's. Later a 3rd party created the VitalLisp extensions + compiler which AutoDesk then bought and renamed VisualLisp (which is the current built-in Lisp engine).

AutoCAD itself was written in C and later (mid 1990's) C++.

Unknown said...
This comment has been removed by the author.
Unknown said...

"Lowest common denominator wins"

What did You mean?

Sami Badawi said...

Hi Oleg Kovalov,

By "Lowest common denominator wins"
I mean that things that dumbed down get popular.

Unknown said...

Nice article!

Bob said...

Too many fractions in the LISP world

s/fractions/factions/

Sami Badawi said...

Hi Bob,

s/fractions/factions/ done.

Thanks!

matthias said...

What makes you think Typed Racket's type system is not as powerful as Haskell's? How do you compare?

Before you respond, please consider that Typed Racket has (1) occurrence typing [completely novel] (2) subtyping and 'true' unions (3) first-class polymorphic functions. It lacks abstract types (by choice) but has opaque structures. It lacks type classes but has a rich numeric tower and overloading where programmers can prove as much or more than in Haskell about their functions.

-- Matthias

matthias said...

p.s. And who says Lisp is dead? Perhaps Lisp 1.5 is dead, but Lisp/Scheme/Clojure/Racket are very much alive.

Sami Badawi said...

Hi Matthias,

I want to work with Typed Racket, but I am stuck with Scala and Haskell now. It is hard to say what is better, sometimes less is more.

My point was not to put Lisp down, quite the contrary.

Paul Berger said...

C was promoted as the language for system programming, besides it was and still often is the intermediary language another higher language resolves to for portable cross compilation.

As states and the precise sequencing of operations are paramount for drivers, IO protocols and network programming it is all too normal C thrived.

On the other hand if one would have ported the cumbersome LISP machines programming model in a portable VM and successfully had run it over the Motorola 68000 and Intel 80386 architecture, history would have been different but maybe not so much as Smalltalk proved this model not so enduring, JMHO.