XMAS LECTURE 2013

Vocals: Anya Bagge and Sarah Piller Piano: Peter Babnik Coding: Ralf Lämmel

M

BEAUTIFUL CODE

LAST CHRISTMAS — WHAM!

http://en.wikipedia.org/wiki/Last_Christmas

MORGEN KOMMT DER WEIHNACHTSMANN

!DEUTSCH TEXT: Hoffmann von Fallersleben (1850) !Morgen kommt der Weihnachtsmann, Kommt mit seinen Gaben. Trommel, Pfeifen und Gewehr, Fahn und Säbel und noch mehr, Ja ein ganzes Kriegesheer, Möcht' ich gerne haben. !!!!

Bring' uns, lieber Weihnachtsmann, Bring' auch morgen, bringe Musketier und Grenadier, Zottelbär und Panthertier, Roß und Esel, Schaf und Stier, Lauter schöne Dinge! !Doch du weißt ja unsern Wunsch, Kennst ja unsre Herzen. Kinder, Vater und Mama Auch sogar der Großpapa, Alle, alle sind wir da, Warten dein mit Schmerzen.

http://german.about.com/library/blmus_morgenkommt.htm

MOZART: !

"MORGEN KOMMT DER WEIHNACHTSMANN" AUSWAHL VON VARIATIONEN

http://de.wikipedia.org/wiki/Morgen_kommt_der_Weihnachtsmann

LESS BEAUTIFUL CODE

class HelloWorld {

static public void main( String args[] ) {

System.out.println( "Hello World!" ); } }

Java

MORE BEAUTIFUL CODE

print "Hello World!”

Python

BOOKS YOU ABSOLUTELY SHOULD READ

Dashing through the snow In a one horse open sleigh O'er the fields we go Laughing all the way Bells on bob tails ring Making spirits bright What fun it is to laugh and sing A sleighing song tonight !Oh, jingle bells, jingle bells

Jingl

e Be

lls 1

/3

http://www.carols.org.uk/jingle_bells.htm

A sleighing song tonight !Oh, jingle bells, jingle bells Jingle all the way Oh, what fun it is to ride In a one horse open sleigh Jingle bells, jingle bells Jingle all the way Oh, what fun it is to ride In a one horse open sleigh !A day or two ago I thought I'd take a ride And soon Miss Fanny Bright Was seated by my side The horse was lean and lank Misfortune seemed his lot We got into a drifted bank And then we got upsot !Oh, jingle bells, jingle bells

Jingl

e Be

lls 2

/3

!Oh, jingle bells, jingle bells Jingle all the way Oh, what fun it is to ride In a one horse open sleigh Jingle bells, jingle bells Jingle all the way Oh, what fun it is to ride In a one horse open sleigh yeah !Jingle bells, jingle bells Jingle all the way Oh, what fun it is to ride In a one horse open sleigh Jingle bells, jingle bells Jingle all the way Oh, what fun it is to ride In a one horse open sleigh

Jingl

e Be

lls 3

/3

Chapter 1 of Beautiful code: A Regular Expression Matcher

Brian Kernighan

REGULAR EXPRESSION CHARACTERS

• Character Meaning

• c matches any literal character c

• . matches any single character

• ^ matches the beginning the input string

• $ matches the end of the input string

• * matches zero or more occurrences of the previous character

EXAMPLES

re1 = "xm.ss*" re2 = “^xm.ss*”

