Anyo

Well, the semester is finally over, and while I won't say that my my project is finished, exactly, it's at least most of the way there.

I will get an A in Friedman's class - and I would just like to say again that being in Friedman's class was a pleasure. The man's an amazing teacher, in his way. Certainly ace at getting you interested in the subject! Unfortunately, there wasn't enough interest to start up a B621 class (the advanced version of B521); maybe next year. So I'm doing the next-best thing and taking Programming Language Implementation instead.

So what do I mean when I say I never finished my project? Basically, it has to do with anyo, which we were required to implement. One of the main points of MiniKanren is that it can get potentially infinite numbers of return values, and anyo is one of the engines by which it does that. When implementing MiniKanren in Scheme this is no problem - because not only does Scheme have macors, but it collapses tail recursion. So if you want a function that turns into a stream - that is, has potentially infinite numbers of values, it's trivial in Scheme. You just define a base case where it returns but define the other cases with further function calls. So if you don't get the base case (that is, n is not equal to 0, or whatever), then the function just returns a call to the same function, which in turn returns a call to the same function, and so on potentially forever.

The problem with this in languages like Ruby is that if you don't collapse these calls, then the computer runs out of memory. You know, because it has to store the whole list of function calls it's waiting to execute, and no computer has infinite storate space! So the trick depends on NOT evaluating the returned function call unless you have to - so-called lazy evaluation - or else you have to make it iterative (so it erases calls after it's executed them - or more accurately just never generates them at all to the same extent).

Unfortunately for me, Ruby doesn't have this, at least not directly. I chose Ruby because I thought it could double as a fully functional language. It turns out it doesn't exactly. (In fact, one other student used Ruby and did his code in the normal functional way - that is, using lambdas and passing functions to functions and all that - and he reports that lambda in Ruby is excruciatingly slow - causing his code to take as many as 30sec. to evaluate factorial of 5!!! So there's that problem with it too.) So I got scared and decided instead to write an interpreter. Which means that my implementation isn't really very Ruby-dependent at all. It could easily be translated to any language (which is good for me, since I have an official promise to myself to implement - or at least try to implement - MiniKanren in Fortran77...). What it does is read strings into lists, and each of these lists represents a function call. The interpreter reads through the list and knows what to do. I thought this would make infinite behavior trivial - because if you get a "call" to a "function" like anyo, all it has to do is just write out the relevant list and pass it back to itself for interpretation - at which point it writes out the same list again, and so on forever, right?

Well, wrong, for some reason I still don't quite understand. So I won't be posting my code until it's completely working. It gets the expansions right, but then for some reason stops evaluating them and just jumps to the final step. So I've implemented something completely wrong.

The TA was very nice about it, and assured me I would be getting a good grade on the project - mostly because I was the only one who bothered to try to write an interpreter (which apparently is what they really wanted, since that keeps it close to the real Scheme implementation - which depends on macro expansions). Everyone else took advantage of the builtin functional shortcuts in their languages. All the other students found it amusing that there is a "Ruby" implementation which makes no use of lambda - but the TA liked it. However, I'm not personally satisfied with it, obviously - so I'm in the superodd position of having completely finished my semester work without the normal rush of freedom you get. Probably a good thing, since I have a tendency to get distracted with things not related to my dissertation at that point. This break it will be easier to stay focused. (Speaking of which, Knuth's Masterwork comes back online tomorrow.) And I REALLY need to stay focused this break, since I will be taking not only my P-level in CSCI next semester (the aforementioned Programming Languages Implementation class) and will have to know some Assembler for that (which I don't), but also a course in Datamining that I hear is pretty intensive - so I'll need a thorough brushup on statistics, and enough knowledge about databases (which I currently don't have - can't even write a Hello, World! in PHP!!!) to pretend like I've done some of this before. In spite of everything, I'll also be taking Advanced Algorithms, which won't be easy, but won't be the worst of the lot either. And then a course in Syntax, which in itself isn't that much, but four classes has always proved to be one too many when teaching - so it wouldn't hurt to get started on my final paper in that over the break so it won't throw off my balance come crunch time Spring 2007! I.e., I don't really get a break, so it's nice in a way that I didn't get a clean finish this semester. What happened instead was that me and two other students spend five hours in the Computer Science bldg. yesterday (during which time I forgot I had driven to school, walked home, found my car not there, briefly panicked, remembered, and took the bus back into town to find a $-40 present for me from the parking nazis) slaving away at getting anyo to work - which I gather none of us did.

So - expect posted code soon. It will also be nice to have the chance to clean it up!

Overall I'm pleased with the project, though. My implementation has the virtue of allowing you to type code directly in MiniKanren, so I can actually write programs in the normal way (athough I've tricked out the syntax to make it easier to parse). Everyone else essentially has to write Ruby (or Python, or Perl, or Java) programs that generate the behavior in MiniKanren they want - which is obviously much clumsier.

As for Ruby - I've discovered that it's a deeply weird language, but I like it anyway. I'll be doing more programming in it over the next couple of weeks, so I'm sure I'll have an opportunity to expand on that thought. Friedman called it a junk language. Well - not Ruby specifically. He's on record saying that Ruby's yield operatior is possibly more complicated than call/cc (he hasn't decided yet). But he did say that he was displeased when he saw the list of languages we were using. "The junk languages of the world," he said. "Ruby, Python, Java - nobody did SML or Haskell, where you would have been done in 10min." Well, yes, right, I did consider SML - and the reason I chose Ruby is because I DIDN'T want to be done in 10min. It's no demonstration of my ability in this class if I just translate Scheme code into Scheme-friendly SML, now, is it? Although I admit that I chose Ruby over something like Java as a way of fudging a bit - keeping things from getting TOO hard! The real doozy will be the Fortran77 version, which I guess is possible, but only just. We'll see.

So, the sad conclusion is that the project is only mostly finished. Stay tuned.

(Sidenote - a synonym for "junk languages" in Friedman-speak is "p-languages," meaning Python and Perl. I think the (functional) programming community should adopt this as slang - maybe for "not sufficiently functional" - or for "cute, trivial.")