Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# vakila/SingleArrow.ipynb

Created Apr 12, 2019
Anjana Vakil, "The Universe in a Single Arrow", JSHeroes 2019
 { "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# The Universe in a Single Arrow\n", "## A live dive into the Lambda Calculus\n", "\n", "JSHeroes 2019\n", "\n", "🐦 **[@AnjanaVakil](https://twitter.com/AnjanaVakil)** \n", " \n", "🗺️ [Mapbox](http://www.mapbox.com), 🗣️ [Mozilla TechSpeakers](https://wiki.mozilla.org/TechSpeakers), 💡 [Recurse Center](https://www.recurse.com), 👩🏽‍💻 [Outreachy](http://www.outreachy.org)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# The whatta calculus?\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "## Lambda (𝛌) Calculus\n", "* Mathematical formalism\n", "* Invented by this hero (Alonzo Church) starting 1932:\n", " ![Alonzo Church](https://upload.wikimedia.org/wikipedia/en/a/a6/Alonzo_Church.jpg)\n", "* Universal model of computation (Turing-complete) (NBD)\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "| ** Lambda function (𝛌) ** | ** Arrow function (`=>`) **\n", "--- | --- | ---\n", "*used for* | thinking | programming\n", "*inputs* | 1 | 0+\n", "*outputs* | 1 | 0+\n", "*side effects?* | no way! | maybe" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### If we treat `=>` like 𝛌, **what can we do** with it?\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "_Spoiler alert:_ EVERYTHING!!!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "#### Disclaimer: \n", "\n", "Experimentation, sillyness, & learning ahead! 😜\n", " \n", "For useful programming tips, please make a U-turn 🖖" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "\n", " | ** Lambda function (𝛌) ** | ** Arrow function (`=>`)**\n", "--- | --- | ---\n", "*making one*
*(\"abstraction\")*| λx.x | `x => x`\n", " *faking multiple args* | λx.λy.x+y | ~~`(x, y) => x + y`~~
`x => y => x + y`\n", "*using one*
*(\"application\")* | (λx.λy.x+y) 5 1
> 5+1
> 6 | `(x => y => x + y)(5)(1)`*
*> `5+1`
> `6`\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Numbers!\n", "\n", "Counting is fun!\n", "\n", "What can we count if all we have are functions?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "We can count **function applications** (calls)!" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "var zero = f => x => x;" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "var one = f => x => f(x);" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "var two = f => x => f(f(x));" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "var three = f => x => f(f(f(x)));" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Wait... are you sure these are numbers?" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "// cheating! but just for sanity checks...\n", "\n", "var toNumber = n => n(i => i+1)(0) ;" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "toNumber(two);" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "## Higher numbers!\n", "\n", "Successor function: given a number, get the next number" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "scrolled": true, "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "var succ = n => f => x => f(n(f)(x));" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "var four = succ(three);\n", "var five = succ(succ(three));\n", "var six = succ(succ(succ(three)));\n", "var seven = succ(succ(succ(succ(three))));" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/plain": [ "7" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "toNumber(seven);" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/plain": [ "8" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "var eight = seven(succ)(one);\n", "toNumber(eight);" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Yay! We have numbers! \n", "\n", "aka...\n", "\n", "### Church Numerals" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Arithmetic!\n", "\n", "How can we add two numbers `n` and `m`, when numbers are call-counters?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Call the function `n` times, then call it `m` more times!" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "var add = n => m => f => x => m(f)(n(f)(x)); " ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "5" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "var four = add(one)(three);\n", "toNumber(add(two)(three));" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Arithmetic!\n", "\n", "What about multiplying `n` and `m`?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Call the function `n` times, `m` times over!" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "var mul = n => m => f => x => m(n(f))(x);" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "12" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "toNumber(mul(four)(three));" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "## Arithmetic!\n", "\n", "What about `n` to the power of `m`?" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "var power = n => m => m(n);" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/plain": [ "81" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "toNumber(power(three)(four));" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## A Deep Thought" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "> What's the answer to life, the universe, and everything?" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "42" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "var answer = add(two)(mul(four)(mul(two)(add(four)(one))));\n", "toNumber(answer);" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "OK cool, we can do some (simple) math!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "What else do we need to write programs?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Booleans! Conditionals!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "These go hand-in-hand: \n", "\n", "` ? : `" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ " if :\n", " then \n", " else:\n", " " ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "var ifThenElse = bool => thn => els => bool(thn)(els);\n", "var troo = thn => els => thn;\n", "var falz = thn => els => els;" ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "var tired = troo ;\n", "var coffeesToday = ifThenElse(tired)(three)(one) ;\n", "toNumber(coffeesToday);" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Logic!" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "false" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "// more cheating, just for simplicity's sake...\n", "var toBoolean = bool => bool(true)(false) ;\n", "\n", "toBoolean(falz);" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "var not = bool => thn => els => bool(els)(thn);" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "false" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "toBoolean(not(troo));" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "## Predicates!" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "var is_zero = n => n(_ => falz)(troo) ;\n", "\n", "toBoolean(is_zero(zero));" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "var is_even = n => n(not)(troo) ;\n", "\n", "toBoolean(is_even(zero));" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## More logic!" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "var or = A => B => A(A)(B);" ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "toBoolean(or(falz)(troo));" ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "var and = A => B => A(B)(A);" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "data": { "text/plain": [ "false" ] }, "execution_count": 28, "metadata": {}, "output_type": "execute_result" } ], "source": [ "toBoolean(and(falz)(troo));" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "Cool, we've got some data!\n", "\n", "### What about data **structures**?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "## Lists!\n", "\n", "What can a list contain?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "* Nothing (empty, aka `nil`)\n", "* One thing\n", "* Multiple things" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "We'll build lists out of **pairs** of two things" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "## Pairs!" ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "var makePair = left => right => f => f(left)(right) ;\n", "\n", "var getLeft = pair => pair(troo);\n", "var getRight = pair => pair(falz);" ] }, { "cell_type": "code", "execution_count": 30, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "toNumber(getRight(makePair(two)(three)));" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "## Lists!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "A list will have the form: `(empty?, list_contents)`" ] }, { "cell_type": "code", "execution_count": 31, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "var isEmpty = getLeft;" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "Only `nil` (the empty list) will have `troo` as left element, i.e. `empty?` === `troo`\n", "\n", "(the right element doesn't really matter; let's make it `troo` too!)" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/plain": [ "true" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "var nil = makePair(troo)(troo) ;\n", "toBoolean(isEmpty(nil));" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "## Lists!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "To add a new item to a list, we prepend the item to the old list,\n", "making the new list:\n", "\n", "`(empty?=falz, (new_item, old_list))`" ] }, { "cell_type": "code", "execution_count": 33, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "var prepend = item => list => makePair(falz)(makePair(item)(list));" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "Non-empty lists are composed of nested pairs, e.g.\n", "\n", "`[3, 2, 1]` --> `(empty?=falz, (3,(2,(1,nil))))`" ] }, { "cell_type": "code", "execution_count": 34, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "var singleItemList = prepend(one)(nil); // (falz, (1,nil))\n", "var multiItemList = prepend(three)(prepend(two)(singleItemList)); // (falz, (3,(2,(1,nil))))" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "## Lists!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "So non-empty lists always have form: `(empty?=falz, (head,tail))` \n", "\n", "How can we get the `head` (1st item in list) & `tail` (rest of list) ? " ] }, { "cell_type": "code", "execution_count": 35, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [], "source": [ "var head = list => getLeft(getRight(list));\n", "var tail = list => getRight(getRight(list));" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "How can we select the `2` in our `multiItemList`? \n", "\n", " (falz, (3,(2,(1,nil))))" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "slideshow": { "slide_type": "skip" } }, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "toNumber(head(tail(multiItemList)));" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Yay, look at all the stuff we've got!\n", "\n", "* Data\n", " * (natural) numbers\n", " * booleans\n", "* Arithmetic\n", "* Logic & Control flow\n", "\n", "Representing data this way is called...\n", "\n", "### Church Encoding" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## There's so much more we could do!\n", "\n", "\n", "* Subtract, Divide\n", "* Successor, Predecessor\n", "* Predicates (e.g. `isZero`, `isEven`, ...)\n", "* (In)equality\n", "* Strings (as lists of characters represented by their char codes)\n", "* Lists (as nested pairs) & list manipulations (e.g. `map`, `reduce`, `filter`)\n", "* ...y'know, all of computation" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Even OOP!\n", "\n", "... wait, what?" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## FP & OOP: BFFs" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "### *Object*: \n", "- receives messages (method name + arguments) \n", "- gives responses\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "### *(Lambda) function*: \n", "\n", "- receives input\n", "- returns output\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "### *Both*: \n", "\n", "* ~~data~~ \n", "\n", "* **behavior**" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## FP & OOP: BFFs" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Smalltalk (iconic OOP language by Kay et al.)\n", "\n", "```\n", "class True\n", " ifTrue: a ifFalse: b\n", " ^ a value\n", "\n", "class False\n", " ifTrue: a ifFalse: b\n", " ^ b value\n", "```" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "Lambda calculus\n", "\n", "```\n", "TRUE := λx.λy.x\n", "FALSE := λx.λy.y\n", "```" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "This was just a taster...\n", "### Go learn more lambdas! 𝛌🐑\n", "\n", "Check out \"Fun with Lambdas\" by Corey Haines\n", " * [Upcoming book](https://leanpub.com/fun_with_lambdas)\n", " * [Talk at GOTO Chicago 2015](https://youtu.be/QPqoFCHpLF4)\n", "\n", "\n", "#### Here's some other stuff you might like!\n", "\n", "* Mary Rose Cook, [\"A practical introduction to functional programming\"](https://maryrosecook.com/blog/post/a-practical-introduction-to-functional-programming)\n", "* Me, [\"Learning Functional Programming in JavaScript\"](https://youtu.be/e-5obm1G_FY)\n", "* Alan Kay, ([Message to Smalltalk/Squeak mailing list, 1998](http://wiki.c2.com/?AlanKayOnMessaging))\n", "* William Cook, [“A Proposal for Simplified, Modern Definitions of ‘Object’ and ‘Object Oriented’”](http://wcook.blogspot.fr/2012/07/proposal-for-simplified-modern.html)\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### 💙 Merci! 💙\n", "\n", "Speaking opportunity courtesy of **JSHeroes**, **MozTechSpeakers**, **Mapbox**\n", "\n", "Inspiration courtesy of **Corey Haines** & **Darius Bacon**\n", "\n", "Slides courtesy of **[RISE](https://github.com/damianavila/RISE)** & **Jupyter notebook**\n", "\n", "Mind-explosion courtesy of **Alonzo Church**\n" ] } ], "metadata": { "celltoolbar": "Slideshow", "kernelspec": { "display_name": "Javascript (Node.js)", "language": "javascript", "name": "javascript" }, "language_info": { "file_extension": ".js", "mimetype": "application/javascript", "name": "javascript", "version": "8.11.3" }, "livereveal": { "controls": "false", "slideNumber": "false" }, "rise": { "footer": "", "scroll": "true", "theme": "white" } }, "nbformat": 4, "nbformat_minor": 2 }
to join this conversation on GitHub. Already have an account? Sign in to comment