I second Clause and Effect. (The Little Schemer, too, but CAE doesn't get much attention.) Sterling and Shapiro's _The Art of Prolog_ is also excellent, though

I second Clause and Effect. (The Little Schemer, too, but CAE doesn't get much attention.) Sterling and Shapiro's _The Art of Prolog_ is also excellent, though you'll probably be better off reading _Clause and Effect_ first if you've never used Prolog. CAE is all about getting a feel for how Prolog operates, step-by-step* , while TAoP is about the logic programming paradigm, interspersed with project case studies and comparisons between Prolog (as an LP implementation with various compromises) and "pure" LP. * This is the main thing it has in common with The Little Schemer: both begin by stepping through their respective languages' evaluation at a micro-level, until the semantics feel totally clear. This is especially helpful since Scheme and Prolog are both very different from the typical imperative/OO languages people know. FWIW, The Little MLer is written in the same style as TLS, and is a good, lightweight introduction to ML's type system / static typing.