Security and Objects

Mobile code is one of the great challenges for software security. Lets say  you are writing an email application. The idea that people could send little apps to each other in email messages might seem like a potentially interesting feature: users could build polls, schedule meetings, play games, share interactive documents. Kind of cool.

And if the platform you are building upon supports reflectively evaluating code, it could be as easy as something like this (in OO pseudocode):

    define load_message(message)
        ...
        eval(message.code)

Of course it can't be that easy. What if the code in the message does something like:

    new stdlib.io.File("/").delete()

The standard way to avoid the vulnerability is to put the code in a so-called sandbox. It sounds very secure, but in practice this usually amounts to gathering up a list of "dangerous" call sites and inserting in each some code to check if the caller has permission to proceed. So the implementation of delete would include code along the lines of:

    define delete()
        if VM.callStackContainsEvilCode?()
            raise YouShallNotPassException()

        ...

This is fraught with problems. It requires runtime support for inspecting the call stack and a system for declaring that certain code has some level of authorization while some other code has a lower level. Not to mention the busywork of going trough the code and peppering that little snippet over every suspect call site. If you miss one — say, for instance, a method that gets the addresses of all contacts on your email application — and you have a security bug on your hands.

A better way ?

Perhaps there is a better way. Take another look at the offending line: new stdlib.io.File("/").delete(). It is only able to call the dangerous delete() method because it has a reference to a file object pointing to the root of the filesystem. And it only has that reference because it could reach for the File class on a global namespace. What if there was no global namespace?

It might seem weird, but it's not that hard to imagine a programming system lacking a global namespace. Many object-oriented languages, following Smalltalk's lead, have a notion of a metaclass, an object that represents a class. Many of them (also following Smalltak) also get by without a "new" operator. Objects are created by calling a method — usually named new() — on the metaclass object.

We are very close now. The last step, unfortunately not taken by most common languages, is to avoid anchoring the metaclass object onto a global namespace. The result is that code can only create objects of the classes it holds a reference to. And it only has a reference if it is given one via a method or constructor parameter.

Proceeding recursively, we end up with a stratified program. There is an entry point that receives a reference to the entire standard library, and each call site decides how much authority to grant each callee. On our example, when we evaluate external code we can grant very little authority, meaning we can pass the evaluated code just a handful of references. Care must be taken so that none of them will direct or indirectly provide a way to create a File. In a way, object design becomes security policy.

And we get very fine-grained control over such policy. We could, for instance, grant loaded code authority to write on a designated directory just by passing it a reference to the Directory object for that directory. Our choices get even more interesting when we realize we can pass references to proxies instead of real objects in order to attenuate authority. Continuing with our example, hoping it doesn't get too contrived, we could build a proxy for the Directory that checks if callers exceed a given quota of disk space.

Research

I have mentioned above that most common languages don't fit this post's description. But there are languages that do, a prime example is E. In fact, there is a whole area of research for dealing with security in this manner, it's called "object capability security".

I'm not really a security guy, I got interested in the area due to the implications for language and system design. If you got interested, for any reason, please check out Mark Miller's work. He is the creator of the E language and the javascript-based Caja project. His thesis is very readable.

Types and Bugs

There are certain discussions in our biz that are so played out they provoke instant boredom upon encounter. A major one is the old dynamic vs. static skirmish, recently resurfaced in a blog post by Evan Farrer. Which is a shame as the post is quite interesting, describing his results transliterating well-tested code in a dynamic language to a static language to see if the type system found any bugs. Which it did.

The full-length paper is a great read as well. He describes his translation methodology and gives some detail on each bug found. At first it may seem the author could be stacking the odds towards the static language as the translation was manually done by himself, but I found his description of the process pretty convincing of its fairness. The choice of Python as a source language probably helped given the pythonic inclination towards straightforward code that avoids sophisticated abstraction and metaprogramming mechanisms.

But the real meat of the paper is in the description of the bugs he found. Upon a not particularly discriminating reading, a clear pattern jumped out. Most of the bugs fell into one of two categories:

• Assuming that a variable always references a valid value when it can contain a null value. 
• Referencing constructs that no longer exist in the source.

The first category is also the largest, comprising several places where the original code could be coerced into letting a variable be set to a null value, usually by just leaving it uninitialized, and a subsequent call would attempt to derefence it assuming it contained a valid value. Haskell's type system avoids the problem as it  simply doesn't have any notion of null. Code that has to deal with optional values must do it trough algebraic data types.

How the second category of bug comes about is easy to guess from the projects histories: some method or variable was present but changed, perhaps it was renamed or subsumed, and not all references were updated to reflect the change. Even pervasive unit tests can't hope to catch these kinds of regressions, as the problem is found on the integration between units of code; the units themselves are just fine. A type system helps when the change affects the signature of the referenced construct, which is often but not always.

If the study's findings are generalizable and my observations are correct, these are the main takeaways:

• If you have a type system at your service, it's prudent to structure code such that behavior-breaking changes are reflected on the types.
• End-to-end integration tests are a necessary complement to both a suite of unit tests and a type system. In my experience how far should these tests stray off the happy path is a difficult engineering trade-off.
• If your type system allows nulls — such as Java's, for instance — its role in bug prevention is greatly diminished. The proportion of null-dereference bugs on the analysed code bases helps to makes it clear just how big a mistake it is to allow nulls in a programming language. 

Experience report: Ruby

For a long time I've been curious about how the supposed benefits and liabilities of programming in a dynamically typed language¹ actually play out in practice. I'm now getting a chance to find it out, since I'm involved in a largish project using Ruby (lots of Rails plus some Sinatra and a couple of random daemons). My professional background has largely been in Java, but I spend a good chunk of my free time learning about different programming languages (and some PL theory), mostly on the static side of the fence. Anyway, here are some notes:

