30.12.05

The Perils of JavaSchools, by Joel Spolsky

Maurice Naftalin and Peter Buneman both sent me pointers to this blog entry on the same day. (Peter claims to be the faculty member described in the entry as having almost killed the writer.)

My favorite quote:

I have never met anyone who can do Scheme, Haskell, and C pointers who can't pick up Java in two days, and create better Java code than people with five years of experience in Java, but try explaining that to the average HR drone.


And another favorite quote:

Without understanding functional programming, you can't invent MapReduce, the algorithm that makes Google so massively scalable. The terms Map and Reduce come from Lisp and functional programming. MapReduce is, in retrospect, obvious to anyone who remembers from their 6.001-equivalent programming class that purely functional programs have no side effects and are thus trivially parallelizable. The very fact that Google invented MapReduce, and Microsoft didn't, says something about why Microsoft is still playing catch up trying to get basic search features to work, while Google has moved on to the next problem: building Skynet, the world's largest massively parallel supercomputer.

7.12.05

LINQ: Microsoft goes functional

I finally had a chance to properly look at LINQ.

This is competitive with the DB end of Links. One can write (typed) expressions in the programming language that compile into SQL access. I would say that Links integrates this in a slightly smoother way than LINQ, but the difference between the two is small. So if Links is to establish itself, it will need to focus on client-server integration rather than server-db integration.

What's most interesting about LINQ is the number of ideas from functional programming and programming languages that it incorporates. Functional programmers will see many old friends here, including lists (masquerading as IEnumerable), lambda expressions (with compact syntax: v => e), fold, and the old idea that syntax in the language is just sugar for a sequence of function calls. They have also brought in the important idea of open classes (where one organization can add methods to a class defined by another, without altering the source code). So a lot of good, basic programming languages stuff is sneaking in under the LINQ banner.

I presume Eric Meijer had a lot to do with this. Well done, Erik!

23.11.05

Ontology is overrated

Recommended by Jeremy Yallop.

Hugh and Dave's Wine Store

Example Web site to implement in Links, and to evaluate (recommended by Rodney Topor):

Hugh and Dave's Wine Store, from Hugh Williams and David Lane, Web Database Applications with PHP and MySQL, Second Edition (O'Reilly, 2004).

21.11.05

Jane Street Capital is recruiting OCaml programmers

Here is their ad:

OCaml Jobs at Jane Street

Are you an OCaml hacker looking for a job where you can program in a good language? Where you can do work that's technically challenging and engages with the real world? Where the people in charge actually care about writing good code? Then send us an application.

Jane Street Capital is looking for people interested in systems administration, software development, and quantitative research (and potentially all three in the same day). We are a rapidly growing trading firm that specializes in bringing programming skills, mathematical tools and scientific thinking to the problem of trading on the financial markets.

We're looking for people with:

* A commitment to the practical. One of the big attractions of our work is the opportunity to apply serious ideas to real-world problems.

* A well-rounded background in computer science. We use a variety of programming languages, so we need people who are comfortable learning new programming paradigms. Our primary programming language is OCaml, so experience with ML or other functional languages is important. Applicants should also have a strong UNIX/Linux background.

* Great communication skills. We need people who can explain things clearly and concisely, who can read dense academic papers and write good documentation.

* A strong mathematical background. This is a must for candidates interested in research, and includes a good understanding of probability and statistics, calculus, algorithms, etc. We draw on ideas from everywhere we can, so we value interest and experience in a range of scientific fields.

Jane Street is an open and informal environment -- you can wear a t-shirt and jeans to the office. The lunches are free, the kitchen is stocked, and discussions are always lively. And it's an environment with a focus on learning, both through formal seminars and classes, as well as through day-to-day conversations with colleagues. The pay is good, and advancement is rapid for people who do well.

If this all sounds too good to be true, there is a catch: we only hire top-notch people. If you think you're up to it, send us an application. We're currently looking for full-time positions as well as summer interns for next year.

Send an application to Yaron Minsky including a resume and a cover letter, as well as some sample code if you have anything you're particularly proud of.

17.11.05

W3C tackles rich web clients

Rodney Topor for points out there is a new W3C activity on rich web clients.

Web APIs
Web applications

Computer Science Unplugged

Don Sannella writes:


I wrote:
> there is some
> child-friendly stuff around about algorithms, for instance a card
> trick that illustrates a simple error-correcting code. (I recall
> seeing a book full of such things, and will try to track it down.)

"Computer Science Unplugged" by Tim Bell, Ian Witten, and Mike
Fellows. I found a copy on the web at

http://www1.idc.ac.il/csu/CSU%20book/unplugged%20book%20part1.pdf
and so on, up to
http://www1.idc.ac.il/csu/CSU%20book/unplugged%20book%20part1.pdf

or buy it at

http://www.lulu.com/content/166249

Don

7.11.05

FP in the real world: Raschke on XML in Python

Many thanks to Francesco Cessarini, who organized an informal get together of Erlang programmers at Cafe Royale on Sat 22 Oct.

Afterwards, Robert Raschke sent me a description of how he uses FP in Python to process XML, not as an academic exercise but as part of his day job. Follow the link above. Thanks, Robert!

26.10.05

SPLS, 25 Oct

The Scottish Programming Language Seminar goes from strength to strength. We consistently have thirty to forty researchers coming from across Scotland, and the range and quality of talks is excellent. All of this with very lightweight organization and coordination.

About thirty souls turned up at Stathclyde, coming from Glasgow, Edinburgh, and St Andrews, and visitors from as far away as Australia. There were five talks, ranging from semantic theory to hardware design. Alex Simpson described an elegant (and beautiful and surprising) way to extend Reynold's semantic parametricity to Moggi's computational lambda calculus. Wim Vanderbauwhede presented a Scheme-like language for programming "Systems on a chip" consisting of hardware modules interconnected by a chip-wide network. Greg Michaelson introduced Hume, an attempt to put fp to work on real applications producing embedded systems with guarantees on the time and space used; they are applying the system to real vision problems in automated vehicles. Joe Wells provided a clear introduction to a calculus for linking, with strong technical results (can be analyzed in close to quadratic time, where the first analysis proposed in this area was NP complete). I liked that he focussed on the simplest possible calculus that could express the problem. Edwin Brady explored how a dependently typed language similar to Epigram can express resource bounds; Epigram is beginning to look familiar to me and I quite like it.

Many thanks to Strathclyde and David Lievens for organizing the meeting. The next will be at St Andrews in January 2006.

Draggable lists

Ezra proposes draggable lists as an exemplar of what we should be able to do with interactive Javascript in web applications (sometimes called AJAX). Great example!

19.10.05

Rodrigo Barnes writes:


Prof Wadler

You probably saw this already, but there's an interesting book covering a lot of the state of the art the Links project tackles (problems/solutions for web application development): 'Beyond Java' by Bruce Tate (O'Reilly, 0596100949)

A large part of it is an exposition of the benefits of Ruby (esp. Ruby on Rails) v. Java frameworks, but he does mention erlang and Haskell and there's a good chapter on Seaside on Smalltalk (a continuation server).

What I find interesting is that this is coming from industry rather than research, but does deal with language issues, if only on a superficial level. Tate has written some good books 'Better, Faster, Lighter Java' and 'Spring, a developer's notebook' which mark a progression away from the 'official' Java enterprise line. This is a line I've been following, as I think I've mentioned previously.

He's not very complementary on generics in Java as he says it is a language rather than JVM based implementation (so you don't get type safety when you integrate with non generic collections code).

http://www.oreilly.com/catalog/beyondjava/index.html

Regards

Rodrigo


No, I had not heard of the book, but I'll check it out. Thanks, Rodrigo!

16.9.05

FLOPS 2006

The call for papers for FLOPS 2006 is now out.

FLOPS benefits from an eclectic mix of FP and LP papers, one of
the few venues where the two communities get together.
It should be a congenial meeting, situated under Mt Fuji.

We have two excellent invited speakers.
Peter van Roy, on Mozart
Guy Steele, on Fortress (just confirmed)

Do come!

Ronnie Brown: Allow Beautiful Minds to Thrive

Copyright 2005 TSL Education Limited
The Times Higher Education Supplement

September 16, 2005

SECTION: LETTER; No.1709; Pg.17
LENGTH: 448 words
HEADLINE: Allow Beautiful Minds To Thrive
BYLINE: Ronnie Brown

BODY:

The British Association for the Advancement of Science warns that the research
assessment exercise does not recognise the importance of the public
communication of science ("Scientists want time to talk", September 9).
Experience in the mathematics faculty at Bangor was that the Teaching Quality
Assessment did not recognise it either.

This is a kind of travesty. Exploration, exposition and communication have for
centuries been recognised as essential to the progress of science.

Where would we be without Euclid's marvellous compilation of the geometry of his
day? Galileo, Faraday, Poincare, Klein, Hilbert, Einstein, Hoyle and Feynman
have all made public communication, and often disagreement with authority, an
important part of their work.

Our aim for the popularisation of mathematics has been, to modify Science
Minister Lord Sainsbury's words in the same issue of The Times Higher, to show
the public, students and the Government not only the important role that
mathematics plays in society, but also how it evolves.

