Transcript slides

Confessions
of a
used programming
language
salesperson
(an appeal to purity)
Erik Meijer
Why Functional
Programming
Matters
Reloaded
…
100 …
110 x = x+1
120 …
…
Artificial
Intelligence
via massively
parallel
machines
using logic
programming
SASL, Miranda, SKI
[f.x.(f (f x))]
=
(S (S (K S) (S (K K) I))
(S (S (K S) (S (K K) I))
(K I)))
Only need 3
instructions
and massively
parallel reduction
machines
Data
Presentation
Business
logic
Presentation
(HaskellScript)
Business
logic
(HSP,
XM)
Data
(Haskell
DB)
List Comprehensions
Example
factors n =
[ x
| x <- [1..n]
, n `mod` x == 0
]
Select
From
Where
isPrime n = factors n = [1,n]
primes n =
[ p | p <- [2..n], isPrime p ]
List Comprehensions
Simplified translation
[ e | True ] =
[ e ]
Syntactic sugar
[ e | q ] =
over standard list
[ e | q, True ]
operations
[ e | b, Q ] =
filter b [ e | Q ]
[ e | x <- l, Q ] =
concatMap (\x -> [e | Q ]) l
[ e | let decls, Q ] =
let decls in [ e | Q ]
Monad Comprehensions
Example
IO monad
generalize lists
words
words
do{
;
;
}
:: IO [String]
=
putStr “enter a value …”
x <- getLine
return (words x)
Parametrized over
type constructor
class Monad m where
{ (>>=) :: m a -> (a -> m b) -> m b
; return :: a -> m a
}
Syntactic sugar
over standard
monad operations
HaskellDb
Query Monad
SELECT X.FirstName, X.LastName
FROM Authors AS X
WHERE X.City = 'OakLand'
Query monad
generalizes IO
monad
oaklands =
do{ x <- table authors
; restrict (x!city .==. constant "Oakland")
; project ( au_fname = x!au_fname
, au_lname = x!au_lname
)
}
intentional representation
for expressions
Haskell Server Pages
XHTML Literals
table :: TABLE
table = <TABLE border="1">
<% mkRows cells %>
</TABLE>
Translated to
universal DOM
representation
cells :: [[(Int,Int)]]
cells = [[ (x,y) | x <- [1..16] ] | y <- [1..16] ]
mkRows :: [[(Int,Int)]] -> [TR]
mkRows =
map $ \cs -> <TR><% mkColums cs %></TR>
ASP-style
embedding
mkColumns :: [(Int,Int)] -> [TD]
mkColums =
map $ \c -> <TD bgcolor=(color c)><% c %></TD>
http://radar.oreilly.com/erlanghaskellruby-thumb.png
XML 2003: Growing C
streams
tuples
Unions
Content classes
XML object literals
Generalized member access
+ SQL comprehensions
Type System Extensions
(structural)
arrays
T ::=
|
|
|
|
|
closures
intersection,
N
union
T[] | T{}
T(…,T,…)
streams
T|T | T&T
T! | T? | T+ | T*
struct {…, T m,…}
XQuery data model
tuples (rows)
C Query Comprehensions
String n = "Wolfram";
struct{String? Subject}* subjects =
select it.Subject from it in inbox
where it.From == n
Compiler
plugins
foreach(r in
select CustomerID, ContactName
from dbo.Customers where City == mycity
order by ContactName) {
…
}
Type inference
SQL = data model + query syntax
Select Name, Age
From Customers
Where City = "Seattle"
Table of rows
XQuery/XPath =
data model + query syntax
From $C In Customers
Where $C/City = "Seattle"
Return <Cust Name={$C/Name}>
{ $C/Age }
</Cust>
Set of nodes
Objects =
data model + query syntax
Foreach C In Customers
If C.City = "Seattle"
R.Add(New With
{C.Name, C.Age})
End If
Collection of
Next
objects
Filtering
T  (T  Bool)  T
2
0
6
2
3
5
1
4
0
X Mod 2 = 0
6
3
5
1
4
Mapping
T  (T  S)  S
2
0
6
4
3
5
1
4
0
X * 2
6
12 10
2
8
Aggregating
T  (S, (S,T)  S)  S
2
0
6
3
5
Sum
1
4
T  ((T,T)  T)  T
21
Monads !
ℳ<T>
ST
A container type
A function type
A constructor
ℳ<T> Unit<T>(T src)
ℳ<T> SelectMany<S,T>
(ℳ<S> src, Sℳ<T> f)
A composer
Monads !
ℳ<T>
ST
IEnumerable<T>
IQueryable<T>
Func<S,T>
Expr<Func<S,T>>
ℳ<T> Unit<T>(T src)
ℳ<T> SelectMany<S,T>
(ℳ<S> src, Sℳ<T> f)
Standard Query Pattern
(generics not expressive enough)
LINQ Project
== monad comprehensions in C# & VB
VB 9
C# 3.0
…
Standard
Query
Operators
DLinq
(relational)
XLinq
(xml)
LINQ Framework
Features
•
•
•
•
•
•
•
•
•
•
•
Local Type Inference
Object & Collection Initializers
Anonymous Types
Lambda Expressions
Query Comprehensions
Enables
Extension Methods
Language
Extensions
Expression Trees
via libraries
Simplified Properties
Partial Methods
Deep XML Support (VB)
Nullable Types (VB)
LINQ 2.0
A better paradigm for
programming massive
clusters of commodity
hardware than Google
MapReduce based on
LINQ
From W In Words
Group By W
Aggregate N = Count()
Select W, N
Map
Group By
Repartition
Aggregate
Sawzall
Example 3
submitsthroughweek:
table sum[minute: int] of count: int;
log: P4ChangelistStats = input;
t: time = log.time; # microseconds
minute: int =
minuteof(t)
+60*(hourof(t)
+24*(dayofweek(t)-1));
emit submitsthroughweek[minute] <- 1;
Using C# 3.0
Comprehensions
var SubmitsThroughWeek =
from s in db.Submits
group s by s.SubmitTime.Minute
+ 60*(s.SubmitTime.Hour
+ 24*s.SubmitTime.DayOfWeek)
into g
select new { minute = g.Key
, count = g.Count()
};
Using Visual Basic 9
Comprehensions
Dim SubmitsThroughWeek =
From s In db.Submits
Group By Minute = s.SubmitTime.Minute
+ 60*(s.SubmitTime.Hour
+ 24*s.SubmitTime.DayOfWeek)
Into Minute, Count()
Using
Standard Sequence Operators
var SubmitsThroughWeek =
db.Submits
.GroupBy(s=>s.SubmitTime.Minute
+ 60*(s.SubmitTime.Hour
+ 24*s.SubmitTime.DayOfWeek))
.Select(g=>new { minute=g.Key
, count=g.Count()}
);
Repartition
“Map”
“Reduce”
Division By 0
Is The Goal,
Not An Error
Do you see a pattern?
Functional PL
Smalltalk
Haskell
XML
LaTex
Betamax
Nouvelle Cuisine
Semantic Web
…
OCaml
Object-Oriented PL
Java
JSON
MS Word
VHS
Fastfood
Search
…
“For Dummies” Version
Cool!
Geeks
Next release is
even better!
P(success) = F(10X improvement * Moore’s Law)
Marketing
Coerce users to
believe gadgets
will make them
happy
Users
P(success) = F(perceived crisis/perceived pain of adoption)
Just want to get
job done
No patience to
learn new stuff
C
Haskell
Haskell98
Haskell’
10x better
Moore’s
Law
Change Function
to the rescue
What is the user
biggest crisis?
P(success) = F(perceived crisis
perceived pain of adoption)
How can we
make adoption
truly painless?
Change Function
to the rescue
P(success) = F(perceived crisis
perceived pain of adoption)
P(success) = F(100%
0)
P(success) =

