Lambda the Ultimate

Lets say you're compiler uses the following structures to represent a function type and a class to represent a function declaration:

class FuncType extends Type {
   List<Type> params;
   Type ret;
}

class FuncDecl {
   String name;
   FuncType type;
   List<String> paramNames;
}

There objects "FuncDecl.type.params" and "FuncDecl.paramNames" are related in ways that aren't expressed in the source code of the two class declarations. For example, each entry in the "paramNames" list matches up with the corresponding type in the "type.params" list.

I've been thinking about "paramNames" as adding attributes to the "FuncType" data structure. So paramNames would actually be a "map" data structure whose keys are structural references to parameter types and whose values are strings. Something like:

class FuncDecl {
   String name;
   FuncType type;
   Map<#type#,String> paramNames;
}
FuncDecl d = ...;
d.paramNames.put(#params[0]#", "dst");  // The "params" refers to the list in "type"
d.paramNames.put(#params[1]#", "src");
...

The best concrete solution I can come up with isn't satisfying:

class FuncType<ExtraParamInfo,ExtraReturnInfo> {
   List<Pair<Type,ExtraParamInfo>> paramets;
   Pair<Type,ExtraReturnInfo> ret;
}

class FuncDecl {
   Type<String,Void> typeAndParamNames;
}

Is there a language or type system that does a good job of expressing such relationships?

I happened to find (and purchase) Theoretical Introduction to Programming by Bruce Mills (Springer, ISBN 978-1846280214) at my local bookstore. I've been patiently digesting it for a few days now, and it's already given me a couple of fine insights into programming that I hadn't realised in my 20+ years in the field.

Has anyone else seen this book? I was actually a bit surprised to search LtU and find no mention of it.

My own opinion is that while it could benefit from a good editor, and I wish the author would spend more than a paragraph or two on some of the subjects mentioned, it's been a good purchse overall.

Programming Parallel Algorithms, Guy Blelloch. 1996.

Many constructs have been suggested for expressing parallelism in programming languages, including fork-and-join constructs, data-parallel constructs, and futures, among others. The question is which of these are most useful for specifying parallel algorithms? If we look at the parallel algorithms that are described in the literature and their pseudocode, we find that nearly all are described as parallel operations over collections of values. For example ``in parallel for each vertex in a graph, find its minimum neighbor'', or ``in parallel for each row in a matrix, sum the row''. Of course the algorithms are not this simple--they usually consist of many such parallel calls interleaved with operations that rearrange the order of a collection, and can be called recursively in parallel, as in Quicksort. This ability to operate in parallel over sets of data is often referred to as data-parallelism, and languages based on it are often referred to as data-parallel languages or collection-oriented languages. We note that many parallel languages have data-parallel features in conjunction with other forms of parallelism.

Before we come to the rash conclusion that data-parallel languages are the panacea for programming parallel algorithms, we make a distinction between flat and nested data-parallel languages. In flat data-parallel languages a function can be applied in parallel over a set of values, but the function itself must be sequential. In nested data-parallel languages any function can be applied over a set of values, including parallel functions. For example, the summation of each row of the matrix mentioned above could itself execute in parallel using a tree sum. We claim that the ability to nest parallel calls is critical for expressing algorithms in a way that matches our high-level intuition of how they work. In particular, nested parallelism can be used to implement nested loops and divide-and-conquer algorithms in parallel (five out of the seven algorithms described in this article use nesting in a crucial way).

IIRC, the team developing Fortress is putting nested data parallelism into Fortress. I think this is one of the most intriguing ways of getting heavy duty parallelism -- something that will grow ever more important as the number of cores in our computers grow.

The Metronome technology, developed at IBM Research and now available in production, solves [the problem of realtime GC] by limiting interruptions to one millisecond and spacing them evenly throughout the application's execution.2 Memory consumption is also strictly limited and predictable, since an application can't be realtime if it starts paging or throws an out-of-memory exception.

The article is primarily about the Metronome garbage collection technology, but includes a nice introduction to garbage collection and realtime terminology as well.

We propose programming language mechanisms to reduce redundancy in program source code. These abbreviation mechanisms, shorthands, make programs shorter and easier to write and read. In addition, we provide a framework for describing language abbreviation mechanisms.

An interesting and odd paper from Todd Proebsting (of "Proebsting's Law"fame) and Ben Zorn. If you like $_ and @_ in Perl, then you may like this, too. I can't recall seeing any other papers on this topic, so pointers are welcome.

Seems like there are lots of folks who don't want to go to the trouble of defining contracts or assertions (much) either before or during software development. However, when it comes time to find and fix bugs, there might be more desire to tighten things down.

I've heard of tools that will run your code a zillion times and try to figure out constraints for it (MrFlow is one thing I can think of, but it is apparently more of a static checker). I have not used them so this is a naive question: might such a system work interactively with the developer to construct and refine contracts? Pick a method, and the system starts an interactive Q & A to define and narrow the contract based on the function signiture and any additional information from static analysis, and from having run the code in various ways.

The idea would be to work with the developer / maintainer to over time refine assumptions about the code to find bugs.