Lambda Calculus
Check-in [5ba8f3a355]
Not logged in

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:changed print->alert and read->prompt removed val from io monad (now it just holds commands) added much more expln on monads to the talk added definition of list constructor functions
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:5ba8f3a3557a32263ccb1dc8ef7400c707bac8d4
User & Date: bill 2011-12-07 01:29:54
Context
2012-03-15
03:14
Create new branch named "pagedown" check-in: 2e490f02c3 user: bill tags: pagedown
2011-12-07
01:53
cleaned up list constructors check-in: c562cd4027 user: bill tags: trunk
01:29
changed print->alert and read->prompt removed val from io monad (now it just holds commands) added much more expln on monads to the talk added definition of list constructor functions check-in: 5ba8f3a355 user: bill tags: trunk
2011-12-06
23:50
added enums to slides fixed invaders to ignore alt-left added enum examples to slides check-in: 73f4c771a2 user: bill tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to evaluator.html.

133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
...
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

181
182
183

184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199


200
201
202
203
204
205
#] =)= reverse
#
# current constructor
# no post processing
# also allows [1, 2, 3 | REST ] (like Prolog)

[ =(]= \item c . c \cont rest . cons item rest
, =.= \f . \item c . c \cont rest . f true (cons item rest)
] =)= \f . f false nil
| =.= \f rest g . f false rest
ident = \x . x
1f = \1 f . f 1
get = \f . f ident
test8 = last \f . f 1 \g . g 2 nil
test9 = last (cons 1 (cons 2 nil))
................................................................................
test10 = puts2 (ident 3)
# difference lists
dl = \list . append list
dlAppend = \da db list . da (db list)
dlList = \dl . dl nil
# simple IO monad
getCmdVal = \cmd . cmd ident
makeIO = \cmds val f . f cmds val
getCmds = \m . m (\cmds val . cmds)
getAllCmds = \m . dlList (getCmds m)
getVal = \m . m (\cmds val . val)
returnCmd = \x f . f x
return = \x . makeIO (dl [(returnCmd x)]) x
bindCmd = \action f . f action
getBindAction = \cmd . cmd ident
bind = \io f . io \cmds val . makeIO (dlAppend cmds (dl [(bindCmd f)])) false
printCmd = \thing f . f thing
print = \thing . makeIO (dl [(printCmd thing)]) false
readCmd = \prompt f . f prompt
read = \prompt . makeIO (dl [(readCmd prompt)]) false
testM1 = return 3
testM2 = print hello
testM3 = read nil
testM4 = bind (read [Please, type, something]) \x . print x

testM5 = bind (read One) \x . bind (print x) \y . bind (read Two) \z . bind (print z) \q . return 50
testM6 = bind (print one) \x . bind (read Two) \y . print y
testM7 = bind (print one) \x . return 3

testM8 = bind (print one) \x . bind (print two) \y . bind (print three) \z . return z
testM9 = bind (print hello) \x . bind (read Goodbye) \y . return y
testM10 = bind (read One) \x . bind (bind (read Two) \y . return y) \z . return x

sunday = \sun mon tue wed thu fri sat . sun
monday = \sun mon tue wed thu fri sat . mon
tuesday =   \sun mon tue wed thu fri sat . tue
wednesday = \sun mon tue wed thu fri sat . wed
thursday =  \sun mon tue wed thu fri sat . thu
friday =    \sun mon tue wed thu fri sat . fri
shabbat =   \sun mon tue wed thu fri sat . sat

dayName = \day . day Sunday Monday Tuesday Wednesday Thursday Friday Saturday
nextDay = \day sun mon tue wed thu fri sat . day mon tue wed thu fri sat sun
prevDay = \day sun mon tue wed thu fri sat . day sat sun mon tue wed thu fri
testDay = dayName (nextDay monday)



#define puts i32 @puts(i8* nocapture) nounwind
#define putsl i32 @putsl(i8* nocapture) nounwind
	</pre>
</body>
</html>







|







 







|
|

<

|


|
|
|
|
|

|
|
|
>
|
<
|
>
|
<
|













>
>






133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
...
157
158
159
160
161
162
163
164
165
166

167
168
169
170
171
172
173
174
175
176
177
178
179
180
181

182
183
184

185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
#] =)= reverse
#
# current constructor
# no post processing
# also allows [1, 2, 3 | REST ] (like Prolog)

[ =(]= \item c . c \cont rest . cons item rest
, =.= \f item c . c \cont rest . f true (cons item rest)
] =)= \f . f false nil
| =.= \f rest g . f false rest
ident = \x . x
1f = \1 f . f 1
get = \f . f ident
test8 = last \f . f 1 \g . g 2 nil
test9 = last (cons 1 (cons 2 nil))
................................................................................
test10 = puts2 (ident 3)
# difference lists
dl = \list . append list
dlAppend = \da db list . da (db list)
dlList = \dl . dl nil
# simple IO monad
getCmdVal = \cmd . cmd ident
makeIO = \cmds f . f cmds
getCmds = \m . m (\cmds . cmds)
getAllCmds = \m . dlList (getCmds m)