Silver Bullet
Are “functional”
languages such as
Erlang and F# the
Silver Bullet for the
many-core problem?
Shared Nothing
Message Passing
Really
?

Page 165:
Shared Nothing
Message Passing
There is a subtle error in on_exit and
keep_alive
…
Write your code such that race
conditions cannot happen.
…
Fortunatley, the OTP libraries have code
for building servers, supervisor trees,
and so on.
These libraries have been well testedReally
?
and should not suffer from any race 
conditions.
Unsafe and Useless
useful
C++
Nirvana
VB
C#
useless
F#
Erlang
unsafe
Haskell
safe
What is a
Functional Language
A language
where functions
are first-class
citizens
Those
Sneaky
Side Effects
unsafeCast :: a -> b
unsafeCast x = unsafePerformIO
$ writeIORef castref x
>> readIORef castref
castref = unsafePerformIO
$ newIORef undefined
new_cell(X) -> spawn(fun() -> cell(X) end).
cell(Value) ->
receive
{set, NewValue}
-> cell(NewValue);
{get, Pid}
-> Pid!{return, Value}, cell(Value);
{dispose}
-> {}
c.set_cell(v)
end.
set_cell(Cell, NewValue) ->
Cell!{set, NewValue}.
4711
get_cell(Cell) ->
Cell!{get, self()},
receive
v =c.get_cell()
{return, Value} -> Value
end.
dispose_cell(Cell) -> Cell!{dispose}.
What is a
function
-calculus
E ::= EE | …
let x = E1
in E0[x]
 E0[x:=E1]
