A folding language


In the descriptions of Ioke, I’ve lately favored using the concept of a “folding language”. I think that description feels very right, and I’ll explain a bit more about that here. I didn’t come up with the term though – Steve Yegge did, in a passing remark in his post “Wizard School”. It’s a funny read, actually. When I read it, the remark about folding languages stayed with me, and for me, Ioke is exactly that.

Let me first reproduce the paragraph from Yegge’s post that mentions this concept:

Of course, blasting out hundreds of thousands of lines a year is missing the point. If a Wizard is given complete technical control over a project (which is usually the smartest thing to do, but companies are rarely very smart), the Wizard will typically write in one of the super-succinct “folding languages” they’ve developed on campus, usually a Lisp or Haskell derivative.

They call them Folding Languages because they write code that writes code that writes code… Wizards swear by it, and there’s no question that they can produce amazingly compact, fast, clean-looking code. But 90% of the devs out there claim they can’t read it, and whine a lot about it to their bosses. Given that most companies can only afford a few Staff Wizards, the Wizards are usually forced to capitulate and use Java or C++. They’re equally comfortable in any language you throw at them, though, and if you force them to use a verbose language, well, you get what you ask for. It still amazes me that companies are bragging about how many lines of code their Wizards have produced. Potential startups take note: your competitors are usually idiots.

Especially in the evolution from Ioke 0 to Ioke S – when I added syntactic macros – the ways I can write code manipulating code is really nice. I am used to it from Lisp, of course, but to me Ioke have this in spades. It feels like a Lisp turned inside out.

Ioke is designed to be expressive, and being able to fold code is an important part of this. Earlier today, Sam Aaron talked about folding languages on IRC, and he said this (I have added some punctuation, that doesn’t change the meaning of the quote):

When I read it I first thought that all languages support folding to some extent, but some languages have limitations – such as the limitations of paper, i.e. with paper you can only fold it so many times before it’s impossible to add another fold, whereas languages like Ioke seem to support infinite folding. And some languages are just so brittle, that folding is pretty impossible.

That pretty much says it all. =) If you want a good example of how Ioke supports code folding, go to the git repository and take a look at the evolution of the Enumerable mixin from Ioke 0 to Ioke S. Let me take as an example the implemention of any?. (I will provide the real source, except for the documentation text). In Ioke any? can take zero, one or two arguments. If you give zero arguments, the method will return true if there are any true values in the collection. If you give one argument, that argument is a message chain that will be applied to every element in the collection. If that message chain returns true for any element, then the any?-method returns true. Finally, the two argument version takes one variable name, and one piece of code that uses that variable name. The code will be executed once for every element with the current element bound to the name. Some usage examples:

[nil, false, "foo"] any? ; => true
[1, 2, 3, 4] any?(odd?)  ; => true
[1, 2, 3, 4] any?(x, x*x > 10)   ; => true

As you can see, these versions all make sense. And what is more, this pattern of taking zero, one or two arguments is pretty common in the Enumerable implementations. Most of the implementations are actually variations on this theme.

So, the implementation of any? in Ioke 0 looked like this:

Mixins Enumerable any? = macro(
  len = call arguments length
  if(len == 0,
    self each(n, if(cell(:n), return(true))),

    if(len == 1,
      theCode = call arguments first
      self each(n, if(theCode evaluateOn(call ground, cell(:n)), return(true))),

      lexicalCode = LexicalBlock createFrom(call arguments, call ground)
      self each(n, if(lexicalCode call(cell(:n)), return(true)))))
  false)

Pretty interesting code, right? Well, there are several problems with it. First, the actual logic of what it does is spread out in three different places, one for each variation in arguments. The second problem is that this code doesn’t check the argument arity. If you give another combination of arguments, it will fail noisily. But the most important problem is that this structure is the same for most of the Enumerable methods. Take a look at two more, none? and find.

Mixins Enumerable none? = macro(
  len = call arguments length
  if(len == 0,
    self each(n, if(cell(:n), return(false))),

    if(len == 1,
      theCode = call arguments first
      self each(n, if(theCode evaluateOn(call ground, cell(:n)), return(false))),

      lexicalCode = LexicalBlock createFrom(call arguments, call ground)
      self each(n, if(lexicalCode call(cell(:n)), return(false)))))
  true)

Mixins Enumerable find = macro(
  len = call arguments length
  if(len == 0,
    self each(n, if(cell(:n), return(it))),

    if(len == 1,
      theCode = call arguments first
      self each(n, if(theCode evaluateOn(call ground, cell(:n)), return(cell(:n)))),

      lexicalCode = LexicalBlock createFrom(call arguments, call ground)
      self each(n, if(lexicalCode call(cell(:n)), return(cell(:n))))))
  nil)

Can you see the difference and describe what they do? I can definitely say that for me, maintaining these methods got problematic quickly. And as you see, the structure is exactly the same, but since the insides of it are quite different, it would be hard to do something about this code in Java, except refactor out small methods for different things. But the essential duplication would still be there.

In Ioke S, the implementation of any? looks like this:

Mixins Enumerable any? = enumerableDefaultMethod(
  .,
  if(cell(:x),
    return(true)),
  false)

