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 family | ancestors | descendants | both | trunk files | file ages | folders 5ba8f3a3557a32263ccb1dc8ef7400c707bac8d4 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

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

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 * makeIO = λcmds f . f cmds *** #How Our Little IO Monad is Defined * makeIO = λcmds f . f cmds Commands: * return = λx . makeIO [(returnCmd x)] * alert = λthing . makeIO [(alertCmd thing)] * prompt = λmsg . makeIO [(promptCmd msg)] * bind = λio f . io λcmds . makeIO (append cmds [(bindCmd f)]) *** #How Our Little IO Monad is Defined * makeIO = λcmds f . f cmds Commands: * return = λx . makeIO [(returnCmd x)] * alert = λthing . makeIO [(alertCmd thing)] * prompt = λmsg . makeIO [(promptCmd msg)] * bind = λio f . io λcmds . makeIO (append cmds [(bindCmd f)]) Command data: * returnCmd = λx f . f x * alertCmd = λthing f . f thing * promptCmd = λprompt f . f prompt * bindCmd = λaction f . f action *** #How Our Little IO Monad is Defined * makeIO = λcmds f . f cmds Commands: * return = λx . makeIO [(returnCmd x)] * alert = λthing . makeIO [(alertCmd thing)] * prompt = λmsg . makeIO [(promptCmd msg)] * bind = λio f . io λcmds . makeIO (append cmds [(bindCmd f)]) Command data: * returnCmd = λx f . f x * alertCmd = λthing f . f thing * promptCmd = λprompt f . f prompt * bindCmd = λaction f . f action 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*?) [ =(]= λ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 *** #Extensible Syntax Here are the definitions :D For purposes of meditation (*torture*?) [ =(]= λ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 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*?) [ =(]= λ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 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?