raganwald
Wednesday, April 18, 2007
  Yeomanry and Exploding Brains
Note: I wrote this post very quickly last evening, in an almost stream-of-conciousness style. I had just endured some particularly frustrating client issues, and I really, really wanted to focus on a few bright moments that I had enjoyed that day. You know, trying to be a good dog.

After publishing it, I felt unsatisfied with the post. It didn’t feel like I was saying or thinking anything particularly new, just the same old, same old thing about stretching the mind and looking for the elusive “quality without a name” that lies behind well-written software.


So I yanked it and went home. I was talking with a friend who writes for a living, and she quoted a great aphorism: “All writing is rewriting.” She suggested I rework it, not discard it. So here it is again, and I hope to rework it until I’m satisfied. The first major change will probably be to cut it in half.

We’ll see about the rest.



I finished reading The Little MLer this morning. This is a wonderful book. It’s obviously valuable if you want to learn something about SML or Ocaml. But having read it, I’d argue that it’s a great introduction to strongly typed functional languages, period.

In fact, it’s probably the very best first book to read before learning Haskell if you haven’t already used a language that combines first-class functions and strong, static typing. If you read this first, you can concentrate on lazy evaluation and monads without having to grok currying and other first-class functional ideas at the same time.

Stars, Arrows, and Elegance

Two things jumped out at me this morning. The first was chapter eight, “Bows and Arrows.” This was an introduction to currying and partial function application. When I say it that way, it sounds rather dry. But it rolled along quite pleasantly. The material will be familiar to anyone with a passing familiarity with the idea of a function returning a function. It has the same ideas you’ll find in Structure and Interpretation of Computer Programs, but delivered with static typing.

This alone is worth the price of the book: I came to the subject with an impoverished experience set: I had used latently typed languages like Scheme and Ruby, as well as static and declaratively typed languages like C++ and Java. Although I knew “intellectually” how languages like Ocaml and Haskell deliver some of the power of Scheme along with the benefits of compile-time type checking, there is no substitute for walking through the examples to spark the “Aha!” feeling. Incredibly, chapter eight got better. It finished with a real bang:

The examples in the chapter constructed various functions that took multiple arguments, then constructed their equivalents by combining smaller functions with partial evaluation. Then it closed with The Eighth Moral:

Replace stars by arrows to reduce the number of values consumed and to increase the generality of the function defined.

In other words, first-class functions let you break monolithic functions that take a lot of arguments into smaller components that can be combined and recombined. This is a deep idea in writing programs. We often see the tension between programs as collections of small pieces that fit together and black boxes that are configured by means of switches and dials on the outside.

This is a good tension: we call the black box approach “abstraction” and we call the combinatory approach “bottom-up programming.” Both produce programs that are expressed economically, but the black box does so by sweeping the complexity “under the carpet” and bottom-up programming does so by identifying and combining the simple constituent elements of a program in an economical way.

I think of black box abstractions like inventing new nouns for new ideas. A web server? We’ll call that a “Fizbuhlsweepnik.” A REST server? We’ll call that a “Harkonnensmelt.” Whereas I think of bottom-up programming as inventing smaller nouns, verbs, adjectives, and adverbs, so we can say a “web server” or a “REST server” or even a “Caching REST server.” Being able to combine the small words gives us more to say with much less effort. (I am not a linguist, so this argument is suspect!)

Giles Bowkett nailed this idea when he wondered whether languages like Scheme are actually easier to learn than languages like Java.1 This makes a lot of sense from the perspective of simplicity. Pure Scheme is based on just five axiomatic “special forms” plus macros to build almost everything else out of the five axioms. That’s a lot easier to learn than a language that tries to provide the same power with a plethora of knobs and switches like package, static, and main.

This tells us something about ecosystems versus languages. Lately, quite reasonable people have wondered aloud whether the ecosystem of frameworks and libraries are more important than the languages themselves. As we’re beginning to see with multiple languages running on common VMs, the point may become moot very shortly. But for now, it is easy to see that libraries tend to look like black boxes. When they do exactly what you need, they save time and trouble. But they tend to be wide and shallow, just like Java. They have a lot of knobs and switches.

Good languages, OTOH, give you power that can be combined and recombined like first-class functions. They let you tame the black boxes by wrapping up the parts you need and combining them in simple ways. With currying, a function with twenty arguments can be transformed into a function with one argument. With powerful languages, a baroque library can be deftly specialized to fit your program.

My Brain Explodes

In the same chapter, the authors talked about extensional equivalence.2 This is the idea of two functions that can have the exact same behaviour as each other, even though they are defined in different ways. As the authors point out, proving that two functions are extensionally equivalent is impossible in the general case.

That shouldn’t stop anyone with a taste for reading esoteric programming weblogs.3 Something was tickling the back of my mind about this problem. Yes, it had to do with rewinding into the past to correct mistakes, something like backtracking in a reasoning system.

So perhaps we want an equivalence function that takes two functions “p” and “q” and returns a Boolean. Both functions must have the same signature, obviously. How can we write such a function? Here’s one approach: Scan the history of the program for calls to p. For each call, call q and compare the results. If they differ, return false. Do the same for each call to q, comparing its result to the result of calling p with the same arguments.

If there are no differences, return true. But wait, maybe your sample size is insufficient. No problem, continue forward in the program, and every time p or q are called in the future, compare the results from both functions again. If they are the same, continue on. But if they differ, rewind back to when the equivalence function was called and return false.

