tag:blogger.com,1999:blog-101626392024-03-18T00:04:10.962-03:00Rafael ramblingAnonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.comBlogger84125tag:blogger.com,1999:blog-10162639.post-19887159770523772832014-09-28T23:01:00.002-03:002014-09-30T15:30:15.486-03:00Themes from Strangeloop 2014One of the many reasons making the Strangeloop conference special is the interdisciplinary perspective, taking on themes as diverse as core functional programming concepts - what could fit this description better than the infinite tower of interpreters seen on Nada Amin's keynote - to upcoming software deployment approaches.<br />
<br />
Still, some common themes seem to have emerged. One candidate is the spreadsheet as inspiration for programming. One thinker that seems to have taken some inspiration for his work is Jonathan Edwards, that opened the <a href="http://www.future-programming.org/program.html">Future of Programming</a> workshop with a talk showcasing the latest version of his research language Subtext. Earlier prototypes explored the idea of programming without names, directly linking tree nodes to each other via a kind of cut-and-paste mechanism. In its latest incarnation it appears to have evolved into a reactive language with a completely observable evaluation model, the entire evaluation tree is always available for exploration, and a two stage reactive architecture allows for relating input events to evaluation steps. User interface is auto generated, sharing the environment with the code, much like their older reactive cousing, the spreadsheet.<br />
<br />
<a href="http://vimeo.com/107069470">Kaya</a>, a new language created by David Broderick, explores the spreadsheet metaphor in a more literal manner: what if spreadsheets and cells were composable, allowing for naturally nested structures? Moreover, what if we could query this structure in a SQL-like manner? The result is a small set of abstractions generating complex emergent behavior, including, as in Subtext, a generic user interface.<br />
<br />
Data dependency graph driven evaluation is an important part of both modern functional reactive programming languages and of all spreadsheet packages since 1978's VisiCalc. We saw some of the first on Evan Czaplicki's highly approachable talk "<a href="http://youtu.be/Agu6jipKfYw">Controlling Time And Space: Understanding The Many Formulations Of Frp</a>". And a bit of the latter on Felienne Hermans's talk "<a href="http://youtu.be/0CKru5d4GPk">Spreadsheets for Developers</a>", sort of wrapping around the metaphor and looking to software engineering for inspiration to improve spreadsheet usage.<br />
<br />
One of the great aspects of spreadsheets is the experience of direct manipulation of a live environment. This is at the crux of what Brett Victor has been <a href="http://worrydream.com/#!/InventingOnPrinciple">demonstrating</a> on many of his demos, showing how different programming could be if our tools were guided by this principle. Though he did not present, the idea of direct manipulation was present in Strangeloop in several of the talks. Subtext's transparency and live reflection of code updates on the generated UI moves in this direction. Still on the Future of Programming workshop, <a href="https://www.google.com.br/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CB8QFjAA&url=https%3A%2F%2Fthestrangeloop.com%2Fsessions%2Fshadershop&ei=cfQqVMDrEtDygwT4q4HIDw&usg=AFQjCNH6Obe4LmcYXyoqELbjfwJHGxakkA&sig2=to3TV6grNsO_dznnl9AOtA&bvm=bv.76477589,d.eXY">Shadershop</a> is an environment whose central concept seems to be directly manipulating real-valued functions by composing simpler functions while live inspecting the resulting plots. Stephen Wolfram's keynote was an entertaining <a href="http://youtu.be/EjCWdsrVcBM">demonstration</a> of his latest product, the Wolfram Language. Its appeal was due, among other reasons, to the interactive exploration environment, particularly the visual representation of non-textual data and the seamless jump from evaluating expressions to building small exploratory UIs. <br />
<br />
Czaplicki's <a href="http://youtu.be/Agu6jipKfYw">talk</a> discussed several of the decisions involved in designing Elm, his functional reactive programming language. I found noteworthy that many of those were taken in order to allow live update of running code and an awesome time-traveling debugger.<br />
<br />
Taking a different perspective at the buzzword du Jour, reactive, is another candidate theme for this year's Strangeloop: the taming of callbacks. They were repeatedly mentioned as one evil to be banished from the world of programming, including on Joe Armstrong's keynote, "The mess we are in" and all the functional reactive programming content took aim at the construct. Not only functional, another gem from this year's Future of Programming workshop was the imperative reactive programming language <a href="http://ceu-lang.org/">Céu</a>. Created by Fransico Sant'anna at PUC Rio - the home of the Lua programming language - Céu compiles an imperative language with embedded event based concurrency constructs down to a deterministic state machine in C. Achieving, among other tricks, fully automated memory management without a garbage collector.<br />
<br />
Befitting our age of microservices and commodity cloud computing, another interesting current was looking at modern approaches to testing distributed systems. Michael Nygard <a href="http://youtu.be/N5HyVUPuU0E">exemplified simulation testing</a> - which can be characterized as property based testing in the large - with Simulant, a clojure framework to prepare, run, record events, make assertions and analyze the results of sophisticated black box tests. Kyle @aphyr Kingsbury delivered another <a href="http://youtu.be/QdkS6ZjeR7Q">amazing performance</a> torturing distributed databases to their breaking point. Most interesting was the lengths he had to go to in order to control the combinatorial explosion of the state space and actually verify global ordering properties like linearizability. <br />
<br />
Speaking of going to great lengths to torture database systems, we come to what might have been my favorite talk at the conference, by the FoundationDb team, "<a href="http://youtu.be/4fFDFbi3toc">Testing Distributed Systems w/ Deterministic Simulation</a>". Like @aphyr's Jepsen, they control the external environemnt to inject failures while generating transactions and asserting the system maintains its properties. They take great care to mock out all sources of non-determisim, including time, random number generation, even extend C++ to add better behaved concurrency abstractions. <br />
<br />
Tests run thousands of times each night, nondeterministic behavior is weeded out by running twice each set of parameters and checking outputs don't change. FoundationDb's team goes further than Jepsen in the types of failures they can inject; not only causing network partitions and removing entire nodes from the cluster, but also simulating network lag, data corruption, and even operator mistakes, like swapping data files between nodes! Of course the test harness itself could be buggy, failing to exercise certain failure conditions; to overcome this specter, they generate real hardware failures with programmable power supplies connected to physical servers (they report no bugs were found on FoundationDb with this strategy, but Linux and Zookeeper had defects surfaced - the latter isn't in use anymore). <br />
<br />
What I particularly enjoyed from this talk was the attitude towards the certainty of failures in production. Building a database is a serious endeavor, data loss is simply not acceptable, and they understood this from the start. <br />
<br />
Closing the conference in the perfect key was Carin Meier and Sam Aaron's keynote demonstrating the one true underlying theme: <a href="http://youtu.be/3_zW63dcZB0">Our Shared Joy of Programming</a>.Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com159tag:blogger.com,1999:blog-10162639.post-56895905653013025382012-10-21T03:16:00.002-02:002012-10-21T03:16:35.045-02:00Security and ObjectsMobile 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.<br />
<br />
And if the platform you are building upon supports reflectively evaluating code, it could be as easy as something like this (in OO pseudocode):<br />
<br />
define load_message(message)<br />
...<br />
eval(message.code)<br />
<br />
Of course it can't be that easy. What if the code in the message does something like:<br />
<br />
new stdlib.io.File("/").delete()<br />
<br />
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:<br />
<br />
define delete()<br />
if VM.callStackContainsEvilCode?()<br />
raise YouShallNotPassException()<br />
<br />
... <br />
<br />
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.<br />
<br />
<h3>
A better way ?</h3>
Perhaps there is a better way. Take another look at the offending line: <span style="font-family: "Courier New",Courier,monospace;">new stdlib.io.File("/").delete()</span>. It is only able to call the dangerous <span style="font-family: "Courier New",Courier,monospace;">delete()</span> 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 <span style="font-family: "Courier New",Courier,monospace;">File</span> class on a global namespace. What if there was no global namespace?<br />
<br />
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 <span style="font-family: "Courier New",Courier,monospace;">new()</span> — on the metaclass object.<br />
<br />
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.<br />
<br />
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 <span style="font-family: "Courier New",Courier,monospace;">File</span>. In a way, object design becomes security policy.<br />
<br />
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 <span style="font-family: "Courier New",Courier,monospace;">Directory</span> 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 <span style="font-family: "Courier New",Courier,monospace;">Directory</span> that checks if callers exceed a given quota of disk space.<br />
<br />
<h3>
Research</h3>
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 <a href="http://www.erights.org/">E</a>. In fact, there is a whole area of research for dealing with security in this manner, it's called "object capability security".<br />
<br />
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 <a href="http://research.google.com/pubs/author35958.html">Mark Miller</a>'s work. He is the creator of the <a href="http://www.erights.org/">E language</a> and the javascript-based <a href="http://code.google.com/p/google-caja/">Caja</a> project. His <a href="http://www.erights.org/talks/thesis/">thesis</a> is very readable.Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com257tag:blogger.com,1999:blog-10162639.post-89774927276161865432012-08-29T01:18:00.001-03:002012-08-29T01:18:39.505-03:00A Practitioner's requests for Programming Language ResearchI have been interested in programming languages and programming language theory for some time, CTM is my favorite technical book, and I even managed to wade through the first chapters in Pierce's TAPL (some day I'll get through the rest, some day...). But it's not often that I can connect that interest with by job as practicing programmer. This post is an attempt to forget about my particular research interests and try to list my daily pain points and wants as a user of programming languages.<br />
<br />
If this is to make any sense, I have to start outlining the context: mostly back-end-related web development, currently with a content-based website, with past consulting stints at more and less enterprisey environments. I won't presume to represent any particular segment of the programming population, but I would be surprised if my peeves are unique. <br />
<br />
<h2>
Semi-automatic mapping between data representations.</h2>
Most programs receive data in one or more external forms — database rows, JSON documents, ASN.1 records, form data and many others — transform them to internal representations for computation and write them out again. Reflection enables generic marshaling libraries so we can escape the drudge of writing and maintaining all that conversion code by hand. There is a whole research area for doing about the same in typed functional programming — polytypic programming — but I know next to nothing about it, I'm afraid.<br />
<br />
All this is great, but in practice a completely generic mapping algorithm is rarely sufficient. It forces one of the two representations to bend to conform to the other: who hasn't seen horrible schema-generated classes or ugly auto-generated xml? On the other hand, when we try to sophisticate the mapping to give developers more flexibility, we get <a href="http://www.javaworld.com/javaworld/jw-07-2008/jw-07-hibernate-search.html?page=3">ever more cumbersome configuration options</a> cluttering our code. We need something better and I hope PLT can help; it could be an elegantly terse language for writing the mappings, it could be an ingenious abstraction mechanism for composing generic mapping with custom instructions, or it could be something else entirely.<br />
<br />
<h2>
Library versioning</h2>
The issues around library versioning and dependency management are well known and have been for a long time, generation after generation of technology creating it's own version dependency hell. The situation is so dire, just enabling the coexistence of many versions of a library <a href="http://msdn.microsoft.com/en-us/library/ms973843.aspx">on a single machine</a> is hailed as a major breakthrough.<br />
<br />
A language based approach can afford to be much more <span>ambitious</span>. Most module systems I'm familiar with handle compatibility by having client-supplied rules preside over version numbers defined by the library provider. The provider, in turn, must decide wholesale for his entire library what level of compatibility he thinks each release can maintain. In practice there is a lot of guessing going on both on the client and the provider side, mediated by the very lossy medium that is the version number.<br />
<br />
Perhaps things need not be so complicated if the language gets in on the action. Imagine if we could indicate to our compiler "this little change in this method here is supposed to be compatible, while this other change over there is not" and the information would trickle down from caller to caller all the way to the public API surface. The compiler would of course flag a call from a compatible method to a non-compatible method, and perhaps a theorem prover/counterexample generator could pinpoint places where the developer unwittingly broke compatibility. If our <a href="http://wcook.blogspot.com.br/2012/07/proposal-for-simplified-modern.html">modules are first-class</a>, we can even contemplate having several versions of them interoperating in runtime to satisfy transitive dependencies differences.<br />
<br />
<h2>
Data evolution</h2>
If the behaviour evolution problem described on the item above is solved, the next issue to tackle is the evolution of data. In a way it's a harder problem to face, as it's not enough to track what changed, we need to know why it changed (simple example: the User record has a <i>surname</i> String field on version one; on version two this field is gone and a new <i>last_name</i> field is there; should it be considered a rename?).<br />
<br />
In the context of server-side web applications I don't see a particular need for in-memory application data evolution (clusters alleviate the need for hot-deploys). But migrating externally stored data is a real necessity. As far as I know, the state of the art now amounts to filtering and sorting manually written database scripts to run at deploy time, perhaps with some syntactic sugar sprinkled on top.<br />
<br />
But if we note that on the moment the data declaration code is being changed, the developer knows why it's changing, we just need a way to record this intent and tie it to the mapping and change structures from the previous two items, and voilà. <i>Things sure sound easy on blog posts, don't them?</i><br />
<br />
<h2>
Tooling</h2>
I've <a href="http://blog.rafaelferreira.net/2011/08/speculating-about-future-development.html">written about this before</a>, so I'll just briefly lament what a shame it is we are trapped between monstrous cockpit-like IDEs and dumb-as-a-rock text editors, when the obvious path of a language-aware editor seems to interest almost no one. By the way, I wish the Light Table guys all the luck.<br />
<br />
<h2>
Non-issues</h2>
From my biased perspective as a practitioner on my particular domain, there are some problems tackled by programming language research that I don't see as particularly pressing.<br />
<ul>
<li><b>Sequential performance</b>: Cache is king.</li>
<li><b>Parallel performance</b>: On the server, multicore parallelism is very well exploited by request-level concurrency and virtualization.</li>
<li><b>Concurrency:</b> STM and Actors are nice but a very large portion of the concurrency issues in practice are simply delegated to the database (and I haven't the foggiest idea what concurrency support those guys crave for, but I bet many are content with locks, monitors and semaphores).</li>
<li><b>Correctness</b>: We have bugs, of course, but they seldom present themselves as classical broken invariants. What are they then? <a href="http://www.exampler.com/testing-com/writings/omissions.html">Faults of omission</a>, unintended interactions between separate systems, API usage misunderstandings. I'm skeptical on language help for these, but I'd be glad to be proven wrong.</li>
</ul>
Seems like a good time to repeat that on this post I'm trying to connect my particular needs as a developer on my current domain to what programming language research might accomplish. I'd expect the issues and non-issues to be different for other domains, or even for other developers in a similar domain but with a different background.<br />
<br />
<h2>
Cake</h2>
Who doesn't love cake? No, not <a href="http://goo.gl/8bKBa">this</a> cake, <a href="http://goo.gl/F0Zbu">this</a> cake. Hmm.Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com27tag:blogger.com,1999:blog-10162639.post-25300264207924646672012-07-07T22:17:00.000-03:002012-07-09T21:33:16.605-03:00Types and BugsThere 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 <a href="http://evanfarrer.blogspot.ca/2012/06/unit-testing-isnt-enough-you-need.html">blog post</a> 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.<br />
<br />
The <a href="https://docs.google.com/open?id=0B5C1aVVb3qRONVhiNDBiNUw0am8">full-length paper</a> 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.<br />
<br />
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:<br />
<ul>
<li>Assuming that a variable always references a valid value when it can contain a null value. </li>
<li>Referencing constructs that no longer exist in the source. </li>
</ul>
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 <i>null</i>. Code that has to deal with optional values must do it trough algebraic data types.<br />
<br />
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.<br />
<br />
If the study's findings are generalizable and my observations are correct, these are the main takeaways:<br />
<ul>
<li>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.</li>
<li>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.</li>
<li>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 <a href="http://qconlondon.com/london-2009/presentation/Null+References:+The+Billion+Dollar+Mistake">how big a mistake</a> it is to allow nulls in a programming language. </li>
</ul>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com92tag:blogger.com,1999:blog-10162639.post-259453952729579932011-08-11T01:21:00.001-03:002011-10-02T22:59:47.701-03:00Speculating about Future Development Environments<div style="font-family: inherit; text-align: justify;">
<div style="text-align: left;">
<a href="http://lenz.unl.edu/2011/04/09/life-on-the-command-line.html">This</a> <a href="http://lenz.unl.edu/2011/07/25/the-mythical-man-finger.html">series</a> <a href="http://lenz.unl.edu/2011/08/05/the-man-finger-aftermath.html">of essays</a>, making up a sort of ode to the command line, got me thinking again about the user interface we face everyday, our software development environments. Remember when you were a kid and spent time imagining the ideal car — it should be able to fly and transform into a submarine —, or the ideal house — it should have an underwater garage to park the plane-submarine-car? No? Perhaps I was a weird kid. But that's what this post is about, conceiving what would be my ideal programming environment.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
I can't get into this subject without first discussing the big rift: editors versus IDEs. I have to say I'm not a member of either faction, I love vim, I get a kick of learning new tricks (did you know that if you accidentally delete something and lose a previously yanked text, you can get it back with "0p ?), but I'm also a happy user of modern IDEs. In fact, I don't know why we have these factions. I suspect the origin is in the name IDE, Integrated Development Environment. It suggests a large piece of software <i>integrating</i> lots of tools to be used in the making of software, stuff like stupid code generation wizards and the always dissatisfying WYSIWYG interface designers. This perspective isn't entirely misleading, but I think it fails to capture the most important aspect of IDEs: they are editors that understand the programming language being used. They analyse your code's with regard to syntax, semantics and type structure to be able to realise feats such as jumping from a call to a definition site, changing a symbol definition and all it's uses, listing all lines of code that call a certain method/function, etc.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
I see absolutely no reason why any programmer would forgo these abilities, but I see why many avoid current IDEs. The user interface is a mess of toolbars, menus, tabs, docked windows, popup windows of different sorts and gargantuan settings dialogs. Only after some time spent living in these strange environments one is expected to reap the benefits of working with a smart editor. In a way, the current crop of IDEs reminds me of the web just before Google appeared. To try to find anything with the search engines of the time was a guarantee of wasted time and probable frustration. The situation was so bleak that most of those search engines gave up on being starting points for the web and were becoming "portals", so users could stand a chance of finding what they were looking for within the sections and categories and subcategories of specifically produced pieces of information. Then came Google, with the right technology to extract relevance from the same sea of data everyone else was floundering on.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Aside from the immensely better ranking of search results, another striking difference was Google's minimalistic approach to user interfaces, showing little more than a search box and a list of results. That's where I'd start my ideal environment, a visually simple application to help the programmer focus on reading and writing code. Reading and writing code, not just text, and to be able to help with that, the application would need the code navigation and refactoring tools found in today's IDEs. The question then is, can this be done without all the cruft?</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
I think it can, and the way to do it is the same Google took to beat the competition: relevance and minimalism. All the housekeeping functionality we are accustomed to in current IDEs should be cast aside the in favor of a search centric interface. And there is plenty of housekeeping to get rid of: modules, windows, tabs, workspaces, perspectives, views, projects, buffers, editors, etc... As I envision it, a minimum productive environment would consist of a few tiled panes for editing code, with no tabs. The last part deserves a little explaining. The purpose of tabs is to show the currently opened files. My thinking is that whether a file is currently open or closed should be an implementation detail invisible to users. In order for this to work well, changes in files should be continuously saved and we should have access to a full version history (this is an <a href="http://www.asktog.com/Bughouse/10MostWantedDesignBugs.html">old idea</a> that is <a href="http://arstechnica.com/apple/reviews/2011/07/mac-os-x-10-7.ars/7#document-model">being picked up</a> in Apple's latest OS).</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
As the ubiquitous file-tree view would be gone, all navigation would be done either directly — following a reference in a source file — or via search. The key to make this work is to go to extra lengths to perfect search relevance, perhaps taking contextual clues enriched by the abstract model of the code. For instance, a recently opened file that is close in the call graph to the file currently being edited would spring to the top of the results.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
This minimalism isn't just an exercise in modernistic aesthetics; the problems caused by the litany of housekeeping features go beyond visual clutter. Each of those features generate work for the user, who has to spend time organising his environment and then remember where everything is. This is the kind of work we should delegate to computers, the user needs to deal only with the content he is currently working on and ask the environment for what he needs next. Don Norman makes a much better argument than I ever could for search based user interfaces in <a href="http://www.jnd.org/dn.mss/ui_breakthrough-command_line_interfaces.html">his column</a> for the CACM.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
Ok, so much for editing. What about the rest of the services of a modern IDE? Stuff like version-control integration, build systems, debuggers, test runners, console runners, diagram editors, kitchen-sink explorers, etc. My answer is that while many of these tools benefit from graphical user interfaces, they don't necessarily need to be in the same application as the editor. Some of them could maybe reuse some code from the IDE, but there is no need for them to share window space with the code.</div>
<div style="text-align: left;">
<br /></div>
<div style="text-align: left;">
So ends my wish-list for a future development environment, a fitting time to restate this is not a prediction, as I see no movement in this direction. Quite the opposite, actually, as most IDEs keep sprawling in ever larger feature matrices.</div>
<br />
<br /></div>
Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com42tag:blogger.com,1999:blog-10162639.post-17406300365164553412011-08-01T01:26:00.002-03:002011-08-01T01:27:43.284-03:00Experience report: RubyFor a long time I've been curious about how the supposed benefits and liabilities of programming in a dynamically typed language<sup><a href="#note1">1</a></sup> 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:<br />
<br />
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<a href="#note2"><sup>2</sup></a>, 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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
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.<br />
<br />
Apologies for an opinionated blog post.<br />
<br />
<br />
<div id="note1">1. Unittyped, for the pedantic.</div><div id="note2">2. Such as Agda or Coq, or some styles of programming in ML, Haskell or Scala.</div>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com57tag:blogger.com,1999:blog-10162639.post-79956819299085482102011-05-22T02:19:00.004-03:002011-08-01T01:37:21.048-03:00Unsolicited and uninformed rant about Software Engineering Research<a href="http://catenary.wordpress.com/2011/05/19/how-do-practitioners-perceive-software-engineering-research/">Jorge Aranda interviewed</a> industry professionals regarding their opinions of software engineering research. Needless to say I wasn't asked, and also needless to say I'll shoot my mouth off anyway. As with most of the interviewees, my knowledge of software engineering research goes little beyond Brooks' classic papers. Despite my reduced exposure, the impression I have of S.E. research is less then stellar. I have a feeling that a lot of the research tries to be too helpful, and ends up lacking in enlightenment.<br />
<br />
It seems the goal is often to evaluate a certain practice in order to recommend it or not to the industry. I find this goal suspect for a number of reasons: the definition of success is too context bound (e.g. some environments value fast feedback while others value more a well crafted user experience), the measures of project success may mislead, some practices can help at certain parts of a project and hinder at different parts, people respond differently to different incentives, personal preferences play a major factor, etc. Perhaps Cockburn's "<a href="http://goo.gl/5udiJ">Characterizing people as non-linear first-order components in software development</a>" helps to explains my uncertainty. <br />
<br />
I'm not writing just to complain that research I'm not familiar with goes about the wrong way. I'm also writing to offer unsolicited advice regarding what the aforementioned research should do. In a nutshell, I would like to learn more about programmers, teams, and culture. Research about programmers could investigate stuff like correlation between psychological attributes and professional attributes (e.g. are people with certain personality profiles more attracted to some kinds of software than others), differences in thinking processes between programmers doing different kinds of work, differences in the work of programmers that have been doing the same thing for an extended amount of time versus programmers with a more diverse career, etc.<br />
<br />
Research about teams could look into communication patterns (how and when they tend to take place, not which are more "effective" than others), how people react to homogeneous versus heterogeneous skill-set compositions, how the amount of time spent as a team affects the work (not just wrt productivity), at what team sizes people tend to jell into cliques (and what other factors are in play in the process), how the physical layout affects the communication (again, not trying to find "optimal placements"), ...<br />
<br />
The "culture" part may seem a strange focus for software engineering research, but I would enjoy reading anthropological accounts of the differences an similarities between behaviours of the different programming cultures: systems programming, the smalltalk/OOPSLA/XP culture, lispers, modern large-scale web development, game developers, etc. The very question of whether it is meaningful to apply the word "culture" here would be worthy investigating.<br />
<br />
Anyway, the particulars aren't important, I just want to emphasize the most interesting research, from my point of view, is the one that tries to understand, not merely to optimze.<br />
<i><br />
<br />
Edit: Jorge Aranda commented to point out the interviews were conducted by a team including himelf, Margaret-Anne Storey, Marian Petre, and Daniela Damian.</i><span style="background-color: transparent; color: black; font-family: Arial; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline;"></span>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com117tag:blogger.com,1999:blog-10162639.post-54424978180514874292010-11-17T01:28:00.001-02:002010-11-17T10:07:22.158-02:00Book review: Growing Object Oriented Software Guided by Tests<div style="background-color: transparent; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span id="internal-source-marker_0.3330381428822875" style="background-color: transparent; color: black; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span class="Apple-style-span" style="font-family: inherit;">I’m a curious kind of guy. It is with some surprise, then, that I catch myself re-reading a technical book: Nat Pryce and Steve Freeman’s </span><a href="http://www.amazon.com/Growing-Object-Oriented-Software-Guided-Tests/dp/0321503627/"><span class="Apple-style-span" style="font-family: inherit;">Growing Object Oriented Software Guided By Tests</span></a><span class="Apple-style-span" style="font-family: inherit;">. It’s a very practical book, stuffed with code and useful advice, but it’s also more than that.</span></span></div><div style="background-color: transparent; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span style="background-color: transparent; color: black; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span class="Apple-style-span" style="font-family: inherit;"><br />
</span></span></div><div style="background-color: transparent; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span id="internal-source-marker_0.3330381428822875" style="background-color: transparent; color: black; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span class="Apple-style-span" style="font-family: inherit;"></span></span><span style="background-color: transparent; color: black; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span class="Apple-style-span" style="font-family: inherit;">The first section of the book gives an overview of the basic principles of object-oriented design and test-driven development; not much is new but everything is clearly explained. The third and final section is a potpourri of test-centric techniques to identify problems and improve code quality. But the meat of the book is in the second section, a long walkthrough the development of a sample program. It’s a much larger example than usually found on programming books, tackling thorny issues such as asynchornous inter-process communication and end-to-end testing of GUIs. And it reads like a real software project, there are missteps, refactorings are rolled-back, some of the work is almost clerical, but then there are the great design breakthoughs, the elegant ideas that simultaneously solve several difficulties, the joy in seeing the product grow. It felt like reading a good novel. And that’s kind of what it is, a programming book that is a narrative, not an exposition.<span class="Apple-style-span" style="white-space: normal;"> </span></span></span><span style="background-color: transparent; color: black; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span class="Apple-style-span" style="font-family: inherit;">Besides making for a good read, the narrative aspect of the book is important for showing how modern object-orientation practice takes place.</span></span></div><div style="background-color: transparent; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span style="background-color: transparent; color: black; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span class="Apple-style-span" style="font-family: inherit;"><br />
</span></span></div><div style="background-color: transparent; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span style="background-color: transparent; color: black; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span class="Apple-style-span" style="font-family: inherit;"></span></span><span style="background-color: transparent; color: black; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span class="Apple-style-span" style="font-family: inherit;">OO criticisms nowadays are a dime a dozen, and though they sometimes present good points, often many of the arguments are directed at practices that aren’t so common, or at least that shouldn’t be so common. For instance, inheritance hierarchies, rampant mutable state, and patternitis (the FactoryFactory syndrome), are not indictments of object orientation, just symptoms of bad programming practice. One of the great things about </span><a href="http://www.amazon.com/Growing-Object-Oriented-Software-Guided-Tests/dp/0321503627/"><span class="Apple-style-span" style="font-family: inherit;">GOOS</span></a><span class="Apple-style-span" style="font-family: inherit;"> is that it provides a great example of actual non-trivial object-orientation. And the same goes for test-driven-development, any abstract discussion of the benefits of TDD is bound to seem hand-wavey; this book helps to ground the understanding in real coding, done step by step in front of the reader’s eyes.</span></span></div><div style="background-color: transparent; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span class="Apple-style-span" style="font-family: inherit;"><br />
</span></div><div style="background-color: transparent; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span style="background-color: transparent; color: black; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"><span class="Apple-style-span" style="font-family: inherit;"></span></span><span class="Apple-style-span" style="font-family: inherit;">Anyway, I've read some pretty good technical books this year, but this one was the best.</span></div><div style="background-color: transparent; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px;"><span style="background-color: transparent; color: black; font-family: Arial; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"></span><span style="background-color: transparent; color: black; font-family: Arial; font-size: 11pt; font-style: normal; font-weight: normal; text-decoration: none; vertical-align: baseline; white-space: pre-wrap;"></span></div>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com39tag:blogger.com,1999:blog-10162639.post-42034299973954311382010-06-08T19:58:00.006-03:002010-06-10T11:23:54.553-03:00Where scala left me wanting<div>n the past few years, I've grown to enjoy more and more programming in a functional style. Even the <a href="http://github.com/rafaeldff/Iogi/" id="s062" title="java code">java code</a> I write nowadays is mostly free of mutable state. But before that, I spent a good chunk of time learning about object orientation and found some great ideas there. Ideas that can carry over to the functional world. One of them is Domain Driven Design, where we strive to have the symbols in the code respresent conncepts in the domain. Of course, I'm oversimplifying DDD, but the ideal of a bijection between the reality our software models and constructs in a programming language is one I believe we should maintain in many, perhaps most, applications.</div><br />
<div>A natural consequence is that our systems architecture tends to resemble an onion, with the domain model in the center and code to make it interact with the rest of the world surrounding it:<br />
<div class="separator" style="clear: both; text-align: center;"></div><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/_AUV7ymG1mDc/TA71W-WtG7I/AAAAAAAAAIQ/wLgNN-QQ6fM/s1600/Wherescalaleftmewanting+(3).png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img height="300" src="http://1.bp.blogspot.com/_AUV7ymG1mDc/TA71W-WtG7I/AAAAAAAAAIQ/wLgNN-QQ6fM/s400/Wherescalaleftmewanting+(3).png" style="-webkit-user-select: none;" width="400" /></a></div><br />
</div>I've labeled the code that interacts with the rest of the world "Adapters", as it should do little more than adapt external representations into concepts the domain model can understand. This architecture is not in any way novel. In fact, it is a version of Alistair Cockburn <a href="http://alistair.cockburn.us/Hexagonal+architecture" id="pwfq" title="Hexagonal Architecture">Hexagonal Architecture</a>. In the common case where the only interactions the domain model has with the rest of the world are through a Database on one end and an User Interface on the other, we've just described the 3-layer architecture that was so popular in the 90s. Some examples of adapters are — to increase our shot at the buzzword bingo — Web MVC Controllers, Repositories or DAOs, message endpoints, GUI listeners, etc., you get the picture.<br />
<br />
<div>Since Scala is a truly hybrid language, marrying quite elegantly OO and FP, it would appear to be the perfect vehicle to write this kind of software. I've found this premise to be correct, for the most part. As you might have guessed, there is an exception; (If there weren't, I wouldn't be writing this post, would I?). The problem is in the code for the adapters. As mentioned, they tend to be simple shims, translating some external representation into domain objects. Coding such translations every single time for every adapter instance in every application is very dull. We desperately need our old friend, lady abstraction, to help us out here. In the Java world, she lends us a hand though dynamic reflection, allowing the construction of objects and invocation of methods to be done generically. Unfortunately, Scala has no reflection API, so we have no alternative but to resort to Java reflection, in a sense reverse-engineering the Scala compilation process.</div><br />
<div>This isn't a major gripe, as Scala constructs tend to map to Java constructs in a straightforward fashion. Also, rumor has it that a Scala reflection API is being developed for 2.8.1. But that's only half the story. Powerful as it is, dynamic reflection alone is not enough to solve the Adapter problem once and for all. We often need to parameterize the translation in some way. For instance, when translating objects to database rows, we must discover the Column names corresponding to object properties. In many cases we can trust convention, for instance we could expect the columns to match exactly the names of the properties. But in other cases there is no option but to somehow configure the translation with an explicit mapping.</div><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/_AUV7ymG1mDc/TA70rXu7iNI/AAAAAAAAAII/d340VNZMmqM/s1600/Wherescalaleftmewanting+(2).png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="300" src="http://1.bp.blogspot.com/_AUV7ymG1mDc/TA70rXu7iNI/AAAAAAAAAII/d340VNZMmqM/s400/Wherescalaleftmewanting+(2).png" width="400" /></a></div><br />
<div> In the Java world this kind of thing used to be done with verbose and annoying XML configuration files. As the language evolved, annotations were introduced, and they are now the main way to configure such translations.</div><br />
<div>Annotations are a great improvement over external XML files, but they can't be the end of the story. There is the relatively minor issue that annotations pollute the domain model we strive so much to keep clean and organized, specially when the same domain objects will be active in many adapters. Beyond that, there is the larger problem that annotations are just metadata. Sometimes we want to parameterize our adapters in richer ways. Take, for instance, the <a href="http://relation.to/Bloggers/ATypesafeCriteriaQueryAPIForJPA" id="t2vu" title="proposal">proposal</a> for a typesafe API for database queries to be added to the new version of the Java Persistence API. It requires a special pre-processor to generate a metamodel that can be used to parameterize a database adapter. </div><br />
<div>A better and more generic approach would be to have the language itself provide this metamodel: a kind of <a href="http://www.lixo.org/archives/2006/09/25/java-feature-request-static-reflection/" id="x09v" title="static reflection">static reflection</a>. I would love to see something like this in Scala. Some time ago I toyed with the idea of writing a compiler plugin to provide a static meta-model of Scala classes, but apparently compiler plugins have issues with non-transparent code generation. </div><br />
<div><i>Postscript. As with all matters regarding programming languages on the web, we must tread lightly. I am not ranting against Scala, in fact I rather enjoy it, as can be gleaned from some of the previous posts. I am only relating a very specific domain where I believe the language can be much improved. </i></div>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com13tag:blogger.com,1999:blog-10162639.post-39782023985557632332009-11-22T21:27:00.005-02:002009-11-29T23:24:55.625-02:00On Exceptions, Mythological Monsters and Household Appliances<div style="text-align: right;"><i><br />
Philosophy aims at the logical clarification of thoughts. Philosophy is not a body of doctrine but an activity. A philosophical work consists essentially of elucidations. Philosophy does not result in 'philosophical propositions', but rather in the clarification of propositions. Without philosophy thoughts are, as it were, cloudy and indistinct: its task is to make them clear and to give them sharp boundaries. </i><br />
Wittgenstein<br />
<br />
<i>If language is not correct, then what is said is not what is meant; if what is said is not what is meant, then what must be done remains undone; if this remains undone, morals and art will deteriorate; if justice goes astray, the people will stand about in helpless confusion. Hence there must be no arbitrariness in what is said. This matters above everything.</i><br />
Confucius<br />
<br />
<i>Shit happens</i><br />
Forrest Gump?<br />
</div><p>Exceptions are a controversial matter among programmers. We disagree about how to deal with them. We disagree if the should be <i>checked </i>by the compiler. We even disagree if they are useful at all. Sometimes controversy arises from real disagreement: I may argue that test-driven-development is the best way to write software while you might say that formal proofs are the way to go. Both sides can productively debate the issue and present thoughtful arguments either way. I posit that the polemics surrounding exceptions are <b>not</b> of this sort. They are, rather, brought about by the inherent confusion in the mechanism. Exceptions are the <a href="http://en.wikipedia.org/wiki/Lernaean_Hydra">Hydra</a> of current programming languages, under a simple banner — <i>to handle exceptional conditions</i> — they mix several mechanisms.</p><h2>The heads<br />
</h2><p>Let's begin with the humble <b>throw </b>term, which is a sort of <i>procedure exit statement</i>, causing the current routine to throw his hands up in the air, call it quits, and immediately return to the caller. The only other statement with a similar effect is <i>return</i>. Of course when calling <i>return</i>, we must return something! In statically typed languages, this something must have a type: the return type of the function or method. Exceptions muddle the picture, if we think of a <i>throw </i>as a kind of <i>return</i> then what is the type being returned? There can be many answers to this question, but let me put forth a proposal: the "return type" of a "throw" is, for all intents and purposes, a <b>variant type</b>, and that is the second head of the Hydra.</p><p>This warrants a small digression. Most functional languages have a way of saying "this type <i>FOO</i> is really either a <i>BAR </i>or a <i>BAZ</i>". So every place in the code that is handed a <i>FOO</i> must check whether it is a <i>BAR</i> or a <i>BAZ</i> and deal appropriately. We call <i>FOO</i> a <i>variant type</i>, and <i>BAR</i> and <i>BAZ</i> are its variants. The syntax for the check is called called a type-case<sup><a href="#FOOTNOTE-1">1</a></sup>. And where have we seen syntax for checking the type of something and then acting on it? Catch clauses!</p><p>But of course many languages lack the concept of variant types. I'll argue that in practice, exception handling code in effect <a title="greenspuns" href="http://en.wikipedia.org/wiki/Greenspunning" id="a4u0">greenspuns</a> variant types. First, we can observe that in languages with <i>checked exceptions </i>the declaration of the exceptions a method can throw — the throws clause in Java — is basically a variant type declaration in disguise. Even when working with unchecked exceptions variants lurk behind, encoded through subtyping. Just notice how little polymorphism is exploited in exception class hierarchies. Different exceptions are given different types for the sole reason of being distinguished in catch clauses. Just like variant types.</p><br />
Ok, time for the next head of the monster. We'll continue to look at the <b>catch</b> clause, but this time we'll look at it as a <b>control structure</b>. As such, it is a strange beast, neither a repetition nor purely a decision structure. Once an exception is thrown, the calling method will stop everything it was doing and jump straight to a catch block. In a way, every exception-throwing method call can be seen as a regular call paired with a conditional jump. Dijkstra may not be rolling in his grave, but he is probably feeling a little tingly.<br />
<br />
Since we've talked about control flow, let's direct our attention to the mischievous head of the Hydra: <b>stack unwinding</b>. After a throw happens, if the calling method doesn't care to handle an exception, his caller will have to bare the burden or leave it up to <b>his</b> caller, recursively unwinding the stack until some frame decides it can be bothered to catch the exception and deal with it. This is a pretty powerful feature, sometimes it's even exploited to simulate continuations in languages that lack them.<sup><a href="#FOOTNOTE-2">2</a></sup><br />
<br />
One more head left: <b>call stack introspection</b><i>. </i>Besides unwinding the call stack, exceptions may reify it. It is a limited form of reflection, typically used only to print stack traces to a log someplace where they can be attentively ignored. Common lore says capturing the stack frames is an expensive operation, and so should be executed only on, well, exceptional circumstances.<br />
<br />
<h2>Exceptional Situations</h2>The confusion bus doesn't stop here, I'm afraid. All the complexity we've examined so far is justified under a deceptively simple banner: <i>to handle exceptional conditions</i>. Hidden in these four words is the vast range of situations that may be interpreted as "exceptional". Like any piece that deals with the subject of exceptions, we can't escape the temptation to suggest a taxonomy. At least this one is short, these are the three main categories of "exceptional situations":<br />
<br />
<ul><li><b>Programming error</b><i>:</i> A traditional example would be code trying to index an array beyond it's bounds. Ideally we would design our abstractions so as to make it impossible to commit such coding errors. From formal grammars to dependent type systems this ideal has been driven much of the research on programming languages over the years. Unfortunately, at least for now, we cannot always evade the need for run-time checks.</li>
<li><b>External failure</b><i>:</i> Something bad happened to some component not within control of the application. Examples: network cable cut, disk crapped out, database died, sysadmin was drunk and lost a round of <a title="UNIX Russian roulette" href="http://ask.slashdot.org/comments.pl?sid=1019609&cid=25652759" id="u:oz">UNIX Russian roulette</a>.</li>
<li><b>Invalid user entry</b><i>:</i> <i>"</i>If an error is possible, someone will make it. The designer must assume that all possible errors will occur and design so as to minimize<br />
the chance of the error in the first place, or its effects once it gets made. Errors should be easy to detect, they should have minimal consequences, and, if possible, their effects should be reversible.<i>"</i> This is from Don Norman's superb <i>The Design of Everyday Things</i>. The book is so good I'm going to slip another quote in here: "The designer shouldn't think of a simple dichotomy between errors and correct behaviour; rather, the entire interaction should be treated as a cooperative endeavor between person and machine, one in which misconceptions can arise on either side"</li>
</ul><br />
<p>Let's not forget we are classifying "exceptional situations", not exception types. Here is an example that I hope will make the distinction clear. Take the always popular FileNotFoundException, that is thrown when application code attempts to read a file and the file isn't there: where do we place it on our little taxonomy? Imagine the application is a boring old word processor and the user types in the wrong file name. That obviously is a case of <i>invalid user entry</i>. Now, consider the case of a mail server attempting to open the file where it stores all queued outgoing mail. This file was probably created by the server application itself, maybe during the installation procedure, and its absence would be an indication that something is very borked in the server environment. The same File Not Found event is now clearly an <i>external failure.</i> This matters, because the strategy used for dealing with the three categories is different, as we'll soon see.</p><br />
<h2>The Inevitable Cross Product</h2>Time to look at how the heads of the hydra fare up to our new categories:<br />
<div><br />
<b>Programming errors</b> are, by definition, unexpected. If we aren't expecting them, there is no point in writing code to handle different exception types. What could you do when you know some code tripped a NullPointerException that's different from what you would do if the offence was an IndexOutOfBounds? In other words, the <b>variant types</b> head is useless here. Exceptions triggered by programming errors are usually caught in a generic stack frame, in the bowels of infrastructure code — through the magic of <b>stack unwinding</b> — and dealt with by logging the error type, message, and stack trace. After logging there is little left to do but to roll over and die. In multi-user systems, killing the whole process is not very polite, so we might nuke just the current work item. This is the gist of the <a title="fault barrier pattern" href="http://www.oracle.com/technology/pub/articles/dev2arch/2006/11/effective-exceptions.html" id="u:.i">fault barrier pattern</a>. <b>Call stack introspection </b>is a very valuable aid to pinpoint the bug. So valuable that I go as far as point its absence as the single most important reason to avoid C for teaching programming to beginners.<br />
<br />
Practical strategies for dealing with <b>external failures</b> aren't too different. We tend to exploit <b>stack unwinding</b> to catch the exceptions in a frame deep in infrastructure land and log them in pretty much the same way. But, every so often, we might want to code a different action, such as to retry the operation or to trigger a compensation transaction. In these relatively rare cases it might be useful to deal distinctly with different <b>variants</b>. Another aspect where external failures are distinct from programming errors is that <b>call stack introspection</b> isn't so helpful: if the failure is external, the exact place in the code where it was detected is of little significance. Of course, it is important that the exception carries enough information to enable a system administrator to find the origin of the fault by just looking at the log.<br />
<br />
<b>Invalid user input</b> is a different beast altogether. <b>Variants</b> are definitely useful; after all it's important to let the user know if their request was <i>over quota </i>rather than <i>under quota</i>. On run-of-the mill interactive OLTP systems, we handle invalid user entry by providing immediate feedback on what was wrong. But not every case is so simple: in some circumstances it may be important to identify suspicious input and raise security flags; in others, we could offer suggestions for the user to correct the data; in asynchronous interactions, we might want to proceed with the action substituting a default or normalized value for the invalid input; and so on. Altogether, there is a wide range of handling strategies, mostly domain-specific. This is a key observation, as not only handling strategies, but also the detection and the very definition of what values are invalid, are full of domain specific decisions. I would go as far as proposing that the controversial <i>domain exceptions</i> all boil down to cases of invalid user input. <br />
<br />
What about the other heads of the monster, are they helpful for <b>invalid user inputs</b>? <b>Call stack introspection</b> is clearly not needed. Moreover, the performance costs of reifying the stack can be detrimental for the not-so-rare instances of invalid input. This isn't just premature optimization, as the conscience of these costs can prevent users from even considering exceptions for the domain logic. What about <b>stack unwinding? </b>I'm afraid I don't really have an answer for this one. On the one hand, domain specific handling logic seems to fit naturally in the calling method. On the other paw, if all we do is inform the user that something happened, a generic code further down the stack is awfully convenient.<sup><a href="#FOOTNOTE-3">3</a></sup> <br />
<br />
</div><div><h2>So what?</h2>We've seen that the feature by the name <i>exceptions</i> is really a hodgepodge of language constructs. Beyond the technical aspects, the very raison d'être for the feature is also muddled. It's as if some crazy nineteenth century inventor decided that since people need to be protected from the heat and, hey, food needs cooling to be preserved as well, why not make buildings like large refrigerators? Just keep the food near the bottom where it's colder, the humans near the top where it's not freezing, and presto! His solution is absurd, but that is because the problem itself is ill-formulated: "to keep stuff cool" is not an useful problem statement. "To deal with exceptional circumstances" isn't either.<br />
<br />
I don't know if the above ramblings are of any practical significance. I certainly don't have any concrete proposal to make things better. My only hope is that language designers will keep in mind context and necessity when devising new constructs.</div><br />
<div class="endnotes"><sup>1 </sup><a name="FOOTNOTE-1"></a>In languages where pattern matching is available, it subsumes type-cases. In fact, one way of thinking about pattern matching is that it is a sophisticated form of type-case.<br />
<br />
<sup>2 </sup><a name="FOOTNOTE-2"></a>Some languages without full support for exceptions do offer a feature called <i>long jumps</i>, that is very close to what I'm calling <i>stack unwinding</i>.<br />
<br />
<sup>3 </sup><a name="FOOTNOTE-3"></a>To further complicate the issue, languages offering variant types usually allow different program structuring techniques. For instance, instead of a direct chain of method calls we may thread a monad through a series of functions.</div>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com9tag:blogger.com,1999:blog-10162639.post-50495290125803367842009-10-10T20:27:00.006-03:002009-10-10T20:42:23.150-03:00Type-safe printf in scala ‽All the excitement surrounding Scala's next big release - 2.8.0 - reminds me of another big release a few years ago. Java 5 was poised to be a huge leg up for developers, long feature lists were all over the java blogosphere: generics, enums, enhanced for-loops, autoboxing, varargs, util.concurrent, static imports, and so on; in sum, a whole heap of goodness. But there were a few odd ducks hidden in the feature lists, most notably <i>"an interpreter for printf-style format strings"</i>.<br />
<br />
Anyone who has been around curly-brace-land long enough knows that printf (or java.util.Formatter) serves one main purpose: it's a poor substitute for built-in variable interpolation in the language. Unfortunatly Scala also lacks variable interpolation and there isn't much we can do about it: our BDFL has ruled. But, there is another use for printf, as a shortcut for applying special formatting for some value types. We can specify a currency format using the string <b><i><code>"%.2f USD"</code></i></b>, or a short american date format with <b><i><code>"%tD"</code></i></b>. We can even go wild and use the two together:<br />
<br />
In Java:<br />
<pre class="prettyprint">String.format("%.2f USD at %tD", 133.7, Calendar.getInstance());</pre><br />
In Scala:<br />
<pre class="prettyprint">"%.2f USD at %tD" format (133.7, Calendar.getInstance)</pre><br />
This snippet is saying that 133.7 should be formatted as a decimal with two digits after the point, and Calendar.getInstance() - the horrific Javaism for "right now" - should be formatted as a date, not a time. What always trips me up is that the order of the values must exactly correspond to the order of the format specifiers. It's a simple task, but my tiny little brain keeps messing it up. Let's see if our good friend the Compiler can help.<br />
<br />
<span style="font-size: large;">Formatters</span><br />
The first step is to have our logic leave it's String hideout and show itself. So, instead of "%.2f", we'll say <b><code>F(2)</code></b><sup><a href="#nota1">*</a></sup>, and instead of <b><code>"%tD"</code></b> we'll say <b><code>D(T)</code></b>. <b><code>D</code></b> and <b><code>F</code></b> are now <b><code>Formatters</code></b>:<br />
<br />
<pre class="prettyprint">trait Formatter[E] {
def formatElement(e: E):String
}
case class F(precision: Int) extends Formatter[Double] {
def formatElement(number: Double) = ("%."+precision+"f") format number
}
import java.util.Calendar
abstract class DateOrTime
object T extends DateOrTime
object D extends DateOrTime
case class T(dateOrTime: DateOrTime) extends Formatter[Calendar] {
def formatElement(calendar: Calendar) = dateOrTime match {
case Time => "%tR" format calendar
case Date => "%tD" format calendar
}
}
</pre><br />
<span style="font-size: large;">Chains</span><br />
Next we tackle the issue of how to chain formats together. The best bet here is to use a composite, very similar to <a href="http://www.scala-lang.org/docu/files/api/scala/List.html">scala.List</a> <sup><a href="#nota3">***</a></sup>. We even have a <b>::</b> method to get right-associative syntax. This is how it looks like:<br />
<br />
<pre class="prettyprint">val fmt = F(2) :: T(D) :: FNil</pre><br />
And this is the actual, quite unremarkable, code:<br />
<br />
<pre class="prettyprint">trait FChain {
def :(formatter: Formatter) =
new FCons(formatter, this)
def format(elements: List[Any]):String
}
object FNil extends FChain {
def format(elements: List[Any]):String = ""
}
case class FCons(formatter: Formatter, tail: FChain) extends FChain {
def format(elements: List[Any]):String =
formatter.formatElement(elements.head) + tail.format(elements.tail)
}
</pre><br />
There is still a missing piece. Remember <b><i><code>"%.2f USD at %tD"</code></i></b>? We have no way of chaining the <b><i><code>" USD at"</code></i></b> to our formatters. This is what we want to be able to write:<br />
<br />
<pre class="prettyprint">val fmt = F(2) :: " USD at " :: T(D) :: FNil</pre><br />
The solution is simple, we overload <b>::</b> in FChain:<br />
<br />
<pre class="prettyprint">trait FChain {
...
def ::(constant: String) =
new FConstant(constant, this)
...
}
</pre><br />
and create a new type of format chain that appends the string constant:<br />
<br />
<pre class="prettyprint">case class FConstant(constant:String, tail: FChain) extends FChain {
def format(elements: List[Any]):String =
constant + tail.format(elements)
}
</pre><br />
Cool, that works. But wait; what have we gained so far? The problem was to match the types of the formatters with the types of the values, and we aren't really using types at all. The remedy, of course, is to keep track of them.<br />
<br />
<span style="font-size: large;">Cue the Types</span><br />
We want to check the types of the values passed to the <code>FChain.format()</code>, but this method currently takes a <code>List[Any]</code>, a List of anything at all. We could try to parameterize it somehow and make it take a <code>List[T]</code>, a list of some type <code>T</code>, instead. But, if we take a <code>List[T]</code>, it means all values must be of the same type <code>T</code>, and that's not what we want. For instance, in our running example we want a list of a <code>Double</code> and a <code>Calendar</code> and nothing more.<br />
<br />
So, <code>List</code> doesn't cut it. Fortunately, the great Jesper Nordenberg created an awesome library, <a href="http://www.assembla.com/wiki/show/metascala">metascala</a>, that contains an awesomest class: <code>HList</code>. It is kind of like a regular List, with a set of similar operations. But it differs in an important way: HLists "remember" the types of all members of the list. That's what the H stands for, Heterogeneous. Jesper explains how it works <a href="http://jnordenberg.blogspot.com/2008/08/hlist-in-scala.html">here</a>.<br />
<br />
We'll change FChain to remember the required type of the elements in a type member, and to require this type in the format() method:<br />
<br />
<pre class="prettyprint">trait FChain {
type Elements <: HList
...
def format(elements: Elements):String
}
</pre><code>FNil</code> is pretty trivial, it can only handle empty HLists (<code>HNil</code>): <br />
<pre class="prettyprint">object FNil extends FChain {
type Elements = HNil
def format(elements: Elements):String = ""
}
</pre><code>FCons</code> is somewhat more complicated, it is parameterized on the type of the head element, and on the type of the rest of the chain: <br />
<pre class="prettyprint">case class FCons[E, TL <: HList](formatter: Formatter[E], tail: FChain { type Elements = TL }) extends FChain {
type Elements = HCons[E, TL]
def format(elements: Elements):String =
formatter.formatElement(elements.head) + tail.format(elements.tail)
}
</pre>We also had to tighten-up the types of the constructor parameters: formatter is now <b><code>Formatter[E]</code></b> <sup><a href="#nota2">**</a></sup> — so it can format elements of type <code>E</code>, and tail is now <b><code>FChain{type Elements=TL}</code></b> — so it can format the rest of the values. The <b><code>Elements</code></b> member is where we build up our list of types. It is an HCons: a cons pair of a head type - <b>E</b> - and another HList type - <b>TL</b>. We changed how to FCons constructor parameters, so we also need to change the point where we instantiate it, in FChain: <br />
<pre class="prettyprint">trait FChain {
type Elements <: HList
...
def ::[E](formatter: Formatter[E]) =
new FCons[E, Elements](formatter, this)
...
}
</pre>Just passing along the type of the formatter and of the elements so far to FCons. FConstant has to be changed in an analogous way. This is it, now <b><code>format()</code></b> only accepts a list whose values are of the right type. Check out an interpreter session: <br />
<br />
<pre class="prettyprint">scala> (F(2) :: " USD at " :: T(D) :: FNil) format (133.7 :: Calendar.getInstance :: HNil)
res5: java.lang.String = 133.70 USD at 10/10/09
scala> (F(2) :: " USD at " :: T(D) :: FNil) format (Calendar.getInstance :: 133.7 :: HNil)
<console>:25: error: no type parameters for method ::: (v: T)metascala.HLists.HCons[T,metascala.HLists.HCons[Double,metascala.HLists.HNil]] exist so that it can be applied to arguments (java.util.Calendar)
--- because ---
no unique instantiation of type variable T could be found
(F(2) :: " USD at " :: T(D) :: FNil) format (Calendar.getInstance :: 133.7 :: HNil)
</console></pre><br />
<span style="font-size: large;">Some random remarks</span><br />
<ul><li>The interpreter session above nicely showcases the Achilles heel of most techniques for compile-time invariant verification: the error messages are basically impenetrable.</li>
<li>A related issue with this kind of metaprogramming is that it's just plain hard. The code in this post looks pretty simple (compared with, say, JimMcBeath's <a href="http://jim-mcbeath.blogspot.com/2009/09/type-safe-builder-in-scala-using-church.html">beautiful builders</a>), but it took me days of fiddling around with metascala to find an adequate implementation.</li>
<li>Take the above two points together and it's clear that we are talking about a niche technique. Powerful, but not for everyday coding.</li>
<li>Since I've mentioned the word coding, the FChain structure showed here looks like a partial encoding of a stack-automaton. Stack automata can represent context-free grammars, if I remember my college classes correctly. That said, I don't see any particular use for this tidbit of information.</li>
<li>Since this is random remarks section, I'll randomly remark that we can implement the whole thing without type members and refinements. Just good old <a href="http://paste.pocoo.org/show/144292/">type parameters in action</a>.</li>
<li>Since it is possible to use nothing but type parameters, and Java has type parameters, would it be possible to implement our type-safe Printf in Java? Quite possibly, a good way to start would be with Rúnar Óli's <a href="http://apocalisp.wordpress.com/2008/10/23/heterogeneous-lists-and-the-limits-of-the-java-type-system/">HLists in Java</a>. Just take care not to get cut wading through all those pointy brackets. </li>
<li>A powerful type system without type inference is useless. Quoting Benjamin Pierce: "The more interesting your types get, the less fun it is to write them down".<br />
</li>
</ul><br />
<hr/>The whole code:<br />
<pre class="prettyprint">import metascala._
import HLists._
object Printf {
trait FChain {
type Elements <: HList
def ::(constant: String) =
new FConstant[Elements](constant, this)
def ::[E](formatter: Formatter[E]) =
new FCons[E, Elements](formatter, this)
def format(elements: Elements):String
}
case class FConstant[ES <: HList](constant:String, tail: FChain { type Elements = ES }) extends FChain {
type Elements = ES
def format(elements: Elements):String =
constant + tail.format(elements)
}
object FNil extends FChain {
type Elements = HNil
def format(elements: Elements):String = ""
}
case class FCons[E, TL <: HList](formatter: Formatter[E], tail: FChain { type Elements = TL }) extends FChain {
type Elements = HCons[E, TL]
def format(elements: Elements):String =
formatter.formatElement(elements.head) + tail.format(elements.tail)
}
trait Formatter[E] {
def formatElement(e: E):String
}
case class F(precision: Int) extends Formatter[Double] {
def formatElement(number: Double) = ("%."+precision+"f") format number
}
import java.util.Calendar
abstract class DateOrTime
object T extends DateOrTime
object D extends DateOrTime
case class T(dateOrTime: DateOrTime) extends Formatter[Calendar] {
def formatElement(calendar: Calendar) = dateOrTime match {
case T => "%tR" format calendar
case D => "%tD" format calendar
}
}
}
</pre><br />
<div id="nota1">* Or F(precision=2) thanks to Scala 2.8 awesome named parameter support. <br />
</div><div id="nota2">** In fact, the previous untyped version didn't even compile, as Formatter has always been generic. Sorry for misleading you guys. <br />
</div><div id="nota3">*** If you are unfamiliar with how Scala lists are built, check out <a href="http://oldfashionedsoftware.com/2009/07/22/building-a-simple-scala-list-from-scratch/">this article</a>. <br />
</div>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com11tag:blogger.com,1999:blog-10162639.post-65846511134888740302009-09-28T03:57:00.005-03:002009-09-28T05:08:43.353-03:00Context, context, contextJoel Spolsky's <a href="http://www.joelonsoftware.com/items/2009/09/23.html">latest diatrabe</a>, and the outcry the blogosphere predictably issued, got me thinking about, well, about an old joelonsoftware article: <a href="http://www.joelonsoftware.com/articles/FiveWorlds.html">Five Worlds</a>. This one is a favorite of mine, maybe second only to the classic <a href="http://www.joelonsoftware.com/articles/LeakyAbstractions.html">The Law of Leaky Abstractions</a>. The point, in a nutshell, is that we too often forget the importance of context when discussing our trade.<br /><br />I personally believe the Agile movement induced solid progress in software development teams worldwide, but we shouldn't forget where it came from: corporate software projects. Extreme Programming was born in a Chrysler project, it doesn't get much more corporate than this. Most of the signatures under the Agile Manifesto come from consultants, and again, is there anything more corporate that consultants?<br /><br />This isn't meant to be a put-down of enterpresey work. I am myself a consultant and won't apologise for it. But it pays to look at the differences between the internal corporate projects world and the software product development world:<br /><ul><li>Corporate projects tend to be wide: lots of forms gathering data, lots of reports spitting data out, huge ugly menus. Products are usually more focused, with fewer interaction points that are backed with more sophisticated logic.</li><li>A consequence is that, while a developer for an internal corporate system might see any given screen a handful of times throughout the project, a software product developer can live inside the system almost as much as the end users (and so, catch more bugs).</li><li>Corporate systems are expected to reproduce complicated real-life behavior. Tax codes and compliance requirements come to mind. Sounds boring, but at least there are clear expectations for what the correct functioning of the software should be. Another way to put it is that in these systems, it's feasible to anticipate putative bugs. In a product, on the other hand, there could be many undesirable characteristics that are impossible to precisely specify (say we're working on a game, and level 3 should be just a notch more difficult than level 2 but still much easier that level 4 - how would you precisely specify that?).</li><li>First impressions are crucial for a product. A 1.0 dud can kill a startup - just think of Cuil. Not only it must work, it must be polished, discoverable and pretty. The incentive framework for internal products is very different; as long as the team delivers anything at all, even if almost useless, it's often possible to change course and steer the project towards the actual needs.</li></ul>Reading these points, it seems that I'm justifying a lower standard of code quality in product development. I'm not. TDD really does allow you to go faster, I can't even fathom what would be like to code without refactoring every few seconds, and all the old sayings about how we spend much more time reading that writing code are true, regardless of how crucial is that we reach that 1.0 milestone.<br /><br />I was desperatly trying to avoid this cliché, but I just couldn't resist. In the end, we should really try to learn from each other. Agile teams should spend more time thinking about the people who will live in their systems day-in-day-out, and product devs might have a thing or two to learn from the fast pace of a pair TDD-ing away.Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com6tag:blogger.com,1999:blog-10162639.post-6165666984192622642009-03-07T18:45:00.006-03:002009-03-09T21:24:13.776-03:00Software<blockquote><br /><span style="font-style: italic;">This is my Quality is Dead hypothesis: a pleasing level of quality for end users has become too hard to achieve while demand for it has simultaneously evaporated and penalties for not achieving it are weak. The entropy caused by mindboggling change and innovation in computing has reached a point where it is extremely expensive to use traditional development and testing methods to create reasonably good products and get a reasonable return on investment. Meanwhile, user expectations of quality have been beaten out of them. When I say quality is dead, I don’t mean that it’s dying, or that it’s under threat. What I mean is that we have collectively– and rationally– ceased to expect that software normally works well, even under normal conditions. Furthermore, there is very little any one user can do about it.</span><br /></blockquote><p style="text-align: right;"><a href="http://www.satisfice.com/blog/archives/224">James Bach</a></p><br /><blockquote style="font-style: italic;">If you look at engineering or maths, we've been doing that for thousands of years, so we now know how to build a building and make it solid. With code, we've been doing computer science for 70-75 years, so we are still scratching the surface - we don't have a real theory or like physics, where they have a good foundation. We have the Turing machine that doesn't really reflect distributed computation. The lambda calculus captures certain parts, then there is a lot of process algebra, but it's not yet clear that we really have understood everything, which I think is fantastic, because that means there is opportunity to discover new things.</blockquote><p style="text-align: right;"><a href="http://www.infoq.com/interviews/LINQ-Erik-Meijer">Erik Meijer</a></p><br /><blockquote style="font-style: italic;">Much of what is wrong about our field is that many of the ideas that happened before 1975 are still the current paradigm. He <span>[Alan Kay]</span> has a strong feeling that our field has been mired for some time, but because of Moore’s law, there are plenty of things to work on. The commercialization of personal computing was a tremendous distraction to our field and we haven’t, and may not, recover from it.<br /><br />One of Alan’s undergraduate degrees is in molecular biology. He can’t understand it anymore despite having tried to review new developments every few years. That’s not true in computer science. The basics are still mostly the same. If you go to most campuses, there is a single computer science department and the first course in computer science is almost indistinguishable from the first course in 1960. They’re about data structures and algorithms despite the fact that almost nothing exciting about computing today has to do with data structures and algorithms.</blockquote><p style="text-align: right;"><a href="http://www.windley.com/archives/2006/02/alan_kay_is_com.shtml">Alan Kay (paraphrased by Phil Windley)</a></p><p style="text-align: right;">[Actually, check the comments for Alan's clarification].<br /></p>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com12tag:blogger.com,1999:blog-10162639.post-60211359266680092742008-07-17T02:59:00.002-03:002009-01-27T01:46:33.168-02:00Comments on Comments on the Previous post<div xmlns='http://www.w3.org/1999/xhtml'><ul><li>Henry Ware <a href='http://www.nabble.com/Re:--scala-user--Phantom-types-td18372260.html#a18373739'>suggested</a> a modification to the <a href='http://snippets.dzone.com/posts/show/5741'>builder with abstract members</a> removing a lot of the boilerplate. Incidentally, this is a nice illustration of how nested types can be <a href='http://michaelfeathers.typepad.com/michael_feathers_blog/2008/06/are-nested-clas.html'>put to a good use</a> in Scala.</li><li>Justin <a href='http://blog.rafaelferreira.net/2008/07/type-safe-builder-pattern-in-scala.html?showComment=1215638460000#c1427852678424330516'>ported</a> the code to Haskell, which was very cool.</li><li>A couple of commenters suggested that languages with support for default parameter values (like Python and Groovy) don't need elaborate constructs such as the builder pattern. There are two ways to respond. One is to remind that the intent of the pattern, specially as originally described in the GoF book, has little to do with optional data. The other is to acknowledge that I probably put too much emphasis on this issue and forgot to mention a very common idiom for building objects in Scala: just declare mandatory "parameters" as abstract vals and optional ones as concrete vals with default values, like so:<br/><pre class='prettyprint'>abstract class OrderOfScotch {<br/> val brand:String<br/> val mode:Preparation<br/> val isDouble:Boolean <br/> val glass:Option[Glass] = None<br/>}</pre><br/>And to instantiate:<br/><pre class='prettyprint'>val myDose = new OrderOfScotch {val brand = "Bobby Runner"; val mode = OnTheRocks; val isDouble = false}</pre></li><li>I guess that's it. Thanks y'all.<br/></li></ul></div>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com15tag:blogger.com,1999:blog-10162639.post-17886548726024009402008-07-09T03:42:00.006-03:002008-07-09T19:02:52.564-03:00Type-safe Builder Pattern in Scala<i>The Builder Pattern is an increasingly popular idiom for object creation. Traditionally, one of it's shortcomings in relation to simple constructors is that clients can try to build incomplete objects, by omitting mandatory parameters, and that error will only show up in runtime. I'll show how to make this verification statically in Scala.</i><br /><br /><br />So, let's say you want to order a shot of scotch. You'll need to ask for a few things: the brand of the whiskey, how it should be prepared (neat, on the rocks or with water) and if you want it doubled. Unless, of course, you are a pretentious snob, in that case you'll probably also ask for a specific kind of glass, brand and temperature of the water and who knows what else. Limiting the snobbery to the kind of glass, here is one way to represent the order in scala.<br /><pre class='prettyprint'>sealed abstract class Preparation /* This is one way of coding enum-like things in scala */<br />case object Neat extends Preparation<br />case object OnTheRocks extends Preparation<br />case object WithWater extends Preparation<br /><br />sealed abstract class Glass<br />case object Short extends Glass<br />case object Tall extends Glass<br />case object Tulip extends Glass<br /><br />case class OrderOfScotch(val brand:String, val mode:Preparation, val isDouble:Boolean, val glass:Option[Glass])</pre><br />A client can instantiate their orders like this:<br /><pre class='prettyprint'>val normal = new OrderOfScotch("Bobby Runner", OnTheRocks, false, None)<br />val snooty = new OrderOfScotch("Glenfoobar", WithWater, false, Option(Tulip));</pre><br />Note that if the client doesn't want to specify the glass he can pass None as an argument, since the parameter was declared as Option[Glass]. This isn't so bad, but it can get annoying to remember the position of each argument, specially if many are optional. There are two traditional ways to circumvent this problem — define telescoping constructors or set the values post-instantiation with accessors — but both idioms have their shortcomings. Recently, in Java circles, it has become popular to use a variant of the <abbr title='Gang of Four'>GoF</abbr> Builder pattern. So popular that it is Item 2 in the second edition of Joshua Bloch's <a href='http://www.amazon.com/gp/redirect.html?ie=UTF8&location=http%3A%2F%2Fwww.amazon.com%2FEffective-Java-2nd-Joshua-Bloch%2Fdp%2F0321356683%2F&tag=rafaeldivagan-20&linkCode=ur2&camp=1789&creative=9325'>Effective Java</a><img width='1' height='1' border='0' style='border: medium none ! important; margin: 0px ! important;' alt='' src='http://www.assoc-amazon.com/e/ir?t=rafaeldivagan-20&l=ur2&o=1'/>. A Java-ish implementation in Scala would be something like this:<br /><pre class='prettyprint'>class ScotchBuilder {<br /> private var theBrand:Option[String] = None<br /> private var theMode:Option[Preparation] = None<br /> private var theDoubleStatus:Option[Boolean] = None<br /> private var theGlass:Option[Glass] = None<br /><br /> def withBrand(b:Brand) = {theBrand = Some(b); this} /* returning <b>this</b> to enable method chaining. */<br /> def withMode(p:Preparation) = {theMode = Some(p); this}<br /> def isDouble(b:Boolean) = {theDoubleStatus = some(b); this}<br /> def withGlass(g:Glass) = {theGlass = Some(g); this}<br /><br /> def build() = new OrderOfScotch(theBrand.get, theMode.get, theDoubleStatus.get, theGlass);<br />}</pre><br />This is almost self-explanatory, the only caveat is that verifying the presence of non-optional parameters (everything but the glass) is done by the Option.get method. If a field is still None, an exception will be thrown. Keep this in mind, we'll come back to it later.<br /><br />The var keyword prefixing the fields means that they are mutable references. Indeed, we mutate them in each of the building methods. We can make it more functional in the traditional way:<br /><pre class='prettyprint'>object BuilderPattern {<br /> class ScotchBuilder(theBrand:Option[String], theMode:Option[Preparation], theDoubleStatus:Option[Boolean], theGlass:Option[Glass]) {<br /> def withBrand(b:String) = new ScotchBuilder(Some(b), theMode, theDoubleStatus, theGlass)<br /> def withMode(p:Preparation) = new ScotchBuilder(theBrand, Some(p), theDoubleStatus, theGlass)<br /> def isDouble(b:Boolean) = new ScotchBuilder(theBrand, theMode, Some(b), theGlass)<br /> def withGlass(g:Glass) = new ScotchBuilder(theBrand, theMode, theDoubleStatus, Some(g))<br /><br /> def build() = new OrderOfScotch(theBrand.get, theMode.get, theDoubleStatus.get, theGlass);<br /> }<br /><br /> def builder = new ScotchBuilder(None, None, None, None)<br />}</pre><br />The scotch builder is now enclosed in an object, this is standard practice in Scala to isolate modules. In this enclosing object we also find a factory method for the builder, which should be called like so:<br /><pre class='prettyprint'>import BuilderPattern._<br /><br />val order = builder withBrand("Takes") isDouble(true) withGlass(Tall) withMode(OnTheRocks) build()</pre><br />Looking back at the ScotchBuilder class and it's implementation, it might seem that we just moved the huge constructor mess from one place (clients) to another (the builder). And yes, that is exactly what we did. I guess that is the very definition of encapsulation, sweeping the dirt under the rug and keeping the rug well hidden. On the other hand, we haven't gained all the much from this "functionalization" of our builder; the main failure mode is still present. That is, having clients forget to set mandatory information, which is a particular concern since we obviously can't fully trust the sobriety of said clients<a href='#n1'>*</a>. Ideally the type system would prevent this problem, refusing to typecheck a call to build() when any of the non-optional fields aren't set. That's what we are going to do now.<br /><br />One technique, which is very common in Java fluent interfaces, would be to write an interface for each intermediate state containing only applicable methods. So we would begin with an interface VoidBuilder having all our withFoo() methods but no build() method, and a call to, say, withMode() would return another interface (maybe BuilderWithMode), and so on, until we call the last withBar() for a mandatory Bar, which would return an interface that finally has the build() method. This technique works, but it requires a metric buttload of code — for <b>n</b> mandatory fields <b>2<sup>n</sup></b> interfaces should be created. This could be automated via code generation, but there is no need for such heroic efforts, we can make the typesystem work in our favor by applying some generics magic. First, we define two abstract classes:<br /><pre class='prettyprint'>abstract class TRUE<br />abstract class FALSE<br /></pre><br />Then, for each mandatory field, we add to our builder a generic parameter:<br /><pre class='prettyprint'>class ScotchBuilder[HB, HM, HD](val theBrand:Option[String], val theMode:Option[Preparation], val theDoubleStatus:Option[Boolean], val theGlass:Option[Glass]) {<br /><br /> /* ... body of the scotch builder .... */<br /><br />}</pre><br />Next, have each withFoo method pass ScotchBuilder's type parameters as type arguments to the builders they return. But, and here is where the magic happens, there is a twist on the methods for mandatory parameters: they should, for their respective generic parameters, pass instead TRUE:<br /><pre class='prettyprint'>class ScotchBuilder[HB, HM, HD](val theBrand:Option[String], val theMode:Option[Preparation], val theDoubleStatus:Option[Boolean], val theGlass:Option[Glass]) {<br /> def withBrand(b:String) = <br /> new ScotchBuilder[TRUE, HM, HD](Some(b), theMode, theDoubleStatus, theGlass)<br /><br /> def withMode(p:Preparation) = <br /> new ScotchBuilder[HB, TRUE, HD](theBrand, Some(p), theDoubleStatus, theGlass)<br /><br /> def isDouble(b:Boolean) = <br /> new ScotchBuilder[HB, HM, TRUE](theBrand, theMode, Some(b), theGlass)<br /><br /> def withGlass(g:Glass) = <br /> new ScotchBuilder[HB, HM, HD](theBrand, theMode, theDoubleStatus, Some(g))<br />}</pre><br />The second part of the magic act is to apply the world famous <a href='http://www.artima.com/weblogs/viewpost.jsp?thread=179766'>pimp-my-library</a> idiom and move the build() method to an implicitly created class, which will be anonymous for the sake of simplicity:<br /><pre class='prettyprint'>implicit def enableBuild(builder:ScotchBuilder[TRUE, TRUE, TRUE]) = new {<br /> def build() = <br /> new OrderOfScotch(builder.theBrand.get, builder.theMode.get, builder.theDoubleStatus.get, builder.theGlass);<br />}</pre><br />Note the type of the parameter for this implicit method: <b>ScotchBuilder[TRUE, TRUE, TRUE]</b>. This is the point where we "declare" that we can only build an object if all the mandatory parameters are specified. And it really works:<br /><pre>scala> builder withBrand("hi") isDouble(false) withGlass(Tall) withMode(Neat) build()<br />res5: BuilderPattern.OrderOfScotch = OrderOfScotch(hi,Neat,false,Some(Tall))<br /><br />scala> builder withBrand("hi") isDouble(false) withGlass(Tall) build() <br /><console>:9: error: value build is not a member of BuilderPattern.ScotchBuilder[BuilderPattern.TRUE,BuilderPattern.FALSE,BuilderPattern.TRUE]<br /> builder withBrand("hi") isDouble(false) withGlass(Tall) build()</pre><br />So, we achieved our goal (see the full listing below). If you are worried about the enormous parameter lists inside the builder, I've posted <a href="http://snippets.dzone.com/posts/show/5741">here</a> an alternative implementation with abstract members instead. It is more verbose, but also cleaner.<br /><br />Now, remember those abstract classes TRUE and FALSE? We never did subclass or instantiate them at any point. If I'm not mistaken, this is an idiom named Phantom Types, commonly used in the ML family of programming languages. Even though this application of phantom types is fairly trivial, we can glimpse at the power of the mechanism. We have, in fact, codified all 2<sup>n</sup> states (one for each combination of mandatory fields) as types. ScotchBuilder's subtyping relation forms a lattice structure and the <b>enableBuild()</b> implicit method requires the supremum of the poset (namely, <b>ScotchBuilder[TRUE, TRUE, TRUE]</b>). If the domain requires, we could specify any other point in the lattice — say we can doll-out a dose of any cheap whiskey if the brand is not given, this point is represented by <b>ScotchBuilder[_, TRUE, TRUE]</b>. And we can even escape the lattice structure by using Scala inheritance. Of course, I didn't invent any of this; the idea came to me in <a href='http://scholar.google.com.br/scholar?cluster=15738227024751313970'>this</a> article by Matthew Fluet and Riccardo Pucella, where they use phantom types to encode subtyping in a language that lacks it.<br /><br /><hr/><br /><pre class="prettyprint">object BuilderPattern {<br /> sealed abstract class Preparation<br /> case object Neat extends Preparation<br /> case object OnTheRocks extends Preparation<br /> case object WithWater extends Preparation<br /><br /> sealed abstract class Glass<br /> case object Short extends Glass<br /> case object Tall extends Glass<br /> case object Tulip extends Glass<br /><br /> case class OrderOfScotch(val brand:String, val mode:Preparation, val isDouble:Boolean, val glass:Option[Glass])<br /><br /> abstract class TRUE<br /> abstract class FALSE<br /><br /> class ScotchBuilder<br /> [HB, HM, HD]<br /> (val theBrand:Option[String], val theMode:Option[Preparation], val theDoubleStatus:Option[Boolean], val theGlass:Option[Glass]) {<br /> def withBrand(b:String) = <br /> new ScotchBuilder[TRUE, HM, HD](Some(b), theMode, theDoubleStatus, theGlass)<br /><br /> def withMode(p:Preparation) = <br /> new ScotchBuilder[HB, TRUE, HD](theBrand, Some(p), theDoubleStatus, theGlass)<br /><br /> def isDouble(b:Boolean) = <br /> new ScotchBuilder[HB, HM, TRUE](theBrand, theMode, Some(b), theGlass)<br /><br /> def withGlass(g:Glass) = new ScotchBuilder[HB, HM, HD](theBrand, theMode, theDoubleStatus, Some(g))<br /> }<br /><br /> implicit def enableBuild(builder:ScotchBuilder[TRUE, TRUE, TRUE]) = new {<br /> def build() = <br /> new OrderOfScotch(builder.theBrand.get, builder.theMode.get, builder.theDoubleStatus.get, builder.theGlass);<br /> }<br /><br /> def builder = new ScotchBuilder[FALSE, FALSE, FALSE](None, None, None, None)<br />}<br /></pre><br /><br /><br /><p id='n1'>* Did you hear that noise? It's the sound of my metaphor shattering into a million pieces</p><br /><br /><i>EDIT 2008-07-09 at 19h00min: Added introductory paragraph.</i>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com454tag:blogger.com,1999:blog-10162639.post-72367479028567478832008-04-08T04:52:00.010-03:002008-12-11T16:55:04.263-02:00A couple of interesting DSLsIt may not yet be an industry tsunami, but there certainly is a growing wave of interest in Domain Specific Languages. As <a href="http://lambda-the-ultimate.org/node/2302">often happens</a> when thinking about programming language design, there appears to be an excessive concern with syntax and little talk of semantics. Dave Thomas <a href="http://pragdave.blogs.pragprog.com/pragdave/2008/03/the-language-in.html">points out</a> 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.<br /><br /><br /><span style="font-weight: bold;font-size:180%;" >Kay</span><br />Alan Kay is one of the giants in our little <a href="http://www.laputan.org/catfish/archives/000199.html">science</a>, 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 <a href="http://www.vpri.org/pdf/steps_TR-2007-008.pdf">report</a>.<br /><span style="font-style:italic;"><blockquote><br />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.<br /></blockquote></span><br />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:<br /><br /><div style="overflow:auto"><pre><br />+-------------+-------------+-------------------------+----------+----------------------------------------+<br />| 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 |<br />+-------------+-------------+-------------------------+----------+----------------------------------------+<br />| version | headerSize | typeOfService | length |<br />+-------------+-------------+-------------------------+----------+----------------------------------------+<br />| identification | flags | offset |<br />+---------------------------+-------------------------+----------+----------------------------------------+<br />| timeToLive | protocol | checksum |<br />+---------------------------+-------------------------+---------------------------------------------------+<br />| sourceAddress |<br />+---------------------------------------------------------------------------------------------------------+<br />| destinationAddress |<br />+---------------------------------------------------------------------------------------------------------+<br /></pre></div><br /><br />Most implementations just <a href="http://src.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/common/inet/ip/ip.c">hardcode</a> 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:<br /><br /><div style="overflow:auto"><pre><br /> { structure-diagram }<br />+-------------+-------------+-------------------------+----------+----------------------------------------+<br />| 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 |<br />+-------------+-------------+-------------------------+----------+----------------------------------------+<br />| version | headerSize | typeOfService | length |<br />+-------------+-------------+-------------------------+----------+----------------------------------------+<br />| identification | flags | offset |<br />+---------------------------+-------------------------+----------+----------------------------------------+<br />| timeToLive | protocol | checksum |<br />+---------------------------+-------------------------+---------------------------------------------------+<br />| sourceAddress |<br />+---------------------------------------------------------------------------------------------------------+<br />| destinationAddress |<br />+---------------------------------------------------------------------------------------------------------+<br /> ip -- Internet Protocol packet header [RFC 791]<br /><br /></pre></div><br /><br />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 <a href="http://www.cs.ucla.edu/%7Eawarth/ometa/">OMeta</a> 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...<br /><br />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:<br /><br /><div style="overflow:auto"><pre><br />['{ svc = &->(svc? [self peek])<br /> syn = &->(syn? [self peek]) . ->(out ack-syn -1 (+ sequenceNumber 1) (+ TCP_ACK TCP_SYN) 0)<br /> req = &->(req? [self peek]) . ->(out ack-psh-fin 0 (+ sequenceNumber datalen (fin-len tcp))<br /> (+ TCP_ACK TCP_PSH TCP_FIN)<br /> (up destinationPort dev ip tcp<br /> (tcp-payload tcp) datalen))<br /> ack = &->(ack? [self peek]) . ->(out ack acknowledgementNumber<br /> (+ sequenceNumber datalen (fin-len tcp))<br /> TCP_ACK 0)<br /> ;<br /> ( svc (syn | req | ack | .) | . ->(out ack-rst acknowledgementNumber<br /> (+ sequenceNumber 1)<br /> (+ TCP_ACK TCP_RST) 0)<br /> ) *<br /> } < [NetworkPseudoInterface tunnel: '"/dev/tun0" from: '"10.0.0.1" to: '"10.0.0.2"]]<br /><br /></pre></div><br /><br />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 <a href="http://en.wikipedia.org/wiki/Parsing_expression_grammar">Parsing Expression Grammars</a>. 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 <a href="http://en.wikipedia.org/wiki/Procrustes">procrustean</a> effort of trying to shoehorn "natural language" text into a general purpose programming language.<br /><br /><br /><span style="font-weight: bold;font-size:180%;" >Pierce</span><br />Now let's turn our attention to a different kind of DSL, developed for the Harmony <a href="http://www.seas.upenn.edu/%7Eharmony/">project</a> led by Pierce at UPenn. The problem to solved <a href="http://www.cis.upenn.edu/%7Ebcpierce/papers/lenses-toplas-final.pdf">here</a> 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 <span id="xhi8"><b id="ny5r">extracting</b></span> a <span id="qi-e"><b id="joqv">view</b></span> from a set of <span id="cl96"><b id="igo8">tables</b></span>, updating it, and <span id="wyv0"><b id="w1wm">propagating</b></span> the changes back to the original tables, they <span id="p8xo"><b id="yd95">get</b></span> an <span id="s-r3"><b id="j6_b">abstract representation</b></span> from a <span id="qkl-"><b id="eg1h">concrete</b></span> one, update it (the synchronization proper), and <span id="wjjd"><b id="m:yb">putback</b></span> the modified data to the original concrete format. So, one concrete input for Mozila would be the following html-ish file:<br /><br /><div style="overflow:auto"><pre><br /><html><br /> <head> <title>Bookmarks</title> </head><br /> <body><br /> <h3>Bookmarks Folder</h3><br /> <dl><br /> <dt> <a href=\"www.google.com\"<br /> add_date=\"1032458036\">Google</a> </dt><br /> <dd><br /> <h3>Conferences Folder</h3><br /> <dl><br /> <dt> <a href=\"www.cs.luc.edu/icfp\"<br /> add_date=\"1032528670\">ICFP</a> </dt><br /> </dl><br /> </dd><br /> </dl><br /> </body><br /></html><br /></pre></div><br /><br />The abstract representation of that data is :<br /><br /><div style="overflow:auto"><pre><br />{name -> Bookmarks Folder<br /> contents -><br /> [{link -> {name -> Google<br /> url -> www.google.com}}<br /> {folder -><br /> {name -> Conferences Folder<br /> contents -><br /> [{link -><br /> {name -> ICFP<br /> url -> www.cs.luc.edu/icfp}}]}}]}<br /></pre></div><br /><br />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 <span id="t29t"><b id="b7_2">get</b></span> direction would be trivial, but the <span id="s85w"><b id="t6fj">putback </b></span>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 <span id="g663"><b id="ocu8">putback</b></span>.<br /><br />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 <span id="gmuq"><b id="gvcu">get</b></span> (from the <span id="o9q."><b id="d5om">concrete</b></span> to the <span id="n6ho"><b id="rcxh">abstract</b></span>) and one for <span id="v9ah"><b id="yw_h">putback</b></span>. A <span id="xj6_"><b id="rpgv">putback</b></span> lens takes a modifed <span id="hjzt"><b id="r.84">abstract</b></span> element <span id="j1q8"><u id="pq28">and</u></span> the original <span id="shy5"><b id="tmn0">concrete</b></span> element, mapping to an update <span id="hcur"><b id="n9wb">concrete</b></span> element.<br /><br />Rephrasing more formally, though diverging from the notation used in the paper, a lens <span id="tc56"><b id="w.in">L</b></span> would be a pair of functions <span id="l6xb"><b id="vu_-">(Lg, Lp)</b></span>. Using <span id="jaua"><b id="huu5">A</b></span> as the domain of abstract elements and <span id="dg55"><b id="v5uu">C</b></span> for the domain of the concrete elements, the functions would be defined in:<br /><br /><div id="apvp"><span id="fbsk"><b id="t3-2">Lg: C -> A</b></span><br /><span id="jj2t"><b id="zzvy">Lp: (C x A) -> C</b></span><br /><div id="v_sj" style="text-align: left;"><br />So far we haven't gained much, but the above definitions allow us to express our requirements of "information conservation" as equations:<br /><br /><span id="efp2"><b id="lrjr">Lp(Lg(c), c) = c</b></span> for all <span id="xwte"><b id="lmjy">c</b></span> in <span id="ewwa"><b id="hv1k">C</b></span><br /><span id="p2:7"><b id="mk-d">Lg(Lp(a, c)) = a</b></span> for all <span id="f.x2"><b id="mgeu">a</b></span> in <span id="h924"><b id="sr35">A</b></span> and <span id="hqoq"><b id="zv3z">c</b></span> in <span id="vhgi"><b id="ormi">C</b></span><br /></div></div><br />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):<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://3.bp.blogspot.com/_AUV7ymG1mDc/R_sxiVpAJgI/AAAAAAAAABs/53GVJm4rVDo/s1600-h/id_lens.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;" src="http://3.bp.blogspot.com/_AUV7ymG1mDc/R_sxiVpAJgI/AAAAAAAAABs/53GVJm4rVDo/s320/id_lens.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5186793861841692162" /></a><br /><br />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:<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://3.bp.blogspot.com/_AUV7ymG1mDc/R_sx-VpAJhI/AAAAAAAAAB0/37UspwUtgOY/s1600-h/map_lens.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;" src="http://3.bp.blogspot.com/_AUV7ymG1mDc/R_sx-VpAJhI/AAAAAAAAAB0/37UspwUtgOY/s320/map_lens.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5186794342878029330" /></a><br /><br />The behavior isn't complicated, <span id="yb-h"><b id="yau.">map</b></span> is parametrized by another lens <span id="fmx."><b id="vry-">l</b></span>, and just applies it to each subnode in the concrete tree for <span id="o5fg"><b id="n5:.">get</b></span>. In the putback direction, it also just applies the putback for each element in the abstract tree, relying on the assumption that <span id="z2ld"><b id="vkkn">l</b></span> behaves correctly for nodes missing in <span id="i106"><b id="k_s.">c</b></span>. 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 <span id="fous"><b id="gf.f">l</b></span>.<br /><br />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:<br /><br /><div style="overflow:auto"><pre><br />link =<br /> hoist *;<br /> hd [];<br /> hoist a;<br /> rename * name;<br /> rename href url;<br /> prune add_date {$today};<br /> wmap {name -> (hd []; hoist PCDATA)}<br /><br />folder = hoist *;<br /> xfork (*h} {name}<br /> (hoist *t;<br /> hd [];<br /> rename dl contents)<br /> wmap {name -> (hoist *;<br /> hd [];<br /> hoist PCDATA)<br /> contents -> (host *;<br /> list_map item)}<br /><br />item =<br /> wmap {dd -> folder, dt -> link};<br /> rename_if_present dd folder;<br /> rename_if_present dt link<br /><br />bookmarks =<br /> hoist html;<br /> hoist *l<br /> tl {|head --> {| * --> [ {|title --> {|* --><br /> [{|PCDATA --> Bookmarks|}]|}|}]|}|};<br /> hd [];<br /> hoist body;<br /> folder<br /></pre></div><br /><br />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.<br /><br /><br /><span style="font-size:180%;"><span style="font-weight: bold;">Wrapping up</span></span><br /><ul><li>DSL design is language design, and that involves more than just syntax.</li><li>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.</li><li>Automata and similar non-turing-complete models can be very useful in Domain Specific Languages.<br /></li><li>Sometimes it pays to develop whole new semantics for your DSL.</li><li>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 <a href="http://en.wikipedia.org/wiki/Domain_theory">domain theory</a> to prove the totality of their lens combinators.<br /></li><li>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.<br /></li><li>Have fun!</li></ul>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com18tag:blogger.com,1999:blog-10162639.post-20620802917908329182007-12-14T07:14:00.000-02:002007-12-14T07:17:47.258-02:00Semantic RamblingsThis past Tuesday I attended a talk about the Semantic Web and social networks by Sun's <a href="http://blogs.sun.com/bblfish">Henry Story</a>. I've <a href="http://blogs.sun.com/rafaelferreira/entry/bblfish_at_usp">posted</a> my impressions, mixed with some uninformed commentary about semweb in general, on my work blog.Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com7tag:blogger.com,1999:blog-10162639.post-48407038626822425822007-12-09T23:19:00.000-02:002007-12-10T00:33:32.723-02:00REST Beyond the Obvious<div id="lqt5" style="padding: 1em 0pt; text-align: center;"><a href="http://flickr.com/photos/andresv/378372229/"><img style="width: 500px; height: 375px;" src="http://docs.google.com/File?id=dd34rvt4_34gr8q45dt" /></a></div> <p style="margin-bottom: 0in;">Now that the heat of the REST vs. SOA battle seems to be dissipating, we can try to shed some light into how the choice of a resource centric design affects overall enterprise architecture. We can start by following a thought experiment. Imagine a company growing so fast the HR staff is overwhelmed by the task of forwarding all the new job openings to recruiting agencies. Our job is to automate this problem away. Using REST.</p><p style="margin-bottom: 0in;"><br /></p> <h3>The basics<br /></h3> <p style="margin-bottom: 0in;">As RESTful Web Services go, this one seems pretty simple. One resource per job opening, represented with a simple custom XML format; maybe a collection resource, listing all current openings; and possibly also a search resource, to look for openings with specific attributes. Something like this:</p><br /><div style="margin-left: 5%; margin-right: 5%;"><table style="border-color: rgb(255, 102, 0);" border="1" cellspacing="0" width="87%"> <col width="100*"> <col width="24*"> <col width="132*"> <thead> <tr valign="top"> <th width="39%"> <span style="font-size:85%;">URI Template</span> </th> <th width="9%"> <span style="font-size:85%;">Method</span> </th> <th width="52%"> <span style="font-size:85%;">Representation</span> </th> </tr> </thead> <tbody> <tr valign="top"> <td width="39%"> <span style="font-size:85%;">/job_opening/{id}</span> </td> <td width="9%"> <span style="font-size:85%;">GET</span> </td> <td width="52%"> <span style="font-size:85%;">Job Opening XML <a title="Schema" href="http://relaxng.org/" id="ufqq">Schema</a></span> </td> </tr> <tr valign="top"> <td width="39%"> <span style="font-size:85%;">/job_openings</span> </td> <td width="9%"> <span style="font-size:85%;">GET</span></td> <td width="52%"> <span style="font-size:85%;">Links to all openings as a custom schema or with <a title="XOXO" href="http://microformats.org/wiki/xoxo" id="a9yd">XOXO</a>.</span> </td> </tr> <tr> <td width="39%"><span style="font-size:85%;">/job_openings/find?{query_params}</span> </td> <td width="9%"><span style="font-size:85%;">GET</span></td> <td width="52%"><span style="font-size:85%;">Custom schema or XOXO or atom feed, all w/ <a title="Opensearch" href="http://www.opensearch.org/" id="uhzj">Opensearch</a> elements.</span> </td> </tr> </tbody></table></div> <p style="margin-bottom: 0in;">So, how do we create the job opening resources? The obvious choice would be to apply the traditional RESTful <a title="collections pattern" href="http://bitworking.org/news/restful_json" id="qc6-">collections pattern</a>: a POST to the /job_openings collection with an entity body containing the xml representation of the opening triggers the creation of a new resource, whose URL would then be returned in the <a title="RFC 2616 - Sec 14.30 - Location Header" href="http://www.w3.org/Protocols/rfc2616/rfc2616-sec14.html#sec14.30" id="wy43">location</a> header of the response.<br /></p><p style="margin-bottom: 0in;"><br /></p> <h3>Shaking things up<br /></h3><p style="margin-bottom: 0in;">But there is an alternate model: let client departments simply publish job_opening resources by themselves, on their departmental web servers. There is a vast array of options to do such a thing, none of them requiring users to write XML, of course. IT could whip up a word processor macro to convert documents to our xml format, and save them to a web server. In the MsWorld, one could use Word's XML <a title="support" href="http://blog.jonudell.net/2007/02/05/a-conversation-with-brian-jones-about-office-and-xml/" id="um1m">support</a> for inserting elements from the job_opening namespace into a document and publish it to an WebDav enabled server, maybe using Sharepoint. In the OpenOffice universe, we could just as easily save a document as <a title="OASIS OpenDocument/ISO/IEC 26300" href="http://xml.openoffice.org/" id="yax-">ODF</a>, pass it trough an xml transformation to the job_opening format, and then publish it to an Web Server. The publishing itself can be made with a number of techniques, from FTPing to a shared directory to using an Atompub client with a <a title="mod_atom: an open source project driven by Tim Bray" href="http://www.google.com/search?as_q=mod_atom&as_sitesearch=tbray.org" id="rh-n">compatible server</a> to the aforementioned WebDav protocol. A completely different, and much more complex, option would be to have the department run an instance of a custom job openings application, maybe even something similar to the “obvious choice” outlined above, but I really don't see how it could be useful.</p> <p style="margin-bottom: 0in;"><a id="x7r5" href="http://flickr.com/photos/josefstuefer/9500503/" target="_blank"><img style="margin: 1em 1em 0pt 0pt; width: 240px; height: 240px; float: left;" src="http://docs.google.com/File?id=dd34rvt4_35hhzngndm" /></a>So far, all very cute and distributed, postmodern even, but does it work? I mean, the end goal is to send all the openings info to external recruiting companies, and just throwing the resources at the internal web doesn't quite accomplish that. The missing piece of the puzzle is a simple crawler; a small piece of software that scans the web by following links and looks for resources that <a title="RFC 2616 - Sec 14.1 - Accept header" href="http://www.w3.org/Protocols/rfc2616/rfc2616-sec14.html#sec14.1" id="n_z3">accept</a> being viewed as job_openings. A side effect of most publishing options mentioned in the past paragraph is that a link is created to the newly available document in some sort of listing. Our crawler needs only to know how to get at those listings and how to parse them looking for links. If you think parsing is complicated, I urge you to think about the following code snippet: /(src|href)="(.*?)"/</p><br /><p style="margin-bottom: 0in;"><br /></p><p style="margin-bottom: 0in;"><br /></p> <h3>What If...<br /></h3> <p style="margin-bottom: 0in;">Since this is a thought experiment, we can get more, well, experimental. Let's see what could be gained from shunning XML altogether and using an HTML <a title="microformat" href="http://microformats.org/" id="x_o.">microformat</a> for the job_opening resource representations. This would expand even more the publishing options. For instance, a plain Wordpress blog, maybe already used as a bulletin board of sorts by some department, could be repurposed as a recruiting server. Another benefit would be to have every document in the system in human-readable form, not XML “human-readable”, but really human-readable. </p> <p style="margin-bottom: 0in;">Now, suppose the company decided it just wasn't growing fast enough, went ahead and bought a smaller competitor. And of course, this competitor already had an in-house recruiting application. Being of a more conservative nature, which just might explain why they weren't market leaders, their IT department built it as a traditional Web front-ed / RDBMS backed application. How do we integrate that with our REST-to-the-bone job openings system? First we note that there is no need to have the data available in real-time, after all, no company needs to hire new people by the minute. Given that, the simplest solution would probably be a periodic process (someone said cron?) that extracts the data directly from the database, transforms it to our job_opening format and shoves it in some web server. </p><br /><br /><h3>So what?<br /></h3> <p style="margin-bottom: 0in;">I can't say if this scenario were for real would I choose such a distributed approach. Maybe a quick Rails app running on a single server would better fit the bill. But that's not the point of our little exercise in architectural astronautics, we are here to think about the effects of REST's constraints to overall architecture. So, let's recap some of them:<a href="http://flickr.com/photos/rafaeldff/2098699545/"><img id="l1vb" style="margin: 1em 0pt 0pt 1em; width: 200px; height: 240px; float: right;" src="http://docs.google.com/File?id=dd34rvt4_31hqbsf6g7" /></a></p> <ul> <li><p style="margin-bottom: 0in;">The line between <i>publishing content</i> and <i>using an application</i> blurs. “Static” documents and active programs have equal footing as members of the system.<br /></p> </li><li><p style="margin-bottom: 0in;">Thanks to the uniform interface constraint, the mere definition of a data format allows for unplanned integration.</p> </li><li><p style="margin-bottom: 0in;">If we add a standard media type to the mix, we can take advantage of established infrastructure, as in the case of a blogging platform reused as a “service endpoint” simply by adoption of HTML microformats.</p> </li><li><p style="margin-bottom: 0in;">REST in HTTP encourages <a title="Excellent piece by Sean McGrath" href="http://www.itworld.com/AppDev/nlsebusiness070410/" id="tidb">pull-based architectures</a> (think of our HR crawler), which aren't all that common outside of, well, HTTP web applications</p> </li><li><p style="margin-bottom: 0in;">The very idea of a service may fade away in a network of distributed connected resources. The closest thing to a <i>service</i> in our system is the crawler, but note that it does its work autonomously, no one ever actually <i>calls</i> the service.</p></li><li>Links (aka <a title="hypermidia" href="http://www.ics.uci.edu/%7Efielding/pubs/dissertation/rest_arch_style.htm" id="g7vn">hypermidia</a>) are a crucial enabler for loosely-coupled distributed services. In some sense, everything is a <a title="service registry" href="http://www.looselycoupled.com/stories/2005/registry-infr0131.html" id="smfu">service registry</a>. </li><li><p style="margin-bottom: 0in;">One of the forgotten buzzwords of the 90's, intranet, may come to have a new meaning.</p> </li></ul>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com8tag:blogger.com,1999:blog-10162639.post-79032657577176464542007-12-02T22:38:00.000-02:002007-12-04T02:32:46.565-02:00Metaprogramming and conjuring spells<div style="text-align: right;"><span style="font-style: italic;">"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 </span><em style="font-style: italic;">programming languages</em><span style="font-style: italic;"> that prescribe the tasks we want our processes to perform."</span><br />- Abelson and Sussman — <a href="http://mitpress.mit.edu/sicp/full-text/sicp/book/node4.html">SICP</a></div><br /><br />Among the plethora of metaphors that plague our field, I find computing as incantation of spells one of the least annoying. Some <a href="http://images.google.com/images?q=James+Gosling">fellow</a> <a href="http://images.google.com/images?q=jim+gray">with</a> <a href="http://research.microsoft.com/users/lamport/">a</a> <a href="http://images.google.com/images?q=Richard+Stallman">long</a> <a href="http://homepages.cs.ncl.ac.uk/brian.randell/NATO/N1968/DIJKSTRA.html">beard</a> writes odd-looking prose that will later, through some magical process, turn <a href="http://en.wikipedia.org/wiki/Dot_com_bubble">lead into gold</a> or help vanquish some inept demon. Man, that <a href="http://en.wikipedia.org/wiki/Charmed">show</a> 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.<br /><br />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, <span style="font-style: italic;">changing the tires while the car is running metaprogramming</span>, 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 <del>wizard </del>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:<br /><pre>01 class DrunkenActress<br />02 attr_writer :blood_alcohol_level<br />03 end<br />04<br />05 shannen_doherty = DrunkenActress.new<br />06 shannen_doherty.blood_alcohol_level = 0.13<br /></pre>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.<br /><br />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).<br /><br />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 <a href="http://blogs.sun.com/tor/entry/ruby_screenshot_of_the_week20">kind of thing</a> would be impossible. Also note that recent Rails projects probably use Migrations to specify schema info in yet another static format.<br /><br />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 <a href="http://www.citeulike.org/tag/staging">staging</a>.<br /><br /><span style="font-style: italic;">[EDIT: corrected a mistake relating to the code sample]</span>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com13tag:blogger.com,1999:blog-10162639.post-1111702829112723212007-11-29T19:06:00.000-02:002007-11-29T19:10:01.813-02:00JSR-311 at USPI gave a talk about RESTful Web Services and JSR-311 at our local USPJUG meeting, the slides are available <a href="http://blogs.sun.com/rafaelferreira/entry/rest_demo">here</a> (in portuguese).Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com13tag:blogger.com,1999:blog-10162639.post-87075316812342549852007-11-14T22:03:00.000-02:002007-11-14T22:06:18.680-02:00Event "Conexão Java 2007"This past week I've attended an event called Conexão Java. I've posted my notes <a href="http://blogs.sun.com/rafaelferreira/entry/cj2007">on the other blog</a>.Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com6tag:blogger.com,1999:blog-10162639.post-80591647686284090062007-10-15T16:51:00.000-02:002007-10-15T16:55:23.015-02:00Link-blogI've setup an alternate feed that splices my <a href="http://del.icio.us/rafaeldff">bookmarks</a> from <a href="http://del.icio.us/">del.icio.us</a> with this blog's entries. You can find it <a href="http://feeds.feedburner.com/RafaelRamblingAndLinks">here</a>.Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com7tag:blogger.com,1999:blog-10162639.post-14144358473787379732007-10-13T21:58:00.000-03:002007-10-15T00:25:14.544-02:00Pondering<blockquote style="font-style: italic;">"Formal methods will never have any impact until they can be used by people that don’t understand them."</blockquote><div style="text-align: right;">Tom Melham<br /></div><br /><br /><blockquote style="font-style: italic;">"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.<br /><br />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)."<br /></blockquote><div style="text-align: right;">Steve McConnell<br /><a href="http://www.amazon.com/gp/product/0735619670?ie=UTF8&tag=rafaeldivagan-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0735619670">Code Complete, Second Edition</a><img src="http://www.assoc-amazon.com/e/ir?t=rafaeldivagan-20&l=as2&o=1&a=0735619670" alt="" style="border: medium none ! important; margin: 0px ! important;" border="0" height="1" width="1" /></div><br /><br /><blockquote style="font-style: italic;">"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."<br /></blockquote><div style="text-align: right;">Paul Graham<br /><a href="http://www.paulgraham.com/head.html">Holding a Program in One's Head</a><br /></div><br /><br /><blockquote style="font-style: italic;">"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. [...]<br /><br />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."</blockquote><div style="text-align: right;">Fred Brooks<br /><a href="http://scholar.google.com/scholar?hl=en&lr=&safe=off&cluster=9642008317513099198">No Silver Bullet</a><br /></div><br /><br /><blockquote style="font-style: italic;">"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. [...]<br /><br />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. "</blockquote><div style="text-align: right;">Ted Neward<br /><a href="http://blogs.tedneward.com/2007/09/20/Hard+Questions+About+Architects.aspx">Hard Questions About Architects</a><br /></div><br /><br /><span style="font-style: italic;"><blockquote>"The more interesting your types get, the less fun it is to write them down!"<br /></blockquote></span><div style="text-align: right;">Benjamin C. Pierce<br /><a href="http://www.cis.upenn.edu/%7Ebcpierce/papers/tng-lics2003-slides.pdf">Types and Programming Languages - The Next Generation</a><br /></div><br /><br /><blockquote><span style="font-style: italic;">"If you don’t know the difference between a group, a ring, and a field, you have no business overloading operators. </span> <p style="font-style: italic;">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."</p></blockquote><p style="font-style: italic;"></p><p style="text-align: right;">Elliotte Rusty Harold<br /><a href="http://cafe.elharo.com/java/operator-overloading/">Operator Overloading: Trickier Than it Looks</a></p><br /><br /><blockquote style="font-style: italic;">"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.<br /><br />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."<br /></blockquote><div style="text-align: right;">Joel Spolsky<br /><a href="http://www.joelonsoftware.com/articles/ThePerilsofJavaSchools.html">The Perils of JavaSchools</a><br /></div>Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com7tag:blogger.com,1999:blog-10162639.post-71229068800266843542007-10-06T03:50:00.000-03:002008-12-11T16:55:05.313-02:00Four booksAnother blog post, still no inspiration for anything creative, so lets just rehash that old bloggers' recipe of stuffing some "cultural" reviews in a post and hope it passes for content. Excited yet?<br /><br /><h4>Concepts, Techniques, and Models of Computer Programming</h4><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.amazon.com/gp/product/0262220695?ie=UTF8&tag=rafaeldivagan-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0262220695"><br /><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer;" src="http://1.bp.blogspot.com/_AUV7ymG1mDc/RwBevHMW4pI/AAAAAAAAAAs/sD_xJ2ZPYow/s320/2108ZG1TTPL._AA_SL160_.jpg" alt="" id="BLOGGER_PHOTO_ID_5116193340170625682" border="0" /></a><img src="http://www.assoc-amazon.com/e/ir?t=rafaeldivagan-20&l=as2&o=1&a=0262220695" alt="" style="border: medium none ! important; margin: 0px ! important;" border="0" height="1" width="1" />First up is Peter Van Roy's "Concepts, Techniques, and Models of Computer Programming". Don't let that big title scare you away. The book is pretty hefty in itself, but don't let that scare you either, it is a great read. But what is it about, you may ask? Well, CTM - as it is affectionately called - could sit comfortably on the "programming paradigms" shelf, alongside Sebesta and Kamin. All books that aim to take the reader through a stroll down the computing Zoo, allowing him or her to gaze in awe of the strength of higher order functions, be amused by the quirkiness of dataflow variables, marvel at the elegant logical predicates lying under a sunny...<br /><br />Ok, I took the metaphor too far, sorry about that. What I was trying to say is that CTM doesn't limit itself to enumerate paradigms accompanying each with a brief description and a couple of examples and leaving it at that. Van Roy's text goes further by discussing in reasonable depth programming techniques applicable to each <span style="font-style: italic;">computation model </span>(the authors prefer to avoid the term "paradigm") and, more that that, advising the reader on how to best integrate them.<br /><br />The technical approach that enables this leveling is to describe the models in terms of a <span style="font-style: italic;">kernel language</span> that is expanded throughout the book. Each chapter shows how the kernel language needs to be augmented to support the required features, how it is interpreted by an <span style="font-style: italic;">abstract machine</span> and what syntactic sugar can be added on top of the kernel to ease programming.<br /><br />It would not be a fair review if I didn't relate at least one negative point, but it is a minor one. I think that the approach to logic/relational programming would be more representative of the usual intent if the language was more predicate-and-fact based. Or, to put it in other words, I like the Prolog syntax better than the "Relational Oz" one. As the authors explain, both approaches are semantically equivalent in their core, so I'm nitpicking. Overall, I can safely say that I recommend this book. It is, if you pardon the cliché, an eye-opener, making it clear that the "mainstream" imperative and stateful programming model is but one of many equally significant alternatives.<br /><br /><h4>Engines of Logic</h4><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.amazon.com/gp/product/0393322297?ie=UTF8&tag=rafaeldivagan-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0393322297"><br /><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer;" src="http://4.bp.blogspot.com/_AUV7ymG1mDc/Rwg1d3MW4qI/AAAAAAAAAA0/tQkml2xCtCQ/s320/21JKCXP8WVL._AA_SL160_.jpg" alt="" id="BLOGGER_PHOTO_ID_5118399763654828706" border="0" /></a><img src="http://www.assoc-amazon.com/e/ir?t=rafaeldivagan-20&l=as2&o=1&a=0393322297" alt="" style="border: medium none ! important; margin: 0px ! important;" border="0" height="1" width="1" />If you've ever been subject to any formal instruction in computing (or "informatics" or Information Systems or whatever), you probably had to endure at least one lecture on the "history of computing", which usually amounts to a lengthy enumeration of machines. If you were particularly unlucky, it started with some blabber about the abacus back in who-the-fuck-cares AD, and it invariably went on to spend a great deal of time discussing punched cards and looms. Yeah, freaking looms! I'm sure Joseph Marie Jacquard is a swell guy and all, but is a rudimentary mechanical input system all that important in the grand scheme of things? My answer, of course, is no. As Dijkstra put it: "Computer science is as much about computers as astronomy is about telescopes". And that is why Engines of Logic is such a great little book, it seeks to give an account of the history of ideas that culminated in modern computing.<br /><br />We see how Leibnitz' utopia of a machine to automate human reasoning, up to the point of forever settling all disputes and intellectual arguments, evolved to a series of formal mathematical systems for "calculating with thoughts" (mathematical logic) by the hand of such great man as Boole, Frege, Cantor, Gödel, and others, culminating with the notion of "universal computers" and their actual realization. The book reads like a good popular science work, with amusing biographical anecdotes scattered throughout the nine chapters. Although, contrary to many works in this genre, Engines of Logic is not afraid of stating formulas and proving theorems when when deeper insight is required*. Check out a small excerpt from the chapter on David Hilbert for a sample of the lighter side of the book:<br /><span style="font-style: italic;"><blockquote>During my own graduate student days in the late 1940s, anecdotes about Göttingen in the 1920s were still being repeated from one generation of students to the next. We heard about the endless cruel pranks that Carl Ludwig Siegel played on on the hapless Bessel-Hagen, who remained ever gullible. My own favorite story was about the time that Hilbert was seen day after day in torn trousers, a source of embarrassment to many. The task of tactfully informing Hilbert of the situation was delegated to his assistant, Richard Courant. Knowing the pleasure Hilbert took in strolls in the countryside while talking mathematics, Courant invited him for a walk. Courant managed matters so that the pair walked through some thorny bushes, at which point Courant informed Hilbert that he had evidently torn his pants on one of the bushes. "Oh no," Hilbert replied, "they've been that way for weeks, but nobody notices".</blockquote></span>Also of note in the paragraph I quoted is the personal touch given at times by the author, Martin Davis. He is a theoretical computer scientist, with the distinction of being present in Princeton back in the 1950s, in the companion of chaps like John Von Neumann, Kurt Gödel, Hermann Weyl and Albert Einstein. As an author, Davis is probably best known for writing more technical books on computability and complexity. But please, make no mistake, this is emphatically not an academic textbook; it goes to great pains to clearly explain subtle concepts like Cantor's diagonal method, achieving a balance between rigor and ease that is hard to come by**.<br /><br /><h4>1984</h4><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.amazon.com/gp/product/0151010269?ie=UTF8&tag=rafaeldivagan-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0151010269"><br /><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer;" src="http://3.bp.blogspot.com/_AUV7ymG1mDc/RwhFLnMW4rI/AAAAAAAAAA8/D6u_-V_8XM4/s320/11KNYJ5S45L._AA_SL160_.jpg" alt="" id="BLOGGER_PHOTO_ID_5118417042308260530" border="0" /></a><img src="http://www.assoc-amazon.com/e/ir?t=rafaeldivagan-20&l=as2&o=1&a=0151010269" alt="" style="border: medium none ! important; margin: 0px ! important;" border="0" height="1" width="1" />It is sad that I only got around to reading this book now. "Now" meaning late 2006, as these reviews are a little bit behind schedule... Anyway, as I'm having a hard time finding worthy adjectives, I guess something I could say is that after finishing 1984 I felt utterly stunned. It is powerful and it is important, so put it on your reading list if you haven't already.<br /><br />A final observation is that the edition I'm linking to - a combined printing of Animal Farm and 1984 published by Harcourt - is cheap and pretty good. The preface is signed by Christopher Hitchens.<br /><br /><h4>Snow Crash</h4><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://www.amazon.com/gp/product/0553380958?ie=UTF8&tag=rafaeldivagan-20&linkCode=as2&camp=1789&creative=9325&creativeASIN=0553380958"><br /><img style="margin: 0pt 10px 10px 0pt; float: left; cursor: pointer;" src="http://2.bp.blogspot.com/_AUV7ymG1mDc/RwhH8XMW4sI/AAAAAAAAABE/ndBCkukG7xo/s320/21BD5J2MB5L._AA_SL160_.jpg" alt="" id="BLOGGER_PHOTO_ID_5118420078850138818" border="0" /></a><img src="http://www.assoc-amazon.com/e/ir?t=rafaeldivagan-20&l=as2&o=1&a=0553380958" alt="" style="border: medium none ! important; margin: 0px ! important;" border="0" height="1" width="1" />I'm getting lazy (well, lazier) so this will be short: good book, so-so plot, so-so characters, awesome ambiance.<br /><br /><br /><br /><br /><br /><br /><br /><br /><br />* To be fair, some of the most tricky proofs for non-crucial topics are left to end notes. Still, those notes are far easier to read than most academic mathematical tomes.<br />** Off the top of my head, I can only think of Nagel and Newman's book on Gödel's proof.Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com2tag:blogger.com,1999:blog-10162639.post-16131951095547271082007-09-03T03:14:00.000-03:002007-09-03T03:35:24.212-03:00Concurrency and the demand for computingOn my previous post I expressed some doubt with the “market” for rich internet applications. The skepticism was rooted on an observation that the demand side of the equation isn't looking so promising: what applications will emerge benefiting from those wonderful technologies?<br /><br />I find myself thinking along similar lines with regard to concurrency. For the sake of analysis, lets split the space of applications in server-based and client-based. Members of the first group basically deal with responding to requests coming over the network. This means that there is a naturally high degree of parallelism and, of course, this has been exploited for a long time. The typical scenario is some serial business application code atop a middleware platform that handles threading and I/O. This means that on the server front, the “multicore revolution” will impact little on most software development efforts. Now, desktop software developers don't have such luck – the era of surfing on Moore's Law is really over. And so what? The way I see it,* raw computing has ceased to be an important bottleneck, long gone are the days of watching a crude hourglass animation while the CPU labored away. Not that we do any less waiting by now, these days we spend our time waiting for the network.<br /><br />Anyway, maybe the concurrency boogieman is less scary than we think.<br /><br /><br />*(this is a blog, after all)Anonymoushttp://www.blogger.com/profile/03350776762967743057noreply@blogger.com6