Lambda the Ultimate

Does anyone have any reference material or thoughts on the idea of a method in an object oriented language always being allowed access to the sender of that message? It seems to be universally true that the sender of a message is unknown to the method unless explicitly passed as a parameter. I'm curious as to why that seems to be the default assumption. My gut instinct is that the rationale is connected with the idea of preserving encapsulation, but I wonder if that's really been tested or if that's more of a gut feeling that's been passed down through the years? (I know of no language that would prevent a sender from sending a reference to itself along as a message parameter - and indeed that is a common way around this limitation when the need arises. Why enforce the barrier in one case in the name of encapsulation, but not another if that is indeed the reason?)

A quick link (and one that will cause google haters to jump on me, surely): http://googleresearch.blogspot.com/2009/08/under-hood-of-app-inventor-for-android.html

Alex Stepanov and Paul McJones's Elements of Programming has been published by Pearson/Addison Wesley. I picked up a copy at the Siggraph conference in New Orleans and skimmed it on the plane home. Under the covers it's an apologia for STL, and as such will doubtless stir debate. Examples are written in an extremely spare dialect of C++.

The problem of void calls, or null pointer dereferencing, plagues programs written in any language using pointers or references with a "null" or "void" value. Tony Hoare recently described it as his "one-billion dollar mistake". The problem is very simple to state: in the typical object-oriented call

x.f (args)

x, a reference, should normally denote an object but can be void, in which case the call will fail and produce an exception, often leading to a crash. This is one of the main sources of instability in today's software.

The void-safety mechanism of Eiffel, as defined in the ISO/ECMA standard (2006), is now fully implemented in EiffelStudio and guarantees the absence of void calls. With version 6.4, beyond the mechanism itself, all libraries have been updated to be void safe.

With Alexander Kogtenkov and Emmanuel Stapf I wrote an article describing not only the principles but also the delicate engineering issues that we have encountered and tried to address in making Eiffel void-safe. An abstract, and a link to the PDF of the article, can be found at http://bertrandmeyer.com/tag/void-safety/.

Hoopl: Dataflow Optimization Made Simple by Norman Ramsey, João Dias, and Simon Peyton Jones.

We present Hoopl, a Haskell library that makes it easy for compiler writers to implement program transformations based on dataflow analyses. The compiler writer must identify (a) logical assertions on which the transformation will be based; (b) a representation of such assertions, which should form a lattice of finite height; (c) transfer functions that approximate weakest preconditions or strongest postconditions over the assertions; and (d) rewrite functions whose soundness is justified by the assertions. Hoopl uses the algorithm of Lerner, Grove, and Chambers (2002), which can compose very simple analyses and transformations in a way that achieves the same precision as complex, handwritten ``super-analyses.'' Hoopl will be the workhorse of a new back end for the Glasgow Haskell Compiler (version 6.12, forthcoming).

A continuation of work previously mentioned on LtU here. Original people, new language. More purity, more goodness. Sinfully, there does not yet seem to be a hackage package.

I'm part of a group that is writing a paper trying to explain, to other computer scientists and engineers, the importance to universities of teaching undergraduate courses on programming languages. (The group is a subcommittee of the (newly formed) ACM SIGPLAN education board.) The hope is that this paper will be useful in influencing the IEEE/ACM curriculum revisions and ABET accreditation process. It might also help motivate students in such a course.

So, we are seeking a set of examples (or data) that say how the kind of knowledge taught in (esp. undergraduate) courses on programming languages help students in their careers. These careers could be in industry or research, but probably the most interesting and least debatable examples would come from industry. What we'd like are examples that would be convincing to computer scientists and engineers who are outside the field of programming languages, since those are the ones we have to sell on the importance of courses in programming languages.