That does not guarantee equivalence, of course, they may differ for some set of inputs that you never tested in your program. But if they are equivalent for the set of inputs you actually run, what do you care if they differ for inputs outside of the “event horizon” of your program?

Now quite honestly, I cannot think of a practical use for this “rewinding extensional equivalence predicate.” I mention it only because the thought captures for me one of the benefits of reading certain kinds of books: they provoke you into thinking about new things in new ways. They may be useful immediately, or they may pop up down the road. Or maybe they were just a passing thought that amounted to nothing of grave importance.

But overall, my experience is that people and writing that pushes you into unfamiliar thinking territory is good for you. And in that spirit, I recommend The Little MLer4 with as much enthusiasm as I recommend writing your own version of the Y Combinator.


  1. See also: Giles Bowkett turns language elitism upside down

  2. Equivalence has been on my mind recently!

  3. And you wonder why I have been doing this since the seventies but somehow managed to miss out on earning a Turing Award while utterly failing to amass a small private fortune?

  4. Judging by the click-throughs on my blog in the last year, there are plenty of people who can’t quite bring themselves to pick up a book about ML. Don’t fret, the authors have also written The Seasoned Schemer for your first-class functional pleasure. In an effort to expand my own mind, I will be starting their book about logic programming, The Reasoned Schemer tomorrow.
 

Comments on “Yeomanry and Exploding Brains:
I read it in bloglines last night, liked it, and was going to add it to programming.reddit, but subsequently couldn't find it on your site. Good to hear what happened. (and I think it's interesting, for one data point)
 
Bill:

Thanks! I have no idea when I'll find the time, but the second bit, the part about extensional equivalence, seems far more interesting to me, so I hope to flesh it out into a post of its own.
 
I will have to admit I am a little lost when it comes to understanding the full understanding of "rewinding extensional equivalence predicate", but it seems that developers sometimes do this when they are debugging.. Let me explain, and maybe you can tell me if my understanding matched yours.

In my attempt to avoid making unit cases, it either make, or find, equivalent-functioning code. One version is my preferred implementation, and the other is a naïve (but more likely to be correct) version , or maybe a version I scraped off the internet. I then make a third version which uses the other two and compares their results. I use this third version in my code until some optimization is required.

During any particular debugging session, I have several (long forgotten) "equivalence predicates" working in the background. Should one of the predicates be broken, I perform an effective "rewinding": Fixing one of the three implementations, and then returning to my debugging.

Is this an example of "rewinding extensional equivalence predicate"?
 
I work at BigCo, but the upside is that I have a Books24x7 account, which I have just searched and found The Little MLer. I shall start reading it Monday.
 
So what happens if you rewind the program and return false, and as a result the program executes such that the two functions are now equivalent? :)
 
what happens if you rewind the program and return false, and as a result the program executes such that the two functions are now equivalent?

This exposes a real problem with functions that talk about other functions!

You can change the implementation to try to fix things, but you can never succeed. You are up against a fundamental limit in consistency.
 




<< Home
Reg Braithwaite


Recent Writing
Homoiconic Technical Writing / raganwald.posterous.com

Books
What I‘ve Learned From Failure / Kestrels, Quirky Birds, and Hopeless Egocentricity

Share
rewrite_rails / andand / unfold.rb / string_to_proc.rb / dsl_and_let.rb / comprehension.rb / lazy_lists.rb

Beauty
IS-STRICTLY-EQUIVALENT-TO-A / Spaghetti-Western Coding / Golf is a good program spoiled / Programming conventions as signals / Not all functions should be object methods

The Not So Big Software Design / Writing programs for people to read / Why Why Functional Programming Matters Matters / But Y would I want to do a thing like this?

Work
The single most important thing you must do to improve your programming career / The Naïve Approach to Hiring People / No Disrespect / Take control of your interview / Three tips for getting a job through a recruiter / My favourite interview question

Management
Exception Handling in Software Development / What if powerful languages and idioms only work for small teams? / Bricks / Which theory fits the evidence? / Still failing, still learning / What I’ve learned from failure

Notation
The unary ampersand in Ruby / (1..100).inject(&:+) / The challenge of teaching yourself a programming language / The significance of the meta-circular interpreter / Block-Structured Javascript / Haskell, Ruby and Infinity / Closures and Higher-Order Functions

Opinion
Why Apple is more expensive than Amazon / Why we are the biggest obstacles to our own growth / Is software the documentation of business process mistakes? / We have lost control of the apparatus / What I’ve Learned From Sales I, II, III

Whimsey
The Narcissism of Small Code Differences / Billy Martin’s Technique for Managing his Manager / Three stories about The Tao / Programming Language Stories / Why You Need a Degree to Work For BigCo

History
06/04 / 07/04 / 08/04 / 09/04 / 10/04 / 11/04 / 12/04 / 01/05 / 02/05 / 03/05 / 04/05 / 06/05 / 07/05 / 08/05 / 09/05 / 10/05 / 11/05 / 01/06 / 02/06 / 03/06 / 04/06 / 05/06 / 06/06 / 07/06 / 08/06 / 09/06 / 10/06 / 11/06 / 12/06 / 01/07 / 02/07 / 03/07 / 04/07 / 05/07 / 06/07 / 07/07 / 08/07 / 09/07 / 10/07 / 11/07 / 12/07 / 01/08 / 02/08 / 03/08 / 04/08 / 05/08 / 06/08 / 07/08 /