Lambda the Ultimate

In First-class Macros Have Types, POPL 2000, Alan Bawden describes a way to make macros behave as first class values.

In modern Scheme, a macro captures the lexical environment where it is defined. This creates an opportunity for extending Scheme so that macros are first-class values. The key to achieving this goal, while preserving the ability to compile programs into reasonable code, is the addition of a type system. Many interesting things can be done with first-class macros, including the construction of a useful module system in which modules are also first-class.

Bawden points out that while he used a static type system...

[t]here is no fundamental reason why this macro type system needs to be static. The same safety could be achieved using dynamic typing....The compiler would emit code to check the tags at runtime to make sure that a value used as an operator always had the type that the programmer promised the compiler it would have.

In Polymorphic Algebraic Data Type Reconstruction, Tom Schrijvers and Maurice Bruynooghe create some magic: in addition to normal type declaration inference, they infer ADT definitions. From the abstract:

One of the disadvantages of statically typed languages is the programming overhead caused by writing all the necessary type information: Both type declarations and type definitions are typically
required. Traditional type inference aims at relieving the programmer from the former.

We present a rule-based constraint rewriting algorithm that reconstructs both type declarations and type definitions, allowing the programmer to effectively program type-less in a strictly typed language.

Is the algorithm guaranteed to terminate? Well...

...theoretically there must be some programs for which it does not terminate. However, as with Henglein’s algorithm, we are not aware of any actual program for which it does not terminate.

We quote Henglein to emphasize that the termination of the inference is only an issue for programs that have problematic types:

     . . . why type checking is no more practical than type inference:
     there are constructible ML-programs that fit on a
     page and are, at least theoretically, well typed, yet writing
     their principal types would require more than the number of
     atoms in the universe. So writing an explicitly typed version
     of the program is impossible to start with.

Marshall, C.C. From Writing and Analysis to the Repository: Taking the Scholars' Perspective on Scholarly Archiving. Proceedings of JCDL'08

This paper reports the results of a qualitative field study of the scholarly writing, collaboration, information management, and long-term archiving practices of researchers in five related subdisciplines. The study focuses on the kinds of artifacts the researchers create in the process of writing a paper, how they exchange and store materials over the short term, how they handle references and bibliographic resources, and the strategies they use to guarantee the long term safety of their scholarly materials.

Not directly programming language related, but two things makes this paper relevant. First, many of the tools involved, especially those that really enhance productivity are language-based, or include DSLs (e.g., Latex, Bibtex, R (+Sweave) etc.). Second, many of us write papers, and as language geeks we surely crave great tools...

So, what is you ideal tool chest when it comes to doing and publishing research? And what do you actually use everyday?

A useful short article by Ben Brosgol in COTS Journal.

On the surface, Ada and Java offer similar features to support real-time embedded military applications. But under the hood, they differ significantly in their underlying philosophy...

All that said, the Java / Ada decision need not be either/or. Mixed-language programming is provided by Java through the Java Native Interface, and by Ada through a standard interfacing framework. The enhancements in Ada 2005 make such interfacing easier, and there is current implementation support for mixed Ada/Java development. In a large system it may make sense to program different components in different languages—for example, a user interface in Java, hard real-time elements in Ada—thus taking advantage of the strengths of both. Ada and Java, rather than competing in the embedded defense system arena, may turn out to be comrades in arms.

Ben Brosgol is an expert on both Ada and Java support for real time programming, and I've linked to his papers that provide more detailed analysis a few times in the past.

A compelling description of the features that make CL the king of the Perl-Python-Ruby-PHP-Tcl-Lisp language ;)

Lisp is often promoted as a language preferable over others because it has certain features that are unique, well-integrated, or otherwise useful.

What follows is an attempt to highlight a selection of these features of standard Common Lisp, concisely, with appropriate illustrations.

I had received the announcement for the Continuation Fest 2008, but then completely forgot about it. Back in mid-April, some neat stuff was going on in Tokyo:

• Demo of persistent delimited continuations in OCaml for nested web transactions, Oleg Kiselyov, [Slides]. (I wish I had seen that a few years back when I was fooling with the Infernal Device. Just beautiful.)
• How to implement continuation only language in gcc 4.x, Shinji Kono, [Slides].
• Continuing from the past: An approach to building dynamically upgradable applications, Takuo Watanabe and Yuichi Tanaka, [Slides].
• Plus others....

[Edit: fixed url.]

Those of us not at ESSLLI 2008 might want to follow the action using the as usual excellent web site, which contains complete course materials.

Alas, it seems that this year less courses are directly relevant to LtU, but since both logic and linguistics tend to come up around here fairly often I am sure you'll find at least a couple of courses that will whet your appetite.

Computational thinking is a fundamental skill for everyone, not just for computer scientists. To reading, writing, and arithmetic, we should add computational thinking to every child’s analytical ability. Just as the printing press facilitated the spread of the three Rs, what is appropriately incestuous about this vision is that computing and computers facilitate the spread of computational thinking.

Computational thinking involves solving problems, designing systems, and understanding human behavior, by drawing on the concepts fundamental to computer science. Computational thinking includes a range of mental tools that reflect the breadth of the field of computer science.

from Jeannette M. Wing's Computational Thinking Manifesto

The Center for Computation Thinking at CMU has more information about the subject.

We talked briefly about Computational Thinking back in 2006. Recently I listened to Jon Udell's interview with Jeannette Wing and realized that it's time to bring this subject up again for discussion.

Brumley, Poosankam, Song & Zheng, 2008. Automatic Patch-Based Exploit Generation is Possible: Techniques and Implications:

The automatic patch-based exploit generation problem is: given a program P and a patched version of the program P′, automatically generate an exploit for the potentially unknown vulnerability present in P but fixed in P'. In this paper, we propose techniques for automatic patch-based exploit generation, and show that our techniques can automatically generate exploits for 5 Microsoft programs based upon patches provided via Windows Update. Although our techniques may not work in all cases, a fundamental tenet of security is to conservatively estimate the capabilities of attackers. Thus, our results indicate that automatic patch-based exploit generation should be considered practical. One important security implication of our results is that current patch distribution schemes which stagger patch distribution over long time periods, such as Windows Update, may allow attackers who receive the patch first to compromise the significant fraction of vulnerable hosts who have not yet received the patch.

The technique is based on flow analysis, to test code that gets changed for boundaries where safety properties fail. The limitations of the technique they have developed automatically generate vulnerabilities for only a small fraction of propagated updates. Nonetheless I find it astonishing that such a simple analysis can provide such a payoff. Via Bruce Schneier.

A first installment of a booklet by John Barnes titled Safe and Secure Software: An Introduction to Ada 2005.

The purpose of this booklet is to illustrate the ways in which Ada 2005 can help in the construction of reliable software, by illustrating some aspects of its features. It is hoped that it will be of interest to programmers and managers at all levels.

It must be stressed that the discussion is not complete. Each chapter selects a particular topic under the banner of Safe X where Safe is just a brief token to designate both safety and security. For the most critical software, use of the related SPARK language appears to be very beneficial, and this is outlined in Chapter 11.

The introduction is rather amusing, so even non Ada fans may want to take look.