An example of such an example is Paul Graham's paper "Beating the Averages" (see http://www.paulgraham.com/avg.html). Other examples we know something about, but would like more details about, are LexiFi's use of abstraction ideas in financial contracts ("Composing Contracts: An Adventure in Financial Engineering", by Simon Peyton Jones, Jean-Marc Eber, and Jullian Seward, in IFIP 2000), Ericsson's use of Erlang (http://erlang.org/doc.html), Twitter's use of Scala ( http://www.artima.com/scalazine/articles/twitter_on_scala.html), software transactional memory and Haskell ( http://www.haskell.org/haskellwiki/Software_transactional_memory).

If you know of more examples, please let us know by replying to this thread, preferably with a reference or link. Since the functional programming community has done an especially good job of making clear what their commercial successes are (see http://cufp.galois.com/), we are particularly interested in ideas from the programming language community that are not just "apply functional programming ideas" (although those are welcome too), for example older stories of how using OO gave a market advantage, or how some company used logic programming to configure computers. The best kind of examples would relate directly to topics typical of undergraduate programming languages courses (e.g., "How I made a million dollars by using static scoping" :-).

Dao (posted here before) was not initially designed to be a functional programming language, but with time some functional features were added to the language. And recently I designed and implemented (for the next release) several built-in methods to increase its support for functional style programming.

These methods are documented here: http://www.daovm.net/space/dao/thread/137. It is slightly similar to that of Ruby with a few distinctive feature. Basically, it looks like something like this,

RESULT = METHOD( PARAMETER ) -> |VARIABLE| { EXPRESSION }

Here PARAMETER can be one or more list or array (almost all these methods are applicable to numeric arrays), or other data types depending on METHOD. |VARIABLE| is to declare variables associated with list/array items or indices etc. |VARIABLE| can also be omitted so that default parameter names will be used.

EXPRESSION is the inlined function to be applied, normal statements (except return statement) can also be used, in this case, the statement code block must be separated from the EXPRESSION by "return" key word. EXPRESSION can actually be multiple expressions separated by comma(s) in method such as map(), which will return a list of tuples in such cases.

Function composition is simply supported by allowing one or more ->|...|{...} constructs to append one after another. In such cases, |VARIABLE| can be used to declare variables referring the results of EXPRESSION in the previous ->|...|{...} construct.

A simple example:

a = { 1, 2, 3 }
b = { 7, 8, 9 }

zip_ab = map( a, b ) -> |u,v| { u, v }
zip_ab = map( a, b ) -> { x, y }
zip_ab = select( a, b ) -> { 1 }

c = map( a, b ) -> |x,y| { x-y, x+y } -> |u,v| { u*v }

d = map( a ) -> |x| {
  u = 10*x;
  v = x+10;
  if( u < v ) u += v;
  return u*v 
}

e = unfold( 5 ) -> |x| { while x > 0 return x - 1 }

e = unfold( 5 ) -> |x| {
  stdio.println(x)
  while x > 0 return x - 1
}

Your comments, suggestions or opinions are welcome,
I think they will be very invaluable for the future improvements. Many thanks in advance!

There's a paper I would like to find... I can't get the right incantation in google.

I think it was a relatively recent thesis, like within the last 10 years... I can't remember if it was phd or master's, and I'm only 70% sure it was 'officialy' marked a thesis in the first place.

The main idea was extensible compilation.
A sexpr language was used/implemented for examples.

One specific concept that resonated with me was that APIs like OpenGL that require a specific protocol of function calls are making their own DSL/VM. By coding to this protocol/VM, you are essentially "manually compiling", with all the inefficiency and risk of error that entails, and there should be a better solution. I specifically remember the wording "manual compilation" pertaining to APIs being in the paper.

I lost a hard drive and I can't re-find this paper, please help :/

Perhaps not great news to most, but I found this study of late binding in OO languages to help me [1] [2] better understand how the term is context-sensitive . It appears that Smalltalk was the most flexible/robust in some sense.

On the safety critical mailing list an interesting discussion is taking place, about formal methods. Me, having interest in them, was surprised by the following statement of Nancy Leveson:

Virtually every software-related accident I have heard about in the past 30 years (and I've seen a lot of them) occurred while the software was "performing as specified."

http://www.cs.york.ac.uk/hise/safety-critical-archive/2009/0310.html

(Ariane 5 was not among them, then)

She also writes:

There is a reason that formal methods have not been widely adopted for the past 40 years that academics have been telling practitioners they must use them. Before they are used, the researchers will have to provide:
1. Languages and tools that can be used by a wide range of engineers with only a bachelor's degree. They
cannot be usable only by a small group of Ph.D. mathematicians.
2. Extentions of the techniques to the things they don't cover. Formal methods have been very oversold. They do not handle many of the most important problems.
3. Careful demonstration and experimentation to show that formal methods are less error-prone and more effective than less formal methods for the hardest parts of the problem -- not just the parts that they work best on.

http://www.cs.york.ac.uk/hise/safety-critical-archive/2009/0321.html

and

My students were very fine mathematicians. But they were not pilots or engineers--it required the latter to find the errors my students could not. Formal methods experts cannot and should not be "gurus" outside their field. Most software-related accidents are caused by errors in the requirements specification -- not typos or simple things to find, but misunderstanding basic things about the controlled system and the behavior of the computer. That requires a domain expert, not a mathematician.

http://www.cs.york.ac.uk/hise/safety-critical-archive/2009/0325.html

So the aim is to have formal languages that domain experts do understand. Which of your favourite FM languages stands this test?

Some of them are based on LISP notation which is very compsci-biased. Still, these systems (PVS, ACL2) are used mostly in actual verifications. Isabelle and Coq have more user-friendly notation but it is a question whether these can bridge the gap. Some might call them "cryptic".

What are your favourite languages in this sense?