Infinite Recursion

September 2, 2009

A few days ago I posted an article on Tail Call Optimization. One really quick way to determine if any language/VM/interpreter performs Tail Call Optimization (TCO) is to write a function that calls itself, in other words, creating an infinitely recursive function. If the function just runs forever and doesn't return, the interpreter is doing TCO, otherwise you will get some sort of stack overflow error. So I decided to test a variety of languages to see what happens when you write an infinitely recursive function. First up is ruby:

def forever
  forever
end

forever

It was no surprise to me that running this results in this error:

run.rb:2:in `forever': stack level too deep (SystemStackError)
    from run.rb:2:in `forever'
    from run.rb:5

Ruby doesn't have TCO, I knew that. Next up, Python:

def forever(): forever()

forever()

This has a similar result, but the stack track is a little more revealing:

Traceback (most recent call last):
  File "run.py", line 3, in <module>
    forever()
  File "run.py", line 1, in forever
    def forever(): forever()
  File "run.py", line 1, in forever
    def forever(): forever()
...
  File "run.py", line 1, in forever
    def forever(): forever()
  File "run.py", line 1, in forever
    def forever(): forever()
RuntimeError: maximum recursion depth exceeded

This shows pretty clearly what is going on, the stack frames are pilling up and eventually it gets to the point where the Python interpreter says enough is enough. Interestingly enough, this mailing list thread shows that it's completely feasible to add TCO to Python and Guido just doesn't want to add it.

JavaScript is no surprise either, but we can write our infinitely recursive function with an interesting little twist:

(function(){ arguments.callee() })()

Yes that's right, it's an anonymous recursive function! Running this with SpiderMonkey results in InternalError: too much recursion. So how about Java:

class Run {
  public static void main(String[] args) {
    Run run = new Run();
    run.forever();
  }

  public void forever() {
    forever();
  }
} 

The stack trace for this one looks a bit like the Python one, we see a stack frame for each iteration:

Exception in thread "main" java.lang.StackOverflowError
    at Run.forever(Run.java:8)
    at Run.forever(Run.java:8)
    at Run.forever(Run.java:8)
    at Run.forever(Run.java:8)
...

So that means no TCO on the JVM. So Scala doesn't have TCO, right?

def forever : Unit = forever

forever

Wrong. This one runs forever. Scala does TCO with some bytecode tricks which Nick Wiedenbrueck explains really well in this blog post.

Clojure is a functional Lisp saddled with the problem of no-TCO on the JVM, but it gets around it in a slightly different way than Scala. If you write a tail recursive function like this:

(defn forever [] (forever))

You will get a java.lang.StackOverflowError just as you do in Java. Instead, Clojure provides a language level feature to do recursion:

(defn forever [] (recur))

Calling recur in the function makes it call the function again. recur also checks that it is in the tail recursive position, which ends up being an interesting feature because you have to explicitly say "I expect this to do TCO". In other languages that do it transparently, you might think TCO is happening, but it might not be and you won't find out until you get a stack overflow error. Also, this construct allows us to have recursive anonymous functions:

((fn [] (recur)))

Erlang, being a function language, has TCO as well:

-module(run).

-compile(export_all).

forever() ->
  forever().

Now one thing all of these functional languages that have TCO; Scala, Clojure and Erlang, all have in common is that while the infinitely recursive function runs, it essentially does nothing, but it will peg your CPU utilization to nearly 100%. This next language, Haskell, being the mother of all functional langauges, of course has TCO. Here's the function:

forever = forever

Yes, that's a function. And if you call it with forever, it just sits there and runs forever. But here's the crazy thing, it uses no CPU. My guess is that it has to do with lazy evaluation, but I'm not sure. Any ideas?

Posted in Technology | Tags TCO, Javascript, Scala, Haskell, FunctionalProgramming, Python, TailCallOptimization, Ruby, Java, Erlang, Clojure | 19 Comments

In Search Of Sharper Tools

July 21, 2009

After reading the comments in my last post, one thing I realized that I neglected to do is define what I mean by metaprogramming. Rubyists probably already know what I mean, but people coming from other programming languages might have different ideas about what I mean by metaprogramming.

