Archive for May, 2009

Trawl for DSL Debugging Anecdotes…

May 29, 2009
I intend to send out the following message. I welcome suggestions on targets and editing.
I’m looking for some (serious) anecdotes describing debugging experiences of domain-specific language programs. In particular, I want to know about particularly thorny bugs which caused you lots of headaches. I’d like to know how you cracked the problem– what techniques/tools you used: did you ‘home in’ on the bug systematically, did the solution suddenly come to you in your sleep, etc. A VERY brief stream- of-consciousness reply (right now!) would be much much better than a carefully-worked-out story. I can then get back to you with further questions if necessary.
Motivation: For my Master’s research I will study DSL debugging. DSLs get lots of hype—from Paul Graham, Dave Thomas, Charles Simonyi, Sergey Dmitriev, the Ruby crowd and others—but debugging issues are rarely discussed. This trawl is  inspired by Marc Eisenstadt’s “Tales of Debugging from the Front Lines.” In fact the text above is ripped from his paper.

Thesis Way Forward

May 29, 2009

I’m back from ICSE, mostly recovered from jet lag and overcoming my caffeine withdrawal symptoms. It’s time to plot my Master’s thesis:

  1. Research
    1. Emulate Marc Eisenstadt’s “Tales of Debugging from The Front Lines” to try to draw in some DSL debugging stories.
    2. Get out to Toronto tech companies using DSLs (leaning heavily on Greg’s network) to interview and observe as an exploratory study so I can plot my case study.
    3. Informed by the above explorations, perform a case study of DSL debugging in practice.
  2. Learning
    1. Learn how to perform a great case study.
    2. Read more background papers in the area. I’ve got about twenty in the queue.
  3. Writing
    1. Write the background/introductory sections as I read background papers.
    2. Write the rest of the thesis as I get work done.

Climate Change Wager

May 28, 2009

Pascal’s wager:

Pascal's Wager

The environmental wager:

Environmental Wager

Notes on “Beautiful Code”

May 28, 2009

While away at ICSE I finished up Beautiful Code.

If one thing is clear, it’s that there’s no agreement among the book’s many authors what “beauty” means when applied to code. Each uses it to name the other software qualities (s)he feels are most important.

Many of the chapters used toy examples not from production. I think real production code rarely reaches the high standards of elegance we dream about.

My personal favourites:

  • Chapter 1, Kernighan: Rob Pike’s basic regular expression matcher.
  • Chapter 8, Petzold: On-the-fly code generation for the .NET virtual machine for image processing.
  • Chapter 9, Crockford: Top-down operator precedence parsing. I continue to be interested in this chapter and Vaughan Pratt’s paper that inspired it.
  • Chapter 10, Warren: Really fast bitcount.
  • Chapter 22, Cantrill: A fascinating debugging tale of Solaris’ threading code.
  • Chapter 23, Dean & Ghemawhat: MapReduce.
  • Chapter 24, Jones: Software transactional memory in Haskell.

How Software Engineers Can Help the Climate

May 22, 2009

I had a conversation with Jon after Steve’s talk yesterday. Here’s the gist of it. The disagreeable parts are my unfounded opinions. The reasoned, intelligent stuff is Jon’s.

First: Climate change is a big problem. We have many possible activities which could help. Most of them are distractions because they could never solve the big problem.

Imagine I ask you to move a handful of dirt across a garden. You would pick it up and move it with your hands.

Let’s say I ask you to move a few kilos of dirt across the garden. Then, you might move it one handful at a time. It would take all day, but it would get you there. If you were impatient, you might step back and look for new tools. Perhaps you would go out to find a shovel and move the dirt one shovelful at a time. Or maybe you would use a wheelbarrow.

What happens if I ask you to move a mountain? It is true that moving dirt one handful at a time is progress. But it’s obvious that it will never get you there. If you try to move the mountain one handful at a time, you waste your energy and time. You’ll be forced to step back and think about the problem. You couldn’t do it with a shovel. You couldn’t do it with a wheelbarrow. In fact, you couldn’t do it with any tool currently in existence.