(x.E0[x])E1  E0[x:=E1]
What is a
function
let t = DateTime.Now.Ticks
in (x,x)

( DateTime.Now.Ticks
, DateTime.Now.Ticks
)
Race
condition
Mens sana in corpore sano
Haskell
Purity is
the key to
success
Mistake
DateTime.Now.Ticks  long
Type error
!!!!!!!!!!!!!!!
What is a
function
let t = ().DateTime.Now.Ticks
in (x,x)

( ().DateTime.Now.Ticks
, ().DateTime.Now.Ticks
)
Value
restriction
Values
vs Computation
How to turn something
mutable into something
immutable?
Time
changes,
the clock
does not
Generalization
Monads
M<A>
M  IO
Exception
Animation
Collection
A computation that produces
a value of type A with sideeffects described by M
Algebra/API
Return  A  M<A>
Bind  M<A>(AM<B>)M<B>
Join  M<M<A>>M<A>
UnsafePerformIO  M<A>A
LINQ
Monads are the secret
sauce behind LINQ
Bind
IEnumerable<S> SelectMany<T,S>(
IEnumerable<T> src,
Func<T, IEnumerable<S>> selector
)
IO
data IO a
putChar :: Char -> IO ()
getChar :: IO Char
Sideeffecting
computation
that yields a
value of type
a
newIORef :: a -> IO (IORef a)
readIORef :: IORef a -> IO a
writeIORef :: IORef a -> a -> IO ()
forkIO :: IO a -> IO ThreadID
IO
Does
nothing

main :: IO()
main =
do{ x <- newIORef “hello”
; c <- getChar
; s <- readIORef x
; writeIORef x (c:s)
; ...
}
STM
data STM a
atomic :: STM a -> IO a
retry :: STM a
orElse :: STM a -> STM a -> STM a
newTVar :: a -> STM (TVar a)
readTVar :: TVar a -> STM a
writeTVar :: TVar a -> a -> STM ()
STM
putR :: TVar Int -> Int -> STM ()
putR r i =
do { v <- readTVar r
; writeTVar r (v+i)
}
main :: IO()
main =
do{ …
; atomic $ putR 4711
; …
}
STM
getR :: TVar Int -> Int
-> STM ()
getR r i =
do { v <- readTVar r
; if (v < i) then retry
else writeTVar r (v-i)
}
STM
nonBlockGetR :: TVar Int -> Int
-> STM Bool
nonBlockGetR r i =
do { getR r i
; return True
}
retry
‘orElse‘
do { return False
}
STM
nonBlockGetR :: TVar Int -> Int
-> STM Bool
nonBlockGetR r i =
do { getR r i
; return True
}
retry
‘orElse‘
do { return False
}
STM
An MVar is a mutable location
either empty, or full with a value.
takeMVar function leaves a full MVar empty, blocks
on an empty MVar.
putMVar on an empty MVar leaves it full, and blocks
on a full MVar.
type MVar a = TVar (Maybe a)
newEmptyMVar :: STM (MVar a)
newEmptyMVar = newTVar Nothing
STM
Read the contents of the TVar
retry until not Nothing:
takeMVar :: MVar a -> STM a
takeMVar mv =
do { v <- readTVar mv
; case v of
Nothing -> retry
Just val ->
do { writeTVar mv Nothing
; return val
}
}
STM
Retry until Nothing,
Update the underlying TVar
putMVar :: MVar a -> a -> STM ()
putMVar mv val =
do { v <- readTVar mv
; case v of
Nothing ->
do{ writeTVar mv (Just val) }
Just val -> retry
}
Is the
Perceived Real
10x
better
Crisis
Haskell
>>>>
Perceived pain of
Haskell98
adoption?
Moore’s
C
Law
Haskell’