omg i <3 teh Cylons!

I’ve been reading this book on Lisp over at MIT press, a little at a time. Yesterday I read something that pushed me a little further along the path of understanding and I thought I’d share it here.

Many people who know functional programming say it’s indispensable, and others who aren’t familiar with it dismiss it as inefficient, academic, or irrelevant. I’d like to believe the first group, and am trying to work toward a real understanding . It is sometimes difficult to come from the perspective of a procedural programmer and see how it’s possible to achieve anything in a language that discourages the use of mutable variables. It takes a dramatic change in perspective — something I think I’m acquiring little by little.

Here are some excerpts from chapter 2 in the book. As they discuss a little in this section, it helps to think of functional programming in terms of data flow and circuits. I think really exploring this idea can lead to a lot of insight. Circuits can’t have mutable variables either, unless you introduce a clock. Using map you can “loop”, but I think it’s more consistent to think of it as parallel processing.

Here is an excerpt from section 2.2.3 of the book:

” the following procedure… takes a tree as argument and computes the sum of the squares of the leaves that are odd:

(define (sum-odd-squares tree)
  (cond ((null? tree) 0)  
        ((not (pair? tree))
         (if (odd? tree) (square tree) 0))
        (else (+ (sum-odd-squares (car tree))
                 (sum-odd-squares (cdr tree))))))

On the surface, this procedure is very different from the following one, which constructs a list of all the even Fibonacci numbers Fib(k), where k is less than or equal to a given integer n:

(define (even-fibs n)
  (define (next k)
    (if (> k n)
        nil
        (let ((f (fib k)))
          (if (even? f)
              (cons f (next (+ k 1)))
              (next (+ k 1))))))
  (next 0))”

If you’re not familiar with lisp syntax and all that makes your eyes glaze over, those functions are very similar to how you would write the same algorithms in Java or C. The first uses recursion to traverse the tree, the second uses tail recursion analogous to an iterative loop to traverse the list, just like you would in C. The main thing to note is that almost half of the above code is taken up by control structures, since even the recursive calls are the equivalent of “i++” in a for loop.

After some discussion about a more abstract description of the computations and how to think in terms of signal processing, the book presents the same functions reformulated using the higher order functions enumerate, map, filter, and accumulate:

“Now we can reformulate sum-odd-squares and even-fibs as in the signal-flow diagrams. For sum-odd-squares, we enumerate the sequence of leaves of the tree, filter this to keep only the odd numbers in the sequence, square each element, and sum the results:

(define (sum-odd-squares tree)
  (accumulate +
              0
              (map square
                   (filter odd?
                           (enumerate-tree tree)))))

For even-fibs, we enumerate the integers from 0 to n, generate the Fibonacci number for each of these integers, filter the resulting sequence to keep only the even elements, and accumulate the results into a list:

(define (even-fibs n)
  (accumulate cons
              nil
              (filter even?
                      (map fib
                           (enumerate-interval 0 n)))))”

Clearer? Hell yes… that is, once you internalize those extremely reusable higher order functions.

And the real gem that sums it all up, un-presuming and hidden away down in footnote #15:

“One of the reasons for the success of Lisp as a programming language is that lists provide a standard medium for expressing ordered collections so that they can be manipulated using higher-order operations.”

All this together led me to a bit of an “Ah ha!” moment, or rather, an “Ah ha!” half hour or so of deep thought.

I think the point I’m seeing is the enormous benefits of suppressing repetitive and verbose syntax of flow control. Instead you use flow control template functions like enumerate, map, filter and accumulate. This is only possible in a language where you can easily pass function pointers down for use by the flow control logic. The only way to do this in OOP is by using Polymorphism, which is a big reason why it’s one of The Pillars.

The only criticism I could think of against this new formulation of the functions was that by batching each step, you’re now required to allocate a new list after every step. However, another feature of most functional programming languages comes to the rescue: Lazy evaluation and call-by-need. Later in the program where the resulting lists would actually be used, the values will in fact be produced one at a time as they are requested from the list.

And this is a huge win in and of itself. Not the performance wins or parallelization available via lazy evaluation, but the fact that this kind of programming makes batch and on demand processing look exactly the same, all you’d need to do to switch between them would be to hint the run-time/compiler. Wow.

A minute ago I shared this on Google Reader. It’s got some very interesting phrasing in the way it describes the custom software industry and possible future directions. Specifically “craft based labor-arbitrage outsource businesses” as the current state of things, and something he somewhat ambiguously refers to as “Software Factories” as the future. There is an article on software factories on wikipedia.

It’s the sort of thing that sounds pretty far out, even ridiculous. The idea of real component based software and all the re-usability that needs to accompany it is still a pipe-dream. Every time someone comes out with a solution that claims that kind of capability, it always seems to fall far short of expectations. You still need a real developer that knows what they’re doing to accomplish much of anything.

For some reason, though, the description on wikipedia brought to mind a short clip I saw on the history channel years ago that has stuck in my mind ever since. It was a re-enactment of a scene that occurred near the beginning of the industrial age, a man walks into a room and dumps a bag full of gun parts onto a table. He instructs another man to pick through the pile and pick any one of many copies of each component, which he then neatly assembles into a functioning trigger assembly. The other men in the room are astonished, it would have taken a typical gunsmith days to carefully adjust each piece to slot perfectly into all the others so you got just the right fit.

The point is, 10 years before this, it’s unlikely that any gunsmith would have ever believed such a thing would be possible. How could you possibly replace him with some kind of automated process? All the careful hand crafting that goes into each product?