If I asked you to move a mountain, you would need to invent entirely new tools. You would probably need to create an organization to manage the effort of designing the new tools and putting them to work.

If moving the mountain were really important, you wouldn’t want to waste any time on solutions that won’t solve the whole problem. You would want a strategy and a systematic approach. You would create a system that explores potential solutions, evaluates them, and improves them.

My first point is that the scale of the problem is so large that most proposals will be essentially useless. We need systems designed.

Steve asks, “How can we as software engineers help?”

We are specialists at managing complexity. We have techniques and notations for eliciting and modeling requirements. We architect, test and debug large systems. We create abstractions. We are systematic thinkers. Software engineering researchers are increasingly familiar with empirical approaches. We have large libraries of general approaches to problems: Branch and bound, genetic algorithms, searching, machine learning and so on.

We can apply these skills to the design of systems (or meta-systems). There are analogies between software design and organizational design. We should exploit these and apply every tool in our toolboxes to building a robust system for addressing climate change.

I don’t think this is too vague. We could start today by calling together requirements elicitation experts and mapping out requirements for climate change change. We could model the artifacts of an organization such as values documents and organizational structure and link these artifacts to the goals they’re meant to achieve. We can specialize business process models.

Climate Change Talk at ICSE

May 21, 2009

Some key takeaway’s from Steve’s talk at ICSE.

  • Climate change the biggest global crisis ever. The causes and consequences are beyond comprehension for most people. To keep things simple: It is likely that over 90% of the world’s population will die in wars and disasters caused by climate change.
  • Plastic vs. paper, light bulb choices, recycling and other such “green activities” are necessary and good, but far from sufficient. Given that each of these takes psychic energy, they are at best a feel-good distraction and at worst a dangerous and insidious form of problem avoidance.
  • Every moral person must address the problem using his or her skills.
  • Software engineers analyze and build systems. We must apply our skills to climate change.

A man from the UK proposed that ICSE accept only papers that directly address the intersection of software engineering and climate change. This is ridiculous, but the political changes that are necessary to avoid disaster sound even more ridiculous.

ANTLR: Buyer beware

May 13, 2009

The author of ANTLR, Terence Parr, is a professor at the University of San Francisco and is the inventor of the LL(*) parsing strategy.

This might make you think that ANTLR rests on the same academic foundations as many other tools created in universities and given scary names like “LL(*) Parsing Strategy.” Not true.

From “The Definitive ANTLR Reference”:

In particular, Part III provides the only thorough explanation available anywhere of ANTLR’s LL(*) parsing strategy.

Read: There are few academic publications on ANTLR and seemingly none on its underlying technology.

This isn’t normally a problem. Most useful software is not built on academic foundations. However, ANTLR is positioned more than most to look “academic”. It’s not.

Readings in DSLs, Maintenance and Misc.

May 12, 2009

Warning: Many links are PDF.

ANTLR: A predicated-LL(k) parser generator.

An introduction to ANTLR. Pragprog is explicitly positioning ANTLR to be a tool of choice for the coming wave of mainstream DSL creation.

One thing I like about Lex and Yacc is that, given the Dragon book and a couple weeks, I could recreate most of their functionality. So if I wanted a Yacc written in Javascript or Ruby, I could make one. The principles are clearly laid out. I’d like to see a thorough exposition of the techniques and ideas underlying ANTLR.

SWYN: A visual representation for regular expressions.
SWYN is a system for constructing regular expressions by example.

Anecdotal claim of difficulty of comprehending regular expressions from a Cognitive Dimensions perspective. Mentions: Users have no clear mental model of the expression evaluator. Experiment comparing several alternative representations of regular expressions. Notation has a large effect on performance.

The perils and pitfalls of mining SourceForge

A useful collection of pragmatic tips on how to mine a web site like SourceForge, as well as practical notes to consider about the validity of mining SourceForge. It is not representative of software projects, so the paper warns against making that claim.

Supporting the DSL spectrum

A review of DSL approaches including XML files configuration files, Monadic parsers, small compilers built with tools such as Lex and YACC, Excel and Access, a commercial Powerpoint-based system, and embedded languages.

