Wadler's Blog

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

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!

Recommended by Andy Gordon. Thanks, Andy!

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:

• Esther
  
  
• ES
  
  
• HaSh - The Haskell Shell
  
  
• Q
  

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

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

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.

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).

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.

Another recommendation from Will Partain.

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

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.

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

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

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

Examples of "rich" web interfaces.

The Mozilla Amazon Browser

Google Maps

Swiss Maps

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