I've actually mentioned this in a few talks I've given about Ruby. I don't really like the word Metaprogramming, it's a little bit nebulous. I think a better term is dynamic code generation. I like that term because I think most programmers will have a pretty good mental model of what I am talking about when I say that. There are several features of Ruby that when combined together allow you to do almost anything to bend the language to your will. To understand how to do that, I recommend reading the book Metaprogramming Ruby, which is in beta right now.

I'll give a short, real world example of what I'm talking about. I'm working on a Rails app that uses a database that has bit field columns. I want to treat the boolean flags in the bit field as though they are regular boolean attributes throughout my code. So I wrote a Ruby gem has-bit-field, which generates all the methods necessary to work with the bit field columns. You define what is in the bit field in the most clear, simple, elegant way possible by just stating which column has the bit field and then what attributes should be generated for each bit:

class Person < ActiveRecord::Base
  has_bit_field :bit_field, :likes_ice_cream, :plays_golf, :watches_tv, :reads_books
end

This is the kind of abstraction that the metaprogramming capabilities of Ruby afford you. I threw this together, with tests, in an hour or so. Can you imagine the amount of nonsense you would have to go through in Java to create an abstraction equivalent to this?

This type of abstraction is what I think makes Ruby a great language, but I realize you are definitely walking a fine line with this kind of thing. It's possible for this sort of thing to go wrong quickly. The first way these things go wrong is when the abstraction is not intuitive and not documented. First of all, a good abstraction should be almost intuitive, requiring other programmers to be able to guess what is does. This is commonly referred to as the Principal of Least Surprise. This doesn't mean that you are excused from providing some sort of documentation explaining how it works, especially for more complex abstractions.

The reason why it's important that the abstraction is clear is that most of the time the code that defines the abstraction is dense at best, and downright ugly at worst. This isn't a problem specific to Ruby, as anyone who has worked with Lisp macros can attest to. But in the end I'd rather have a small chunk of code that is tested and documented that I don't really need to look at that enables me to make the code where the business logic is defined as clear as possible. If other programmers are constantly having to dive into the guts of the definition of these abstractions just to understand how the code works, you have officially created a mess. And this is no ordinary mess, this is meta-spaghetti, and is a mess on an order of magnitude not possible in statically typed languages.

So does this mean you shouldn't use Ruby? Not at all, and I think Glenn Vanderburg sums it up best:

Weak developers will move heaven and earth to do the wrong thing. You can't limit the damage they do by locking up the sharp tools. They'll just swing the blunt tools harder.

I think developers often associate "blunt tools" with static typing, because really they associate static typing with Java. I'm not sure that static typing is in fact a blunt tool. If static typing means I can't create these kinds of abstractions, then yes, it's a blunt tool. But can you do this kind of thing with Scala Compiler Plugins? How about with Template Haskell? What about with MetaOCaml? If you can, are those tools then sharper than Ruby? Or is there a way to define abstractions like these without metaprogramming at all?

Posted in Technology | Tags Scala, DynamicTyping, MetaOCaml, OCaml, Haskell, StaticTyping, Metaprogramming, Ruby, Java | 0 Comments

Implicit Conversions: Scala's Type Safe Answer To Ruby's Open Class

April 17, 2009

Let's say that you are writing an application that squares things often, so you would like to be able to do this:

>> 4.squared
=> 16

In Ruby, that's easy-peasy:

class Integer
  def squared
    self * self
  end
end

Wham. Done. Open it right up, shove your method in there and you are bending the language to your will. But what if you couldn't modify existing classes? Maybe you would do this:

class IntegerWrapper
  def initialize(value)
    @value = value
  end
  def squared
    @value * @value
  end
end

Cool. Now you haven't modified Integer, but you get the same effect. So you just use it like this:

>> IntegerWrapper.new(4).squared
=> 16

WOAH! WTF? That is a lot of extra syntax. Having all to call wrapper classes like this really makes it too verbose. So now we shift gears into Scala mode:

scala> class IntegerWrapper(val value : Int) { def squared = value * value }
defined class IntegerWrapper

scala> new IntegerWrapper(4).squared
res0: Int = 16

As you can see on the first line, we define the same IntegerWrapper class. Then we use it just the same way we do in Ruby. But now we throw in an implicit conversion to make the syntactic magic happen:

scala> implicit def wrapInt(i:Int) = new IntegerWrapper(i)
wrapInt: (Int)IntegerWrapper

scala> 4.squared
res1: Int = 16