Mathematics progresses partly through the solution of problems, but also through
clarification and good exposition, providing a developing language for
description, verification, deduction and calculation. It makes the difficult
easy. It works over a long timescale. It shows new possibilities through gradual
conceptual advance. It formulates new problems.

So mathematics is a foundation of the modern technological society. It is a
considerable challenge to try to show advanced mathematics from an elementary
viewpoint.

Some results of our work in popularisation of mathematics at Bangor over the
past 20 years may be seen on our website www.popmath.org.uk. We have had strong
support from, among others, the patrons of the sculptor John Robinson, for
promoting his Symbolic Sculptures.

An unplanned consequence has been sculptures by Robinson at, for example,
Bangor, Cambridge, Durham and Macquarie universities.

This supports the aim of associating mathematics and science with art, and
demonstrates art as a mode of symbolising an idea.

Work in communicating to children and the general public ideas in mathematics
has helped us to analyse and express our programme, to communicate mathematical
concepts to fellow scientists and students, and so to interdisciplinary
collaboration.

For the future of the UK, the public communication of science and mathematics
should be supported financially and in career structure, and be part of the
assessment of the success of a university and of the vitality of research and
teaching teams.

Ronnie Brown Emeritus professor of mathematics University of Wales, Bangor

15.9.05

LINQ

From Jeremy Yallop:

