archives

Two papers on combinators

Hello! I have a couple of papers on using combinators in Combinatory Logic (CL).

I've just updated a paper I wrote some time ago that examines the derivation of a combinator that consumes its argument. "Meditations on the Void" is available at http://www.cotilliongroup.com/code/void-meditations.html.

I have developed a new combinator, P (for Propositional combinator) that curries two arguments at linear cost (currying arguments using combinators usually have an exponential size cost); it is also useful for expressing propositions in CL. "Penguin" is available at http://www.cotilliongroup.com/code/penguin.html.

More generally, my research is in programming languages using the predicate and lambda calculus. The main page for my explorations is at http://www.cotilliongroup.com/code/research.htm.

Sincerely,
Doug Auclair

By Doug Auclair at 2005-04-27 00:12 | LtU Forum | 3 comments | other blogs | 5695 reads

The Fortress Language Spec v0.618

The Fortress Language Spec v0.618

We've already discussed the Fortress project at Sun's Programming Language Research lab. The project seems to be progressing well: they have now released a preliminary version of the language spec as a tech report. This should help assuage the folks who were grumbling about the hype and market-speak of Sun's promotional article. Their PL research team includes some real Smarty McSmartpants, so I expect really good things from them.

From a cursory glance at the spec, there seem to be many interesting features, including:

  • an advanced component and linking architecture
  • objects and traits (which look similar to Moby and Scala)
  • multiple dispatch
  • type inference
  • parameterized types
  • extensible syntax (with a conspicuous reference to Growing a Language)
  • first-class functions
  • proper tail calls
  • labelled jumps, exceptions
  • contracts
  • some interesting parallelism features (including futures, parallel loops, atomicity primitives, transactions)
  • matrices
  • comprehensions
  • bignums, fixnums (signed and unsigned), floating-point, imaginary and complex numbers
  • dimensions

Future work includes proving type soundness, apparently. :)

It is so much fun when the luminaries start working on new languages. History in the making!

By Dave Herman at 2005-04-27 04:10 | Implementation | 37 comments | other blogs | 79276 reads

OO runtime graphs are scale-free

If you liked Barabási's book, you'll find this interesting. The May issue of CACM has an article called Scale-Free Geometry in OO Programs [PDF, 180K] by Alex Potanin, James Noble, Marcus Frean, and Robert Biddle. They examined 60 heap snapshots from 35 different Java programs and found all of the resulting object graphs to be scale-free. This is true for both incoming and outgoing links with the qualification that objects rich in incoming links are poor in outgoing links and vice versa.

What are the implications of this for PL research in OO languages? The authors point out the following:

  • One useful aspect of scale-free networks is their high resilience to random network damage. Since most nodes are poorly connected, deleting them doesn't affect the remaining nodes all that much.
  • A small number of nodes are highly connected. You may get the best bang for the buck by concentrating early QA effort on the highly connected nodes first.
  • "is is well-known that garbage collectors can improve their performance by assuming that most objects have only one or two outgoing references. The scale-free nature of object graphs explains why making this assumption is worhtwhile."

    • Any other interesting implications?

    By el-vadimo at 2005-04-27 14:53 | LtU Forum | 2 comments | other blogs | 6804 reads