returnCmd = \x f . f x
return = \x . makeIO (dl [(returnCmd x)])
bindCmd = \action f . f action
getBindAction = \cmd . cmd ident
bind = \io f . io \cmds . makeIO (dlAppend cmds (dl [(bindCmd f)]))
alertCmd = \thing f . f thing
alert = \thing . makeIO (dl [(alertCmd thing)])
promptCmd = \prompt f . f prompt
prompt = \prompt . makeIO (dl [(promptCmd prompt)])
testM1 = return 3
testM2 = alert hello
testM3 = prompt nil
testM4 = bind (prompt [Please, type, something]) \x . alert x
testM5 = bind (prompt One) \x . bind (alert x) \y . bind (prompt Two) \z . bind (alert z) \q . return [x, z]
testM6 = bind (alert one) \x . bind (prompt Two) \y . alert y

testM7 = bind (alert one) \x . return 3
testM8 = bind (alert one) \x . bind (alert two) \y . bind (alert three) \z . return z
testM9 = bind (alert hello) \x . bind (prompt Goodbye) \y . return y

testM10 = bind (prompt One) \x . bind (bind (prompt Two) \y . return y) \z . return x

sunday = \sun mon tue wed thu fri sat . sun
monday = \sun mon tue wed thu fri sat . mon
tuesday =   \sun mon tue wed thu fri sat . tue
wednesday = \sun mon tue wed thu fri sat . wed
thursday =  \sun mon tue wed thu fri sat . thu
friday =    \sun mon tue wed thu fri sat . fri
shabbat =   \sun mon tue wed thu fri sat . sat

dayName = \day . day Sunday Monday Tuesday Wednesday Thursday Friday Saturday
nextDay = \day sun mon tue wed thu fri sat . day mon tue wed thu fri sat sun
prevDay = \day sun mon tue wed thu fri sat . day sat sun mon tue wed thu fri
testDay = dayName (nextDay monday)

testMName = bind (alert Please-enter-your-name) \x . bind (prompt name) \nm . bind (return [nm, Jr]) \nm . alert [Your, actual, name, is, nm]

#define puts i32 @puts(i8* nocapture) nounwind
#define putsl i32 @putsl(i8* nocapture) nounwind
	</pre>
</body>
</html>

Changes to evaluator.js.

20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
}
function setShowPretty(state) {
	showPretty = state
	show()
}
function step(value) {
    if (pendingIO == null || pendingMonad != value) {
	pendingIO = [LC.getAllCmds(value), LC.getVal(value)]
	pendingMonad = value
    }
    pendingIO = LC.stepIO(pendingIO[0], pendingIO[1])
    if (pendingIO.length == 1) pendingIO = null
}
function show() {document.getElementById("control").setAttribute("class", (showDebug ? "" : "hidedebug ") + (showSubs ? "showsubs " : "shownosubs ") + (showPretty ? "showpretty" : "shownopretty"))}
function handleFiles(fileElement) {







|







20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
}
function setShowPretty(state) {
	showPretty = state
	show()
}
function step(value) {
    if (pendingIO == null || pendingMonad != value) {
	pendingIO = [LC.getAllCmds(value), false]
	pendingMonad = value
    }
    pendingIO = LC.stepIO(pendingIO[0], pendingIO[1])
    if (pendingIO.length == 1) pendingIO = null
}
function show() {document.getElementById("control").setAttribute("class", (showDebug ? "" : "hidedebug ") + (showSubs ? "showsubs " : "shownosubs ") + (showPretty ? "showpretty" : "shownopretty"))}
function handleFiles(fileElement) {

Changes to lc.js.

27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
...
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
...
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
...
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
var lconsId
var lnil
var lnilId
var Lhead
var Ltail
var Lappend
var ioMonadId
var printCmdId
var readCmdId
var bindCmdId
var returnCmdId
var getCmds
var getVal
var getCmdVal
var getBindAction
var Ldl
var LdlList
var LdlAppend
var exprs = {}
var order = []
................................................................................
	Lnil = L._nil
	lnilId = LC.lnil.id
	Lhead = lcode2('head')
	Ltail = lcode2('tail')
	Lappend = lcode2('append')
    }
    if (LC.L._makeIO) {
	ioMonadId = LC.L._makeIO().lambda.body.body.id
	printCmdId = LC.L._printCmd().lambda.body.id
	readCmdId = LC.L._readCmd().lambda.body.id
	returnCmdId = LC.L._returnCmd().lambda.body.id
	bindCmdId = LC.L._bindCmd().lambda.body.id
	getCmds = lcode2('getCmds')
	LC.getAllCmds = getAllCmds = lcode2('getAllCmds')
	LC.getVal = getVal = lcode2('getVal')
	getCmdVal = lcode2('getCmdVal')
	getBindAction = lcode2('getBindAction')
	Ldl = lcode2('dl')
	LdlList = lcode2('dlList')
	LdlAppend = lcode2('dlAppend')
    }
}
................................................................................
    for (;;) {
	if (isNil(commands)) {
	    alert("Final value: " + pretty(lastRet))
	    return [lastRet]
	}
	var head = Lhead(commands)
	switch (lambdaId(head)) {
	case printCmdId:
	    alert("Print: " + pretty(getCmdVal(head)))
	    return [Ltail(commands), getVal(head)]
	case readCmdId: return [Ltail(commands), prompt(pretty(getCmdVal(head)))]
	case returnCmdId:
	    commands = Ltail(commands)
	    lastRet = getCmdVal(head)
	    continue
	case bindCmdId:
	    var action = getBindAction(head)
	    var monad = action(wrap(lastRet))

	    commands = LdlList(LdlAppend(getCmds(monad), Ldl(Ltail(commands))))
	    lastRet = getVal(monad)
	    continue
	}
	throw new Error("unknown command: " + pretty(head))
    }
}
function primRead(arg) {
    if (!arg.memo) arg.memo = prompt("Input...")
    return arg.memo
}
function getLambda(l) {return l instanceof Entity ? l : l.lambda}
function lambdaId(l) {var lam = getLambda(l); return lam && lam.id || null}
function isCons(l) {return lconsId && lambdaId(l) == lconsId}
function isIOMonad(l) {return ioMonadId && lambdaId(l) == ioMonadId}
function isNil(l) {return lnilId && lambdaId(l) == lnilId}
function pretty(l, nosubs) {
    var lam = getLambda(l)

    if (lam) {
	if (isCons(l)) return '[' + elements(l, true, nosubs) + ']'
	if (ioMonadId) switch (lambdaId(l)) {
	case ioMonadId: return "MONAD(" + pretty(getAllCmds(l)) + ", " + pretty(getVal(l)) + ")"
	case printCmdId: return "print(" + pretty(getCmdVal(l)) + ")"
	case readCmdId: return "read("+pretty(getCmdVal(l))+")"
	case returnCmdId: return "return("+pretty(getCmdVal(l))+")"
	case bindCmdId: return "bind("+pretty(getBindAction(l))+")"
	}
	return lam.format(false, nosubs)
    }
    return l
}
................................................................................
    Variable: Variable,
    Apply: Apply,
    Cons: Cons,
    cons: cons,
    index: index,
    getLambda: getLambda,
    isIOMonad: isIOMonad,
    getVal: getVal,
    stepIO: stepIO,
    isNil: isNil,
    getAllCmds: null,
}

