Lambda the Ultimate

I wish I'd read this sooner. I've been trying to break my imperative mindset by learning Common Lisp - the basic language is great but navigating the libraries is a headache. I might've chosen to learn Haskell instead based on this paper!

Common Lisp, in practice, seems to most commonly be used in a fairly imperative way, although if you want to you can write nice functional programs with it. But if you're really looking to break a mindset, you might be better off with a language that doesn't pander to imperativeness quite so much. Haskell, ML or Scheme are all candidates, in order of purity.

I'd like to add, though, that if you're serious about breaking the imperative mindset, Haskell is indeed the right choice, because it will help you break the imperative mindset about the one thing everyone else, myself included, compromises on: I/O.

Also, don't let the monad mystics get you down: all a monad is is a type constructor and two higher-order functions. No big deal, and there's tons of good material nowadays on how monads can be implemented and used outside of Haskell. Learn to use the State and I/O monads well and you'll have 95% of everything you need to know about imperative-free functional programming.

I'm taking for granted that you know why you want to go beyond the imperative mindset, but if not, let me know and I'll provide pointers to motivation. :-)

Common Lisp - the basic language is great but navigating the libraries is a headache.

I that find with the help of the chapter index page of the CLHS, navigating Common Lisp is fairly easy. I have been using and skimming the CLHS regularly for a few months and can now find anything in a few clicks. What exactly do you find a headache?

I might've chosen to learn Haskell instead based on this paper!

Yeah... I liked that some of the the reviewers (of the "An Experiment in Software Prototyping Productivity" paper) mistook the Haskell program for a spec.

I found that Paul Graham's Ansi CL was a great resource, with its little reference in the back that's nicely categorized and has terse explanations of stuff.

Also, I personally liked the Chineuals, which certainly isn't CL, but...

However, if your desire is to break into pure functional, well CL is too multiparadigm. Here's some great sources:
* The Little Schemer and The Seasoned Schemer
* SICP
* Bird/Wadler's intro to functional programming. In the second edition, Bird dropped Wadler like a hot potato, but I don't know if it's any better. I hear it really uses Haskell now.

There are three answers:

1. FOPL is undecidable in general, and a lot of DL researchers want their inferences to terminate, always.
2. FOPL is more expressively powerful than most DLs at some non-trivial cost in inference performance. One of the big issues in DLs is precisely balancing expressive power against performance. The canonical example of a not-very-expressively-powerful-but-fast DL is the CLASSIC system; the canonical example of an expressively-powerful DL that makes some performance compromises is PowerLOOM.
3. Not all DLs are necessarily first-order; see Logical Foundations of Object Oriented and Frame Based Languages, for example.

What Paul said, re. decidability.
re. DLs and OWL (the Web Ontology Language, what prompted Graham's work), there are also considerations of what is likely to work well in the web environment - OWL is built on top of RDF (Resource Description Framework, which is more expressive, less decidable - far too loose for some), in turn built to work with existing web technologies.

Bit of background, see The making of the Web Ontology Language OWL: a chair’s perspective and s From SHIQ and RDF to OWL: The Making of a Web Ontology Language (PDF, a DLer's perspective)

I'm not sure, but I suspect that it's this.

Given that it's associated with ISI, I wonder whether STELLA doesn't descend from it, in some indirect way.