Archive for the ‘Artificial Intelligence’ Category

Ronald P. Loui: The Best Student AI Work Is Developed in Gawk

August 15, 2007

Here is some surprising evidence that Perl should still be respected in spite of its “indecent” appearance. And while Gawk appears to beat Lisp at its own game in this case, it may in fact be because it has so much in common with Lisp.

Important Gawk Features based on Ronald P. Loui’s AI class experience:

  • Powerful String Processing Language Features
  • Powerful Constructions for Manipulating a Wide Variety of Data in Efficient Ways
  • Interpreted Language with a Short Learning Curve
  • Automatic Initialization, Implicit Coercion, I/O Support and Lack of Pointers
  • Regular Expressions
  • Associative Arrays
  • Relies on the OS to provide Data Organization, Debugging Tools, and Subroutine Libraries
  • Powerful Uniform Data Structure
  • Trivial Syntax
  • Encourages Bottom-Up Design and Exploratory Programming

If you don’t have time to master Lisp, Gawk might be a pretty good substitute….

(I found the link to the above article in the comments of an blog entry that really trashes poor RPG. Just reading through it I noticed a lot people love to make lame complaints about languages they know nothing about. Whether its Lisp or RPG, most of the things people get hung up on have either been addressed in the 20 years since the person last saw the language or that can be addressed by trivial modifications to a text editor. Anyways, old school RPG’s “program cycle” is very similar to the basic premise of gawk– sans most of the more lispy features, of course. RPG’s tight integration to the OS is is also very similar.)

Beyond Data-Driven Design: Are your abstractions “Hairy at Both Ends”?

July 23, 2007

Going into chapter two of Paradigms of Artificial Intelligence Programming, we get a deceptively simple program to experiment with. The code for this chapter is located in the file simple.lisp, but note that the file does not include the mappend function from section 1.7. (And you thought that “mappend” was just a clever play on words!!)

The whole purpose of this chapter is to compare two approaches to programming. One translates a problem into code following a “quick and easy path” that appears to be the “simplest” but locks your solution into hard coded assumptions. The other approach uses data to describe the problem at a higher, more abstract level. The functions that “do the work” can be attached to varying data sets… and therefore can solve what, on the surface, appear to be different problems. Also, he demonstrates how the same data can be used for different programs. He promises to use this latter, more abstract approach throughout the book.  He calls it a “Rule-based” approach, and says that it’s more work for small problems, but that it minimizes the amount of the solution that’s “written directly in Lisp.”

Norvig’s treatment of the chapter is different because he emphasizes dynamism and code reuse on all sides of the problem. I typically think in terms of data driven design being a way to allow for infinite customization within a single clearly specified problem. Somehow, Norvig’s abstractions are “hairy” at both ends… allowing for an order of magnitude more flexibility. I do some of the things he demonstrates already. For instance, he uses a list to store data and even includes extra non-functional fluff to make it more readable. Then he makes the Lisp equivalent of property accessors in order to allow the program to be self commenting and easier to modify later. But there’s something about the way he thinks that’s foreign to me… or at least, does not come naturally. He doesn’t quite make such a hard separation between code and data that my experiences with OOP Frameworks and Relational Databases have drilled into me.

The chapter really should be no big deal, but my attempts at exercises 2.1 and 2.2 blew up in my face. The first one wasn’t too bad, but I was ignorant of the fact that setf could be used with lexically scoped variables– and also that setf returns the value. Not knowing those two things can lead to some pretty ugly Lisp code, so I’m glad I’ve learned them. The second exercise I completely misunderstood. I don’t know why. Maybe it has something to do with the fact that his “rewrite” function is named in a counter-intuitive way. I even completely missed it after glancing at the answer. Why is it that when Norvig asks me to do something pretty simple I completely blank out?

At this point I should either keep on moving and start on the next chapter… or I should go back an reread Chapter 2 and try to soak up everything he said without missing anything. I can’t tell if I’m overreacting or not. At any rate, Norvig’s writing is fairly dense and requires a great deal of attention. You can’t just skim it and expect to get much out of it.

SICP can wait… I’m taking on PAIP

July 20, 2007

A lot of people are recommending Structure and Interpretation of Computer Programs, but I just can’t bring myself to dive into it. I’ve got a lot of blood sweat and tears wrapped up in Common Lisp and Emacs and I dread moving to another milieu. I really like Peter Norvig’s teaching style, though… and I’m so excited about Paradigms of Artificial Intelligence Programming. Boardgame AI is one of those topics that I’ve always thought of as being way beyond my abilities. I just can’t even think of how to even brute-force my way through such a task. My default trial-and-error code-munging style is completely inadequate there…. (It’s sort of like having to learn how to read music in order to become a better musician. There’s just something here that I need to learn.)

So my deductive reasoning (ie debugging) skills are moderately strong, but my advanced analytical skills are pretty pathetic. Maybe I’m not ready for PAIP…. How can I know? Well… I’ll just start anyway and if I end up having to take a detour then so be it.

His first problem set seems deceptively simple to me. The questions are very simple to state, but to get through them, you have to be fluent in recursion, recursion in trees, and even in getting Common Lisp to do your recursion for you. These are techniques that I really agonized over when I was working through Shapiro. It’s nice to see that I’ve internalized the them. I didn’t have to think about some of the problems and a couple of them worked on the first try.

The very first problem had a couple of snags that caused me to waste a lot of time. One was how to deal with symbols that had commas in them. Of course, you can sandwich anything you want between a couple of pipe characters to allow commas to be inside your symbol names. But how do you clean them out? After several failed searches and not being able to find anything relevant in Common Lisp the Language, I ended up finding what I needed at that always useful Common Lisp Cookbook. My solution may not be beautiful, but it gets the job done without being overly munge-tacular.

Another thing I did was come up with a way to recurse backwards over a lisp. There’s no way that my (reverse (rest (reverse list)))) approach can be at all efficient, but again… it’s very difficult to know what they call that function in the Common Lisp culture.

If anyone else is working through this classic programming text, please drop by and compare notes with me. Maybe we can put together an informal study group or something.  My code for the Chapter 1 problem set is here.