return LC
})()







|
|



<







 







|
|
|




<







 







|
|
|
|









|





<
<
<
<











|
|
|







 







<







27
28
29
30
31
32
33
34
35
36
37
38

39
40
41
42
43
44
45
...
153
154
155
156
157
158
159
160
161
162
163
164
165
166

167
168
169
170
171
172
173
...
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226




227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
...
901
902
903
904
905
906
907

908
909
910
911
912
913
914
var lconsId
var lnil
var lnilId
var Lhead
var Ltail
var Lappend
var ioMonadId
var alertCmdId
var promptCmdId
var bindCmdId
var returnCmdId
var getCmds

var getCmdVal
var getBindAction
var Ldl
var LdlList
var LdlAppend
var exprs = {}
var order = []
................................................................................
	Lnil = L._nil
	lnilId = LC.lnil.id
	Lhead = lcode2('head')
	Ltail = lcode2('tail')
	Lappend = lcode2('append')
    }
    if (LC.L._makeIO) {
	ioMonadId = LC.L._makeIO().lambda.body.id
	alertCmdId = LC.L._alertCmd().lambda.body.id
	promptCmdId = LC.L._promptCmd().lambda.body.id
	returnCmdId = LC.L._returnCmd().lambda.body.id
	bindCmdId = LC.L._bindCmd().lambda.body.id
	getCmds = lcode2('getCmds')
	LC.getAllCmds = getAllCmds = lcode2('getAllCmds')

	getCmdVal = lcode2('getCmdVal')
	getBindAction = lcode2('getBindAction')
	Ldl = lcode2('dl')
	LdlList = lcode2('dlList')
	LdlAppend = lcode2('dlAppend')
    }
}
................................................................................
    for (;;) {
	if (isNil(commands)) {
	    alert("Final value: " + pretty(lastRet))
	    return [lastRet]
	}
	var head = Lhead(commands)
	switch (lambdaId(head)) {
	case alertCmdId:
	    alert(pretty(getCmdVal(head)))
	    return [Ltail(commands), false]
	case promptCmdId: return [Ltail(commands), prompt(pretty(getCmdVal(head)))]
	case returnCmdId:
	    commands = Ltail(commands)
	    lastRet = getCmdVal(head)
	    continue
	case bindCmdId:
	    var action = getBindAction(head)
	    var monad = action(wrap(lastRet))

	    commands = LdlList(LdlAppend(getCmds(monad), Ldl(Ltail(commands))))
	    lastRet = false
	    continue
	}
	throw new Error("unknown command: " + pretty(head))
    }
}




