Lambda the Ultimate

What facets of a programming system (language, libraries, tools, etc) make it easy to learn and use?

If you were to design from scratch a new programming system, what choices would you make in order to attract users? To what extent would you compromise the design in order to do so?

Automatic termination proofs for programs with shape-shifting heaps

Abstract. We describe a new program termination analysis designed to handle imperative programs whose termination depends on the mutation of the program's heap. We first describe how an abstract interpretation can be used to construct a finite number of relations which, if each is well-founded, implies termination. We then give an abstract interpretation based on separation logic formula which tracks the depths of pieces of heaps. Finally, we combine these two techniques to produce an automatic termination prover. We show that the analysis is able to prove the termination of loops extracted from Windows device drivers that could not be proved terminating before by other means; we also discuss a previously unknown bug found with the analysis.

Whatever happened to reactive programming? FRP in particular -- there was a flurry of activity at Yale over the past decade or so, but it appears to have petered out, and nobody else has picked up on it or tried variants.

(By "reactive programming" I mean using the "signals and systems" paradigm to building a real-time program, (e.g. as in Labview or in some signal processing languages), but fleshed out enough to have a coherent semantics and to be able to do all the other things a PL needs to. Most attempts at this from the programming languages mainstream, dating from Lucid, have tried to use streams...)

--Josh

While perusing the internet on the subject of scale-free and small world networks I came across this article, which deals with human language as opposed to Ltu's focus on formal languages. I hope it is not too far off topic and if so please delete this contribution. My main motivation to publish this article lies in the fact that scale-free and small world features can in my opinion be seen back in programming environments with extensive libraries and systems making extensive use of DSL's.

Abstract:
Complex dynamic networks are ubiquitous in nature and human society. In recent years research in large-scale networks has seen a rapid development in various disciplines, inspired by the discovery of two features shared by many real-world networks: small-world and scale-free. This paper introduces how human languages can be studied in this light, and reports some work available in this area. There are two directions of exploration. One is to study networks existing in the language system. Various lexical networks can be built based on different relationships between words, being semantic or syntactic. Recent studies have shown that these lexical networks exhibit small-world and scale-free features. The findings of these global structures of the mental lexicon, which are not detectable in traditional analyses on semantic networks, trigger more interests in the global structures of the mental lexicon and language in general from a network perspective. The other direction of exploration is to study networks of language users (i.e. social networks of people in the linguistic community), and their role in language evolution. Social networks also show small-world and scale-free features, which cannot be captured by random or regular network models. In the past, computational models of language change and language emergence often assume a population to have a random or regular structure, and there has been little discussion how network structures may affect the dynamics. In the second part of the paper, a series of simulation models of diffusion of linguistic innovation are used to illustrate the importance of choosing realistic conditions of population structure for modeling language change.. Four types of social networks are compared, which exhibit two categories of diffusion dynamics. While the questions about which type of networks are more appropriate for modeling still remains, we give some preliminary suggestions for choosing the type of social networks for modeling.

I have recently been going over merging code from various branches. One rather annoying thing I noticed was the diff and merge tools don't seem to understand enough about the language in order to produce good ideas on what's going on. For instance if I am merging an insert where the inserted code just happens to have the same header bit of a comment and ends with the same bit of the comment it wants to merge this new piece in-between the comment rather than viewing the comment as an entire block. The same happens elsewhere often.
So with that, my question is really if better merge tools are viewed as a necessary problem in dealing with languages or if the outcome is not considered worth the effort?

I realize this is not a question directly at PL (theory) in general so if the question is inappropriate for here please take care of it accordingly.

Inspired by 'The Third Manifesto', a book by Chris Date and Hugh Darwen, we're putting forward an implementation of a truly relational language using Python (Dee). We address two problems:

1. The impedance mismatch between programming languages and databases
2. The weakness and syntactic awkwardness of SQL

See www.quicksort.co.uk for details.

In my spare time I'm trying to craft a language, mainly out of curiosity. I'm leaning towards a simple OO-language similar to Python, i.e. highly dynamic. My main goals for the language is simplicity and orthogonality, a rather secondary goal is performance.

I'm looking at unifying the mechanisms for accessing a value within the scope of a closure. Consider the following (in some arbitrary syntax):

class Foo:
   m_x = 2

   function f(x):
      function g(y):
         return m_x + x + y;

It's clear that g is a closure needing access to 1) It's own scope, 2) f's scope and 3) the environment of the instance. The straightforward implementation (which I have seen used in actual production languages) would be to have both closure and function types that upon invocation take whatever combination of environment variables and activation records they need. This implies that the invocation of functions and closures is different as well, and you sort of end up with a big heap of switches and what-if-this-is-a-this-type-of-callable code in your vm. Additionally, the vm ends up with a lot of different load instructions (load-from-stack, load-from-free-vars-stack, load-from-this), which makes anything but a stack-based vm untenable.

The only thing I can come up with is to treat an object and activation records as tables and link them up. A request for a variable can then trickle up these links of tables until a match is found. However, this sounds painfully slow even for the language I was envisaging.

I'm sure this kind of problem has come up and someone language implements this a lot more cleanly. Does anyone have any thoughts on the matter?

kind regards,
Tomas

(Didn't find this on LtU yet, apologies if it is a dupe.) While all benchmarks are questionable, I found this 3 way comparison for a given concurrency situation to be of interest.

This is a continuation of Parallel Ant Colony Optimization for TSP in Standard ML and Multi-Core Ant Colony Optimization for TSP in Haskell. Here the program has been rewritten in the programming language Erlang.

Compile time garbage collection for the declarative language Mercury, by Nancy Mazur. From the abstract:

"The compiler determines the lifetime of the variables that are created during the execution of the program, and thus also the memory that will be associated with these variables. Whenever the compiler can guarantee that a variable, or more precisely, parts of the memory resources that this variable points to at run-time, will never ever be accessed beyond a certain program instruction, then the compiler can add instructions to deallocate these resources at that particular instruction without compromising the correctness of the resulting code. If the program instruction is followed by a series of instructions that require the allocation of new memory cells, then the compiler can replace the sequence of deallocation and allocation instructions, by instructions updating the garbage cells, hence reusing these cells."

[I think I got onto this via some LtU comment that I can't find now.] Looks like MML has been given real legs via a compiler in Haskell. Per chance, has anybody used this? Now if only there were a debugger, and good concurrency support...