Posterous theme by Cory Watilo

Know Your Bounds

Thomas G. Kristensen wrote a nice little post about finding cliques in a graph with core.logic. I recommended reading it first before continuing. It's a very short informative post and the code is clear if you have at least some familiarity with core.logic. At the end of his post he points out a couple of problems - it's about 1000X slower and worse, it doesn't terminate if you specify some number of desired results above 22.

There were a couple of very minor things about his approach that bugged me but figuring out the termination issue really got me thinking. I realized that the issue with his program is that all-connected-to-allo would continue to search for answers even though there weren't anymore to find! That is all-connected-to-allo continues searching for cliques of size n even if n is greater than the number of vertices in the graph.

Prior to cKanren expressing a bounded list relation would have been quite difficult. It's now possible to do this in a relational manner.

This relation guarantees that the size of a list can never exceed n. We can now use this relation to ensure that the clique list never exceeds 6, the number of vertices in the graph we are querying.

Here is the full program:

And it's fast - on my machine this finds all cliques (20) in ~3.5-4ms. Even better if you don't specify how many answers you want it will always terminate.

bounded-listo is so useful I've added it to core.logic.

friendlier

I added a new "pseudo" goal everyo to core.logic. This allows us to remove the redundancy I mentioned yesterday. I also made passing in puzzle hints much more friendly. It should be easy now for anyone to input a sudoku puzzle that's giving them trouble!

I did a small amount of benchmarking yesterday. It turns out that easy sudoku puzzles can be solved in about 6-7ms on my machine. I tried Norvig's hardest puzzle and that takes around 60ms, not 188 seconds that he documented for Python.

There are of course much faster sudoku solvers, and in general I imagine core.logic will never compete with constraint solvers like GeCode or JaCoP. But I'm confident that core.logic is fast enough to be practical and applicable to many problems. Also we haven't given up on the essence of Prolog.

I'm looking forward to seeing this work run on ClojureScript.

A Logic Programming Reading List

A couple of people have asked me if there are any texts that I might recommend on logic programming. First off, let me clarify that I’m very new to the practice of logic programming myself. It’s an incredibly rich field with decades worth of research that’s still being actively explored from many different perspectives. The following list will reflect my biases - I’m as interested in implementation as I am in its practical use.

Thanks to Jim Duey, I became acquainted with logic programming via The Reasoned Schemer.

9780262562140-f30

Written in the same Socratic style as The Little Schemer, The Reasoned Schemer is an incredible well of entertainment, frustration, and outright mysteries. After struggling through its particular flavor of Hard Fun™ , I found it even more confounding that the entire implementation consists of 200 lines of very subtle Scheme.

So while I love The Reasoned Schemer, I do not think it’s the best introduction to logic programming. But if you savor challenges … look no further. 

I recommend a gentler approach - install a well supported open source Prolog implementation (SWI-Prolog, CiaoProlog) and get Sterling & Shapiro’s The Art of Prolog or Ivan Bratko’s Prolog Programming for Artificial Intelligence, or both.

9780262193382-f30

0201403757

After that, if you’re like me, you’ll want to solidify your understanding of the paradigm by actually building a simple implementation. While I had an intuitive understanding of objects, until I built the object oriented system presented in The Structure and Interpretation of Computer Programs, OOP always seemed a bit magical. Logic programming is no different. Building a simple logic engine will deepen your understanding in incomparable ways.

Peter Norvig’s Paradigms of Artificial Intelligence Programming has a classic implementation in Common Lisp.

Paradigms-artificial-intelligence-programming-case-studies-common-lisp_3618_500

William Byrd’s dissertation on miniKanren covers the entire implementation behind The Reasoned Schemer in one chapter. Norvig’s approach will probably be more digestable for someone comfortable with imperative approaches. Similarly, miniKanren will be somewhat daunting if you’re not acquainted with building interpreters or the monadic approach. But if you’re an experienced functional programmer or just plain stubborn, it’s worth it. Sadly I’m not aware of any succinct yet relatively performant non-Lisp approaches - if you know of one, please let me know!

At this point you’ll have quite a bit of knowledge but perhaps it will still be difficult to see how to put any of this into practice if object oriented programming or functional programming pays the bills. How can logic programming be incorporated sensibly into everday practice? 

Concepts, Techniques, and Models of Computer Programming (CTMCP) compellingly describes what a truly multi-paradigm approach to software construction might look like.

9780262220699-f30

Armed with an understanding of the paradigm and basic implementation experience, perhaps this book will give you cool ideas on how to idiomatically embed a simple logic engine into your programming language of choice! CTMCP also covers constraint logic programming which considerably broadens the scope where logic programming can be practically applied.

This short list can serve only as introduction. But hopefully this reading list will provide enough basic material to make approaching the deeper literature less daunting.  Fortunately all the recommended texts here have extensive bibliographies to guide your adventures.

 

 

Lisp doesn't matter

