Lambda the Ultimate

By comparing three versions of the memo (unsigned, but believed written by Irv Ziller) “Proposed Specifications for FORTRAN II for the 704″, dated August 28, September 25, and November 18, 1957, you can watch the design of the subroutine feature of FORTRAN II unfold.

Also: separate compilation.

For once, a story from Kuro5hin.

Formal Specification helps build more robust, more maintainable software with fewer bugs and defects. It has a long history, but it is still a developing field. While it may not be suitable for all software projects, a case can be made that there are many projects not currently using formal specification that stand to benefit from it. As the methods and tools for formal specification develop it is increasingly becoming something that developers and software engineers should learn to use to their advantage.

I haven't had a chance to read it yet, but this story mentions SPARK and CASL, and seems reasonably well-researched.

A couple of weeks ago, I posed the following in my blog: what are the grand challenges of software and software engineering? What do we know we don't know?

I had about a dozen people rise to the question and a lively discussion among many of them unfolded via email. Following are some highlights of that correspondence.

Even though most of the responses weren't about coding and programming language issues, I think this discussion is worth a look.

It might be intereting to discuss if and to what extent programming languages can help improve the state of the art in SE.

I'll go first and argue that a large part of the answer to How to keep significantly raising the level of abstraction in face of ever growing software complexity? lies in better programming languages. Especially as regards module systems, expressive type systems and better concurrency and distributed computing idioms.

Martin Fowler writes,

Most new ideas in software developments are really new variations on old ideas. This article describes one of these, the growing idea of a class of tools that I call Language Workbenches - examples of which include Intentional Software, JetBrains's Meta Programming System, and Microsoft's Software Factories. These tools take an old style of development - which I call language oriented programming and use IDE tooling in a bid to make language oriented programming a viable approach. Although I'm not enough of a prognosticator to say whether they will succeed in their ambition, I do think that these tools are some of the most interesting things on the horizon of software development. Interesting enough to write this essay to try to explain, at least in outline, how they work and the main issues around their future usefulness.

When I was learning to program, we simply called these things good programming...

Seriously, much as I like DSLs and am happy to see more people think about the role of language design in software design, I think it is important to stress that good sofware design comes from familiarity with a large set of techniques. Language oriented techniques are useuful, but they aren't a panacea. They deserve wider recognition, being almost totally unknown in the wider programming community compared to other techniques (e.g., patterns), but shouldn't promise more than they can deliver.

I vaguely remember a long "tutorial" we linked to a couple of years ago about becoming a professional programmer, which included language design along with other techniques one must master. If this rings any bells, please post the link since I don't remember any more deatils...

I've just read one of Joel Spolsky's usual rants, this one on the joys and virtues of Hungarian notation. You can take the boy out of Microsoft …

His example is avoiding malicious user input on a web form by ensuring all unsafe input is always encoded before use. He suggests two coding conventions before settling on Hungarian Notation as the Right Thing.

Now I expect LtU readers (certainly this one) will be wondering how a flakey substitute for a type system ended up being Right Thing instead of the Real Thing we know and love (and at this point everyone should briefly murmur a prayer over their copy of TAPL). But any regular reader of Joel will know he is thoroughly pragmatic (or anti-academic, depending on your mood) and his solution fits his mindframe. So, leaving aside ranting and wailing about Joel's lack of PL education (because, frankly, I'm doing enough for everyone) let's talk instead about how one could change his mind. Specifically, implementing Hungarian is a few days of drudge-work. You're never going to get Joel to sit down with SICP, EOPL or PLAI, and TAPL, to get the necessary background to implement his own statically typed language, and if you tried he would rightly tell you it would take too long to learn. Instead, could you deliver a statically typed variant of Javascript that would catch these errors in a similar time period? If so, what tools would you use? What type systems? How practical can we make our theory?

The results are in for the 2005 Glasgow Haskell Compiler user survey, with a summary and all the raw data. The comments were the highlight for me; see for instance Applications I use GHC for.

(Previous LtU mention)

A type-indexed function is a function that is defined for each member of some family of types. Haskell's type class mechanism provides open type-indexed functions, in which the indexing family can be extended at any time by defining a new type class instance. The purpose of this paper is to present TypeCase: a design pattern that allows the definition of closed type-indexed functions. It is inspired by Cheney and Hinze's work on lightweight approaches to generic programming. We generalise their techniques as a design pattern. Furthermore, we show that type-indexed functions with type-indexed types, and consequently generic functions with generic types, can also be encoded in a lightweight manner, thereby overcoming one of the main limitations of the lightweight approaches.

A new paper in a field we follow quite closely (i.e., generic programming).

The paper starts with a useful summary of important previous results, which is worth reading even if you don't plan on studying the whole paper.

Libraries are central to all major scientific, engineering, and business areas, yet the design, implementation, and use of libraries are underdeveloped arts. This workshop is one of the first steps in the process of placing all aspects of libraries on a sound technical and scientific basis through research into fundamental issues and documentation of best practices.

A software library is an organized collection of code with associated tools supporting programming in general or in specific domains, usually united by a specified set of principles and conventions. Most libraries are aimed at the use by several people and in different environments...

This is an important topic, so I urge you to take a look at the CFP for the workshop, and see if you can help improve the state of the art by contributing.

A Judy tree is generally faster than and uses less memory than contemporary forms of trees such as binary (AVL) trees, b-trees, and skip-lists. When used in the "Judy Scalable Hashing" configuration, Judy is generally faster then a hashing method at all populations.

Some of the reasons Judy outperforms binary trees, b-trees, and skip-lists:

• Judy rarely compromises speed/space performance for simplicity (Judy will never be called simple except at the API).
• Judy is designed to avoid cache-line fills wherever possible.
• A b-tree requires a search of each node (branch), resulting in more cache-line fills.
• A binary-tree has many more levels (about 8X), resulting in more cache-line fills.
• A skip-list is roughly equivalent to a degree-4 (4-ary) tree, resulting in more cache-line fills.
• An "expanse"-based digital tree (of which Judy is a variation) never needs balancing as it grows.
• A portion (8 bits) of the key is used to subdivide an expanse into sub-trees. Only the remainder of the key need exist in the sub-trees, if at all, resulting in key compression.

The Achilles heel of a simple digital tree is very poor memory utilization, especially when the N in N-ary (the degree or fanout of each branch) increases. The Judy tree design was able to solve this problem. In fact a Judy tree is more memory-efficient than almost any other competitive structure (including a simple linked list). A highly populated linear array[] is the notable exception.

Worth a look, considering the open-source LGPL license and range of applications. HP released this library in 2004. From the PDF manual,

Judy arrays are remarkably fast, space-efficient, and simple to use. No initialization, configuration, or tuning is required or even possible, yet Judy works well over a wide dynamic range from zero to billions of indexes, over a wide variety of types of data sets -- sequential, clustered, periodic, random.