enumerableDefaultMethod takes three arguments of code. The first argument is what should be done before (nothing in this case, hence the dot). The second argument is the code that should be executed on each iteration. And the final argument is the code that should be used to return something after the iteration. The n cell is the same as in the long implementations – the current value in the collection. The cell x is the value after applying the code to it. With this understanding in place, you can see that any? will go through each element, check if the transformed value is true, and in that case return true. If none is true, it returns false. Notice that enumerableDefaultMethod is not an exposed method. It’s not part of any API – it’s just a syntactic macro used to make it really easy to implement these Enumerable-methods.

It also gives some other things. For example, it will automatically add arity-checking, so that this method will now return a meaningful condition if given the wrong kind of arguments.

And lets go to the Ioke S implementations of none? and find:

Mixins Enumerable none? = enumerableDefaultMethod(
  .,
  if(cell(:x),
    return(false)),
  true)

Mixins Enumerable find = enumerableDefaultMethod(
  .,
  if(cell(:x),
    return(cell(:n))),
  nil)

Here you clearly see the difference between any? and none?. And it is also clear what find does too, namely if any transformed value is true, return the original value for that transformation. Otherwise return nil.

Now, enumerableDefaultMethod is actually implemented using dsyntax. And dsyntax is a syntax that returns a new syntax, that will finally execute and expand the implementations. And that is what I mean with code folding. You can take coded abstractions and fold the code until the only thing you need to write is what makes this different from the defaults. The above code could probably have been even easier to read by assuming that an omitted first argument means there will be no initialization. So as you can see, this process never really stops. But it allows you to code on a higher level. And when you find the right abstractions, what you end up writing is much closer to the business domain. And that is really what most developers want, right?


12 Comments, Comment or Ping

  1. Hi Ola, could you post the implementation of enumerableDefaultMethod, too?

    January 23rd, 2009

  2. matthias

    Totally offtopic:
    You raved about how cool spaces instead of the dot are. So I tried it but it absolutly doesn’t work for me. I come more from a ML and Haskell background and to me “foo bar” still reads what would be written “foo(bar)” in Java and not as “foo.bar”.

    Has anybody else the same problems I have?

    January 23rd, 2009

  3. Tobias

    Yes.

    “foo bar” is “foo(bar)”.

    January 23rd, 2009

  4. “foo bar” is “foo(bar)” is “bar foo”… ;)

    January 23rd, 2009

  5. January 23rd, 2009

  6. Ola, this is awesome. I really need to pair with you sometime :-)

    January 23rd, 2009

  7. Andrew

    I am totally unfamiliar with this language, so my apologies if I am misunderstanding something.
    I find myself confused, in the interests of DRY, why isn’t any? implemented as the negation of none? (or vice versa)

    January 24th, 2009

  8. jer

    Matthias,

    Problem is you’re coming from a language on the opposite end of the programming spectrum. While no expert on Ioke, nor do I pretend to be. Ioke being inspired from Io, of which one of the primary driving principals on syntax is to be as simple as possible, spaces are really easy to handle from a parser standpoint, requiring no extra syntax. This helps keep your parser implementation simpler, and as far as how it ties into semantics, think english language. It’s a lot easier for someone who knows english to read code that also looks like english than it is to grok things like aCat.setLegs(4).setEyes(2).setTail(true) … the dots are a distraction, and break up flow, in my opinion.

    January 24th, 2009

  9. What is not self describing is :x and :n. Besides the name could be longer, there should be a way for a macro to communicate its available parameters to the “closure”. Or maybe use a longer convention, like

    x – element
    xs – list
    nx – position

    But I must admit, I did not fully understand it.

    Greetings
    Bernd

    January 24th, 2009

  10. I’d second the opinion of Bernd: while this is nice, I find it a bit worrying that the programmer must be a wizard in that he knows what variable names are bound by the macro. You could put that into the documentation, but in my experience that doesn’t work all that well, and in particular doesn’t survive refactoring. I think this is one of the reasons people are doubtful about macros – you might end up depending on implementation details of the macro, with no clear and documented dependency relation between the macro and consuming code. Bad.

    I also still find the introduction of x in “[1, 2, 3, 4] any?(x, x*x > 10) ; => true” a bit weird, or non obvious. I need to know the details of the any? method’s parameter declaration to understand that this introduces a new name, and doesn’t simply refer to “x” in the enclosing scope. This might just be me being unfamiliar with Ioke, but I think it’s generally bad in a language if you have to (potentially) follow the pointers to all methods/modules etc used just to understand the semantics of the code. No idea how to solve that though ;-)

    January 26th, 2009

  11. I am not the world’s brightest programmer but it’s been interesting to me to follow the evolution of Ioke’s Enumerable methods. Initially I had a similar concern: every Enumerable method was a macro or destructuring macro that required the implementor to understand a fair amount about macros. This isn’t necessarily unreasonable–after all, it’s a part of the language–but it isn’t necessarily as terse as you might like. enumerableDefaultMethod is a better way out.

    Ruby’s blocks syntax offer a kind of solution to this, but although they seem simpler at first they don’t much reduce the total complexity involved in writing this kind of thing. Besides, much of the dual-dispatch complexity in Ioke’s Enumerable methods comes from offering a feature that Ruby can’t match: since Ruby doesn’t have macros, you can’t eval the given method inplace on each yielded object. Ioke gives you list each(foo!) where Ruby offers the hacky list.each(&:foo!), and only after someone had to come up with the idea of extending Symbol with #to_proc.

    January 27th, 2009

Reply to “A folding language”