The big question is whether dynamic typing allows for more bugs to pass trough. My answer to this has to be put in context: we are a medium-sized team (between half and a full dozen of devs), all experienced in, and practicing, TDD. As with the rest of this blog post, I don't have hard data to show, but my impression is that the unit tests do indeed catch all the bugs that the Java type system would help to catch; with the caveat that it's often harder to pinpoint the source of a regression. I don't have much real experience in languages whose type systems help to enforce strong guarantees², but I would imagine they would catch a larger fraction of the bugs that are caught by the unit tests, while not really avoiding further bugs. The reason is twofold: firstly, in my experience, many of the bugs are found in the interaction of separate pieces of software (such as Javascript in the browser talking to the web server), secondly, even when the bug is located within process boundaries, it is most often related to a forgotten invariant than to breaking a established one. But that's all conjecture.

On the matter of productivity, the abstraction mechanisms offered by the Ruby language help to structure code and avoid repetition and that's certainly noticeable in comparison to Java (though, in my opinion, not in comparison to Scala, and probably also not in comparison to Smalltalk, ML, Haskell or Oz). That gain is offset to a point by the lack of refactoring tools. There are some who argue that those tools are made necessary by the verbosity of Java, and aren't needed in better languages. That's nonsense. If a language has an abstraction mechanism, that mechanism is used to define an abstraction and to use the defined abstraction elsewhere. If we then want to change the abstraction we must change code at the use sites as well, and that's where such tools can help. This is all so obvious that I find it almost silly to have to write it down.

Many of the abstraction gains in Ruby come from metaprogramming techniques. I'm not completely sold that they are necessary to achieve the level of abstraction attained, and I'm sure that they hinder readability. It's much easier to gain a footing in a library written with straighforward composition mechanisms (be it functions or classes and objects) than in a mess of Strings and calls to define_method and cousins.

While on the subject of abstraction, I have to comment on Rails. It's a mature web framework that does a masterful job of making the common cases easy. This is a much harder feat than it sounds, as we can glean from the failure of JSF, WebForms and similar unsuccessful attempts to abstract the web. The hidden cost of the bargain is when we get to the uncommon cases. It isn't so much the case that there are specific application features that are hard to code in Rails, though it happens, but that the structure of the code that Rails mandates sometimes isn't a good fit to the problem being solved.

I'm sounding a little negative, so let me balance it out by saying that I believe Ruby and Rails were as adequate choices for our project as any. The main reason is the availability of decent quality libraries and tools (refactoring and code navigation notwithstanding), specially in the often overlooked front of deployment and configuration management.

Apologies for an opinionated blog post.

1. Unittyped, for the pedantic.

2. Such as Agda or Coq, or some styles of programming in ML, Haskell or Scala.

A couple of interesting DSLs

It may not yet be an industry tsunami, but there certainly is a growing wave of interest in Domain Specific Languages. As often happens when thinking about programming language design, there appears to be an excessive concern with syntax and little talk of semantics. Dave Thomas points out how much effort is wasted playing syntactic games to make code look like English; effort that would be better spent identifying and representing the domain. To prove his point he talks about make and active record and Groovy builders as examples of successful DSLs. I've stumbled upon some more examples of semantically interesting DSLs on a couple of papers and thought it would be worthwhile to share some stuff I learned in the process.


Kay
Alan Kay is one of the giants in our little science, known for his fearless disposition to carry out "big ideas". His most recent endeavor, partnering with Ian Piumarta and others, is a good example of that. The project is called "Steps Toward the Reinvention of Programming" and aims to build a complete software system, from the metal up to the applications, in under 20 KLOC. Some of that magic will be achieved through, you guessed it, domain specific languages. To quote from first published report.

We also think that creating languages that fit the problems to be solved makes solving the problems easier, makes the solutions more understandable and smaller, and is directly in the spirit of our “active-math” approach. These “problem-oriented languages” will be created and used for large and small problems, and at different levels of abstraction and detail.

The project is only a year-old, so it is understandably far from the goal of a full-system. But they have already delivered bits and pieces that give an idea of the path forward. A particularly cool part is their TCP/IP stack implementation. The first step in any networking stack is to unmarshal packet headers according to some specification. For IP we look in RFC-791 and find a lovely piece of ASCII art describing just that:

+-------------+-------------+-------------------------+----------+----------------------------------------+
| 00 01 02 03 | 04 05 06 07 | 08 09 10 11 12 13 14 15 | 16 17 18 | 19 20 21 22 23 24 25 26 27 28 29 30 31 |
+-------------+-------------+-------------------------+----------+----------------------------------------+
|   version   | headerSize |       typeOfService      |                     length                        |
+-------------+-------------+-------------------------+----------+----------------------------------------+
|                     identification                  | flags    |                  offset                |
+---------------------------+-------------------------+----------+----------------------------------------+
|       timeToLive          |         protocol        |                    checksum                       |
+---------------------------+-------------------------+---------------------------------------------------+
|                                               sourceAddress                                             |
+---------------------------------------------------------------------------------------------------------+
|                                             destinationAddress                                          |
+---------------------------------------------------------------------------------------------------------+

Most implementations just hardcode these definitions, and those for TCP, and for UDP, and so on. Of course the footprint of the traditional approach is too high for Kay and Piumarta purposes. They opted for a seemingly odd technique: just grab the data from the specifications. Here is, in its entirety, the code for unmarshaling IP headers:

                                           { structure-diagram }