Anecdotal claim of 50:1 program length improvement for a military DSL project.

Weaving a debugging aspect into domain-specific language grammars

Grammar-driven generation of domain-specific language debuggers

Debugging domain-specific languages in eclipse

I group these three papers together because they seem to be a project of the common authors. An approach to DSL construction in which debugging code is woven into the parser using aspect-oriented programming, or the parser is explicitly given instruments to facilitate debugging. An Eclipse plugin consumes the debugger info to allow DSL-level debugging. Toy example of a procedural DSL for demonstration. No empirical evaluation.

Using this same framework, these researchers also generate unit testing tools and they’re working on profilers.

Domain-specific languages in software development–and the relation to partial evaluation

Early chapters of his PhD thesis include a thorough and balanced review of the field of DSLs.

Call for empirical studies on DSLs.

Little Languages: Little Maintenance?

A high-level description of a DSL project for financial engineering with extensive discussion of the thoughts that went into it as well as the tools used for implementation. Intuitive arguments that DSLs should increase maintainability along dimensions from previous literature. So, a claim that DSLs improve maintainability.

Call for empirical data collection:

“Collection of empirical data concerning maintenance costs in systems built using domain-specific languages, following, e.g., the maintenance metrics as proposed by Grady (1987).”

Domain-specific languages: An annotated bibliography

A comprehensive survey of the field of DSLs. Only two mentions of maintainability. (I note these two papers later below.) Their lab seems to be maintaining the survey, so there is a more recent unpublished version online.

The next 700 programming languages

This is an CACM paper from 1966.

Landin proposes a family of languages built on a common foundation of an Abstract Syntax Tree (and underlying semantics and abstract machine) with different resultant syntaxes. It includes a mention of the desire to customize programming languages to problem domains. As such it might be among the first published mentions of the idea of DSLs.

The discussion section is actually a transcript of a discussion between computer scientists! In it they debate, among other things:

  • Semantic indentation (We are still arguing about this over Python!)
  • Declarative languages, their utility and role, and whether to embed them in more general languages
  • Tail recursion before it was called tail recursion
  • Function currying before it was called currying
  • The difficulties caused by state for program transformation
  • The frustration of implicitly specifying sequencing in imperative languages. Matrix multiplication as an inherently parallelizable problem they cannot parallelize!

A software engineering experiment in software component generation

“During the post-experiment debriefing, however, the subjects’ answers to questions about ease of error location were not consistent with this data. Subjectively, only two of the four subjects stated that it was easier to locate errors in [the DSL]. In particular, the [DSL Compiler]’s error messages were poor, which impeded location of syntactic errors. For the [general purpose language] version, the error messages were good and the use of the Ada debugger allowed tracing of problems.”

Despite a small sample of four developers, the authors empirically demonstrate a high-confidence 3x productivity improvement and 2x reliability improvement for DSL use versus a general purpose language equivalent. Really nice exposition.

“For the [DSL], a minor extension to the [DSL language] was sufficient to encompass the out-of-scope problem. However, this extension could not be provided by the subjects themselves; it required the expertise of the OGI research team who designed and implemented the [DSL language].

Extension of the [GPL equivalent] was partially successful in handling the nine problems encountered. Extensibility was gained through the Ada programming ability of the subjects that allowed them to produce new code templates. However, in the majority of instances, extensibility problems were handled not by writing new templates, but by finding workarounds or accepting partial solutions.”

KHEPERA: A system for rapid implementation of domain specific languages

Khepera is a source-to-source compiler construction framework that carefully tracks AST node provenance through transformations, to allow DSL-level debugging of the end-product. Disadvantage: Must use Khepera to make your DSL!

Measuring and managing software maintenance

A fluffy high-level view of HP’s metrics and software quality improvement programs as of 1987.

It turns out it is far easier to type ‘—‘ and a newline than it is to post a whole new blog post. There is a reason for lightweight blogging applications! It is shocking that even the delightful WordPress is too heavyweight for some tasks.

My BibTeX Trick