Lisp doesn’t matter.

There I said it.

If you follow this blog, or read my Twitter feed you’ll probably know that I’m deeply involved in the Clojure community. But the level of my involvement is founded on two fundamental things. First, Clojure allows me to explore various aspects of computer science that I find interesting without exerting ridiculous amount of time and energy. I have a job at the New York Times, family, good friends, and other personal creative projects. I have only a few hours a week to explore what I consider to be hard, interesting problems - I need an efficient tool. The second reason is equally important - what’s enjoyable about working on hard, interesting problems without a receptive audience? My first degree is in Film, for me communicating with an audience is critical.

Audience is the main reason I don’t spend too much energy on Common Lisp and Racket (both incredible languages). Life is too short and the audiences are simply too small.

Is community everything? Of course not. The tool you pick will make exploring certain problems easier or harder depending on the constraints you impose - time, generality, performance, extensibility, etc.

Wait? But what problems am I actually interested in?

Do yourself a favor and watch the following videos - Sussman’s We Really Don’t Know How To Compute!, Rich Hickey’s Simple Made Easy, and Alan Kay’s presentation for the ACM's Turing Centenary. The same theme comes up again and again. WHAT not HOW.

So what really matters for me is chipping away at John McCarthy’s challenge that we should infuse our programming languages with a little more Common Sense. When your goal is so far fetched and optimistic it really helps to have a receptive audience. So I thank each and everyone of you who has ever responded to anything I’ve posted or tweeted.

Hooking up core.logic to Light Table is gonna rock.

 

Mori: Persistent Data Structures for JavaScript

I've created several functional programming utility libraries in the past for JavaScript and CoffeeScript. Today they have become obsolete with the release of Mori. Mori is a simple bridge from vanilla JavaScript to ClojureScript's persistent data structures and the supporting API. Mori even includes Rich Hickey's new reducer work for allocation free operations on collections.

So maybe your boss won't let you use Lisp - well use Mori - it's just ~20k of gzipped JavaScript.

Illiterate Programming

Donald Knuth cleverly imprisoned the phrase "Literate Programming" - if you're not documenting your source with his particular methodology then you must be a proponent of "Illiterate Programming," which sounds truly awful.

I very much believe in documented code but I think no amount of pontification in English will ever make a piece of code clearer than the code itself (I'm not talking about project or API documentation). I'm also not talking about the superficial notions / arguments of "readability" that are bandied about these days (Python, CoffeeScript, etc).

Most languages have no deep notion of readability in their core. 

Take a look at this page of Smalltalk:

St

One of the most lovely ideas in Smalltalk was the ad-hoc categorization, "protocols" - here you see initialization, accessing, private. These were not reified in the language but instead were a level of documentation baked right into the software writing experience.

In a similar vein, one of my favorite features of Clojure and ClojureScript is protocols. Their least celebrated benefit is readability - here's how JavaScript primitive arrays are extended to participate in some core language concepts:

Smalltalk has so very few concepts - it's truly stunning. There's nothing more powerful in aiding readability than a small core set of concepts. In this sense I think Smalltalk continues to be one of the few languages to get anywhere near LISP. Most languages these days are just an abomination of features trapped inside of a compiler.

Yet I think Smalltalk still fundamentally failed (remember this is a programming language originally designed to scale from children to adults) because Objects are really hard and no-one really understands to this day how to do them right. This isn't to say they aren't incredibly useful but I think we've truly gone down the wrong path by putting then onstage. They should be backstage patiently waiting for those folks when they're ready to see how the pudding is made (Art of the MetaObject Protocol).

So I suggest repurposing "Illiterate Programming" to mean something very different. Programs, programming languages, and programming paradigms which strive for readability at a deeper level - the elegant self-evident architecture of very simple concepts. "Literate Programming" is admission of defeat.

Logic Programming & JavaScript

I've started porting core.logic to ClojureScript. So far it feels good to rip out all of the JVM-centric optimization bits. However, I'd like core.logic to run at a decent clip in JavaScript - this means a different approach to optimization as well as staying truer to the Scheme miniKanren implementation (such as using lists for the substitution map). I think by the end I'll have amassed some interesting notes on how to write ClojureScript code that performs quite well in comparison to hand-written JavaScript.

core.logic & VPRI STEPS

I stumbled across this amazing blog series which is tackling computational linguistics by porting Prolog to core.logic. It reminds me a bit of my earlier attempt to implement Definite Clause Grammars. I got something experimental working but in order for core.logic to really scale for large parsing tasks we'll probably need to rethink how core.logic handles substitutions. That said, core.logic does have tabling so building packrat parsers shouldn't be too difficult.

All this brings me to the incredibly succinct program in Appendix II of the VPRI 2011 Report (Alan Kay et al). They start with a machine oriented lisp, define a grammar, implement Smalltalk, and finish with a non-trivial program.

Could we take similar approaches when writing software with Clojure?