GULP!

Today in Friedman's Class we got the big bombshell: in place of a final exam we have to implement Mini-Kanren (full technical report here, a goofy application to demonstrate the language in action here) in a language of our choice.

A couple of words about why this could be a bitch of an assignment. First - Mini-Kanren is a logic programming language, and its chief virtue is that it runs forwards and backwards. Pretty much everything is handled through Unification, which is why this works. The spiffy thing about it is that in addition to doing the normal program thing - i.e. you give it a program and it gives you an answer - in a limited sense this one works the other way too - which is to say, you give it an answer and it gives you a program.

That's a sugar-coated way of putting it, of course. In reality, it quickly gets unmanageable, and a lot of the information it would give you wouldn't be very interesting. So, for example, if you give it "5" and some sort of variable in which to store all its responses, it could well give you every possible statement it can think of the answer to which is "5" if you run it. So, you know, it gives you (* 5 1) and (+ 2 3) and (lambda (y) 5) - and eventually starts to get silly, with things like (* 5 (+ 2 (- 3 (+ 2 0)))) and so on. So you wouldn't use it to generate every possible statement that could give you "5" as an answer (it would never return anyway - there are an infinite number of such statements), but it is quite useful for other things. One example we did in class was type inferencing. Some programming languages are "typed," meaning that they enforce rules in which expressions only make sense if used with the proper kinds of values. So, for example, if I multiply 2 and 3, I expect the answer to be another integer. Of course, you can look at it the other way too: if I get an integer as an answer, and I know that it was the result of multiplication, I would expect the two values involved in the expression to also be integers. So it's easy to see how languages like Mini-Kanren come in handy: we need type inferencers to be able to work "both ways." More to the point, the operation involved is really just normal logic unification. That is, statements all pretty much take the form of an equation - like so:

int = int * int

And so on. If I don't know what one of the members is:

??? = int * int

All I really have to do is just unify it with the rule, and the system will realize that the missing element is just "int" (since the rule looks exactly like this statement with the unknown, save that in place of "int" in once place is has "???" - more properly, there would be a variable here).

So Mini-Kanren works well with type inferencing. And of coure, the BIG hope for it is that it will be easily adaptable to automatic theorem proving. (WARNING: the same was hoped for Prolog, and Prolog was something of a disappointment, though it's a healthy programming language and still in regular use over 30 years after it was invented).

Now, anyone who clicked the link to the technical report on Mini-Kanren above will have noticed two things about the language. First - it's very compact. Second - it's implemented in Scheme. The first is what makes it possible to assign this as a last-minute final project in a graduate course. If Mini-Kanren were a full-on programming language, we would need a lot more than a single semester (let alone the just over two weeks we have!) to implement it. The second is what makes it daunting.

See, the thing about Scheme is, it's really (really REALLY) nice for syntax extensions. Scheme is minimalist in the sense that it gives you very little to work with in the package - but maximalist in the sense that what it gives you to work with are high-powered precision tools. It can do (pretty much) anything, just that you might have to build some of what you want to do yourself. In particular, what Scheme has that helps with implementing a language like Mini-Kanren are macros. These allow you - literally - to extend the syntax of the language at low cost. So it isn't really a problem to implement other languages in Scheme - particularly simple languages of streamlined concept like Mini-Kanren. What sucks is that few other programming languages give you these tools in the box. So all the help that Friedman, Oleg and Will had from Scheme getting the base version of Mini-Kanren up and running is unavailable to us for this assignment. And that, of course, is where the challenge comes in. We have to work up a sweat for this one - because we're tested not just on our ability to replicate what was done in class, but in this case how well we actually understood it - because we're applying the knowledge in a completely new environment. It's actually the perfect final for this class. But that doesn't make me any happier about having to do it.

Actually, I'm kidding. I'm ecstatic about doing it. (What I'm NOT happy about is that we apparently have a regular homework assignment due this weekend anyway, and I could really use a break - not the least because I need to get to work on this Mini-Kanren implementation...).

I quickly put dibs on Ruby, a programming language I'm really interested in, have learned, but haven't ever really gotten my hands dirty with. The assignment says that no two people can use the same PL (unless it just so happens that certain people don't have programming experience outside of their One Favorite Language and that turns out to be the same for two people in the class or something), hence my haste (Ruby is sort of trendy these days, so I'm sure someone else would have thought to do it). Of course, the cop-out thing to do is to use a language like Haskell that is similar to Scheme in key ways (in this case: in terms of having lazy evaluation built in, so the infinite recursive features - i.e. the stuff that makes it possible for Mini-Kanren to generate infinite numbers of answers - come easy. Also, Haskell is also a functional language, so the translation from Scheme would be trivial). The badass thing to do is to use a language like Fortran or BASIC which only has very very primitive near-machine-level instructions. I actually was planning to do it in Fortran just to show off, but (fortunately!) Friedman then added that the only other restriction on languages was that the langauge in question must come equipped with a garbage collector. That rules out Fortran (at least, it rules out Fortran77, the version that I would have used) because the only garbage collection I know that's available for g77 - the "standard" home use Fortran77 compiler - is just a collection of homebuilt tools. The language itself doesn't have it.

Now, I'm not going to post here that I want to implement Mini-Kanren in Fortran77 just to show off and then not actually do it. There's nothing more annoying than people who brag they can do something and then don't follow through. But I wiped some sweat off my brow when Friedman ruled out Fortran in this way because it means I don't have to do it NOW. :-) I can start on it when I'm working on my Ruby version (not that Ruby - a purely Object-Oriented Language - is anything AT ALL like Fortran77 - a purely imperative langauge), finish it over the holiday, and mail it to Friedman or Will when (and IF) I finish. The reason I had hoped to do Fortran77 is because I'm interested in how you actually get super-highlevel things like Object Orientation and Infinite Streams out of the actual hardware. Obviously, it happens. Scheme runs, after all, and boasts one of the fastest compilers in the business (and in fact, ML, another highlevel functional language, probably has the best compiler of any language - though I guess C people would take exception to this) - so obviously it's possible to get computers to exhibit the kind of behavior we see in Mini-Kanren. I'm just not clear on all the low-level details some of the time, and Fortran77 would be a nice way to get that way. But OK, Ruby it is (and a damn good thing too!).

This doesn't help my freetime. I know very little about Ruby - so I have to jumpstart knowledge of a new programming language. Which I WANT to do, but probably don't have TIME to do. So we'll see. But it should be interesting. Ruby is a weird little item - whether or not it will continute to look as good on job applications as it does now I don't know (in fact, I have in the past cautiously predicted it won't - another example here - though it's a safe investment for now for sure). But this gives me a good excuse to get really familiar with it, so I jumped on it.

Blogging will be spotty from now till the end of the semester. Wish me luck on the Mini-Kanren implementation (yes, I know that there is an implementation already - but I'm not going to peek at that unless I get really stuck. I haven't actually run it yet - it might not even be any good. There are, in fact, implementations for many languages already out there. I'm sure Giancarlo will have an easy time finding one for Python - the language he got. There's at least one for Java that someone in Friedman's class last year did - but I don't know if it's online. It's probably pretty impressive - getting Java to act like anything but the annoying juggernaut that it is.).

[UPDATE: please forgive the boneheaded math error in one of the above examples. As Noah rightly points out in the comments section, (* 5 (+ 2 (- 3 (+ 2 0)))) actually evaluates to 15. I meant to type this instead: (* 5 (+ 2 (- (+ 2 0) 3))) ]