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.
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.
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.
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.
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!
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.
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
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
9.5.05
It's a whole new internet
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
The Economist
Science