May 12, 2009
@article {citation-needed,
title={{Citation Needed: A To Do Item}},
author={Del. A. Procrast}

Notes on “Program Slice Metrics and Their Potential Role in DSL Design”

May 11, 2009

Program Slice Metrics and Their Potential Role in DSL Design: Steve Counsell, Tracy Hall, David Bowes, Sue Black

They said the words “Slice-based DSL” and I nearly fell down.

Don’t bother clicking through, the paper is actually incoherent. But what a good choice of topic!

A Parable for Graduate Students

May 11, 2009

Via Igor: A Parable for Graduate Students

Thesis-hunting through time

May 11, 2009

I find it interesting that, over the course of my readings and idea-generation to find a thesis topic, I have gradually, inevitably and finally converged on topics of current modern research.

Notes on “Slice-Based Cohesion Metrics and Software Intervention”

May 11, 2009

“Slice-Based Cohesion Metrics and Software Intervention”: Timothy M. Meyers, David Binkley

The authors applied CodeSurfer-based slicing to a large code base. According to the authors, slice-based code metrics successfully quantify code quality. Several metrics are provided:

  1. Tightness: Number of statements in every slice
  2. MinCoverage: Ratio of smallest slice length to module length
  3. Coverage: Ratio of length of slices to length of the entire module
  4. MaxCoverage: Ratio of largest slice length to module length
  5. Overlap: How many statements in a slice are only in that slice

Apparently this work was not possible in the past because no slicing tool properly handled all of C. It’s a shame that the only “good-enough” tool is costly. I am thinking I would like to get an academic license to play with.

“It is believed that smaller intraprocedural slice size indicates a more modular design and thus higher code quality; a formal investigation of this conjecture is left as future work.” Lately I am in love with “future work” statements.

Of interest for my DB2 days: “The above data suggests that slice-based metrics have the potential to quantify the deterioration in cohesion that a program often undergoes as it ages.”

I’ve read through this paper twice and I don’t see where they empirically support their claim that the metrics correlate with quality. I think the argument is that higher cohesion implies higher quality, and on an intuitive level the metrics directly measure cohesion.

The State of ESE

May 10, 2009

Let me get this straight:

  1. We are not able to systematically get requirements right.
  2. We are not able to systematically get estimation right.
  3. We have completely standardized on an diagramming notation that doesn’t address the real needs of diagram users. Accordingly no one uses it.
  4. A large proportion of software engineering research is poured into the general area of formal methods. Yet, the ROI on formal methods is not known to be positive in general or in any specific case.
  5. Debugging is the greatest time sink in any programming activity and yet nearly no curricula contain a systematic debugging course.
  6. We have no agreed notion of the populations of
    1. software engineers,
    2. software engineering students,
    3. software engineering problems,
    4. or of software engineering environments. Therefore we cannot draw representative samples of any of these.
  7. We have no standardized (valid, reliable) constructs for measuring software engineer skill on any dimension whatsoever.
  8. The greatest general productivity improvements in the real world have been attributed to successively higher-level programming languages, yet programming language theory had nearly no influence on the most important programming language of all time (C). Modern programming language theory has had next-to-no influence on the most influential programming languages of this generation (Ruby, Python, PHP).
  9. In sum, we have no knowledge whatsoever of transferability of software engineering research into practice.

And yet, despite these failings, software “out there” has managed to take over the world. Without “us.”


Notes on “Comments on “Formal methods application: an empirical tale of software development””

May 10, 2009

Comments on “Formal methods application: an empirical tale of software development made me happy. I love a good academic smackdown. It’s an art form.

One thing Berry & Tichy didn’t mention (possibly due to timing) was that Sobel’s “research” clearly violated some of the ethical principles laid out in Ethical Issues in Empirical Studies of Software Engineering.

And yes, Sobel’s project was bad enough that it deserves scare quotes around “research.” Ann E. Kelley Sobel: Dogmatic pseudoscience + Ethics violation FAIL.

(I really, really shouldn’t write these things until I can demonstrate I’m capable of doing better. But it’s just so much fun.)