The LINQ Project is a codename for a set of extensions to the .NET
Framework that encompass language-integrated query, set, and
transform operations. It extends C# and Visual Basic with native
language syntax for queries and provides class libraries to take
advantage of these capabilities.
http://msdn.microsoft.com/netframework/future/linq/
(via http://lambda-the-ultimate.org/node/view/967)


There are facilities for "XML programming" as well, including querying XML data. They even "borrowed" our name!

9.9.05

Jeremy's Links demo page

New page of Links demos, contrasting two ways to do "todo" lists, state in the client and state in the server, and showing off our new syntax for specifying whether code executes on server or client.

18.8.05

Doron Zeilberger on how to explain mathematics

The Gelfand Principle: use the simplest example; Buchberger's White-Box and Black-Box principle: learn how to execute a process in detail, then suppress the details. Together with a real-life example of how to apply them to simplify exposition.

Logicomix

A comic about logic's role in the history of the 20th century, featuring Cantor, Russel, Godel, and Turing. I can't wait! (I learned about it from the article copied below.)

Maths isn't just for textbooks

[Thanks to Peter Freyd for posting this to the Categories mailing list. -- P]

Maths isn't just for textbooks
The Independent, 15 August 2005
by Boyd Tonkin

The progress of mathematics abounds in tall tales and unlikely stories. And they don't come much more improbable than this. Outside, the July sun of the Aegean is hammering down on a coastal hotel in Mykonos. Inside, America's most charismatic statistician addresses a gathering that can boast several of the world's top mathematicians as well as a motley assortment of science writers, novelists, historians and theatre people. And what is he doing? He's performing a card trick.

Persi Diaconis, now of Stanford and Harvard Universities, once made his living this way. As a teenage prodigy, he toured the US as junior sidekick to one of the most famous magicians of the age. Then, via gamblers' after-hours talk of odds and probability, the sorcerer's apprentice caught the maths bug and took the first steps towards a career in another sort of spotlight. Diaconis was the expert who unmasked the delusions behind the so-called "Bible Codes" (which supposedly revealed hidden meanings within the text), but today in the Aegean, he's merely baffling his peers.

He chucks a deck of cards towards this highly qualified audience. It's caught by Timothy Gowers, a professor at Cambridge and recipient of a Fields Medal - the maths equivalent of a Nobel Prize. Gowers cuts the pack, takes the top card, then passes it to a neighbouring titan, who himself passes it on. After five cuts, Diaconis asks holders of red-suited cards to stand up. Two do. He then proceeds to tell all five punters exactly which card they hold. Cue a burst of awestruck applause.

How does he do it? Diaconis quips that "magicians aren't allowed to explain their secrets and mathematicians can't explain their secrets". But he tries. The root of card-recognition tricks lies in the De Bruijn Sequences, a branch of what's called "combinatorics" - a discipline with a long history that stretches from the counting patterns used in Indian classical music to the coded instructions for robots used today. The mathematicians grasp the theory easily enough, but the mind-boggling mental speed of the practice still confounds them, and me.

This is a taste ofthe first Mykonos conference on Mathematics and Narrative. Arranged by a group known as Thales and Friends, after the ancient Greek geometer and philosopher who reputedly measured the Pyramids, this unprecedented project to bring scientists and storytellers together was the brainchild of the polymath Apostolos Doxiadis. Worried that the maths he loves has drifted too far out of the cultural mainstream, Doxiadis has already done more than his share of bridge-building. His novel Uncle Petros and Goldbach's Conjecture (Faber) helps to convey the life-enhancing, and life-consuming, attraction of pure mathematical research.

Rebecca Goldstein, a philosopher and novelist who writes in her fiction about the "essentially tragic" lives of mathematicians, called her pet subjects "as bad as novelists in terms of ego". John Allen Paulos, who writes funny and instructive books, such as Innumeracy, about the misuse of statistics in the media, jokes: "How do you define an extravert mathematician? Someone who looks at your shoes when he's talking to you."

If you want evidence of the problem that confronts them, look no further than today's newspapers. Millions of people now enjoy Sudoku puzzles. Forget the pseudo-Japanese baloney: sudoku grids are a version of the Latin Square created by the great Swiss mathematician Leonhard Euler in the late 18th century. Yet these legions of amateur problem-solvers tackle puzzles accompanied by the absurd assertion that "no maths is involved". In parts of popular culture, mathematics has become not so much the love that dare not speak its name as the love that doesn't even know its name.

So, as the sun blazed and the sea sparkled off stage, we heard stories about the extraordinary rhythms of breakthrough and breakdown that punctuate the history of modern maths, and stories about the thinking and imagining that mathematicians do on the cutting edge of creation. John Barrow, another Cambridge professor, related the story of how his play Infinities reached the stage. Marcus du Sautoy, Oxford mathematician and Channel 4 pundit, delivered his multimedia gig about the mysteries of prime numbers and the long quest to prove Riemann's Hypothesis. The show took in David Beckham's Real Madrid shirt (a prime 23), some raucous audience participation and Professor du Sautoy himself on a surprisingly sweet trumpet.

Less noisily, Tim Gowers ended his plea for concreteness and compression in mathematical explanations with some favourite passages from Alan Hollinghurst, Don DeLillo and Jonathan Franzen - to highlight the skills that good novelists have and most mathematicians lack.

Of course, some writers and producers have turned to the lives and the works of mathematicians for inspiration. A gifted populariser such as Simon Singh can now sell in the hundreds of thousands - as he did with Fermat's Last Theorem. Sylvia Nasar's bestselling biography of the game-theory pioneer John Nash, and his decades-long mental illness, led to the big-screen adaptation of A Beautiful Mind. This familiar, Rain Man model of the pattern-seeking maths prodigy as a recluse, an idiot savant, or downright barking mad, recurs often - for instance, in fictionalised portraits (such as Enigma) of the computer prophet and Bletchley Park cryptographer Alan Turing. And it even underlies Mark Haddon's The Curious Incident of the Dog in the Night-time, with its Asperger-afflicted teenage narrator, always ready to reel off a series of prime numbers.

Not surprisingly, real mathematicians have mixed feelings about mass-market yarns that present their domain as the stamping-ground of eccentrics, or even lunatics. But, for the most part, they applaud the endeavour to dramatise the human struggle of mathematical reasoning. Only one (absent) literary figure really fell foul of the Mykonos mob: the American writer David Foster Wallace, who in Everything and More wrote not a novel but a purported history of the mathematics of infinity. The computer-science guru Martin Davis counted "86 really egregious errors" in Wallace's book. "Are we so hard up for approval from the humanities that we have to accept this?" he thundered.

And yet the history of modern maths features such a wealth of near-incredible narratives that certain kinds of faction or docu-drama will exert a huge appeal. After all, this is a field that, early in the last century, plunged into a "foundational crisis" that left its finest minds believing that they stood not on solid rock but on shifting sand. Out of that collective breakdown grew ideas about general computing machines that began as the purest theory but ended up as the intellectual inspiration of almost everything we now do with technology. If mathematics counts as the art of reality, then you might argue that its artistic crisis gave birth to the modern world.

This is the theme of the mathematical narrative that Doxiadis and some colleagues will tell next. Collaborating with the Berkeley-based computer scientist Christos Papadimitriou and the Athenian artists Alecos Papadatos and Annie di Donna, Doxiadis has been working on a ground-breaking graphic novel about the development of 20th-century maths and its makers, from Russell and Hilbert to Gödel and Turing.

Due in 2007, Logicomix will tell an epic human, and political, story. On the one hand, Papadatos, the project's chief graphic artist, depicts the social turmoil, global warfare and deadly ideologies of the last century. On the other, the core story of maths - as with every other brand of creativity - will often come down to the journey of a single mind alone with its dreams, and its demons. "Like a mathematician," Papadatos notes, "a cartoonist works with paper, pens - and a waste-paper basket."

www.thalesandfriends.org

LETTER TO THE EDITOR
Mathematicians struggle for truth
by Ronnie Brown
The Independent, 17 August 2005

Sir: Seeing Boyd Tonkin's article on 'Magic numbers' (15 August) I thought, as a
mathematician, I ought to step aside from my 'essentially tragic life', not
'look at my shoes', stop 'struggling with my demons' awhile, and suggest that
perhaps a wrong impression is given of mathematics as a development of just a
few strange and egocentric minds.

Instead it is a world-wide collaborative effort involving tens of thousands,
struggling to understand, to see what is true and why it is true, and in so
doing to develop a language and notation for description, verification,
deduction, and calculation. It describes structures and analogies. It makes
difficult things easy. So it is a basis for the modern technical world.

Mathematics can also take over for its study what Shakespeare claimed for the
role of the poet: 'And as imagination bodies forth the forms of things unknown/
The Poet's pen turns them to shapes, and gives to airy nothing/ A local
habitation and a name.'

All this explains its fascination, and the joy of communicating at all levels in
the subject.

Ronnie Brown
Emiritus Professor, University of Wales, Bangor

28.7.05

What's next for Google

Charles Ferguson thinks Google and Microsoft will battle over control of the APIs for search.

Eckel on Arnold on Java generics

Arnold thinks generics were a mistake, Eckel mildly disagrees.

30.6.05

Google Maps API

[Courtesy of Jeremy Yallop.] Google has published an API for Google Maps to allow people to embed maps with custom markers into their own pages (which people were doing anyway, via unpublished interfaces).

Lambda the Ultimate, revisited

More Links discussion on LtU, not all of it complimentary.

24.6.05

Service Architectures

A report from a colleague in industry (who prefers to remain anonymous) comparing Erlang with traditional web architectures. A detailed assessment that should be useful input to the design of Links. Many thanks to my nameless friend!

23.6.05

Scottish Programming Language Seminar

Many thanks to Greg Michaelson and Phil Trinder for organizing this meeting!

This is the third meeting of SPLS, and its great to see that SPLS has already grown into what it was intended to be: a robust forum for language researchers in Scotland (and beyond). We had in attendance thirty or forty programming language researchers, from U of Edinburgh, Heriot Watt, U of Glasgow, Strathclyde, and St Andrews, as well as speakers from Nottingham and Hertfordshire, both of whom had traveled to Edinburgh just for the occasion.

Greg Michaelson noted that, as it happened, none of the speakers was Scottish. (Richard is English, Anne is French, Conor is Irish, De Lesley is American, and Sven-Bodo is German.) I suggested that we parse the name differently, and say that it is a seminar for work on Scottish Programming Languages. With POP2, SASL, Hope, ML, Haskell, and (soon, I hope) Links, we have quite enough to keep us busy!

We were hosted by the International Centre for Mathematical Sciences, which is located in the house in which James Clerk Maxwell was born. I work in The James Clerk Maxwell Building in the north campus of the University of Edinburgh, affectionately known as JCMB to its inmates (and rather a cheek in naming, as Maxwell's main connection to Edinburgh is that they refused to hire him). It was a pleasure to visit the other JCMB, which is more appealing in appearance. Cheers to Greg and Phil for finding a wonderful venue.

Richard Connor, Strathclyde University
Typed vs Untyped: performing a real experiment?

Put forward the excellent idea that we should actually try to experimentally measure what impact type systems have on programmer productivity and program reliability and maintanability. Unfortunately, I suspect this will fall foul of a symptom I noticed years ago in papers that report experiments on programming languages. If the person who wrote the paper believed that imperative languages were better than functional languages, thenthat is what his experiments proved, and if the person who wrote the paper believed the opposite then his experiments proved the opposite. Richard's experiment consists of comparing untyped and typed variants of Javascript. But his untyped variant supports the undefined value and his typed variant does not, so its not clear whether he'll be measuring the effects of typing or of flexible null values. I can suggest a number of different experiments, which I suspect would yield rather different results: compare Java 1.4 and Java 1.5 (with and without generics -- this has the great advantage that it is working with two real languages), compare Haskell with and without types, compare Scheme with and without types (using the type inferencer in Dr Scheme for the typed version, so again you have two real languages).

Anne Benoit, Edinburgh University
Enhancing the performance of Grid Applications with Skeletons and Process Algebras

Skeletons with performance models applied to automatically choose the best implementation. Seems like nice work. Unfortunately, I'm not very familiar with skeletons, so I would have benefited from some simple, complete examples to convey the basic ideas.

Conor McBride, Nottingham University
Idioms

A few years ago, John Hughes noticed that sometimes a monad is too strong, and he introduced a weaker structure called 'arrows' with many interesting applications. (Every monad is an arrow, but not conversely.) Conor has now noticed that there is another useful structure halfway between arrows and monads, which he calls idioms. (Every monad is an idiom and every idiom is an arrow, but not conversely.)

class Idiom i where
k : x -> i x
s : i (x -> y) -> i x -> i y

(To see why these are called k and s, take i x = a -> x.) It was a Pearl of a talk, and I encourage him to write it up as a pearl for JFP.

DeLesley Hutchins, Edinburgh University
Feature Oriented Programming

An object calculus that is good for "deep mixin" combination. Unlike most typed languages it is not stratified -- objects and their types are considered to be the same sorts of things, with the <: relation standing for both "subtype" and "instance of". DeLesley presented the motivation of the system and a sketch of how he achieves his goals, a lot to fit in considering the scope of what he is trying to achieve. DeLesley is my student, but I've done little except point him at the literature; he quickly absorbed all of the methods in Pierce's text and Odersky's model of Scala, and put them to good use. David Watt, sitting next to me, commented that it was a very clear presentation.

Sven-Bodo Sholz, University of Hertfordshire
Using Sub-types and Intersection Types to strike the Balance Between Static and Dynamic Typing

An interesting companion to Richard's talk. Sven-Bodo has a functional language for scientific programming with an optimizing compiler that achieves performance comparable to Fortran. (And a compiler consisting of 500K lines of C.) This talk focussed on the type system, which in effect ranges from highly typed to untyped. He has a hierarchy of types for arrays, ranging from no information to specific information.

[*] - any array
[] - any scalar [.] - any vector [.,.] - any matrix
[3] - vector of length 3, [4] - vector of length 4, [2,3] - matrix with 2 rows and 3 columns, ...

The system makes heavy use of intersection types. It tries to give more precise types (lower down in the hierarchy sketched above), but moves up the hierarchy when it is too hard to give a precise type. (It wasn't clear to me under which circumstances it would move up the hierarchy.) This complements Milner's principle: Well-typed programs can't go wrong. In this system, if a program is not well-typed it will typically move up the hierarchy. Hence. one can't guarantee that well-typed programs won't go wrong (unless one inspects them and determines that all subterms are given precise types rather than imprecise types), but one can guarantee that ill-typed programs must go wrong!

A fine day. My thanks to all those who made it happen! The next meetings are scheduled for Strathclyde in September and St Andrews in January.

Why a Lisp fan switched to Erlang

Courtesy of Jeremy Yallop: Joel Reymont's blog entry on why he switched to Erlang (from Lisp) for writing his commercial poker server:

Why Erlang?
Remodelling the house

21.6.05

AJAX examples from Sun

I've been looking for some simple exercises to get started with AJAX. Here are a few, courtesy of Sun.

9.6.05

Scale-free geometry in OO programs

Scale-free geometry in OO programs
Alex Potanin, James Noble, Marcus Frean, Robert Biddle

The only paper on OO that I've really enjoyed reading in the last few years. Points out that the graph representing an OO program is scale-free, meaning that it enjoys a fractal structure similar to the web. One might expect such graphs to have a "typical" scale, where each node has, say, 2.3 outgoing edges on average. But there is no typical scale, because there are lots of nodes with just a few outgoing edges, but also a few nodes with a lot of outgoing edges. Ditto for incoming edges!

Scottish Programming Language Seminar

Next meeting Thursday 23rd June 2005 in Edinburgh. Follow link above for details!

2.6.05

The Unreasonable Effectiveness of Mathematics

I finally thought to find this on the web. The paper from which I stole the title of my inaugural.

Eugene Wigner, The Unreasonable Effectiveness of Mathematics in the Natural Sciences. Communications in Pure and Applied Mathematics, vol. 13, No. I (February 1960)

31.5.05

Concurrency Oriented Programming in Erlang

Joe Armstrong. Concurrency oriented programming in Erlang.
Invited talk, FFG 2003.

This paper is a great introduction to Erlang, more up to date than Joe's invited paper at ICFP, and with more on share-nothing concurrency and on commercial applications.

Some key quotes:

Erlang processes have share nothing semantics - sharing no data leads
to highly efficient code. Traditionally concurrent programs used
shared data, protected by semaphores of mutexs, that reason being
(supposedly) to improve efficiency.

Precisely this sharing of data leads to a number of problems which
ultimately leads to performance degradation.

Constructing systems, as opposed to individual pro- grams, using the
philosophy of share-nothing processes has several significant
advantages:

The system is easily distributable - to turn a non- distributed
program into a distributed program can often be achieve by merely
allocating the different parallel processes to different machines.

The system is easily made fault tolerant - this can be achieved by
arrangements of processes into workers and observers. The worker
processes perform computations, and the observer processes observe the
workers and perform error recovery if anything goes wrong in a worker
process. The worker and observer processes can run on the same machine
(for local error recovery) or on physically separated machines (for
building fault- tolerant systems).

The system is easily scalable - this can be achieved by adding more
processors and moving processes between processors.

AXD301

The AXD301 is a fault-tolerant carrier-class ATM (Asynchronous
Transfer Mode) switch manufactured by Ericsson Telecom AB.

The AXD has 11% of the world market share for carrier class ATM
switches making it the market leader in this market segment.

The measured reliability is quoted as being 99.9999999% (9 nines)
corresponding to a down time of 31 ms. year! - this makes it one of
the most reliable switches ever made.

British Telecom use the AXD301 in their telephony and data backbone,
the system is currently handling 30-40 million calls per week per node
and is the world's largest telephony over ATM network.

The AXD301 has 1.7 million lines of Erlang, making it the largest
functional program ever written.

Richard Brown

I saw a talk on Wed 19 May by Richard Brown, currently an artist in residence in Edinburgh. Like Children Cheering Carpet (see below), his work shows a completely different way to interact computers. I particularly like his Mimetic Starfish from the Millennium Dome: a starfish projected onto a stone table with infrared sensors. If you stretch out your hand to it tentatively, it comes to you; if you stretch out your hand rapidly, it retreats; if you stroke it, colours ripple up its tentacles. Visitors enjoyed stroking it so much that the stone it was projected onto was worn down! I had a vision of an artwork whose purpose was to encourage visitors to, over time, shape a stone in a particular way ...

Children Cheering Carpet

I saw the show by Teatro di Piazza o d'Occasione with my family on Wed 25 May, as part of the Edinburgh's Children Festival.

Children Cheering Carpet is a children's show about a Japanese garden, where the role of the garden is played by an interactive device consisting of (a) an array of touch sensors arranged under a white carpet on the floor and (b) a display projector aimed at the carpet (c) sound system and (d) a Macintosh laptop to run it all. Children were invited on to it and treated to various effects: making music by leaping from stone to stone, chasing flowers drifting across the surface, running to clump together on a leaf. Adam and Leora (age 6) were enthralled, and so were the older children and the adults. For me, it was an insight into a completely different way to interact with computers.

Phil Trinder: No Process Algebra for Links

A suggestion for Links from Phil Trinder.

No Process Algebra for Links

At the Edinburgh Links meeting Jocaml-style coordination was proposed
for links. I'd argue that this is *not* a good design decision, even
though many aspects of the Jocaml design are exactly right.

The key issue is that Jocaml coordination is based on process algebra,
introducing a second stateful notation to Links and causing an impedance
mismatch between the stateless expression language and process
algebra, complicating both language and reasoning.

As Links will require stateful constructs for I/O etc, perhaps
monadic, a far simpler design is to reuse these constructs to specify
and reason about distributed coordination. The programmer specifies
both computation and coordination in a single reduction-oriented
semantic framework. Moreover the programmer can reason equationally
without needing to resort to the process algebra for coordination
aspects. In short, it's unnecessary to have two stateful notations in
Links, one for computation and one for coordination.

The alternative distributed coordination constructs envisaged include
channels similar to those in Jocaml: higher-order and
polymorphic. However the stateful operations on channels are probably
monadic with associated fold & unfold identifies. As Joe Armstrong
recommends, processes should be first class to facilitate fault
tolerance, and the possibility of higher-order fault tolerance
abstractions like Erlang behaviours. First class continuations would
enable the construction of mobile agents.

19.5.05

The Essence of Programming: Reynoldsfest at MFPS

Having just got back from the Reynoldsfest at MFPS, where part of the emphasis was on encouraging folk to look at Reynolds work, let me write down some of what was recommended.

My personal favorites:
Definitional Interpreters (this one changed my life when I was a graduate student)
Gedanken
Towards a Theory of Type Structure
Types, Abstraction and Parametric Polymorphism
The Essence of Algol
Syntactic Control of Interference
Three Approaches to Type Structure (tutorial)
The Discoveries of Continuations (history)

Some papers recommended by others:
The Craft of Programming (recommended by Cliff Jones)
Relating direct and continuation semantics (Filinski's favorite -- this one is tough going)
Separation Logic: A Logic for Shared Mutable Data Structures

Also, while I'm at it, let me recommend
You and Your Research, by Richard Hamming. Want to do Nobel-class research? It's not just a matter of luck. Here is a nuts and bolts guide, from the third winner of the Turing Award.

Two thank yous for Peter van Roy

For FractaSketch. My kids love it!

For "Logic programming in the context of multiparadigm programming: the Oz experience". I always knew Oz was interesting. But, without a lot of time to sit down and write programs, how does one come to grips with a new paradigm? This paper does the trick.

Thanks, Peter!

12.5.05

Dave Patterson on IT funding in US

[Courtesy of Cameron Wilson.]

Dave Patterson (ACM’s current President) wrote a piece in News.com today
about the U.S. Government’s shift away from funding long-term IT R&D.
This is advance of tomorrow's (Thursday, May 12) House Science Committee
hearing on the subject, "The Future of Computer Science Research in the
U.S.," which is at 10:00 a.m. EDT. It will be webcast at
www.house.gov/science.

Darcs, another innovative use of Haskell

[Courtesy of Malcolm Wallace]

Here is a link to 'darcs', the source-code revision control system
written in Haskell, that I mentioned earlier tonight. It is based on a
'theory' of patches, giving it many superior features over other more
well-established RCS systems. When Linus Torvalds recently decided to
move away from using BitKeeper as the RCS system for the Linux kernel,
darcs was one of the contenders he considered to replace it (although in
the end, Torvalds decided to write his own system). -- Malcolm

4.5.05

Two articles on formal computer proof

Two articles on formal computer proof, including Gonthier's proof of the four-colour theorem, courtesy of a summer school announcement from Bengt Nordstrom.

The Economist
Science

29.4.05

Dave Turner on Links

Sorry I probably won't be able to make the Links meeting (shame, since it
would have been a great chance to meet up with old friends). I am going on
holiday tomorrow, so I have a load of stuff to clear off my desk before I
go.

I did get a chance to look at your project proposal though. Generally, I
thought it looks great, though I came up with a few questions/comments which
it may be worth addressing (or expanding on).

1) What are the most costly/difficult aspects of programming a web site.
This is not my area of expertise, but I can take a guess that the following
issues are important:

a) Multi-language development (you already have this covered)

b) Fault tolerance (to network outages etc).