+-------------+-------------+-------------------------+----------+----------------------------------------+
| 00 01 02 03 | 04 05 06 07 | 08 09 10 11 12 13 14 15 | 16 17 18 | 19 20 21 22 23 24 25 26 27 28 29 30 31 |
+-------------+-------------+-------------------------+----------+----------------------------------------+
|   version   | headerSize |       typeOfService      |                     length                        |
+-------------+-------------+-------------------------+----------+----------------------------------------+
|                     identification                  | flags    |                  offset                |
+---------------------------+-------------------------+----------+----------------------------------------+
|       timeToLive          |         protocol        |                    checksum                       |
+---------------------------+-------------------------+---------------------------------------------------+
|                                               sourceAddress                                             |
+---------------------------------------------------------------------------------------------------------+
|                                             destinationAddress                                          |
+---------------------------------------------------------------------------------------------------------+
                           ip -- Internet Protocol packet header [RFC 791]

This is actual working code. But wait; didn't they just swept the parsing dirt under the rug? The rug here being the code to parse this fine looking tables. Surprisingly, that code is a whopping 27 lines of clean grammar definitions with semantic actions. The "trick", so to speak, is the underlying parsing mojo provided my Piumarta's OMeta system. Which is, by the way, itself implemented in about 40 lines of OMeta code. Yeah, turtles all the way down and all that stuff...

Ok, this is all very cute, but I seem to have fallen on my own trap and can't stop talking about syntax. The next bit of this networking stack is a little more interesting, the problem now is to handle each incoming TCP packet according to a set of specified rules such as "in response to a SYN the server must reply with a SYN-ACK packet". Here is the code:

['{ svc     = &->(svc? [self peek])
    syn     = &->(syn? [self peek]) .   ->(out ack-syn    -1 (+ sequenceNumber 1) (+ TCP_ACK TCP_SYN) 0)
    req     = &->(req? [self peek]) .   ->(out ack-psh-fin 0 (+ sequenceNumber datalen (fin-len tcp))
                                                             (+ TCP_ACK TCP_PSH TCP_FIN)
                                                             (up destinationPort dev ip tcp
                                                                 (tcp-payload tcp) datalen))
    ack     = &->(ack? [self peek]) .   ->(out ack           acknowledgementNumber
                                                             (+ sequenceNumber datalen (fin-len tcp))
                                                             TCP_ACK 0)
            ;
    ( svc (syn | req | ack | .) | .     ->(out ack-rst       acknowledgementNumber
                                                             (+ sequenceNumber 1)
                                                             (+ TCP_ACK TCP_RST) 0)
    ) *
  } < [NetworkPseudoInterface tunnel: '"/dev/tun0" from: '"10.0.0.1" to: '"10.0.0.2"]]

The set of rules above is nothing more than a grammar and the code to construct response packets is implemented as corresponding semantic actions. This snippet is much harder do grok than the pretty tables we just saw, but it's much more interesting as well. The crucial idea is to pattern-match on the stream of incoming packets looking for flag patterns and respond accordingly. What's nice is that they already had a well-honed pattern matching language in OMeta's Parsing Expression Grammars. I should note that a powerful parsing engine is not a Golden Hammer, but it is a useful and underutilized computational model. And realizing that is much more significant, IMHO, than the procrustean effort of trying to shoehorn "natural language" text into a general purpose programming language.


Pierce
Now let's turn our attention to a different kind of DSL, developed for the Harmony project led by Pierce at UPenn. The problem to solved here is synchronizing bookmark data among different browsers. Seems a far cry from "reinventing computer programming", but there are some intricacies involved, as we shall soon see. The basic approach taken is to transform each browser-specific representation to an abstract view, synchronize the data in this abstract form, and than propagate it back to the concrete form. If you squint hard enough you can see these transformations are a form of the general "view-update problem" known from database literature. Instead of extracting a view from a set of tables, updating it, and propagating the changes back to the original tables, they get an abstract representation from a concrete one, update it (the synchronization proper), and putback the modified data to the original concrete format. So, one concrete input for Mozila would be the following html-ish file:

<html>
 <head> <title>Bookmarks</title> </head>
 <body>
  <h3>Bookmarks Folder</h3>
  <dl>
   <dt> <a href=\"www.google.com\"
           add_date=\"1032458036\">Google</a> </dt>
   <dd>
    <h3>Conferences Folder</h3>
    <dl>
     <dt> <a href=\"www.cs.luc.edu/icfp\"
             add_date=\"1032528670\">ICFP</a> </dt>
    </dl>
   </dd>
  </dl>
 </body>
</html>

The abstract representation of that data is :

{name -> Bookmarks Folder
 contents ->
  [{link -> {name -> Google
              url -> www.google.com}}
   {folder ->
     {name -> Conferences Folder
      contents ->
       [{link ->
         {name -> ICFP
          url -> www.cs.luc.edu/icfp}}]}}]}

That's a textual representation of a labeled tree. Each {..} is a tree node, subnodes are identified by a label (i.e. label -> {...} ) and stuff inside square brackets are lists. So, basically we have two tree "schemas" and wish to translate between them. Here is where domain specific languages will come into play. We could naively propose to just whip up a couple of XSLTs and be done with it. The get direction would be trivial, but the putback is trickier. Note that the abstract representation lacks information about the add_date of the bookmarks; this is because not all browsers store this data. In a way, the abstract format is a minimal subset of the kinds of data that each browser is interested in. So, the putback of new bookmarks coming from non-Mozilla browsers could just default to some arbitrary date value, but we don't want to lose the data we have for existing bookmarks! This rules-out using a simple stylesheet for the putback.

Essentially, this is why the view-update problem is an interesting research question. The relevance to this post is the path Harmony's team chose to solve it, building a bidirectional language*. It's similar to a functional language, but instead of functions they have lenses. A lens is a pair of functions, one for get (from the concrete to the abstract) and one for putback. A putback lens takes a modifed abstract element and the original concrete element, mapping to an update concrete element.

Rephrasing more formally, though diverging from the notation used in the paper, a lens L would be a pair of functions (Lg, Lp). Using A as the domain of abstract elements and C for the domain of the concrete elements, the functions would be defined in:

Lg: C -> A
Lp: (C x A) -> C

So far we haven't gained much, but the above definitions allow us to express our requirements of "information conservation" as equations:

Lp(Lg(c), c) = c for all c in C
Lg(Lp(a, c)) = a for all a in A and c in C

Any lens obeying this equations can be called "well-formed". To exemplify, here is the identity lens (the arrow pointing up is the get and the opposite is the putback):



Absolutely uninteresting, as to be expected from any identity operation, but note that last line. It is the lens' type signature. Yes, this DSL has a full-blown type system! Take a look at a more interesting example, the map lens, which is analogous to the map function from functional programming:



The behavior isn't complicated, map is parametrized by another lens l, and just applies it to each subnode in the concrete tree for get. In the putback direction, it also just applies the putback for each element in the abstract tree, relying on the assumption that l behaves correctly for nodes missing in c. Now look at the scary type signature, which, to be perfectly honest, I don't fully comprehend myself. It is there to assure the well-formedness of map (and a couple of other properties), based on the type of l.

Lest I reproduce the entire paper here, and completely butcher it in the process, I'll cut to the final chapter of the story and show the program that maps between Mozilla's bookmark format and the abstract representation:

link =
  hoist *;
  hd [];
  hoist a;
  rename * name;
  rename href url;
  prune add_date {$today};
  wmap {name -> (hd []; hoist PCDATA)}

folder = hoist *;
  xfork (*h} {name}
    (hoist *t;
     hd [];
     rename dl contents)
  wmap {name -> (hoist *;
                               hd [];
                               hoist PCDATA)
               contents -> (host *;
                                    list_map item)}

item =
  wmap {dd -> folder, dt -> link};
  rename_if_present dd folder;
  rename_if_present dt link

bookmarks =
  hoist html;
  hoist *l
  tl {|head --> {| * --> [ {|title --> {|* -->
          [{|PCDATA --> Bookmarks|}]|}|}]|}|};
  hd [];
  hoist body;
  folder

I'm afraid I'm unable to explain much of this program without going deeper than is appropriate here. But see how much is accomplished in probably fewer lines of code than would be required for expressing a mere transformation in XSLT . And of course, the whole bookmark synchronization thing is just a toy problem; the resulting system is powerful enough to tackle larger beasts. See the other papers in the project website, where they apply lenses to the traditional relational view-update problem, to character Strings and to data replication in distributed settings.


Wrapping up

• DSL design is language design, and that involves more than just syntax.
• Sometimes an well-known computational model can be repurposed to fit domain requirements, like Kay and Piumarta did adopting a grammar parsing engine to process a packet stream.
• Automata and similar non-turing-complete models can be very useful in Domain Specific Languages.
  
• Sometimes it pays to develop whole new semantics for your DSL.
• Of course there is little that is actually "wholly new" in the world. Taking Harmony's semantics for example, the team did apply a lot of domain theory to prove the totality of their lens combinators.
  
• If you can identify invariants that are hard to get right, it may pay to express them in a type system. But be warned that this is no child's play; even Pierce didn't go all the way to building a typechecker for his lenses.
  
• Have fun!

Metaprogramming and conjuring spells

"A computational process is indeed much like a sorcerer's idea of a spirit. It cannot be seen or touched. It is not composed of matter at all. However, it is very real. It can perform intellectual work. It can answer questions. It can affect the world by disbursing money at a bank or by controlling a robot arm in a factory. The programs we use to conjure processes are like a sorcerer's spells. They are carefully composed from symbolic expressions in arcane and esoteric programming languages that prescribe the tasks we want our processes to perform."
- Abelson and Sussman — SICP

Among the plethora of metaphors that plague our field, I find computing as incantation of spells one of the least annoying. Some fellow with a long beard writes odd-looking prose that will later, through some magical process, turn lead into gold or help vanquish some inept demon. Man, that show sucked, I don't know why anyone would watch that shit, specially the reruns Tuesday to Saturday at 04AM and Monday to Friday at 12PM on channel 49. Well, anyway, what's interesting about the analogy is that it shows the dual nature of software: it is both a magical process and a bunch of scribbled lines. To mix metaphors a bit, we can say that software is, at the same time, a machine and the specification for that machine.

This is what makes metaprogramming possible and, also, what makes it unnecessary. By the way, when I write "metaprogramming", I'm specifically thinking about mutable meta-structures, changing the tires while the car is running metaprogramming, not mere introspection. Throwing away that mundane car analogy and getting back to our wizardry metaphor, metaprogramming would be like a spell that modifies itself while being casted. This begs the question, beyond fodder for bad TV Show scripts, what would this be useful for? My answer: for very little, because if the wizard programmer already has all the information needed for the metaprogram, then he might as well just program it... To make this a little less abstract, take a simple example of Ruby metaprogramming:

01  class DrunkenActress
02   attr_writer :blood_alcohol_level
03  end
04
05  shannen_doherty = DrunkenActress.new
06  shannen_doherty.blood_alcohol_level = 0.13

By the way, I'm not a Rubyist, so please let me know if the example above is wrong. The only line with meta-stuff is line 2, where a method named "attr_writer" is being called with an argument of :blood_alcohol_level. This call will change the DrunkenActress class definition to add accessor methods for the blood_alcohol_level attribute. We can see that it worked in line 6, where we call the newly defined setter.

But the programmer obviously already knows that the DunkenActress class needs to define a blood_alcohol_level attribute, so we see that meta-stuff is only applied here to save a few keystrokes. And that is not a bad motivation in itself, more concise code often is easier to understand. Then again, there are other ways to eliminate this kind of boilerplate without recursing to runtime metaprogramming, such as macros or even built-in support for common idioms (in this case, properties support like C# or Scala).

There may be instances where the cleanest way to react to information available only in runtime is trough some metaprogramming facility, but I have yet to encounter them. Coming back to Rubyland, Active Record is often touted as a poster child for runtime metaprogramming, as it extracts metadata from the database to represent table columns as attributes in a class. But those attributes will be accessed by code that some programmer will write — and that means, again, that the information consumed by the metaprogram will need to be available in development time. And indeed it is, in the database. So ActiveRecord metaprogramming facilities are just means to delegate the definition of some static structure to an external store, with no real dynamicity involved. If it were not so, this kind of thing would be impossible. Also note that recent Rails projects probably use Migrations to specify schema info in yet another static format.

To summarize, runtime mutable metaprogramming is like that bad purple translucent special effect, it is flashy, but ultimately useless. Anyway, that's my current thinking in the matter, but I still need to read more on staging.

[EDIT: corrected a mistake relating to the code sample]

Pondering

"Formal methods will never have any impact until they can be used by people that don’t understand them."

Tom Melham

"The original study that showed huge variations in individual programming productivity was conducted in the late 1960s by Sackman, Erikson and Grant (1968). They studied professional programmers with an average of 7 years' experience and found that the ratio of initial coding time between the best and worst programmers was about 20 to 1, the ration of debugging times over 25 to 1, of program size 5 to 1, and of program execution speed about 10 to 1. They found no relationship between a programmer's amount of experience and code quality or productivity.

Although specific rations such as 25 to 1 aren't particularly meaningful , more general statements such as "There are order-of-magnitude differences among programmers'" are meaningful and have been confirmed by many other studies of professional programmers (Curtis 1981, Mills 1983, DeMarco and Lister 1985, Curtis et al. 1986, Card 1987, Boehm and Papaccio 1988, Valett and McGarry 1989, Boehm et al. 2000)."

Steve McConnell
Code Complete, Second Edition

"If you look at the way software gets written in most organizations, it's almost as if they were deliberately trying to do things wrong. In a sense, they are. One of the defining qualities of organizations since there have been such a thing is to treat individuals as interchangeable parts. This works well for more parallelizable tasks, like fighting wars. For most of history a well-drilled army of professional soldiers could be counted on to beat an army of individual warriors, no matter how valorous. But having ideas is not very parallelizable. And that's what programs are: ideas."

Paul Graham
Holding a Program in One's Head

"Software entities are more complex for their size than perhaps any other human construct because no two parts are alike (at least above the statement level). If they are, we make the two similar parts into a subroutine--open or closed. In this respect, software systems differ profoundly from computers, buildings, or automobiles, where repeated elements abound. [...]

The complexity of software is an essential property, not an accidental one. Hence, descriptions of a software entity that abstract away its complexity often abstract away its essence. For three centuries, mathematics and the physical sciences made great strides by constructing simplified models of complex phenomena, deriving properties from the models, and verifying those properties by experiment. This paradigm worked because the complexities ignored in the models were not the essential properties of the phenomena. It does not work when the complexities are the essence."

Fred Brooks
No Silver Bullet

"Architecture is intended to be facilitative, of course, in that a good architecture should enable developers to build applications quickly and easily, without having to spend significant amounts of time re-inventing similar infrastructure across multiple projects. [...]

But an architecture is also intended to be restrictive, in that it should channel software developers in a direction that leads to all of these successes, and away from potential decisions that would lead to problems later. In other words, as Microsoft's CLR architect Rico Mariani put it, a good architecture should enable developers to "fall into the pit of success", where if you just (to quote the proverbial surfer) "go with the flow", you make decisions that lead to all of those good qualities we just discussed. "

Ted Neward
Hard Questions About Architects

"The more interesting your types get, the less fun it is to write them down!"

Benjamin C. Pierce
Types and Programming Languages - The Next Generation

"If you don’t know the difference between a group, a ring, and a field, you have no business overloading operators.

Now I’m not saying that one has to take a course in abstract algebra before you can be a competent programmer. You don’t as long as the language you program in doesn’t support operator overloading (or as long as you’re wise enough not to use it if it does). However since most programmers are didn’t get beyond ODEs in college (if indeed they got that far–some of my comp sci friends struggled mightily with calculus and had to retake it repeatedly), one can’t responsibly design a language that requires mathematical sophistication in the 99th percentile for proper use."

Elliotte Rusty Harold
Operator Overloading: Trickier Than it Looks

"You used to start out in college with a course in data structures, with linked lists and hash tables and whatnot, with extensive use of pointers. Those courses were often used as weedout courses: they were so hard that anyone that couldn't handle the mental challenge of a CS degree would give up, which was a good thing, because if you thought pointers are hard, wait until you try to prove things about fixed point theory.

All the kids who did great in high school writing pong games in BASIC for their Apple II would get to college, take CompSci 101, a data structures course, and when they hit the pointers business their brains would just totally explode, and the next thing you knew, they were majoring in Political Science because law school seemed like a better idea. I've seen all kinds of figures for drop-out rates in CS and they're usually between 40% and 70%. The universities tend to see this as a waste; I think it's just a necessary culling of the people who aren't going to be happy or successful in programming careers."

Joel Spolsky
The Perils of JavaSchools

Futurologia

A minha bola de cristal enxerga duas tendências* para as linguagens de programação do futuro*:

• Quantificação. Só porque PROLOG foi uma frustração coletiva, não significa que suas idéias sejam inúteis. A propósito, quantificação é a parte mais interessante de AOP, IMNSHO.
• Metaprogramação reflexiva profunda. Bonito isso né, eu li num livro. Falando sério, acredito que a importância de metaprogramação é óbvia, o que não é tão óbvio são os qualificadores "reflexivo" e "profundo". O primeiro vem da observação que se estado mutável é um problema, então metaestado mutável é um metaproblema maior ainda. E "profunda" porque eu acho que a reflexão tem que atingir até o nível da AST - o Erik Meijer nesta entrevista com a InfoQ fala bem sobre isso, como "quoting" é um conceito fundamental em sistemas formais.
  

* Definições:
tendência == algo que eu quero que aconteça.
futuro == ponto no tempo distante o suficiente para que: (a) a tendência supracitada tenha se realizado ou (b) ninguém mais se lembre deste post.

Design Patterns are not Recipes

The controversy

Over the past few months, I've been seeing some Design Patterns backlash on the blogosphere, I guess it is accompanying the agile anti-hype phase that's also strong these days. The most rabid attack came from Mark Dominus, making the case that many innovations in programming languages in the past decades were in response to common practices that could be described as patterns, had the pattern format been known back then. Take, for instance, what we now know as a procedure call: code to stack up register values and return address followed by a jump instruction. Before assemblers became available, programmers used to recode this every time they wanted a subroutine. Dominus sees this observation as a sign that something is wrong with the patterns movement:

"Identification of patterns is an important driver of progress in programming languages. As in all programming, the idea is to notice when the same solution is appearing repeatedly in different contexts and to understand the commonalities. This is admirable and valuable. The problem with the "Design Patterns" movement is the use to which the patterns are put afterward: programmers are trained to identify and apply the patterns when possible. Instead, the patterns should be used as signposts to the failures of the programming language. As in all programming, the identification of commonalities should be followed by an abstraction step in which the common parts are merged into a single solution."

Professor Ralph Johnson, one of the original "Gang of Four" members, responded:

"No matter how complicated your language will be, there will always be things that are not in the language. These things will have to be patterns. So, we can eliminate one set of patterns by moving them into the language, but then we'll just have to focus on other patterns. We don't know what patterns will be important 50 years from now, but it is a safe bet that programmers will still be using patterns of some sort."

Dominus retorts with subtler arguments, and I encourage you to read his article to avoid any misinterpretations of my part. But I'll still quote what I believe is the core of his thinking:

"What I imagine is that when pattern P applies to language L, then, to the extent that some programmer on some project finds themselves needing to use P in their project, the use of P indicates a deficiency in language L for that project.

The absence of a convenient and simple way to do P in language L is not always a problem. You might do a project in language L that does not require the use of pattern P. Then the problem does not manifest, and, whatever L's deficiencies might be for other projects, it is not deficient in that way for your project.

(...)

But to the extent that some deficiency does come up in your project, it is a problem, because you are implementing the same design over and over, the same arrangement of objects and classes, to accomplish the same purpose. If the language provided more support for solving this recurring design problem, you wouldn't need to use a "pattern". Consider again the example of the "subroutine" pattern in assembly language: don't you have anything better to do than redesign and re-implement the process of saving the register values in a stack frame, over and over?"

My take

Mark seems to be worried that programming language innovation will be stifled by the patterns movement, on account of programmers being taught to mimic patterns on their code instead of applying that energy on incorporating them into programming languages. It is important to first acknowledge, as himself put it, that it is valuable to identify commonalities in software design, one could even say this is a precondition for evolving a programming language. So, he sees the problem in not working to embody these commonalities in the language. From my exposure to the patterns literature, I believe the movement is not in any way against incorporating patterns as programming language features. It is implicit in this passage from GoF, page 4:

"Our patterns assume Smalltalk/C++-level language features, and that choice determines what can and cannot be implemented easily. If we assumed procedural languages, we might have included design patterns called "Inheritance," "Encapsulation," and "Polymorphism." similarly, some of our patterns are supported directly by the less common object-oriented languages. CLOS has multi-methods, for example, which lessen the need for a pattern such as Visitor"

And explicit in Ralph Johnson's aforementioned blog post: "Many of the patterns will get subsumed by future languages, but probably not all of them". Now that we know that design patterns are contextual and can be incorporated as language features, we must ask if the emphasis of the patterns movement isn't displaced. Why go to the trouble of publishing large books describing at length things like intent, motivation, participants, consequences, related patterns, etc, when we could just inventory all patterns and shove our favorites in our programming languages? One very simple reason is that not all patterns would yield benefit from being reified. Dominus says that people often mentioned to him MVC as an example of a pattern so complex that it could not be absorbed in a programming languge. But, of course, they were all wrong and he was right, since novel systems like Ruby on Rails or subtext do exactly that, definitively confirming his thesis that the only impediment was an atrocious lack of imagination on the part of his opponents! This is all very strange to me, since "MVC" came to life as pretty concrete software - it was the GUI development framework bundled with Smalltalk-80. Many years later, after several separate versions were developed, it was described and published as an (architectural) pattern. Leaving object orientation early history aside, lets get back to the matter of patterns that aren't targets for reification. One example is the Façade(185) design pattern. As one of the most frequently applied GoF patterns, described having as it's Intent to "provide a unified interface to a set of interfaces in a subsystem", there can be no doubt that it is indeed recurring. Looking at the Structure and Participants sections, we can see that it is very simple, just a Façade class that depends on many other (unidentified) subsystem classes inside a boundary. A consequence of this simplicity is that there would be little gain in incorporating this pattern into a programming language, as it doesn't really represent specific interactions that have to be recoded each time the pattern is applied.

One could respond that if that is the case, then the pattern is useless. It describes a solution so simple that a programmer who has never heard of the "Façade design pattern" would probably be able to construct it by himself. The error in this judgment is that a pattern's merit isn't measured by how interestingly or usefully it gives a solution to a problem. Knowing that its not hard to invent Façade does not detract from the fact that being able to talk about Façade is a big design win in itself. Patterns are as much an aid to communication as they are vehicles to disseminate knowledge.:

"Naming a pattern immediately increases our design vocabulary. It lets us design at a higher level of abstraction. Having a vocabulary for patterns lets us talk about them with our colleagues, in our documentation, and even to ourselves. It makes it easier to think about designs and to communicate them and their trade-offs to others."[GoF, page 3]

On the other hand, we already mentioned that some of the patterns are indeed amenable to reification. In this case there are two paths to choose from: coding it as a library atop usual language abstraction mechanisms or incorporating it as a basic language feature. Dominus second post argues that this choice is a mere implementation detail. Now, to paraphrase him, his point seems completely daft, which may I interpret to mean that there's something that went completely over my head. The difference is obvious: if some feature can be implemented as a library, any programmer that wants it can write it exactly one time and reuse as appropriate; no language modification required. As a contributor to CPAN , he should know well that nowadays much software reuse is done through open source libraries, lowering the recode count to zero for it's users. This is a crucial distinction, as adding something to the language has a huge impact on the whole technical ecosystem, from increased barrier to entry to pernicious interaction between features (non-orthogonality).

Lets take another look at Dominus' central proposition:

"(...) when pattern P applies to language L, then, to the extent that some programmer on some project finds themselves needing to use P in their project, the use of P indicates a deficiency in language L for that project. "

I believe the most important question here is: what does it mean to "use [pattern] P"? If you take it to mean follow the steps from P's description, possibly copying some code from the "Implementation" section, then this reasoning makes sense. But patterns are not merely recipes, and a pattern language is not a cookbook! One way in that patterns differ from recipes is that, as we saw in Façade, the Solution section can be of little importance compared to the communication gain from just naming the pattern. Another difference is that there is wide latitude in implementation strategies for each pattern, not to mention cases where multiple patterns present themselves as design alternatives for a set of forces.

Speculating a bit, I believe the origin of this antagonism toward design patterns is that the idea of a recurrent structure is antithetical to a certain ethos present in the software development community. Mark Dominus summarizes this feeling well in this passage "As in all programming, the identification of commonalities should be followed by an abstraction step in which the common parts are merged into a single solution." It can also be formulated as a call to arms: Don't repeat yourself! Or better yet, DRY! (the love for TLAs is another part of the programming ethos :). I don't dispute that eliminating repetition is an important design heuristic, but I sometimes wonder if it can be taken too far, becoming a sort of factorization fetishism that is detrimental to productivity.

Domain Specific Languages e Estratificação por Estabilidade

2007 mal começou e o meme das DSLs já está provocando polêmica. Eric Evans, em entrevista na InfoQ, disse:

"More out on the cutting-edge are the efforts in the area of domain-specific languages (DSLs), which I have long believed could be the next big step for DDD. To date, we still don't have a tool that really gives us what we need. But people are experimenting more than ever in this area, and that makes me hopeful."

Philip Calçado citou o Evans e foi além, afirmando que "DSLs são iminentes mas as ferramentas simplesmente ainda não chegaram lá". Escrevendo em tom mais cético, Rodrigo Kumpera comentou que DSLs ainda parecem uma tecnologia de um exemplo só; da mesma maneira que toda palestra de AOP fala de logging, toda introdução à DSLs fala em configuração. Citando:

"Todos estão falando o tempo todo sobre como configuração é um problema a ser resolvido por linguagens de domínio. Até o Martin Fowler comete essa gafe em sua palestra na JAOO 2006! O problema é o mesmo que logging, eu diria, representa nenhum risco a complexidade de um projeto. Quantos realmente já tiveram problemas relacionados a dificuldade de colocar logging em uma aplicação? Configuração idem."

Eu acho que a analogia com AOP não procede. Tracing/logging é de fato um caso de uso (quase trivial, BTW) para AOP. Precisamos analisar configuração com mais cuidado. Tome por exemplo uma aplicação de eCommerce B2C tradicional (você pode imaginar que é, quem sabe, uma loja de, sei lá.., animais de estimação). Na primeira iteração do software, cada item à venda tem um preço de catálogo cadastrado. Essa decisão logo se mostra inflexível, pois uma variação sazonal nos preços é comum no varejo. O requisito é atendido com uma nova feature permitindo que se estabeleça um perentual de desconto/acréscimo por mês para cada produto. A interface com o usuário para esta feature se localiza numa tela entitulada "Configurações". Mais adiante percebe-se que a flexibilidade ainda está aquém do ideal, os clientes querem definir regras de preço mais complicadas, como:

se vendeu mais de 500 na semana passada, acréscimo de 10%.

Pode-se inserir estas regras (hard-coded) no meio do sistema ou decidir por manter a parametrização externa e usar uma DSL. Em qualquer caso, ainda podemos chamar isto de configuração?
Sabendo que código e dados são basicamente a mesma coisa, eu vejo a aplicação de DSLs como decisões a respeito de que tipo de informação faz parte do sistema, e que tipo de informação consiste em parametrização "externa". No fim das contas, é técnica para atender ao "Stable Dependencies Principle (S0P)", deve-se isolar as porções de um software com maior volatilidade e uma linguagem específica - talvez até editável por usuários finais - é uma boa alternativa para implementar os módulos menos estáveis.

Language advocacy

• Lisp: author makes a successful effort to show Lisp's virtues to the non-initiated. This tends to be a not so easy task, since the sources of Lisp's superiority are the very same things that make it look so alien to programmers versant in ALGOL descendant languages.
  
• Scheme: Great language, naive writing. Scheme deserves better.
  
• Smalltalk: This article highlights very well a lot of the points that struck me personally when I first came into contact with Smalltalk.
  
• More smalltalk: "Smalltalk: Requiem or Resurgence?" I'm not very optimistic... But, who knows?
• More lisp: When you get bored with reading about computer programming languages, you can relax, sit back, and enjoy this video about computer programming languages.
  

Clássicos II

Prosseguindo com a série de posts sobre artigos clássicos da computação, avançamos duas décadas a partir do End-to-end Arguments, para chegar à OOPSLA 98. Se o leitor considera um paper publicado em 98 recente demais para ser considerado um verdadeiro clássico, fique tranquilo que o autor é Guy Steele. Co-autor da especificação da linguagem Java, chairman do comitê de padronização do Common Lisp, co-criador do Emacs e autor da linguagem Scheme, ele é um dos pesquisadores mais importantes na área.

O clássico desta vez é Growing a Language, texto de uma palestra apresentando uma abordagem evolucionária para o projeto de linguagens de programação. Steele defende a tese de que novas linguagens devem ser conceptualizadas como um pequeno núcleo de primitivas a ser extendido transparentemente pelos usuários. Com o tempo a linguagem cresce através das adições da comunidade, em um modelo muito similar ao dos projetos de software de código aberto. Sua argumentação é feita ressaltando especialmente os aspectos sociais da adoção de linguagens de programação, sugerindo vários pontos em comum com a literatura de metodologias ágeis de programação (design incremental) e patterns (descrições contextualizadas de abstrações). Uma menção importante é feita ao artigo Worse Is Better, do Richard Gabriel, que está na minha fila de clássicos. O artigo não aborda diretamente a motivação estética para linguagens inerentemente extensíveis, provavelmente com bons motivos.

"Growing a Language" também lembra um assunto que está, tipo assim, super na moda: as Domain Specific Languages (DSLs). A idéia básica é tratar parte do projeto de software como projeto de uma linguagem versando sobre o domínio da aplicação. A partir daí existem várias interpretações: tem quem defenda que usuários finais, especialistas no negócio, sejam responsáveis por editar as DSLs para acompanhar mudanças no ambiente; outros pensam que , de alguma maneira, todo desenvolvimento de software é a criação de DSLs; outros ainda acreditam que as DSLs são melhor expressadas como linguagens gráficas de modelagem. E os programadores de Lisp dizem, como sempre, que já fazem esse tipo de coisa há décadas de maneira muito mais elegante e não entendem todo o fuss atual. O texto do Steele o situa entre aqueles que enxergam todo projeto de sofware como projeto de DSL, e ele defende que a linguagem de programação básica seja criada tendo isto em mente.

Tudo isso é muito importante, mas o texto do paper também é imperdível por seu genial desenvolvimento metacircular. Não entendeu? RTFA.

Semáfaros e smalltalk.

Eu sou um pedestre convicto, pelo menos até eu mudar de idéia. Atravesso o campus da USP todo dia sobre as minhas duas pernas, cruzando as largas avenidas e as famosas rotatórias. Atravesso olhando para os dois lados, pois aparentemente esse layout viário é como um convite para os motoristas descarregarem suas frustrações no acelerador acertando, se tiverem sorte, um estudante ou dois no caminho.

Depois de muita enrolação, a prefeitura do campus resolveu o assunto instalando uma meia dúzia de semáfaros para o rebanho de alunos atravessar sem ser abatido. Eu deveria estar contentíssimo com o incremento na minha probabilidade de sobreviver à USP. Mas não. Eu odiei esses semáfaros. E não é porque eu tenho algum desejo inconsciente de comprar um carro veloz e sair atropelando polianos por aí.

Eu não gostei dos semáfaros porquê eles são, bem, feios. Não porquê poluem a paisagem ou outra viadagem desse tipo. São feios porque estragam um sistema que era belo. A beleza do trânsito organizado puramente pela combinação desses dois elementos, avenidas e rotatórias, é corrompida pelos sinais como se alguém escarrasse num Mondrian.

Voltando à vaca fria, admito que ainda não consegui uma resposta satisfatória sobre "o que é ciência da computação", mas tenho a impressão que a resposta envolve esse tipo de beleza. A criação de estruturas é uma constante na prática matemática moderna, mas o apreço ao minimalismo e à composibilidade me parecem marcas características da Ciência da Computação.

Um ótimo exemplo é a linguagem Lisp, onde todas as computações são funções e todo dado é uma lista. Outro exemplo é Smalltalk, onde tudo são objetos que se comunicam pela troca de mensagens. E como ficam as linguagens usadas por seres humanos normais? Retomando a analogia, Java parece um monte de semáfaros enfiados no pobre Smalltalk. E, embora eu nunca tenha programado em C++, ele me lembra um pouco o metrô de tokyo...