The implicit def defines an implicit conversion from an Int to an IntegerWrapper. This is our way to tell scala that if we try to call squared on an Int, use this function to convert the Int to an IntegerWrapper for me. Now as you can see, we can call squared on what appears to be a Int, and get the same syntactic advantage of adding methods to existing classes, without really modifying existing classes.

Posted in Technology | Tags Scala, Ruby | 6 Comments

The Web Application Framework Candidates

February 14, 2008

The web application framework race is heating up, so let's take a moment to meet some of the candidates.

Java

George W. Bush

The current leader in the web application framework space, has a declining approval rating from the general public, but still maintains support from members of the static typing party.

Rails

Hillary Clinton

One of the leading candidates from the dynamic typing party. This candidate has experience that proves she can bring change.

Merb

Barack Obama

A candidate from the dynamic party who is quickly gaining support, running on his campaign of hope. Has a stance similar to that of Rails on many of the campaign issues.

Django

John Edwards

Another strong dynamic party candidate, but having a hard time stealing the spotlight from the two dynamic party candidates, despite running on a strong platform.

Grails

John McCain

The leading candidate for the static typing party, particularly among moderate static typers, but having a hard time gaining support from conservative members of the static party who claim that he is too dynamic on some issues.

Scala

Ron Paul

A candidate that appeals to some members of both the dynamic and static typing parties, quickly gaining notoriety on the web for his support of once unconventional ideas like functional programming.

Posted in Technology | Tags Django, Merb, Scala, Python, Ruby, Java, Rails | 4 Comments

Lift on Leopard

January 25, 2008

Until Steve Yegge's Code's Worst Enemy rant, I hadn't even heard of the language Scala. Although Steve made no mention of Scala in his article, there were plenty of people in the comments suggesting he check out Scala. Not surprisingly, it's getting a lot of love in the blogosphere now. I've read through some of the online documentation and next I wanted to see some code and the web framework for Scala seems to be Lift. I tried get the examples running on my Macbook Pro, which is running Leopard, and I ran into this error:

java.lang.IllegalStateException: The PluginDescriptor for the plugin 
Plugin [org.scala-tools:maven-scala-plugin] was not found.

Luckily I found this thread on the lift google group, which states that the problem is that the maven that comes installed on Leopard is 2.0.6, which doesn't work with Left. I installed 2.0.8 by putting maven at /usr/local/maven and adding /usr/local/maven/bin to my PATH. That got it working and after what seemed like a hour of downloading maven packages, Lift was up an running.

At first glance, I say the Lift Scala code looks just as verbose as Java code. Take this for example:

package com.hellolift.model

import net.liftweb.mapper._
import net.liftweb.util._
import net.liftweb.sitemap._
import net.liftweb.sitemap.Loc._

import com.hellolift.controller.BlogCache
import com.hellolift.controller.BlogCache._
import com.hellolift.controller.AddEntry

object Entry extends Entry with KeyedMetaMapper[Long, Entry] {
  override def dbTableName = "entries"
  // sitemap entry
  val sitemap = List(Menu(Loc("CreateEntry", "/entry", "Create An Entry", 
                     If(User.loggedIn_? _, "Please login"))), 
             Menu(Loc("ViewEntry", "/view", "View An Entry", Hidden)), 
             Menu(Loc("ViewBlog", "/blog", "View Blog")))

  // Once the transaction is committed, fill in the blog cache with this entry.
  override def afterCommit = 
    ((entry: Entry) => {BlogCache.cache ! AddEntry(entry, entry.author.is)}) :: Nil
}

class Entry extends KeyedMapper[Long, Entry] {
  def getSingleton = Entry // what's the "meta" server
  def primaryKeyField = id

  // Fields
  object id extends MappedLongIndex(this)
  object author extends MappedLongForeignKey(this, User) {
    override def dbDisplay_? = false
  }
  object title extends MappedString(this, 128)
  object body extends MappedTextarea(this, 20000) { // Lift Note: 7
    override def setFilter = notNull _  :: trim _ :: crop _ :: super.setFilter
  }
}

Maybe I'm just spoiled by the succinctness of Ruby, but that code doesn't strike me as immediately readable. There's what looks to be routing (URL Mapping) code in here, which strikes me as odd. The model doesn't seem like a very good place for routing code.

Posted in Technology | Tags Scala, Liftweb | 0 Comments

  Older Articles >>