Lambda the Ultimate

Implicit Ownership Types for Memory Management. Tian Zhao, Jason Baker, James Hunt, James Noble, and Jan Vitek. Draft.

The Real-time Specification for Java (RTSJ) introduced a range of language features for explicit memory management. While the RTSJ gives programmers fine control over memory use and allows linear allocation and constant time deallocation, the RTSJ relies upon dynamic runtime checks for safety making it unsuitable for safety critical applications. We introduce ScopeJ, a statically typed, multi-threaded, object calculus in which scopes are first class constructs. Scopes reify allocation contexts and provide a safe alternative to automatic memory management. Safety is the result of our use of an ownership type system that enforces a topology on run-time patterns of references. ScopeJ's type system is novel in that ownership annotations are implicit. This substantially reduces the burden for developers, thus increasing the likelihood of adoption. The notion of implicit ownership is particularly appealing when combined with pluggable type systems, as one can apply different type constraints to components depending on the requirements. In related work we have demonstrated the usefulness of our approach in different applications

An example of a pluggable type system which, unlike previous discussions on LtU, eg. Gilad Is Right and Flexible Addition of Static Typing to Dynamically Typed Programs, adds more type rules to an already statically typed language. It doesn't, however, appear to be an optional type system as it seems to make use of a library and some syntactic rules to encode the region types.

The type system itself seems quite complicated which may be due to building on Java's existing type system as much as the support for first-class and multi-threaded regions, an aspect which seems to be unique in region calculi. Compare the complete type system for F^RGN in Monadic Regions. Not that I can claim to understand all the maths in that paper either but Oleg Kiselyov's implemetation on top of Haskell's ST monad is short and sweet.

This might be a little bit off topic, as it's hardware related, but radical changes in hardware have a way of trickling up to the software. After listening to Ted Neward's keynote about the future of languages, I had a series of thoughts.

1. We really do have fundamental issues related to multi-core concurrency, distributed programming, and (by implication) emergent behaviors of our software systems.
2. FPGAs are dynamic hardware
3. You could, in theory bundle a CPU with an FPGA so they sit on the same die
4. FPGAs are useful for truly running a Virtual Machine (rather than simulating one on the CPU)
5. This would be incredibly powerful, if, as Ted implied, DSLs expand in popularity, we should use the hardware itself as a VM.

One of the most immediate benefits I could envision was the ability to run a webserver in conjunction with an interpreted language at much faster speeds. Or, in high-performance computing, making a multi-core pipeline specific for your research simulation. I'm sure that you all can think of many others; I'm sure it's one of those technological marriages that spawn unexpectedly useful offspring.

Is this idea out there? Does it have a name? What researchers have explored this area? Are FPGAs currently useful for such applications? How long will we have to wait?

Obviously we'll need a DSL just to program the thing (as if multi-core alone wasn't hard enough), and with it, a good silicon compiler.

OMeta: an Object-Oriented Language for Pattern Matching

A new paper by Alessandro Warth and Ian Piumarta, related to the Reinvention of Programming project:

This paper introduces OMeta, a new object-oriented lan-
guage for pattern matching. OMeta is based on a variant of
Parsing Expression Grammars (PEGs) [5]—a recognition-
based foundation for describing syntax—which we have
extended to handle arbitrary kinds of data. We show that
OMeta’s general-purpose pattern matching provides a nat-
ural and convenient way for programmers to implement
tokenizers, parsers, visitors, and tree transformers, all of
which can be extended in interesting ways using familiar
object-oriented mechanisms. This makes OMeta particularly
well-suited as a medium for experimenting with new designs
for programming languages and extensions to existing lan-
guages.

Shape Analysis with Structural Invariant Checkers, Bor-Yuh Evan Chang, Xavier Rival, and George C. Necula. SAS 2007.

Developer-supplied data structure specifications are important to shape analyses, as they tell the analysis what information should be tracked in order to obtain the desired shape invariants. We observe that data structure checking code (e.g., used in testing or dynamic analysis) provides shape information that can also be used in static analysis. In this paper, we propose a lightweight, automatic shape analysis based on these developer-supplied structural invariant checkers. In particular, we set up a parametric abstract domain, which is instantiated with such checker specifications to summarize memory regions using both notions of complete and partial checker evaluations. The analysis then automatically derives a strategy for canonicalizing or weakening shape invariants.

I saw a talk by Evan, and thought this approach is fundamentally the right way to go, because the proper sharing behavior of heap data is information that's integral to the design and not at all in the code. So programmers should be able to supply this information to their analyses.

I am trying to implement heap in CLisp. I have already done it by making a linear data strcuture with no left / right pointers. But now I want to use a nested list format which contains (el () ()) at the highst level.
The problem I am facing with is how to define a recursive case for insertion. Heap requires the tree to be complete.

I approach the issue as follows:

1. I will take a heap and an element
2. I will add the element in the last node keeping it a complete tree
3. I wil swap the child with parent if it is greater than the parent

But I am stuck at the second step i.e. how to add an element without making the tree incomplete? KIndly help me on this!!!!!!!