function getLambda(l) {return l instanceof Entity ? l : l.lambda}
function lambdaId(l) {var lam = getLambda(l); return lam && lam.id || null}
function isCons(l) {return lconsId && lambdaId(l) == lconsId}
function isIOMonad(l) {return ioMonadId && lambdaId(l) == ioMonadId}
function isNil(l) {return lnilId && lambdaId(l) == lnilId}
function pretty(l, nosubs) {
    var lam = getLambda(l)

    if (lam) {
	if (isCons(l)) return '[' + elements(l, true, nosubs) + ']'
	if (ioMonadId) switch (lambdaId(l)) {
	case ioMonadId: return "IO MONAD(" + pretty(getAllCmds(l)) + ")"
	case alertCmdId: return "alert(" + pretty(getCmdVal(l)) + ")"
	case promptCmdId: return "prompt("+pretty(getCmdVal(l))+")"
	case returnCmdId: return "return("+pretty(getCmdVal(l))+")"
	case bindCmdId: return "bind("+pretty(getBindAction(l))+")"
	}
	return lam.format(false, nosubs)
    }
    return l
}
................................................................................
    Variable: Variable,
    Apply: Apply,
    Cons: Cons,
    cons: cons,
    index: index,
    getLambda: getLambda,
    isIOMonad: isIOMonad,

    stepIO: stepIO,
    isNil: isNil,
    getAllCmds: null,
}

return LC
})()

Changes to slides.html.

1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
....
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368


1369
1370
1371
1372

1373
1374
1375
1376

1377
1378

1379
1380
1381
1382

1383
1384
1385


1386
1387
1388
1389

1390
1391
1392
1393


1394
1395
1396
1397

1398
1399
1400
1401
1402


1403
1404
1405
1406

1407
1408
1409
1410



1411


1412
1413
1414
1415
1416
1417

1418
1419
1420
1421
1422



1423
1424
1425
1426


1427
1428
1429
1430

1431
1432
1433
1434
1435





1436
1437
1438
1439

1440


1441
1442

1443
1444



1445
1446
1447
1448
1449

1450
1451

1452
1453
1454
1455




1456
1457

1458
1459

1460
1461
1462
1463
1464

1465
1466




1467
1468
1469
1470
1471






1472
1473

1474
1475

1476
1477
1478
1479
1480

1481
1482




1483
1484
1485
1486
1487

1488





1489
1490
1491
1492
1493


1494










1495


1496






1497
1498
1499
1500
1501


1502












1503


1504














1505
1506
1507
1508
1509


1510




















1511
1512














































































1513
1514
1515
1516
1517
1518
1519
....
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
      printStr "Please enter your name: "
      name <- getLine
      name <- return (name ++ " Jr")
      printStrLn ("Your actual name is: " ++ name)

Lamda Calculus example:

    bind (print hello) λx . bind (read nil) λy . return y
***
#Monads

Monads are one of the treasures of Haskell

* monads let you sequence functional operations
 * let you appear to program imperatively (with the right syntactic sugar)
................................................................................
      printStr "Please enter your name: "
      name <- getLine
      name <- return (name ++ " Jr")
      printStrLn ("Your actual name is: " ++ name)

Lamda Calculus example:

    bind (print Please-enter-your-name) λx . bind (read name) λnm . bind (return [nm, Jr]) \nm . print [Your, actual, name, is, nm]

Or with slightly more readable syntax (only slightly):

    bind (print Please-enter-your-name)
      λx . bind (read name)
      λnm . bind (return [nm, Jr])
      λnm . bind (print [Your, actual, name, is, nm])
***
#How this IO Monad works


***
#How this IO Monad works

It functions like the command pattern.  The result of a string of binds is a monad containing a list of commands.

***
#How this IO Monad works

It functions like the command pattern.  The result of a string of binds is a monad containing a list of commands.


* Bind creates a "bind" IO monad with a lambda in it

***
#How this IO Monad works

It functions like the command pattern.  The result of a string of binds is a monad containing a list of commands.


* Bind creates a "bind" IO monad with a lambda in it
* Print creates a "print" IO monad with the thing to print


***
#How this IO Monad works

It functions like the command pattern.  The result of a string of binds is a monad containing a list of commands.


* Bind creates a "bind" IO monad with a lambda in it
* Print creates a "print" IO monad with the thing to print
* Read creates a "read" IO monad with the text to prompt


***
#How this IO Monad works

It functions like the command pattern.  The result of a string of binds is a monad containing a list of commands.


* Bind creates a "bind" IO monad with a lambda in it
* Print creates a "print" IO monad with the thing to print
* Read creates a "read" IO monad with the text to prompt
* Return creates a "return" IO monad with the value to return


***
#How this IO Monad works

It functions like the command pattern.  The result of a string of binds is a monad containing a list of commands.


* Bind creates a "bind" IO monad with a lambda in it
* Print creates a "print" IO monad with the thing to print
* Read creates a "read" IO monad with the text to prompt