!match(re1, “xmas”) ▶︎ 1 match(re2, “xmas") ▶︎ 1 match(re1, "xmaz") ▶︎ 0 match(re2, "xmaz") ▶︎ 0 match(re1, "qxmas") ▶︎ 1 match(re2, "qxmas") ▶︎ 0 match(re1, “xmess") ▶︎ 1 match(re2, “xmess") ▶︎ 1

int match(char *re, char *text) { if (re[0] == '^') return matchhere(re+1, text); do { /* must look at empty string */ if (matchhere(re, text)) return 1; } while (*text++ != '\0'); return 0; } int matchhere(char *re, char *text) { if (re[0] == '\0') return 1; if (re[1] == '*') return matchstar(re[0], re+2, text); if (re[0] == '$' && re[1] == '\0') return *text == '\0'; if (*text!='\0' && (re[0]=='.' || re[0]==*text)) return matchhere(re+1, text+1); return 0; } int matchstar(int c, char *re, char *text) { do { /* a * matches zero or more instances */ if (matchhere(re, text)) return 1; } while (*text!='\0' && (*text++==c || c=='.')); return 0; }

/* match: search for re anywhere in text */

/* matchhere: search for re at beginning of text */

/* matchstar : search for c*re at beginning of text */

.C

/* match: search for re anywhere in text */ int match(char *re, char *text) { if (re[0] == '^') return matchhere(re+1, text); do { /* must look at empty string */ if (matchhere(re, text)) return 1; } while (*text++ != '\0'); return 0; }

.C

/* matchhere: search for re at beginning of text */ int matchhere(char *re, char *text) { if (re[0] == '\0') return 1; if (re[1] == '*') return matchstar(re[0], re+2, text); if (re[0] == '$' && re[1] == '\0') return *text == '\0'; if (*text!='\0' && (re[0]=='.' || re[0]==*text)) return matchhere(re+1, text+1); return 0; }

.C

/* matchstar : search for c*re at beginning of text */ int matchstar(int c, char *re, char *text) { do { /* a * matches zero or more instances */ if (matchhere(re, text)) return 1; } while (*text!='\0' && (*text++==c || c=='.')); return 0; }

.C

WHITE CHRISTMAS

I'm dreaming of a white Christmas Just like the ones I used to know Where the treetops glisten, and children listen To hear sleigh bells in the snow !I'm dreaming of a white Christmas With every Christmas card I write May your days be merry and bright And may all your Christmases be white

!I'm dreaming of a white Christmas With every Christmas card I write May your days be merry and bright And may all your Christmases be white

http://www.carols.org.uk/white_christmas.htm

.hs

match :: String -> String -> Bool match ('^':r) = matchHere r match r = or . map (matchHere r) . tails matchHere :: String -> String -> Bool matchHere (c:'*':r) xs = matchStar c r xs matchHere "$" xs = null xs matchHere (r :rs) (x:xs) = (r == '.' || r == x) && matchHere rs xs matchHere r _ = null r matchStar :: Char -> String -> String -> Bool matchStar _ r xs | matchHere r xs = True matchStar c r (x:xs) = (c == '.' || c == x) && matchStar c r xs matchStar _ _ _ = False

© Remco Niemeijer

.pro

match(['^'|Rs], T) :- matchHere(Rs, T). match(R, T) :- matchHere(R, T). match(R, [_|Ts]) :- matchHere(R, Ts). !matchHere([], _). matchHere(['$'], []). matchHere([R,'*'|Rs], T) :- matchStar(R, Rs, T). matchHere([R|Rs], [R|Ts]) :- matchHere(Rs, Ts). matchHere(['.'|Rs], [_|Ts]) :- matchHere(Rs, Ts). !matchStar(_, Rs, Ts) :- matchHere(Rs, Ts). matchStar(R, Rs, [R|Ts]) :- matchHere(Rs, Ts). matchStar('.', Rs, [_|Ts]) :- matchHere(Rs, Ts). matchStar(R, Rs, [R|Ts]) :- matchStar(R, Rs, Ts). matchStar('.', Rs, [_|Ts]) :- matchStar('.', Rs, Ts).

© Guillermo Oscar «Tordek» Freschi

LET IT SNOW

Oh the weather outside is frightful, But the fire is so delightful, And since we've no place to go, Let It Snow! Let It Snow! Let It Snow! !It doesn't show signs of stopping, And I've bought some corn for popping, The lights are turned way down low, Let It Snow! Let It Snow! Let It Snow! !

When we finally kiss goodnight, How I'll hate going out in the storm! But if you'll really hold me tight, All the way home I'll be warm. !The fire is slowly dying, And, my dear, we're still good-bying, But as long as you love me so, Let It Snow! Let It Snow! Let It Snow!

http://www.carols.org.uk/let_it_snow.htm

Chapter 23 of Beautiful code: Distributed programming with MapReduce

Jeffrey Dean and Sanjay Ghemawat

map<string, int> word_count; for each document d for each word w in d word_count[w]++; … save word_count to persistent storage …

COUNT WORDS

PARALLELIZED COUNT WORDS

struct CountTable { Mutex lock; map<string, int> word_count; } const int kNumBuckets = 256; CountTable tables[kNumBuckets]; for each document d in parallel for each word w in d { int bucket = hash(w) % kNumBuckets; tables[bucket].lock.Lock(); tables[bucket].word_count[w]++; tables[bucket].lock.Unlock(); } for (int b=0; b<kNumBuckets; b++) … save tables[b].word_count to persistent storage …

O du fröhliche O du selige Gnadenbringende Weihnachtszeit Welt ging verloren Christ ist geboren Freue, freue dich, o Christenheit !O du fröhliche O du selige Gnadenbringende Weihnachtszeit Christ ist erschienen Uns zu versühnen Freue, freue dich, o Christenheit !O du fröhliche O du selige Gnadenbringende Weihnachtszeit Himmlische Heere Jauchzen Dir Ehre Freue, freue dich, o Christenheit

Oh

du fr

öhlic

he

http

://www

.nana

mous

kour

i.de/o

dufro

e.htm

MAPPERS AND REDUCERS

partition 1

partition 1

partition R

piece 1

piece M

map M

reduce 1

reduce R

Output dataIntermediate dataInput data

map 1

partition R

k2 [v2]

k2 v3

k1 v1

Figure 2: Map split input data and reduce partitioned intermediate data

4.2 A distribution strategyLet us recapitulate the particular distribution strategy from the seminal MapReducepaper, which is based on large networked clusters of commodity machines with localstore while also exploiting other bits of Google infrastructure such as the Google filesystem [13]. The strategy reflects that the chief challenge is network performance inthe view of the scarce resource network bandwidth. The main trick is to exploit localityof data. That is, parallelism is aligned with the distributed storage of large data setsover the clusters so that the use of the network is limited (as much as possible) to stepsfor merging scattered results. Fig. 2 depicts the overall strategy. Basically, input data issplit up into pieces and intermediate data is partitioned (by key) so that these differentpieces and partitions can be processed in parallel.

• The input data is split up into M pieces to be processed by M map tasks, whichare eventually assigned to worker machines. (There can be more map tasks thansimultaneously available machines.) The number M may be computed fromanother parameter S — the limit for the size of a piece; S may be specifiedexplicitly, but a reasonable default may be implied by file system and machinecharacteristics. By processing the input in pieces, we exploit data parallelism forlist maps.

22

INPUT & OUTPUT PROCESSORS

const int M = 1000; // Number of input processors const int R = 256; // Number of output processors main() { // Number of documents to assign to each process const int D = number of documents / M; for (int i=0; i<M; i++) fork InputProcess(i*D, (i+1)*D); for (int i=0; i<R; i++) fork OutputProcess(i); … wait for all processors to finish …

INPUT PROCESSORS

void InputProcess(int start_doc, int end_doc) { map<string, int> word_count[R]; // table per output process for each document d in range [start_doc .. end_doc-1] for each word in d { int b = hash(w) % R; word_count[b][w]++; } for (int b=0; b<R; b++) { string s = EncodeTable(word_count[b]); … send s to output process b … } }

OUTPUT PROCESSORS

void OutputProcess(int bucket) { map<string, int> word_count; for each input process p { string s = … read message from p … map<string, int> partial = DecodeTable(s); for each <word, count> in partial do word_count[word] += count; } … save word_count to persistent storage … }

DIVISION INTO MAP AND REDUCE

void Map(string document) { for each word w in document EmitIntermediate(w, “1’); } !

void Reduce(string word, list<string> values) { int count = 0; for each v in values count += StringToInt(v): Emit(word, IntToString(count)); }

DRIVER FOR MAP AND REDUCEmap<string, list<string>> intermediate_data; void EmitIntermediate(string key, string value) { intermediate_data[key].append(value); } void Emit(string key, string value) { … write key/value to final data file … } void Driver(MapFunction mapper, ReduceFunction reducer) { for each input item do { mapper(item); } for each key k in intermediate_data { reducer(k, intermediate_data[k]); } }

TIE THE KNOT

main() { Driver(Map, Reduce); }

SANTA CLAUS IS COMING TO TOWN

You better watch out You better not cry Better not pout I'm telling you why Santa Claus is coming to town He's making a list And checking it twice; Gonna find out Who's naughty and nice !!! !

Santa Claus is coming to town He sees you when you're sleeping He knows when you're awake He knows if you've been bad or good So be good for goodness sake! O! You better watch out! You better not cry Better not pout I'm telling you why Santa Claus is coming to town Santa Claus is coming to town

http://www.stlyrics.com/lyrics/elf/santaclausiscomingtotown.htm

Chapter 24 of Beautiful code: Beautiful Concurrency

Simon Peyton Jones

BANK TRANSFER PROBLEM

Write a procedure to transfer from one bank account to another. To keep things simple, both accounts are held in memory; no interaction with databases is required. The

procedure must operate correctly in a concurrent program, in which many threads may call transfer simultaneously. No thread should be able to observe a state in which the money has left

one account, but not arrived in the other (or vice versa).

A SIMPLE ACCOUNT CLASS

class Account { int balance; synchronized void withdraw(int n) { balance = balance - n; } void deposit(int n) { withdraw(-n); } }

FIRST ATTEMPT AT TRANSFER

void transfer(Account from, Account to, int amount) { from.withdraw(amount); to.deposit(amount); }

EXPLICIT LOCKING CODE

void transfer(Account from, Account to, int amount) { from.lock(); to.lock(); from.withdraw(amount); to.deposit(amount); from.unlock(); to.unlock(); }

ORDERED LOCKS

if from < to then { from.lock(); to.lock(); } else { to.lock(); from.lock(); }

LOCKS ARE BAD• Taking too few locks

• Taking too many locks

• Taking the wrong locks

• Taking locks in the wrong order

• Error recovery

• Lost wakeups and erroneous retries

COLOURFUL XMAShttp://www.youtube.com/watch?v=4kkQJuQlc_Q

TRANSFER IN HASKELL

transfer :: Account -> Account -> Int-> IO () transfer from to amount = ...

SOFTWARE TRANSACTIONAL MEMORY IN HASKELL

transfer :: Account -> Account -> Int-> IO () transfer from to amount = atomically (do { deposit to amount ; withdraw from amount })

Provided guarantees of “atomically act”

• Atomicity: The effects of execution become visible to another thread all at once. This ensures that no thread can see a state in which money has been deposited in to but not yet withdrawn from from.

• Isolation: During its execution, act is completely unaffected by other threads. It is as if takes a snapshot of the state of the world when it begins running, and then executes against that snapshot.

TRANSACTION VARIABLES

type Account = TVar Int !withdraw :: Account -> Int -> STM () withdraw acc amount = do { bal <- readTVar acc ; writeTVar acc (bal - amount) } !deposit :: Account -> Int -> STM () deposit acc amount = withdraw acc (- amount)

WINTER WONDERLANDSleigh bells ring, are you listening, In the lane, snow is glistening A beautiful sight, We're happy tonight. Walking in a winter wonderland. !Gone away is the bluebird, Here to stay is a new bird He sings a love song, As we go along, Walking in a winter wonderland. !In the meadow we can build a snowman, Then pretend that he is Parson Brown !He'll say: Are you married? We'll say: No man, But you can do the job When you're in town.

!Later on, we'll conspire, As we dream by the fire To face unafraid, The plans that we've made, Walking in a winter wonderland. !In the meadow we can build a snowman, And pretend that he's a circus clown We'll have lots of fun with mister snowman, Until the other kids knock him down. !When it snows, ain't it thrilling, Though your nose gets a chilling We'll frolic and play, the Eskimo way, Walking in a winter wonderland.

http://www.carols.org.uk/winter_wonderland.htm

Rudolph, the red-nosed reindeer had a very shiny nose. And if you ever saw him, you would even say it glows. !All of the other reindeer used to laugh and call him names. They never let poor Rudolph join in any reindeer games. !Then one foggy Christmas Eve Santa came to say: "Rudolph with your nose so bright, won't you guide my sleigh tonight?" !Then all the reindeer loved him as they shouted out with glee, Rudolph the red-nosed reindeer, you'll go down in history!

Rudo

lph,

the

red

nos

ed r

eind

eer

http

://www

.caro

ls.org

.uk/ru

dolf_

the_

red_

nose

d_re

indee

r.htm

WE WISH YOU A MERRY CHRISTMAS

We wish you a Merry Christmas; We wish you a Merry Christmas; We wish you a Merry Christmas and a Happy New Year. Good tidings we bring to you and your kin; Good tidings for Christmas and a Happy New Year. !Oh, bring us a figgy pudding; Oh, bring us a figgy pudding; Oh, bring us a figgy pudding and a cup of good cheer We won't go until we get some; We won't go until we get some; We won't go until we get some, so bring some out here !We wish you a Merry Christmas; We wish you a Merry Christmas; We wish you a Merry Christmas and a Happy New Year.

http://www.carols.org.uk/we_wish_you_a_merry_christmas.htm

Wir wünschen Euch ein Frohes Fest und Ein Gesundes Neues Jahr 2014.