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.

Wednesday, May 1, 2013

Collision with the Zeitgeist

It has been 5 years since I started my blog. Back then I was alone with my obscure computer interests: functional programming languages, machine learning and AI.

I felt lucky when I met a Python programmer that I could chat with once in a while. Occasionally I would boil over and just start a computer rant to people at social events, until they ran off.

When I met my first Haskell programmer at a machine learning Meetup, it was like seeing a unicorn. Now I use Scala for work and discuss Haskell, Idris, LISP, category theory or machine learning on a daily basis.

In April 2013 my blog had over 8000 page views, which is more than I ever had imagined.


I am still surprised that my once obscure interests have become part of the zeitgeist, and hope they will stay for a while. But with technology you never know what is coming next.