c) Performance constraints (interactive response times etc)

d) Inability to debug in realistic environments (can't have real web
server and database for each developer)

e) Difficult to isolate and test components (eg. I don't want to have to
fire up a real database and web server just to write an automated test for
my gui logic)

f) Performance does not scale well (this includes CPU, memory and
bandwidth scaling problems)

Do you think Links will address all these areas? If not, are you sure that
this will not be a significant weakness of the approach?

2) The Links project proposes to knit together a number of separate
technologies. What reason do you have to believe that they can combined
into a single coherent language?

3) Access to existing library code seems essential if you want to get
realistic web sites to use Links. How do you propose to interface to
existing libraries? Although foreign function calls and the like are well
understood now, I can imagine that the addition of such functionality may
well break your code generation model (for example, calling out to a Java or
C# library means the calling code cannot be moved onto the Javascript client
machine).

4) I would say more about tool support. Emacs modes and the like are well
out of date. Current developers (especially Java and C# ones) are used to
very sophisticated development environments which support integrated
debugging, browsing, refactoring etc. These IDEs can have a significant
effect on productivity, so I would consider integration your tools into a
modern, open, IDE such as Eclipse (which is specifically designed to work
with different languages etc).

Dave

CRA Computing Leadership Summit report Feb 2005

List of problems with how computing is perceived, and strategies for the solution, from a US perspective.

19.4.05

asxcaml

Another project related to Links. Thanks to Alan Schmitt for reminding me of this!

11.4.05

Clone of Google maps using Flash

Another useful pointer from Jeremy Yallop

Somebody's written a
clone of Google maps using Flash.

It's apparently written using a tool that allows you to write in a
".NET language" (C#, VB.NET) and compile to Flash.

I found it via
Chris Double's weblog.

Ajax: A New Approach to Web Applications

One target audience for Links is those writing rich web clients in the style of Gmail, Google Maps, Amaztype, Mozilla Amazon Browser, and the like (see links below). The article linked to above explains key components of this brave new world. Thanks to Jeremy Yallop for the pointer.

Perl 6 in Haskell (PUGS)

While I'm on the subject of Perl and functional languages, here's another message from Will Partain. Of course, his implication in the first paragraph that I would already know of such a thing is completely wrong -- Will is my lifeline for learning this stuff.

Phil, you _probably_ know but just in case: this Autrijus Tang has
been making waves in Perl land, by *actually doing something* about
Perl 6 -- in Haskell! Relevant message below.

As you also probably know, Perl 6 is undergoing the most drawn out
design process in history :-) and the implementation people seem to do
nothing but tweak their VM (Parrot), usually to support Intercal or
something. Autrijus has broken the cycle. (Whether it will be
sustained is another matter.)

Will

PS: Damian is, of course, the "how to write Perl in Latin" guy.

====


From: Damian Conway
Newsgroups: gmane.comp.lang.perl.perl6.language
Subject: Kudos to Autrijus
Date: Thu, 17 Feb 2005 11:02:27 +1100


It's been mentioned to me that some folks were surprised that the design team
hasn't been more effusive in it's support for the incredible job that Autrijus
is doing prototyping the Perl 6 interpreter over the top of Haskell.

We had thought that answering his questions about 1000 times faster and much
more extensively that we ever answer anyone else's (;-) might have indicated
how much respect and admiration we have for the work he's doing. But
apparently not.

So let me publicly state that Larry, Allison, Patrick, Luke, Hugo, chromatic,
and myself find Autrijus's work both amazing and amazingly useful: as a way of
exploring the deeper design and implementation issues, and also as a way for
people to start playing with (and experiencing the real power of) Perl 6.

Well done, Autrijus!

Damian

Higher-Order Perl

By Mark Jason Dominus. Noted by Will Partain. (Thanks, Will!) Takes techniques familiar to functional programmers and transposes them to Perl. I liked the story about the cover.

7.4.05

Links meeting at ETAPS

Forty-plus folk showed up!





Our afternoon treat was a cake modeled after the Bruntsfield Links.





There were lively discussions. Copies of slides to appear on the web page shortly.

6.4.05

Links meeting at ETAPS - enter comments here

Those attending the Links meeting at ETAPS should enter a comment here. (Click where it says "n comments".) Please include

* Your name
* Your institution
* Your web page
* Why are you interested in Links?
* Killer app: what facility could Links provide that would entice users?

You may also wish to answer the following challenge, posed by Simon Peyton Jones.

Describe a language feature or features that is/are qualitiatively better than what we have in either Haskell or ML. The feature does not need to be fully designed yet; but it should be more than content-free e.g. "better reasoning about concurrency". What are the challenges we need to overcome to make it real?

5.4.05

Josef Svenningsson on Links

I'm sorry I haven't responded to your invitation to the Links workshop
earlier. Although it sounds like great fun I have my hands full with
writing up my thesis. Whether or not I'll be participating in the
future depends on who my future employer might be...

I'd still like to make some comments on the project though. First of
all I think the Links project has a lot of potential. I'm absolutely
confident that Links is going to be a really sweet language. There is
also a lot of opportunities for exciting research in the design and
programming experience with this language.

Now to my remarks. Here's a short summary:
One of your primary goals with Links seems to be to make a widely used
language. The mechanisms of language stardom is very complex and
completely different from designing a good language. Below I share
some thoughts on what I think it takes for a language to become
popular these days. The last paragraph talks about types and effects.

I'd like to start by quoting you:
"If we bent our minds to it, could we produce a functional language
that was as widely used as Python? There is reason to believe that
functional languages are particularly well suited to building web
applications."
These are two sentences which have very little in common. The first talks
about a language which is going to be famous and widely used. The second
talks about a technically superior language. I think it is time we learn
from history. Whether a technology becomes standard or widely used has
very little to do with the quality of that technology. As I said above I
am convinced that you're going to cook up a very nice language. But making
it widely used is a whole different mission.

But maybe it won't be that difficult to get Links widely used? After all it
has a "killer app"; web applications. But in my experience this is not
enough to draw attention. What you have to do nowadays to draw attention to
a language is to write a really unique program or system which people will
want to use. Recent examples of this is darcs, the revision control program
written in Haskell. It is a nice piece of software which could have
been written in any language really. To draw attention to Links I think you
should involve some hard core web developers (it is a good idea anyway
to hear what they have to say about the design of the language.) You will
be needing to write eye popping applications. Example of such applications
abound at Google; Google suggest, Google maps, GMail for example.

After getting peoples attention to a language there really needs to be
a lot of example code, libraries and tutorials for people to use and
look at. Haskell still lacks in this respect. And this is because it
is tedious work to write these things, work that one doesn't get score
any academic point with. Companies like Sun and Microsoft can handle
these things by setting their armies of programmers and technical
writers to work.

I find it interesting that you suggest that Links type system should
be equipped with effects. In fact I'm really thrilled by this language
design experiment. As far as I know there is really no knowledge at
all about the practical use of effects in programming so its going to
be interesting to see what comes out of this. Immediate obstacles that
come to mind is for instance debugging. I believe that using print
statements inside a algorithms is still a very common thing to do. But
with monads or effects this suddenly changes the type of my algorithm
making it incompatible with the rest of my program. In Haskell this
has led to some gruesome hacks such as the trace function. Another
thing is common exceptions like arithmetic exceptions and stack
overflow. In Java they solve this by having a special class of
exceptions. This may or may not be the best way to solve the
problem. Finally, since effects are rather fresh ground they might not
be the best choice for a language which is supposed to be widely used.

I hope my tone hasn't been overly patronising. As I said above I think
Links is going to be just great I'm looking forward to seeing it
develop. I wish you good luck with the workshop next week.

/Josef Svenningsson

31.3.05

Amaztype

Jeremy Yallop spotted this cool hack, which uses Amazon web services.

24.3.05

Joe Armstrong on Links

I'd also like to comment on your "new language" initiative -
unfortunately I can't make the April meeting (dates clash) - and it's
unlikely that I can participate in any active sense (I'm asking to see
if this would be possible) - I would however like to "sit on the
sidelines" and try to influence your work in a certain direction.

I'll try to explain:

What's the problem - do we need another programming language?

Answer No and Yes.

No we don't need yet another programming language YAPL but we do need
decent system description language(s).


+-----------+ +-----------+ +-----------+
| | | | | |
| --->---| --->---| |
| | | | | |
| ---<---| ---<---| |
| | | | | |
+-----------+ +-----------+ +-----------+


At a high level of abstraction we can consider the world to be made
up of communicating black boxes.

Some of these black boxes represent software, others hardware, others
objects in the real world.

Black boxes communicate by message passing.

There is no shared data between boxes.

Note: This is how the world works - we communicate by modulating
streams of light or sound - this takes place in time and space and
there is no such thing as a simultaneous update (if you believe
special relativity :-) - this is a phycists view of the world.

Programming language are normally "what goes on inside the black box".

But this I find relative uninteresting and a "solved" problem.

Thus I do not want "Yet another language inside the box" - there
are hundreds (thousands) of these already - why make another.

What happens inside the black box is irrelevant when seen from the
perspective of being "outside the box" - indeed if two black boxes are
observationally equivalent then who cares what goes on inside.

There is a severe lack of languages for describing "what goes on
outside the black boxes"

This is what you should do.

No there is a problem - the real world.

Functional boxes (a la function programming, type systems etc) are
predictable, type safe etc (or they should be :-)

But black boxes representing the real world are not.

Errors can occur in real-world black boxes.

How do we (or should we) describe protocols?

Pure functions are at the level of reliable RPCs - these are
(pretty) easy to describe.

Imagine a "factorial machine" - a black box - you send it an integer
N it replies with N!

A first pass at a description language might be:

factorial_machine is:

int => int

ie a machine that if you send it an integer returns an integer.

How do we introduce the real world?

We need to describe timings and failure

factorial_machine is:

x:int => y:int within 100 ms
when x < 1010
| outofservice

Machines in the real world - may suddenly stop - may be
non-deterministic - may lie - may fail intermittently - may produce
incorrect results occassionaly.

How do we describe this?

Worse - the languages INSIDE the black boxes are all different -
how do we describes types in a language neutral way, that is
nevertheless reasonably efficient (ie not XML :-)

As I see things - we need a hierarchy of languages


L3 - evolution languages
L2 - configuration languages
L1 - protocol description languages
L0 - programming languages

L0 are programming languages - like Erlang, Haskell

L1 are protocol languages - like SDL? - my UBF???

L2 are languages that say how the bits of a system fit together -
language abstraction of things like (say) the red-hat package manager

L3 are evolution languages - language that allow me to express how
(say) the protocols of L1 change with time.

All these should fit together in an aesthetically pleasing manner.

UML is much touted as the universal solution to these kinds of problem -
but I'm not sold - we could do better (a lot better)

That's about what I wanted to say - I probably said it badly -
please don't make yet another L0 - make a family L0-L3 - think through
the handling of failure - non-determinism - evolution - security - trust.

Cheers

/Joe

BTW - If I'm not at the April meeting I will be there in spirit -
please raise these questions on my behalf.

----

And here's my response ...

I think there is a role for yet another programming language, if its not just trying to be a general purpose programming language. Links integrates with databases on the back end and browsers on the front end, and few languages around are designed for that.

On the other hand, the problems you raise are very important ones, and I agree with you absolutely that it makes more sense to focus on these than to focus on questions of language design in a space that is well trodden.

I don't feel ready quite yet to give up on design of particular programming languages and focus exclusively on ways to knit languages together, because I still don't have what I want in a particular language. I might feel differently about that if Erlang had types!

Jon Udell on using Xquery on blogs

Recommended by Andy Gordon. Thanks, Andy!

23.3.05

Warren Harris on Links

Hi Philip,

I've been thinking more about your Links project, and what might be the most important areas to focus on. Previously we had discussed web applications and using a functional language to span the client and server programming as well as bringing good functional language technology to bear on the problem, e.g. types, pi-calculus, Erlang-style RPC, db comprehensions, etc. I think all this would be great, and a tremendous help to the web application developer. But the more I think about it the more I think there's a more pressing need in the computer world, and that is to have a well-designed (functional) shell language.

A functional shell language (fsh?) would be a program I could use instead of bash when I log into a linux system. It would give me command-line, interactive access to all the things I can do with bash -- list files, pipe output between programs, run programs in the background, etc. The difference would be that fsh could bring all that good functional technology to bear on shell programming: higher-order functional programming with lexical closures, strong typing, type inference, efficient native compilation, structural pattern matching, and most of all, sanity to the basic language design.

The ideal fsh would allow seamless interaction between locally-defined functions and linux programs residing in the file system. Languages like perl still depend on a "real" shell to launch linux programs (using 'system' or 'exec') or when creating input or output streams to them ('open'). This both forces the programmer to shift gears slightly to bridge the shell and perl world, and also runs the risk of introducing security holes. Ideally, fsh would provide an automatic way to call linux programs directly and pipe their output back into the program. Additionally, wrappers could be created around common programs (e.g. 'ls') to format their arguments and parse their output to return structural equivalents for easier down-stream processing.

Another area where significant advancements could be made is in pattern-matching. ML does an excellent job with structural matching (CDUCE goes even farther), but string pattern matching is relegated to library routines. A lot of perl's power comes from having string pattern matching embedded directly in the language, although a lot could be done to improve their usability. For instance, rather than matching a pattern and allowing the matching process to implicitly bind variables (e.g. $1), it might be better to express patterns as expressions that mention variables within them, similar to ML's structural matching. For example one might match a host and port with: /host:string ':' port:int/ rather than /(\w+):(\d+)/. Another idea might be to introduce pattern abstraction so that one might define 'addr' as the above pattern, and then reference it later, e.g.: /(host1, port1):addr ' -> ' (host2, port2):addr/ would match two addr patterns delimited by a literal ' -> ' string, and bind host1, port1, host2, port2 in the process.

I think having a solid functional shell could form the basis of a later all-singing-all-dancing-xml-processing web application language, but first-things-first. The key idea here is that this has to be an interactive language that's capable enough for routine control of the system. It's got to look and smell like a shell to start winning the minds of real-world programmers.

Warren

----

And my reply to Warren, with Warren's reply to my reply interleaved.

Philip Wadler wrote:


I like this style of lateral thinking.   But if you do a web search you will find that the functional shell idea has been tried a few times in the past, and never conquered the world.  So I'm not convinced that its worth putting the other Links ideas to one side in order to work on a functional shell.


I did a quick search and turned up a few things:

but I think it's safe to say that none of these are on the path to mainstream adoption. There certainly is a lot more to winning the minds of programmers than having solid underpinnings. I think it's mostly driven by practical matters, and building a community as you attempt to solve real problems. I hope that you don't underestimate this part of the effort.

Just to put one more plug in for making Links a shell language... Real web site administrators are driven to strip production machines down to the bare minimum amount of software running on them -- primarily as a security precaution. I've been questioned in my current job about the need for installing perl or cpan modules on machines that don't absolutely need them. Making Links a replacement for bash could facilitate its adoption by acknowledging this need for a minimal environment. If I could propose a mission statement for Links, I'd say, "#!/bin/links".


However, I was already convinced that a new language should build-in string pattern matching, as in Perl and Python.  XML regular expression types give you almost for free regular expressions as (static!) types for strings.


Regular expressions with static types would be helpful. I'm reminded of ocaml's static typing for format statements -- also very useful.

I hope that you consider more the idea of pattern abstraction, i.e. being able to macro-ize or functionalize common patterns. This would go a long way in facilitating understanding and maintainability of code. In perl, it's a real chore to study patterns and try to understand what they might match. I'm sure you've heard perl described as a "write-only language". I'd personally like to see something more like a yacc grammar, and less like a packed string with meta-characters. In fact, I believe the packed string approach is appealing primariliy due to the lack of abstraction in patterns.

I think it could also be very useful to use common patterns as printers as well as parsers. This is particularly useful for complex yacc-grammar style patterns, but could be equally as useful for regular expressions. (I recall once writing a language grammar in yacc, and then spending a significant amount of time writing a printer to get all the precedence relationships and parenthesization right.) There is a lot of power in having a "print-read equivalence" as shown by the lisp world, and having more powerful tools to facilitate this would go a long way.


The one new thing I take away from your note is that a proper version of exec should work directly rather than via some shell.   That's pretty easy to do, and would make Links attractive as a shell language with almost no extra work.  Thanks for the good idea!


You're welcome. In addition to exec, the forking and piping has to be there too. Perhaps pipes could be generalized into a polymorphic synchronization/streaming/functional-composition operator that would work for passing datastructures between threads as well as strings between shell programs.


May I publish your comment on my blog?  Cheers,  -- P

Absolutely.

Warren

17.3.05

The POPLmark Challenge

Here's a cool idea who's time has come. My student Benjamin Kavanagh
is working on a closely related idea, a tool to support animation
and typesetting (but not proofs) for programming language semantics.
Kudos to the Penn/Cambridge team for formulating a crisp challenge,
an excellent model for promoting research.

The POPLmark Challenge

How close are we to a world where programming language papers are
routinely supported by machine-checked metatheory proofs, where
full-scale language definitions are expressed in machine-processed
mathematics, and where language implementations are directly tested
against those definitions?

To clarify the current state of the art, and to motivate further
research, we propose some concrete benchmarks for measuring progress.
Based on System Fsub, a typed lambda-calculus with second-order
polymorphism, subtyping, and records, the benchmarks embody many
aspects of programming languages that are challenging to formalize:
variable binding at both the term and type levels, syntactic forms
with variable numbers of components (including binders), proofs
demanding complex induction principles, and algorithmic questions.
To keep the challenge manageable, it is intermediate in scale between
`toy' calculi and full programming languages.

The challenge problems are available from the web page

http://www.cis.upenn.edu/group/proj/plclub/mmm/,

with informal definitions of syntax and semantics, hand proofs of the
metatheoretic results, and a prototype implementation.

We encourage users and developers of automated reasoning tools to
attempt the challenges and send the results to the POPLmark mailing
list (from that same web page), which will provide a forum for debate.
Queries and clarifications should also be discussed there. The
POPLmark team can also be mailed directly at provers@lists.seas.upenn.edu.

We are not ourselves automated reasoning experts but rather potential
users; our impression is that current tools are _almost_ at the point
where they can be used routinely. It's time to bring mechanized
metatheory to the masses - go to it!


Peter, for the POPLmark team:

Brian Aydemir, Aaron Bohannon, Matthew Fairbairn, Nathan Foster,
Benjamin Pierce, Peter Sewell, Dimitrios Vytiniotis, Geoffrey
Washburn, Stephanie Weirich, and Steve Zdancewic

14.3.05

A Links suggestion - help please!

I received the following excellent suggestion from Norman Ramsey.
Would someone care to contribute to the Links effort by putting together
the web page suggested? I'll then Link to it from my page. I'll implement
the suggestion myself when I get the time, but it would be wonderful to
have some participation from the wider community.

Norman writes:

I do have one somewhat diffident suggestion, however:
if some of the papers you mention are gathered onto a single web
page, it might make it more likely that people will have read them.

Tom Sgouros

My family (two five year olds, geek averse wife, and geeky I) all enjoyed Tom Sgouros's show, Judy -or- What is it like to be a robot? Old chestnuts about philosophy, strong AI, and the soul turned fresh and funny. The most enjoyable evening I've spent in the theatre in years (and Edinburgh has plenty of theatre).

Simon Patterson at the Fruitmarket

You'll have seen one artwork by Simon Patterson: "The Great Bear" is the London subway map with the names of stations replaced by philosophers, actors, explorers, Italian painters, and the like. All of his artwork involves similar transpositions from one form of representation to another -- perfect for computer scientists! I particularly enjoyed his short films High Noon (heavy-breathing timepieces) and Escape Routine (airplane instructions intersperesed with Houdini). He's on at the Fruitmarket in Edinburgh until 1 May.

The long tail of software

Another recommendation from Will Partain.

10.3.05

Vital

An intriguing Haskell environment. Thanks to Sue Eisenbach for passing this on!

POPL, Plan-X, FOOL

Here are notes on some of my favorite talks at POPL, Plan-X, and FOOL.

Plan-X, 11 Jan 2005.

Michael Carey, BEA, on BEA Liquid Data, an approach to data integration. He notes that BEA developers tend to ignore the strong typing features of XQuery, for two reasons, one trivial and one material. Trivial: developers find it inelegant to have to validate the data after it is created in order to attach type information to it. This is just a matter of writing "validate { ... }" around the XML that creates the data, but they strong resist this. Material: validation can change the data in various corner cases, and so interferes heavily with optimization. I took two points away from this. First, XQuery seems to have failed in the goal of integrating types with queries -- trying to fit well with Schema has inevitably thrown up a lot of road blocks. Second, sometimes seemingly trivial points can be just as significant as material ones; another example of this is how the C-like syntax of C++ and Java helped these languages to spread rapidly.

Alan Schmitt on Xtatic. The pattern matching style of Xduce/Xtatic does not do well with data evolution, unlike XPath, as adding more elements to the data causes matching to fail. I would have thought of this as a bad thing, but Schmitt claims it is good, as the failure tells you where you need to change your code.

The demo session worked well. I particularly liked Fisher and Fernandez's PADX, which I had not seen before.

POPL, 12-14 Jan 2005.

Rob Pike on a programming language for searching Google's data. His neatest example was an animated map, with one pinprick of light for each query sent to Google in one day, correctly located in space and time -- one could watch the pattern of queries flow across the world. The data for the map was generated by a program just a few tens of lines long. The key to the query language is, as Rob noted, a simple idea from the functional programming community: use map and fold as the basis of parallel programming, where the fold is over over associative and commutative operators. Pike's language is based on Google's map-reduce system. (Added 27 Aug 2007: Pike's language is called Sawzall. Later a paper on it appeared here.)

Peter Selinger on a quantum programming language. A lovely presentation of tricky ideas, the first time I had made it through to the end. I finally understood that quantum programming involves two levels of probability, within a state there is the probability attached to each qbit, and then there is the probability of being in a particular entangled state. Selinger explained a clever matrix representation due to von Neuman that captures both levels. He gave a nice explanation of quantum teleportation/quantum compression as two halves of a "use once" isomorphism -- a pair of inverse functions that contain a free linear variable so each can be used only once, where the order of composition determines whether one has teleportation or compression. When I asked him why one should bother with programming languages for computers that might never be built, he pointed to the ability of the language to give precise descriptions of tricky thought experiments, as in the teleportation/compression example.

Pat Hanrahan argued that game processors pose a worthy challenge for language designers. He observes that game processors have a steeper "Moore's law" curve than traditional processors, and hence will outperform them by an exponentially increasing factor.

Dinner on the Queen Mary was fun. Mads Tofte hasn't been active in research lately, and it was great that he showed up to receive the award for Most Influential POPL paper of 1994, for his work on regions.

FOOL, 15 Jan 2005.

There was some question as to whether FOOL would continue after this year, but the meeting was lively and there was a strong concensus in favor of continuing. Benjamin Pierce commented "Most years there is at least one talk at FOOL that, after you hear it, you wish it wasn't accepted. But that wasn't the case this year." Special thanks to Benjamin for serving as chair of the FOOL steering committee for many years, and to Kathleen Fisher for picking up this role going forward.

My two favorite comments, both from the final panel on "Extreme Typing".

Robby Findler: Programmers are motivated to write strong contracts, because the stronger the contract the more likely that blame for a failing program will be assigned to the other guy. This explains why the notion of blame attached to higher-order contracts is important.

Jan Vitek: A recipe for stealth adoption: don't change the syntax of the language, but reinterpret the semantics of the existing constructs. (No one will notice the change anyway!) He was following the mandate to be provocative, but there is a knotty kernel of truth here.

Yet another Links comment.

A Links comment from Chui Tey. Pat Hanrahan of Stanford gave an invited talk at POPL 2005 on a similar theme, arguing that game processors ose a worthy challenge for language designers. He observes that game processors have a steeper "Moore's law" curve than traditional processors, and hence will outperform them by an exponentially increasing factor.

----

Another area worthwhile looking at is in designing languages for the current generation of game machines, where parallelization is important.

It is worthwhile because:
1) Computer game development do not suffer the constraints of corporate programming, and are more adventurous with tools. A lot of games run with embedded scripting languages. Why not have highly parallelizable functional languages for computer generated graphics?

2) Existing languages are inadequate, and it has taken several years for developers to learn how to squeeze performance from the Sony PS2 architecture.

3) Computer gaming is a big industry, so there will be sufficient commercial interests in the project

4) Specfic target constituency. It's not as important to have broad library support compared to a language targeted for general purpose use. Our baby language needs a niche to survive and prosper. Most of the goals mentioned do seem to fit this market.

5) Avoiding hard things. Programming for the business processes in the real world is hard. It's full of non-strictly typed interactions and full of side-effects. LISP picked up a bad name because AI was too nebulous an aim.

6) Cell processors - we need new languages for them. Once proven, there is a general future for this language.

7) The coolness factor associated with computer games can accelerate the adoption of a language
# posted by Chui Tey : 1:43 AM

Another area worthwhile looking at is in designing languages for the current generation of game machines, where parallelization is important.

It is worthwhile because:
1) Computer game development do not suffer the constraints of corporate programming, and are more adventurous with tools. A lot of games run with embedded scripting languages. Why not have highly parallelizable functional languages for computer generated graphics?

2) Existing languages are inadequate, and it has taken several years for developers to learn how to squeeze performance from the Sony PS2 architecture.

3) Computer gaming is a big industry, so there will be sufficient commercial interests in the project

4) Specfic target constituency. It's not as important to have broad library support compared to a language targeted for general purpose use. Our baby language needs a niche to survive and prosper. Most of the goals mentioned do seem to fit this market.

5) Avoiding hard things. Programming for the business processes in the real world is hard. It's full of non-strictly typed interactions and full of side-effects. LISP picked up a bad name because AI was too nebulous an aim.

6) Cell processors - we need new languages for them. Once proven, there is a general future for this language.

7) The coolness factor associated with computer games can accelerate the adoption of a language

6.3.05

Xcaml

Xcaml is an extension of Caml for web applications, overlapping with Links in goals and methods.

Links update

Two updates on Links.

(1) The meeting will be 9.30--17.30 Wednesday 6 April 2005, in the Conference Suite, School of Informatics, 2 Buccleuch Place. After the meeting, we will adjourn for a drink in The Links Bar, Bruntsfield. As before, let me know if you want to attend.

(2) The Links meeting is colocated with ETAPS. There is no requirement to register for ETAPS to attend Links, but you may wish to do so. Please note that ETAPS registration fees increase after Monday 7 March. (Apologies for the late notice, but the venue was confirmed only recently.)

http://www.etaps05.inf.ed.ac.uk/

Cheers, -- P

2.3.05

Three links from Will Partain

Tim O'Reilly on The Open Source Paradigm Shift
http://tim.oreilly.com/opensource/paradigmshift_0504.html

The magic behind google maps
http://jgwebber.blogspot.com/2005/02/mapping-google.html

For ideas about applications students will want to work on,
see Jamie Zawinski's recent rant on "groupware":
http://jwz.livejournal.com/444651.html

17.2.05

More Links comments

More comments, from Tony Hoare and Joachim Durchholz.

--------

From Tony Hoare

Dear Phil,

Thanks for the note. I'm afraid I can't get to Edinburgh on April 6th.
But I hope your discussions go well.

I would recommend that you concentrate initially on a clear definition
of the purely scientific, possibly long-term, challenges of expressing
web applications in a transparent functional style. As a result, even
if you never get as popular in the short term as python (let alone
Visual Basic, with its four million programmers), your project will
represent a significant step forward in our understanding of the
principles of programming and programming language design.

Your long list of existing languages is essential as a summary of
sources of experimental data for evaluating and evolving any emerging
language and implementation by application to realistic examples; I
think this is your intention. Otherwise your project may just
degenerate into an attempt to throw everything into one unholy stew.
Leave that kind of cookery to the standardisation bodies who made the
mess: the scientific method has no particular contribution to make to
clearing it up.

My last two paragraphs have described two extremes. Most people engaged
in your project will take a position somewhere between them. Perhaps
no-one would or should embrace solely the scientific ideals. A most
fruitful outcome of your meeting would be to define a framework within
which scientists can collaborate in working towards a long-term goal,
while competing in achievement of shorter term milestones.

Now let me add my own bit of gristle to the stew. A modern language for
Web Services should surely incorporate the concept of a long-running
transaction, as in languages such as BPEL or Microsoft's XLANG.

Please circulate this note if you think it will contribute.

Yours,

Tony.

--------

From Joachim Durchholz

Dear all,

as the response to the above message in the comp.lang.functional newsgroup has shown, there's an immense interest in this project.

The announcement also sparked a rather extensive discussion on the features that such a language should (or should not) have. However, the discussion suffered from the typical newsgroup syndrome: no consensus, threads dropping off into silence, etc.

Since I know that WikiWiki webs have a better track record in this regard, I have set up one at

http://durchholz.org/jo/links/wiki/pmwiki.php

(For those who don't know what a WikiWiki web is: it's a web site where anybody can edit the pages. Since the pages are versioned, it's easy to revert accidentally or maliciously defaced pages to the last known good state.)

I have already added some of my personal pet peeves, but I sincerely hope that others will contribute as well, with additional proposals or critiques.

Enjoy!

Jo

--------

14.2.05

Links comments

I received useful comments on Links from Garry Hodgson, Amanda Clare, and Rodrigo Barnes. (Posted with permission.)

--------

From Garry Hodgson

i hope you are successful. i worry, though, that much of the focus in your outline is on the language technology, and not on the ecosystem surrounding the language which, i believe, is what will make it "as widely used as python" or not. perl, python, java, etc. are not popular primarily based on their language design.

everyone on this list uses highly advanced languages on a daily basis. but if i want to write a mail or http client or server, or parse or generate xml, or run a unix process and gets its exist code and output, or whatever, how do i do that? yes, there are libraries out there, but i have to go find them, and build them, and integrate them, etc. and this raises the threshold of pain sufficiently high that it's usually easier to just use what i've got.

mind you, i'm a big fan of FP. i use erlang and ocaml whenever i can. but it costs me a lot of effort to do so, both in finding what i need and in justifying the decision. if you want to read the vast majority of users who don't already want to use FP, you'll need to make it easy to do so.

a while back, python was using the slogan "batteries included" to get this idea across. while y'all are designing the ultimate "take over the world" functional language, please don't forget the batteries.

-- Garry Hodgson, Technical Consultant, AT&T Labs

--------

From Amanda Clare

I'll be busy attending NESC's Globus Week in Edinburgh on that date, so won't be able to come (I'm not a language designer anyway, so wouldn't have been much use at this stage). But I love the idea and would be happy to be a real-world user to test any system you make. Python usually wins out over Haskell nowadays for me for most apps I have to say for practical reasons.

Currently my project involves Grid technology - Java-based Globus, to grid-enable laboratory automation systems. The object oriented approach the Globus team have taken to the whole Grid and web services concept (and the WSRF team as well) frequently have me amazed at how complicated they have to make it all.

Just to give an example from Borja Sotomayor's excellent tutorial
(http://gdp.globus.org/gt4-tutorial/):

> Whoa! Three Java classes to implement something as simple
> as addition and subtraction? Yes, it's true. But that's simply
> the price you have to pay for statefulness. Before looking at
> the Java code, let's make sure we understand how these three
> implementation files are related.

(and this is step 2 of a 5 step process to make a web service)

There has to be a better way. Even if in future they automate some of the steps (eg automatically generate WSDL so that I don't have to remember to name my Java get/set methods exactly the same as the resource properties in the WSDL file, and so on), I just feel less and less like I'm in control or have a good feel for what's happening, or understand the interactions and errors.

On the plus side I was interested to see that Polar Humenn had used Haskell as a language for describing XACML policies, so maybe Haskell ideas will sidle into Grid/Globus in the future.

Amanda Clare

--------

From Rodrigo Barnes

I've spent quite a bit of time (8+ years) developing and managing development of networked applications which can be a painful thing! Clearly anything that could make it a more pleasant experience would be worthwhile. On top of that the possibility of developing a new language (in the broadest sense) for this purpose would be interesting in its own right.

As an aside - on the J2EE front have you tracked the workings of http://www.springframework.org ? We've used it in our latest project and it's certainly made some aspects nicer as well as clearer and easier to maintain. Spring + Hibernate (http://www.hibernate.org) is proving a popular complement and/or alternative to the J2EE stack (EJBs and the like).

In general, my concern with such a project, having also spent quite a bit of time developing tools in academia, is that it aims to prove points rather than developing industrially viable tools (witness e.g. some of the problems in getting e-science tools to market). Having said that you only get the chance to develop this sort of innovation in a research context.

Another idea that might appeal to the group is to look at development tools, such as IntelliJ IDEA (http://www.jetbrains.com/) which along with Eclipse (http://www.eclipse.org) made refactoring tools easy to use for the working Java programmer. When I first saw IDEA it struck me they just went through Martin Fowler's 'Refactoring' book and used it as a requirements doc. So if you took his Patterns of Enterprise Application Architecture book (http://www.martinfowler.com/books.html#eaa) what tool would you get?

-- Rodrigo Barnes

--------

1.2.05

Links meeting at ETAPS

Taking advantage of the fact that the world will be visiting my
doorstep, with the help of some colleagues I am organizing a
meeting on Links for 6 April 2005, to overlap with ETAPS.
The meeting is by invitation only --- please
let me know if you would like to be invited!

Dear Colleagues,

If we bent our minds to it, could we produce a functional language
that was as widely used as Python? There is reason to believe that
functional languages are particularly well suited to building web
applications.

* Databases. Kleisli and Mnesia (not to mention SQL and
XQuery) have demonstrated the value of functional languages as query
languages.

* XML. Xduce, Cduce, Bigwig (not to mention XSLT and XQuery)
have demonstrated the value of functional languages for manipulating
XML.

* Continuations. PLT Scheme and WASH have demonstrated the value of
functional languages for structuring CGI interfaces.

* Distribution. Erlang and JoCaml have demonstrated the value of
functional languages for distribution and mobility.

The technique of building a coalition to design, implement, and
promote a general-purpose programming language has proven
spectacularly successful for ML and Haskell. Can we apply this
technique again, this time aimed at an application domain?

ETAPS will attract a large number of researchers to Edinburgh, and
seems an appropriate point for launching this project. We propose
to meet on *** Wednesday 6 April 2005 in Edinburgh ***. We hope you
can come.

The working name for this project is Links. A quarter of a century
ago, Burstall, MacQueen, and Sannella introduced Hope, the source of
the algebraic types of ML and Haskell. Hope was named after Hope Park
Square, located near Edinburgh University on the Meadows. Links is
named after the Bruntsfield Links, located at the other end of the the
Meadows and site of the first public golf course.

Points to be discussed at the Links meeting include:

* Presentations on work to date -- we hope you will contribute to this.

* Types. The type system of Haskell and the module system of ML
are both extremely powerful, but quite different. Regular expression
types for XML are also powerful, but it is unclear how to combine
these with polymorphism or higher-order functions. Further, to be
successful, any new language must play well with SOAP, Java, and C#,
at a minimum; how do we integrate OO and FP types?

* Effects. It is proposed that the language be strict, with an effect
type system (combining the advantages of Haskell monads with ML effects).
What variety of effects should be supported? Can we provide support for
laziness within this framework? (See Wadler and Thiemann for
relations between monads and effect type systems, see Wadler, Taha, and
MacQueen for a proposal to support laziness in a strict language.)

* Targets. Web applications are often structures as three tiers:
browser (running HTML, XML, Javascript, Flash, Java), server
(running Java, C#, Python, Perl), and database (running SQL or XQuery).
We hope to compile code to run in all three tiers from a single source.
How can a compiler framework support multiple targets of this kind?
(See Thiemann on generating multi-tier programs from a single source.)

* Organization. How to structure the work? Should we put in for
European and/or US grants?

Volunteers for presentations and suggestions as to topics and organization
would be most welcome.

We look forward to hearing from you!

Yours sincerely,
Xavier Leroy
Simon Peyton Jones
Benjamin Pierce
Philip Wadler

20.1.05

TIOBE Programming Community Index

The TIOBE Programming Community Index tracks popularity of programming languages. "The ratings are based on the world-wide availability of skilled engineers, courses and third party vendors. The popular search engines Google, MSN, and Yahoo! are used to calculate the ratings." Lisp, Scheme, and ML rate mentions. Erlang and Haskell are tracked, but no ratings are reported since they are not in the top 50.

7.1.05

ICDT

ICDT is in Edinburgh this year. Some highlights:

Moshe Vardi on model checking for database theorists. A lovely introduction.

Michael Schwartbach on type systems for XML. A perfect invited talk: a summary of the field as a whole, including the speaker's work but not focussed on it, with some hot-off-the-presses new research at the end (static typing for XSLT with DTDs as types). Beautifully illustrated with cows.

Wim Martens, Frank Neven and Thomas Schwentick on Which XML Schemas Admit 1-Pass Preorder Typing. Neat results, neatly presented. They have a very nice characterization of the "element declarations consistent" constraint in Schema.

David Maier on Streaming. One of the more interesting things I learned at ICDT is that Maier is responsible for introducing the term "impedance mismatch" to the database field, circa 1984. (It may have been introduced into computing more than once, as I believe I saw the same term used in a paper on AWK earlier than that.)

Victor Viana told me about his latest work. I went back to my office and downloaded his Specification and Verification of Data-driven Web Services from PODS 2004.

Links in Lambda the Ultimate

Ehud Lamm at Lambda the Ultimate was kind enough to post something about Links, and the comments have been positive so far. Thanks, guys!

(Tim Sweeney expressed a hope that the syntax would be more like C/Java/Python than like Haskell. That is the plan. Once the language is out, comments on all aspects, including the syntax, will be welcome.)

5.1.05

FP goes mainstream

Jeremy Yallop has pointed me to an article describing continuations for web programming at the IBM DeveloperWorks website. Nice to see working programmers picking this up, as it is one of the key ingredients in Links.