* Return creates a "return" IO monad with the value to return



A small, JavaScript "driver" function executes the monad's list of commands, which allows you to keep side effects out of your funcitonal code.  It executes the commands in the following way, keeping track of the current value (which starts as false):
***
#How this IO Monad works

It functions like the command pattern.  The result of a string of binds is a monad containing a list of commands.


* Bind creates a "bind" IO monad with a lambda in it
* Print creates a "print" IO monad with the thing to print
* Read creates a "read" IO monad with the text to prompt
* Return creates a "return" IO monad with the value to return




A small, JavaScript "driver" function executes the monad's list of commands, which allows you to keep side effects out of your funcitonal code.  It executes the commands in the following way, keeping track of the current value (which starts as false):

* Bind: call the lambda, which returns another monad, then add that monad's commands at the front of the current list of commands, replace the current value with the monad's value


***
#How this IO Monad works

It functions like the command pattern.  The result of a string of binds is a monad containing a list of commands.


* Bind creates a "bind" IO monad with a lambda in it
* Print creates a "print" IO monad with the thing to print
* Read creates a "read" IO monad with the text to prompt
* Return creates a "return" IO monad with the value to return






A small, JavaScript "driver" function executes the monad's list of commands, which allows you to keep side effects out of your funcitonal code.  It executes the commands in the following way, keeping track of the current value (which starts as false):

* Bind: call the lambda, which returns another monad, then add that monad's commands at the front of the current list of commands, replace the current value with the monad's value

* Print: display the argument in a JavaScript alert, replace the current value with false


***
#How this IO Monad works


It functions like the command pattern.  The result of a string of binds is a monad containing a list of commands.




* Bind creates a "bind" IO monad with a lambda in it
* Print creates a "print" IO monad with the thing to print
* Read creates a "read" IO monad with the text to prompt
* Return creates a "return" IO monad with the value to return


A small, JavaScript "driver" function executes the monad's list of commands, which allows you to keep side effects out of your funcitonal code.  It executes the commands in the following way, keeping track of the current value (which starts as false):


* Bind: call the lambda, which returns another monad, then add that monad's commands at the front of the current list of commands, replace the current value with the monad's value
* Print: display the argument in a JavaScript alert, replace the current value with false
* Read: prompt the user with the given prompt, replace the current value with the user's response




***
#How this IO Monad works


It functions like the command pattern.  The result of a string of binds is a monad containing a list of commands.


* Bind creates a "bind" IO monad with a lambda in it
* Print creates a "print" IO monad with the thing to print
* Read creates a "read" IO monad with the text to prompt
* Return creates a "return" IO monad with the value to return


A small, JavaScript "driver" function executes the monad's list of commands, which allows you to keep side effects out of your funcitonal code.  It executes the commands in the following way, keeping track of the current value (which starts as false):





* Bind: call the lambda, which returns another monad, then add that monad's commands at the front of the current list of commands, replace the current value with the monad's value
* Print: display the argument in a JavaScript alert, replace the current value with false
* Read: prompt the user with the given prompt, replace the current value with the user's response
* Return: replace the current value with the return argument






***
#How this IO Monad works


It functions like the command pattern.  The result of a string of binds is a monad containing a list of commands.


* Bind creates a "bind" IO monad with a lambda in it
* Print creates a "print" IO monad with the thing to print
* Read creates a "read" IO monad with the text to prompt
* Return creates a "return" IO monad with the value to return


A small, JavaScript "driver" function executes the monad's list of commands, which allows you to keep side effects out of your funcitonal code.  It executes the commands in the following way, keeping track of the current value (which starts as false):





* Bind: call the lambda, which returns another monad, then add that monad's commands at the front of the current list of commands, replace the current value with the monad's value
* Print: display the argument in a JavaScript alert, replace the current value with false
* Read: prompt the user with the given prompt, replace the current value with the user's response
* Return: replace the current value with the return argument







Later, we'll use the Lambda Calculator to step through some monads
***
#Extensible Syntax

`[ 1 , 2 , 3 ]` constructs lists













`[`, `,`, and `]` are really just functions









`[` creates a "list builder function"

`,` makes the list builder continue

`]` makes the list builder produce the final list















Without any extra rules, you can make functions that look like infix

















Extra parsing goodies will let you do even better

Like allowing you to leave out spaces and define groups:

`append [1,2,3] [4,5]`























This and custom control structures are good for creating your own "[DSLs](http://en.wikipedia.org/wiki/Domain-specific_language)" -- domain specific languages
***














































































#Parallel Computing

A thread changing data while another thread uses it is one of the worst horrors of parallel computing

But in functional programs, you ***can't change data***

The data you have is going to remain as it is
................................................................................

Yes, but transformed data structures can reuse parts of the original structure