Now, I’m not saying that this is where the software industry is headed. We can already produce identical copies of the same component. In fact, it’s a trivial copy and paste. We can already assemble pre-built components, but it’s the glue that goes in between that’s the hard part. Not the things that are the same, but the things that need to be different. It’s also true that as simple as the interface to a software component might be, the interface is only the beginning. In a sense, a simple mechanical component is little more than it’s interface to the outside world. It’s shape, weight, strength and texture.

So there are lots of reasons why software is far more complicated than a mechanical device, but there are a lot of trends in software that seem significant in this light. Dependency Injection and lightweight containers like Spring. Domain Specific Languages strike me as a neat way of scripting dependency injection in a custom language. From a high level, some of this stuff starts to look more like software assembly rather than software development.

Maybe the result will be a more significant division within the industry. The real demand will start to be for more and more complicated software. The low hanging fruit will all have been taken care of and the remaining demand will be for exceptionally intricate work. There isn’t much of a market for gunsmiths anymore, but there are(some) jobs for rocket scientists. Or maybe the demand for highly customized software will remain high enough to counter-act the relative ease of developing these simpler systems.

Either way, it will be interesting to see what happens over the next decade.

I read this article over on slate.com.  It talks about community style sites, specifically Wikipedia, Digg and Slashdot and compares the “Democratic” nature of how content is generated.  It fashions itself as an expose of how they aren’t as democratic as they pretend to be, and how we should try to “fix” that.  The numbers it cites for usage are interesting to think about, for example the top 100 Digg users were responsible for 44 percent of front page stories last year.  There are some other interesting numbers in there as well.

I think it misses the point, though.  It seems like a lot of things are more plagued by the pollution generated by “democratic” content and the dominance of the “least common denominator” more than they are a lack of democracy.  A co-worker of mine has  de-motivational poster on his cube wall:

“Meetings: None of us is as dumb as all of us”

It’s funny because it can so easily be true.  Understanding how to overcome that, I think, is an extremely important(and difficult) problem.

Here’s the latest blog post from Schneier on Security.   I pretty much read every entry at least in passing, but this one strikes me as a bit off.

Schneier on Security: Why Some Terrorist Attacks Succeed and Others Fail

At the bottom he concludes with “see, this is what I’ve been saying” while citing the statement that terror plots are rarely foiled in the act.  I think this overlooks the implication in several of the other points, though, that people should be watching carefully and reporting any suspicious activity to authorities.  While I think the main thesis of the article supports his position in one way, there are a number of points there that should probably be addressed within the context of his “War on the Unexpected.”

I’ve been thinking really hard about programming language concepts lately.  I need to learn Lisp.

Beating the Averages

Here’s an article by Martin Fowler, author of the book “Refactoring,” about Language Workbenches. The idea is that Domain Specific Language’s(DSL’s) are good, but creating them can be hard, so IDE’s of the future may include tools to do so more easily.

Language Workbenches: The Killer-App for Domain Specific Languages?

In the article he also references a company, Intentional Software, which is working on just such an IDE. Here’s the wikipedia about Intentional Programming which has some interesting ideas in it.

http://en.wikipedia.org/wiki/Intentional_programming

Here’s another article I read about the creator of that company, Charles Simonyi. He’s a Microsoft billionaire that worked on Office way way back. I don’t necessarily recommend reading the whole thing, it’s pretty sparse, but the last couple of pages are sort of appendices about concepts. It criticizes the Intentional Programming as yet another leaky abstraction layer. It does sort of look pretty hand-wavey “create a DSL, then programming with the DSL will be easy.” Creating the DSL is of course the hard part, not just because of lack of tools, but from a design perspective as well. If you can design a good DSL, you can design a good API to layer your programs on top of. One of the pitches for the DSL is that you create a cool API, wrap it in the DSL, then hand off the DSL to non-technical people. Since the point of a DSL is to remove features from a Turing complete language to make it easy and safe, non-programmers can use it, so the real pitch is it lets non-programmers program. It also has some neat ideas about not storing the program in a text file, but in a more abstract form and then “projecting” it for editing. From what I gather it looks a lot like the Abstract Syntax Tree the compiler builds during compile time, and that most modern IDE’s maintain on the fly to do syntax highlighting and code completion.

Jon,

This is a couple hops away from your poll link:

http://scienceblogs.com/cognitivedaily/2008/01/very_cool_poll_at_slashdot.php 

via the Keynesian beauty contest on Wikipedia, through the references.  I enjoy reading economic theory from time to time.  While a great deal of this seems obvious in hind-sight, like most of my experience with economics, it is sometimes very enlightening to see someone line up perfectly obvious facts to elaborate a quite a bit less obvious but seemingly inescapable conclusion.

The General Theory of Employment, Interest, and Money, by John Maynard Keynes chapter12

I don’t grok all this, but I’ve been reading articles themed around programming language selection and evolution, and the idea that design patterns are markers of language short-comings. I’m not sure I totally buy that thesis, but it is certainly an interesting idea to bounce around for a while. Most of the work I’ve done has been in statically typed languages, and from the blogs I’ve been reading, and all the hype around Ruby and Python, the world/industry is at least partly moving on to Dynamic languages.

This article talks about some ideas on this front. I’ve starred it and plan to come back to it and some as yet unknown future date when I get time to think about this stuff really seriously.

Dare Obasanjo aka Carnage4Life - Does C# 3.0 Beat Dynamic Languages at their Own Game?

Interesting article, a bit long for a casual read, but it made me think a lot more about Exception handling and how it really works.  It definitely seems to fall in the category of taking a potentially large performance hit in exchange for ease of use.

Efficient exceptions?

It’s a link from the first paragraph of this blog post.

An interesting story about Richard Feynman.  It’s a little long, but quite interesting.

Long Now: Views: Essays