Lambda the Ultimate

I'm doing work on designing languages for probabilistic reasoning.

In probability theory, it seems that random variables play the part of a bridge between the informal and the formal. They are defined as functions

Z : Omega -> S

where Omega and S are "sample spaces" (sets that can be quantified by probability measures). Formally, Omega and S are both well-defined. In practice, Omega seems to be regarded as the set of all possible realities, which Z can operate on and return formal values in S. (It seems that it has to be, or probability users couldn't use probability theory to theorize about real-world phenomena.)

I was recently reading Olin Shivers's excellent dissertation, in which he states that free variables can be seen as bridging the informal with the formal. In other words, a program that consists of just an identifier "x" (assuming valid programs can have free variables) can be taken as meaning

x  ; to be changed later by some external, informal process

or that the context of "x", which "x" will be embedded in later by an external process, will determine its value.

I'm interested in explaining random variables in familiar terms. Besides Shivers's observation, I've had I/O functions suggested. What have you come across that can be regarded as bridging the informal and the formal?

Neil T

I have an idea: what if we can convert a class to an interface with only a requirement that the class just need implements all the member of the interface without point out the interface in its declaration (this is similar to duck-typing but it has different principle, though i didn't know about duck-typing before writing the article). And when using an object with unknown type, I think the dynamic type isn't a perfect solution (because many error-exception could occur at runtime). To read complete article, please go to this link: http://dakurai.blogspot.com/2009/06/new-wild-idea-in-oop.html . Please read and give me some reply. Thanks you.

Background

In traditional formalisms, programs are texts that conform to some concrete syntax. These are presented to a computing system which interprets them and produces output.

In graphical programming languages, the notion of a "text" is generalized to include various forms of diagram rather than simply linear texts. But graphical languages can still be regarded has having a concrete syntax - it just happens to be a diagram syntax.

Visual programming systems (e.g., Scratch) offer dynamic graphical languages, usually over simple object models. Thus, as a programmer edits the diagram which defines a program, interpretation of the diagram is interleaved and the effects of program changes immediately appear in the running program.

Drawbacks

Relative to string-based languages, graphical languages typically suffer the drawback of limiting the kinds of transformations that are conveniently available to write programs. For example, when writing C programs we certainly make use of transforms that can be expressed using a C pre-processor but, beyond that, it is often helpful to write simple text processing programs (e.g., sed or AWK programs) that carry out global transformations on large bodies of source. I see no theoretical obstacle to having similar tools for graphical languages but they do not seem to be common. Perhaps this situation will change as more mature, more general purpose graphical languages arise.

Even text-based languages suffer from weaknesses in how user-initiated program transformations are handled. For example, consider two (textual) programs which differ by the systematic renaming of some globally visible function. Typically, software development tools regard the change between these programs in terms of retroactively computed "diffs" - a note of which lines of code have been altered. In "diff" format, the information content of the transformation - the renaming of a function - is lost. The information is lost in the sense that if we begin with the original program, then make unrelated changes (say, simply reformatting the code), and then try to apply the diff - we usually will not get a new program with that function successfully renamed.

One response to this drawback can be seen in contemporary "integrated development environment" editors. It is common and popular, these days, for such editors to have features which automate various commonly used transformations, such as renaming a function (and updating all callers). Taken to an extreme, such editors become fully "syntax directed editors" in which all changes to a program text are expressed as transformations that are sensible from the perspective of an underlying abstract syntax. Still, the concrete syntax of the underlying program is king in these systems: it is what is saved on disk or in revision control systems and it is the input to interpretation. For example, using a syntax directed editor on a program does not help someone else to merge the transformations you performed into a related but variant copy of the program, nor is there a handy record of the transformations for other programmers to study to try to understand the program.

Gestures and Visualizations

Consider a language defined in terms of an abstract syntax but, for the moment, not given a concrete syntax. Any language you like can be "reduced" to such and we can use "'" ("prime") to denote that: C' is C without concrete syntax (hence to CPP, either); Scheme' is Scheme without surface syntax, etc.

Given such a language, two useful constructions can be made: a class of concrete visualizations for the language and a basis set of abstract transformations of programs.

Visualizations are simply various means of presenting the abstract syntax of a program - pretty printing, picture drawing, etc.

Gestures are a class of abstract transformations on abstract syntax objects that form a basis set and have certain compositional properties. The basis set of gestures is minimally sufficient to construct any possible abstract syntax object as a series of transformations that begin with a "null program" (e.g., "main(){ return 0; }"). Gestures can be composed (yielding more complex gestures).

Programs as Edit Histories

Consider the "hello world" program. One way to describe in C is (essentially) "main() { printf ("hello world\n"); return 0; }". The same program could be described as gestures: "begin with the null program; insert an initial statement which is a call to 'printf'; pass the constant string 'hello world\n' to printf."

If we drop the first part of that gesture ("begin with the null program") we're left with a parameterized gesture: it takes any program as input and modifies that program by inserting the printf call at the top of 'main'. If one started with the null program and applied the hello world gesture twice, presumably the result would be a program that printed "hello world", twice.

Programs in any of our "primed" languages (C', Scheme') can be regarded not as a string in a concrete syntax but, rather, as a transcript of the gestures used to form the program.

Gesture transcripts, of course, have some semi-algebraic properties. For example, a transcript that inserts the hello world printf 3 times and then deletes one printf is recognizably the same program as a transcript that only inserts the printf twice: the equivalence is reflected in the final abstract syntax object constructed from the gesture transcript.

Interesting Possibilities

One simple but potentially powerful observation is that if programs are gesture transcripts, then programs are also revision control records: the two become one and the same. Contemporary and historic revision control systems struggle at fundamental operations such as "merging" the changes made in one version of a program to a variant version of the program. They struggle because, as mentioned above, they work with textual differences rather than with the desired semantic transformations. Gesture based languages could begin to repair that situation.

Perhaps more interestingly: consider the myriad possibilities that arise if we permit:

• annotations to gestures (commenting)
• attachment of verifiable assertions to gestures (applicability and effect checking)
• programmatic generation and transformation of complex generators (macros)

The concept suggests to me that we could build "Domain Specific Programming Systems" rather than traditional "Domain Specific Languages". That is, in place of a traditional language definition - a concrete syntax over an abstract syntax over a semantics - we would have at core an abstract syntax and a semantics, sure, but atop those an integrated editor command set, revision control record type specification, and an extensible means of defining what constitutes "correctness preserving" transformations on programs (for some definitions of "partial correctness").

What Would it Look Like? How Can it Be Built?

There are many ways in which a C' or Scheme' (or YourFavoriteLanguage') system could be built. I'll sketch one that seems practical to me, although it is not a small job, and from this sketch we can get at least one imagining of what a system would "look like" in practice and real-world use.

Let's choose C' for a concrete example.

The abstract syntax of C' can be derived from the specification of C and described as an XML Schema (that is to say, as a sub-type of XML data objects generally). Given a C' program that has been reduced to an AST in XML form, it is a trivial matter to "pretty print" that XML as standard C code and pass the result to an existing C compiler. We thus obtain, fairly trivially, an interpreter for C' abstract syntax trees.

An XML representation for abstract syntax objects affords a wide range choices for how to define and implement gestures. For illustration I'll choose a certainly imperfect and ad hoc technique: gestures for C' can be defined to be a subset of XSLT programs. For those less familiar, XSLT programs are programs in a widely implemented, simple, functional language for expressing tree transformations on XML data. The input to a gesture program is in part the abstract syntax object of a program but additional parameters (e.g., a number or string provided by a user) can also be provided. If suitable conventions are created, gestures-as-xslt can be referenced and accessed by globally unique name. XSLT programs are themselves XML datums and they can be extended in ways that support annotations such as the verifiable assertions we want to add to gestures. XSLT programs can be modular and automatically constructed. (Summary: XML and XSLT give us a simple but workable programming environment for tree transformations, suitable to the task at hand.)

Visualizations are then easily programmed as XSLT transformations, CSS, and optionally Javasccript to render programs in browsers in any number of ways. Interactive editors for transcripts of gestures fall out of this naturally.

One example benefit I mentioned earlier was the notion of directly using gesture transcripts as the unit of storage in revision control systems so as to, for example, improve the quality of support for complex merging of changes among variations on a program. How would this work? Well... a "transcript" can be defined as a member of a slender subset of all XSLT programs that have the form of a simple composition of primitive gestures and other transcripts along-side user-supplied parameters. C.f., for example, Darcs for an introduction to the semi-algebraic ways in which archives of such compositions can be manipulated to implement familiar revision control system practices.

Summary

The hypothesis argued for in this piece is that:

Concrete syntaxes are the wrong input to programming systems.

Programming languages should be defined in terms of an abstract syntax and a semi-algebraic structure of transformations of abstract syntax objects. We dub these transformations "gestures".

We regard programs as transcripts of gestures that, beginning with the null program, produce the desired program.

This understanding of programming affords the possibility of multiple ways to visualize a program and edit a program.

This understanding of a programming unifies (roughly, identifies) a program with its revision control history.

Through extensions such as annotating gestures, verifying assertions in gestures, and automatically generating gestures a new and interesting approach to domain specific programming systems is revealed.

It is not a small project but not a hard project to begin to build such a thing.

Disclaimer: The author is not aware of prior work that is quite like this but welcomes news of such.

-t

The Myth of the Genius Programmer, Brian Fitzpatrick and Ben Collins-Sussman, Google I/O Conference 2009

This video is tangentially off topic, but I think it will be of interest the community here. There are several aspects that mesh with various ideas on the Meta-LTU Thread.

One recurring theme in Ben and Brian's talk is that while you usually cannot solve sociological problems via technology, there are often small software tweaks that you can do to significantly improve the behaviour of people using a computer network. Choosing the right defaults is a rather important task!

They also talk about launching open-source projects, especially with regard to seeking collaborators and building community. It can be done too quickly and early, but they argue that more often this is done too late.

Brian and Ben's talk seems to be, in part, a response to Linus Torvalds' Google Tech Talk on GIT, which used a certain kind of rhetorical hyperbole to express his point. This is in stark contrast to the presentation style that Brian and Ben used.

Now, I suspect that many people will like one of the talks, and dislike the other, but I actually really like both. Linus's talk focuses mainly on the technical decisions behind GIT, and lambastes some of technical decisions behind SVN, which Brian and Ben started. Brian and Ben spend some time defending some of the decision making that went into SVN, although they adopt an agnostic "wait and see" attitude on the technical differences.

A major part of Linus's sales pitch is that GIT tends to hide "bad branches" and encourages experimentation, so that you don't have to know what everybody else is doing. Ben and Brian point out the importance of community and the value of documenting failure. I should emphasize that their reasons for documenting failure is not for ridiculing or disciplining programmers, but rather to help others learn from these mistakes, and hopefully help to avoid them in the future.

I daresay that discussions on LtU usually have a very "Brian and Ben" tone to them. In an interesting parallel, I'll point out that I found this via Reddit, and I find the discussion of this particular story there to be sorely disappointing thus far. Reddit is built on different technology, serving a larger community, and has it's own unique community dynamics.

So, to summarize, these two talks are polar opposites in communication style. They both discuss community dynamics, and while there is some disagreement in the respective ideals, there is much more agreement than there is disagreement. They both emphasize importance of the "right defaults" and the ability of technology to impact community behavior. And of course, there is discussion of version control systems, something that should be of interest to every serious programmer.

If you have a language with extensible records (like those of Gaster and Jones), and you view functions like a -> Maybe { r } for some row r as patterns, are there practical obstacles that prevent you from extending the environment of a case alternative with the row of the result type of its controlling pattern?

I would appreciate pointers to anywhere that this is discussed in the literature, or an explanation of why it is a bad idea. Google hasn't been especially helpful.

-- concrete syntax for records is entirely made-up

wildcard_pattern = const Just {}

-- without first class labels, the compiler would have to make a whole family
-- of declarations like this, one for each variable bound by a pattern
variable_pattern_x val = Just { x := val }

-- same comment applies
as_pattern_x pat val = case pat val of
                         Just rec -> { x := val, rec }
                         Nothing -> Nothing

-- I'm not 100% sure that this handles laziness correctly, but you get the idea
-- declarations like this would be automatically generated from the datatype declarations
cons_pattern pat_head pat_tail [] = Nothing
cons_pattern pat_head pat_tail (x:xs) = case pat_head x of
                                          Just rec_head -> case pat_tail xs of
                                                             Just rec_tail -> record_join rec_head rec_tail
                                                             Nothing -> Nothing
                                          Nothing -> Nothing

nil_pattern [] = Just {}
nil_pattern _ = Nothing

A constraint programming system combines two essential components: a constraint solver and a search engine. The constraint solver reasons about satisfiability of conjunctions of constraints, and the search engine controls the search for solutions by iteratively exploring a disjunctive search tree defined by the constraint program. In this paper we give a monadic definition of constraint programming where the solver is defined as a monad threaded through the monadic search tree. We are then able to define search and search strategies as first class objects that can themselves be built or extended by composable search transformers. Search transformers give a powerful and unifying approach to viewing search in constraint programming, and the resulting constraint programming system is first class and extremely flexible.

Those of you who apply advanced PL ideas to operating systems might be interested in the upcoming PLOS 2009 workshop. See the abbreviated CFP below, and please consider submitting a short paper!

Thanks! ---

Eric.

Historically, operating system development and programming language development went hand-in-hand. Today, although the systems community at large retains an iron grip on C, many people continue to explore novel approaches to OS construction based on new programming language ideas. This workshop will bring together researchers and developers from the programming language and operating system domains to discuss recent work at the intersection of these fields. It will be a platform for discussing new visions, challenges, experiences, problems, and solutions arising from the application of advanced programming and software engineering concepts to operating systems construction, and vice versa.

Please visit the Web site for more info: http://plosworkshop.org/2009/

At some point we will need to discuss Google Wave and its connection to the google web toolkit (GWT), but for the moment, this piece might be of interest.

The Code Generation conference is Europe's leading event on the practical application of Domain-Specific Languages and Model-Driven Software Development.

30+ sessions from leading practitioners are designed to enable participants to get the most from the tools and technologies in these emerging areas.

This year's event runs from June 16-18 in Cambridge, UK.

1, 2 and 3 day packages are available. Visit the Code Generation 2009 web site for more information.

WHAT PEOPLE SAID ABOUT OUR PREVIOUS EVENTS

"The combined—for that matter, individual—expertise present was remarkable, and presented a tremendous opportunity for knowledge exchange."

"I enjoyed the conference very much, it has been the best conference of the last years I’ve been to. A very good selection of speakers, but I also think that the level of expertise of the audience was very high, much higher than I expected. ... it gives the opportunity to dig much deeper."

"I've been working in domain-specific modelling for a dozen years … and in this time this has been the highest-quality conference on this topic that I've been to - and I've been to a few."

"Three very long, exhausting but thoroughly enjoyable and very informative days."

"The presentations were all top quality, making it often difficult to decide between the concurrently running sessions."

CG2009 is sponsored by Microsoft, Soft Fluent, itemis, Kennedy Carter and others.

Event supporters include InfoQ.com, OMG, IASA, ACCU, and Skillsmatter.

Phil seems to have made the mistake most of us make from time to time: failing to follow the classic interpreter pattern in handling the environment (from SICP, not GoF!).

It seems such a trivial thing... But if you don't handle the env correctly, it is bound to bite you in the a** sooner or later. It's one of the many things SICP and EOPL teach you without belaboring the point - so subtly in fact that you can easily fail to keep the message firmly in mind when you set up to implement your own language.

I am pretty sure I wrote here about the time I made this mistake, but I haven't managed to find that post in the archives.