And speed != efficiency (a Viper isn't quite as efficient as a Prius)

NVIDIA Fermi needs to run over 20,000 of threads for optimal usage

But to use that many threads, we needs automatic ways to *massively* parellelize code
***
#Parallel Computing

Isn't creating new data instead of changing existing data inefficient?

Yes, but transformed data structures can reuse parts of the original structure

And speed != efficiency (a Viper isn't quite as efficient as a Prius)

NVIDIA Fermi needs to run over 20,000 of threads for optimal usage

But to use that many threads, we needs automatic ways to *massively* parellelize code

Relegating high-level tasks to another thread (like updating a browser tab) isn't good enough
***
#Parallel Computing

So, functional programming can *support* parallel computing well, but can it make it easier?








|







 







|



|
|

|

|
>
>

|

<
>

|

<
>

<
>

|

<
>

<
<
>
>

|

<
>

<
<
|
>
>

|

<
>

<
<
|
|
>
>

|

<
>

<
<
|
>
>
>
|
>
>

|

|

<
>

<
<
<
<
>
>
>

|

<
>
>

|

<
>

<
<
<
<
>
>
>
>
>

|

<
>
|
>
>

<
>

<
>
>
>

<
<
<
<
>

<
>

<
<
<
>
>
>
>

<
>

<
>

<
<
<
<
>

<
>
>
>
>

<
<
<
<
>
>
>
>
>
>

<
>

<
>

<
<
<
<
>

<
>
>
>
>

<
<
<
<
>

>
>
>
>
>




|
>
>

>
>
>
>
>
>
>
>
>
>
|
>
>

>
>
>
>
>
>





>
>

>
>
>
>
>
>
>
>
>
>
>
>
|
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>





>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>


>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|











|







1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
....
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373

1374
1375
1376
1377

1378
1379

1380
1381
1382
1383

1384
1385


1386
1387
1388
1389
1390

1391
1392


1393
1394
1395
1396
1397
1398

1399
1400


1401
1402
1403
1404
1405
1406
1407

1408
1409


1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421

1422
1423




1424
1425
1426
1427
1428
1429

1430
1431
1432
1433
1434

1435
1436




1437
1438
1439
1440
1441
1442
1443
1444

1445
1446
1447
1448
1449

1450
1451

1452
1453
1454
1455




1456
1457

1458
1459



1460
1461
1462
1463
1464

1465
1466

1467
1468




1469
1470

1471
1472
1473
1474
1475




1476
1477
1478
1479
1480
1481
1482

1483
1484

1485
1486




1487
1488

1489
1490
1491
1492
1493




1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
....
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
      printStr "Please enter your name: "
      name <- getLine
      name <- return (name ++ " Jr")
      printStrLn ("Your actual name is: " ++ name)

Lamda Calculus example:

    bind (alert hello) λx . bind (prompt nil) λy . return y
***
#Monads

Monads are one of the treasures of Haskell

* monads let you sequence functional operations
 * let you appear to program imperatively (with the right syntactic sugar)
................................................................................
      printStr "Please enter your name: "
      name <- getLine
      name <- return (name ++ " Jr")
      printStrLn ("Your actual name is: " ++ name)

Lamda Calculus example:

    bind (alert Please-enter-your-name) λx . bind (prompt name) λnm . bind (return [nm, Jr]) λnm . alert [Your, actual, name, is, nm]

Or with slightly more readable syntax (only slightly):

    bind (alert Please-enter-your-name)
      λx . bind (prompt name)
      λnm . bind (return [nm, Jr])
      λnm . bind (alert [Your, actual, name, is, nm])
***
#Monads

We have a little IO monad!
***
#What Our Little IO Monad is


It's pretty much an implementation of the command pattern.  The result of a bunch of monad code is a monad containing a list of commands.
***
#What Our Little IO Monad is


It's pretty much an implementation of the command pattern.  The result of a bunch of monad code is a monad containing a list of commands.


* Bind "extends" an IO monad by making a new monad with the old commands and a new "bind" command with the lambda in it
***
#What Our Little IO Monad is


It's pretty much an implementation of the command pattern.  The result of a bunch of monad code is a monad containing a list of commands.



* Bind "extends" an IO monad by making a new monad with the old commands and a new "bind" command with the lambda in it
 * I.e. it doesn't actually execute the lambda body (that happens later)
***
#What Our Little IO Monad is


It's pretty much an implementation of the command pattern.  The result of a bunch of monad code is a monad containing a list of commands.



* Bind "extends" an IO monad by making a new monad with the old commands and a new "bind" command with the lambda in it
 * I.e. it doesn't actually execute the lambda body (that happens later)
* Alert creates an "alert" command with the thing to alert
***
#What Our Little IO Monad is


It's pretty much an implementation of the command pattern.  The result of a bunch of monad code is a monad containing a list of commands.



* Bind "extends" an IO monad by making a new monad with the old commands and a new "bind" command with the lambda in it
 * I.e. it doesn't actually execute the lambda body (that happens later)
* Alert creates an "alert" command with the thing to alert
* Prompt creates a "prompt" command with the message to use in the prompt
***
#What Our Little IO Monad is


It's pretty much an implementation of the command pattern.  The result of a bunch of monad code is a monad containing a list of commands.



* Bind "extends" an IO monad by making a new monad with the old commands and a new "bind" command with the lambda in it
 * I.e. it doesn't actually execute the lambda body (that happens later)
* Alert creates an "alert" command with the thing to alert
* Prompt creates a "prompt" command with the message to use in the prompt
* Return creates a "return" command with the value to return
***
#What Our Little IO Monad does

A small, JavaScript "driver" function executes the monad's list of commands, which allows you to keep side effects out of your funcitonal code.  It keeps track of the "current value" (starting at false) as it executes commands:
***
#What Our Little IO Monad does


A small, JavaScript "driver" function executes the monad's list of commands, which allows you to keep side effects out of your funcitonal code.  It keeps track of the "current value" (starting at false) as it executes commands:





* Bind: call the lambda with the current value, which returns another monad, then add that monad's commands to the front of the current list of commands, then change the current value to false
***
#What Our Little IO Monad does

A small, JavaScript "driver" function executes the monad's list of commands, which allows you to keep side effects out of your funcitonal code.  It keeps track of the "current value" (starting at false) as it executes commands:


* Bind: call the lambda with the current value, which returns another monad, then add that monad's commands to the front of the current list of commands, then change the current value to false
* Alert: display the argument in a JavaScript alert, then change the current value to false
***
#What Our Little IO Monad does


A small, JavaScript "driver" function executes the monad's list of commands, which allows you to keep side effects out of your funcitonal code.  It keeps track of the "current value" (starting at false) as it executes commands:





* Bind: call the lambda with the current value, which returns another monad, then add that monad's commands to the front of the current list of commands, then change the current value to false
* Alert: display the argument in a JavaScript alert, then change the current value to false
* Prompt: prompt the user with the given prompt, then change the current value to the user's response
***
#What Our Little IO Monad does

A small, JavaScript "driver" function executes the monad's list of commands, which allows you to keep side effects out of your funcitonal code.  It keeps track of the "current value" (starting at false) as it executes commands:


* Bind: call the lambda with the current value, which returns another monad, then add that monad's commands to the front of the current list of commands, then change the current value to false
* Alert: display the argument in a JavaScript alert, then change the current value to false
* Prompt: prompt the user with the given prompt, then change the current value to the user's response
* Return: change the current value to the return argument
***

#How Our Little IO Monad is Defined


* <code>makeIO  = <span class="def">λcmds f</span> . f cmds</code>
***
#How Our Little IO Monad is Defined





* <code>makeIO  = <span class="def">λcmds f</span> . f cmds</code>


Commands:




* <code>return  = <span class="def">λx</span> . makeIO [(returnCmd x)] </code>
* <code>alert	= <span class="def">λthing</span> . makeIO [(alertCmd thing)] </code>
* <code>prompt	= <span class="def">λmsg</span> . makeIO [(promptCmd msg)] </code>
* <code>bind	= <span class="def">λio f</span> . io <span class="def">λcmds</span> . makeIO (append cmds [(bindCmd f)])</code>
***

#How Our Little IO Monad is Defined


* <code>makeIO  = <span class="def">λcmds f</span> . f cmds</code>





Commands:


* <code>return  = <span class="def">λx</span> . makeIO [(returnCmd x)] </code>
* <code>alert	= <span class="def">λthing</span> . makeIO [(alertCmd thing)] </code>
* <code>prompt	= <span class="def">λmsg</span> . makeIO [(promptCmd msg)] </code>
* <code>bind	= <span class="def">λio f</span> . io <span class="def">λcmds</span> . makeIO (append cmds [(bindCmd f)])</code>





Command data:

* <code>returnCmd = <span class="def">λx f</span> . f x</code>
* <code>alertCmd	= <span class="def">λthing f</span> . f thing</code>
* <code>promptCmd	= <span class="def">λprompt f</span> . f prompt</code>
* <code>bindCmd   = <span class="def">λaction f</span> . f action</code>
***

#How Our Little IO Monad is Defined


* <code>makeIO  = <span class="def">λcmds f</span> . f cmds</code>





Commands:


* <code>return  = <span class="def">λx</span> . makeIO [(returnCmd x)] </code>
* <code>alert	= <span class="def">λthing</span> . makeIO [(alertCmd thing)] </code>
* <code>prompt	= <span class="def">λmsg</span> . makeIO [(promptCmd msg)] </code>
* <code>bind	= <span class="def">λio f</span> . io <span class="def">λcmds</span> . makeIO (append cmds [(bindCmd f)])</code>





Command data:

* <code>returnCmd = <span class="def">λx f</span> . f x</code>
* <code>alertCmd	= <span class="def">λthing f</span> . f thing</code>
* <code>promptCmd	= <span class="def">λprompt f</span> . f prompt</code>
* <code>bindCmd   = <span class="def">λaction f</span> . f action</code>

Later, we'll use the Lambda Calculator to step through some monads
***
#Extensible Syntax

`[1, 2, 3]` constructs lists
***
#Extensible Syntax

`[1, 2, 3]` constructs lists

Well, sort of.
***
#Extensible Syntax

`[1, 2, 3]` constructs lists

Well, sort of.

Actually, `[`, `,`, and `]` are just functions
***
#Extensible Syntax

`[1, 2, 3]` constructs lists

Well, sort of.

Actually, `[`, `,`, and `]` are just functions

`[` creates a "list builder function"

`,` makes the list builder continue

`]` makes the list builder produce the final list
***
#Extensible Syntax

`[1, 2, 3]` constructs lists

Well, sort of.

Actually, `[`, `,`, and `]` are just functions

`[` creates a "list builder function"

`,` makes the list builder continue

`]` makes the list builder produce the final list

So, without any extra syntax rules, you can make functions that look like infix
***
#Extensible Syntax

`[1, 2, 3]` constructs lists

Well, sort of.

Actually, `[`, `,`, and `]` are just functions

`[` creates a "list builder function"

`,` makes the list builder continue

`]` makes the list builder produce the final list

So, without any extra syntax rules, you can make functions that look like infix

Extra parsing goodies will let you do even better

Like allowing you to leave out spaces and define groups:

`append [1,2,3] [4,5]`
***
#Extensible Syntax

`[1, 2, 3]` constructs lists

Well, sort of.

Actually, `[`, `,`, and `]` are just functions

`[` creates a "list builder function"

`,` makes the list builder continue

`]` makes the list builder produce the final list

So, without any extra syntax rules, you can make functions that look like infix

Extra parsing goodies will let you do even better

Like allowing you to leave out spaces and define groups:

`append [1,2,3] [4,5]`

This and custom control structures are good for creating your own "[DSLs](http://en.wikipedia.org/wiki/Domain-specific_language)" -- domain specific languages
***
#Extensible Syntax

Here are the definitions :D
***
#Extensible Syntax

Here are the definitions :D

For purposes of meditation
***
#Extensible Syntax

Here are the definitions :D

For purposes of meditation (*torture*?)
***
#Extensible Syntax

Here are the definitions :D

For purposes of meditation (*torture*?)

<code>[ =(]= <span class="def">λitem c</span> . c <span class="def">λcont rest</span> . cons item rest</code>

<code>, =.= <span class="def">λf item c</span> . c <span class="def">λcont rest</span> . f true (cons item rest)</code>

<code>] =)= <span class="def">λf</span> . f false nil</code>

<code>| =.= <span class="def">λf rest g</span> . f false rest</code>
***
#Extensible Syntax

Here are the definitions :D

For purposes of meditation (*torture*?)

<code>[ =(]= <span class="def">λitem c</span> . c <span class="def">λcont rest</span> . cons item rest</code>

<code>, =.= <span class="def">λf item c</span> . c <span class="def">λcont rest</span> . f true (cons item rest)</code>

<code>] =)= <span class="def">λf</span> . f false nil</code>

<code>| =.= <span class="def">λf rest g</span> . f false rest</code>

This demonstrates =.=, =(?=, and =)=; our lame syntax additions...

=.= makes a function that doesn't need spaces to delimit it

=(?= makes a function that starts a group and specifies the end group function name (the '?')

=)= makes a function that closes a group
***
#Extensible Syntax

Here are the definitions :D

For purposes of meditation (*torture*?)

<code>[ =(]= <span class="def">λitem c</span> . c <span class="def">λcont rest</span> . cons item rest</code>

<code>, =.= <span class="def">λf item c</span> . c <span class="def">λcont rest</span> . f true (cons item rest)</code>

<code>] =)= <span class="def">λf</span> . f false nil</code>

<code>| =.= <span class="def">λf rest g</span> . f false rest</code>

This demonstrates =.=, =(?=, and =)=; our lame syntax additions...

=.= makes a function that doesn't need spaces to delimit it

=(?= makes a function that starts a group and specifies the end group function name (the '?')

=)= makes a function that closes a group

so ...{group-start}...{group-close}... is the same as ... ( {group-start} ... {group-close} ) ...

and ...{token}... is the same as ... {token} ...
***
#Parallel Computing

A thread changing data while another thread uses it is one of the worst horrors of parallel computing

But in functional programs, you ***can't change data***

The data you have is going to remain as it is
................................................................................

Yes, but transformed data structures can reuse parts of the original structure

And speed != efficiency (a Viper isn't quite as efficient as a Prius)

NVIDIA Fermi needs to run over 20,000 of threads for optimal usage

But to use that many threads, we need automatic ways to *massively* parellelize code
***
#Parallel Computing

Isn't creating new data instead of changing existing data inefficient?

Yes, but transformed data structures can reuse parts of the original structure

And speed != efficiency (a Viper isn't quite as efficient as a Prius)

NVIDIA Fermi needs to run over 20,000 of threads for optimal usage

But to use that many threads, we need automatic ways to *massively* parellelize code

Relegating high-level tasks to another thread (like updating a browser tab) isn't good enough
***
#Parallel Computing

So, functional programming can *support* parallel computing well, but can it make it easier?