31:[] 2f:{"title":"The Universe in a Single Arrow","cells":[{"id":12,"value":"Title = slide.md`# The Universe in a Single Arrow\n## A live dive into the Lambda Calculus\n
\n### Anjana Vakil\nDeveloper Advocate, [Observable](https://observablehq.com)\n\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":38,"value":"Intro = slide.md`## What's the Lambda (𝛌) Calculus?\n\n- Mathematical formalism based on functions\n- Developed by Alonzo Church starting 1932\n- Universal model of computation (Turing-complete) (!)\n- Foundation of functional programming (!!!)\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":61,"value":"slide.md`\n | ** Lambda function (𝛌) ** | ** Arrow function (\\`=>\\`) **\n--- | --- | ---\n*used for* | thinking | programming\n*inputs* | 1 | 0+\n*outputs* | 1 | 0+\n*side effects?* | no way! | maybe\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":89,"value":"slide.md`\n### If we treat \\`=>\\` like 𝛌... \n### *what can we do with it?*\n\n`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":87,"value":"slide.md`\n### If we treat \\`=>\\` like 𝛌... \n### *what can we do with it?*\n\n\n *Spoiler alert:* EVERYTHING!!!\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":107,"value":"slide.md`\n### If we treat \\`=>\\` like 𝛌... \n### *what can we do with it?*\n\n\n*Spoiler alert:* EVERYTHING!!!\n\n**Warning:** Abstract mathematical beauty & learning ahead! 😜\n\nWant practical programming tips? You're in the wrong place 🙃\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":242,"value":"slide.md`\n\n | ** Lambda fn (𝛌) ** | ** Arrow fn (\\`=>\\`)**\n--- | --- | ---\n
*making one*
*(\\\"abstraction\\\")*

| λx.x | \\`x => x\\`\n
*faking multiple
arguments*

| λ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\n\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":99,"value":"Numbers = slide.md`\n\n## Numbers!\n\nCounting is fun!\n\nWhat can we count if all we have are functions? 🤔\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":101,"value":"slide.md`\n\n## Numbers!\n\nCounting is fun!\n\nWhat can we count if all we have are functions? 🤔\n\nWe can count **function applications** (function calls)!\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":207,"value":"slide.html('small')`
\n\n

Numbers!<\\h2>\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":194,"value":"zero = f => x => x","pinned":true,"hidden":false,"mode":"ojs"},{"id":196,"value":"one = f => x => f(x)","pinned":true,"hidden":false,"mode":"ojs"},{"id":258,"value":"two = f => x => f(f(x))","pinned":true,"hidden":false,"mode":"ojs"},{"id":203,"value":"three = f => x => f(f(f(x)));","pinned":true,"hidden":false,"mode":"ojs"},{"id":265,"value":"slide.html('small')`

Wait... are you sure these are numbers?

\n\n

Let's cheat and convert them to JS numbers just to be sure

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":270,"value":"toNumber = n => n(i => i+1)(0);","pinned":true,"hidden":false,"mode":"ojs"},{"id":272,"value":"toNumber(two)","pinned":true,"hidden":false,"mode":"ojs"},{"id":341,"value":"slide.md` \n\nYay! We have numbers!\n\nalso known as...\n\n## Church Numerals\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":343,"value":"Arithmetic = slide.html`
\n\n

Arithmetic!

\n\n

How can we add two numbers n and m,
when numbers are function-call-counters? 🤔

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":348,"value":"slide.html('small')`
\n\n

Arithmetic!

\n\n

How can we add two numbers n and m,
when numbers are call-counters?

\n\n

Call the function n times, then call it m more times!\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":352,"value":"add = n => m => f => x => m(f)(n(f)(x))","pinned":true,"hidden":false,"mode":"ojs"},{"id":354,"value":"four = add(one)(three)","pinned":true,"hidden":false,"mode":"ojs"},{"id":366,"value":"toNumber(four)","pinned":true,"hidden":false,"mode":"ojs"},{"id":373,"value":"slide.html`
\n\n

Arithmetic!

\n\n

What about multiplying n and m? 🤔

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":377,"value":"slide.html('small')`
\n\n

Arithmetic!

\n\n

What about multiplying n and m?

\n\n

Call the function n times, and do that m times over!\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":391,"value":"mul = n => m => f => x => m(n(f))(x)","pinned":true,"hidden":false,"mode":"ojs"},{"id":400,"value":"toNumber(mul(two)(three))","pinned":true,"hidden":false,"mode":"ojs"},{"id":421,"value":"slide.html('small')`

\n\n

Arithmetic!

\n\n

What about n to the power of m?

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":424,"value":"pow = n => m => m(n)","pinned":true,"hidden":false,"mode":"ojs"},{"id":426,"value":"toNumber(pow(two)(three))","pinned":true,"hidden":false,"mode":"ojs"},{"id":433,"value":"slide.html('small')`

\n\n

A Deep Thought

\n\n

What's the answer to life, the universe, and everything? 🤔

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":436,"value":"answer = add(two)(mul(four)(mul(two)(add(four)(one))))","pinned":true,"hidden":false,"mode":"ojs"},{"id":438,"value":"toNumber(answer)","pinned":true,"hidden":false,"mode":"ojs"},{"id":441,"value":"slide.md`\n\nOK cool, we can do some (simple) math! 🎉\n\nWhat else do we need to write computer programs? 🤔\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":447,"value":"BooleanConditions = slide.html('small')`
\n\n

Booleans! Conditionals!

\n\nThese go hand-in-hand:\n
\n\\< boolean > ? \\< then do this > : \\< else do this >\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":485,"value":"ifThenElse = bool => thenDo => elseDo => bool(thenDo)(elseDo)","pinned":true,"hidden":false,"mode":"ojs"},{"id":487,"value":"troo = thenDo => elseDo => thenDo","pinned":true,"hidden":false,"mode":"ojs"},{"id":489,"value":"falz = thenDo => elseDo => elseDo","pinned":true,"hidden":false,"mode":"ojs"},{"id":493,"value":"tired = troo","pinned":true,"hidden":false,"mode":"ojs"},{"id":495,"value":"coffeesToday = ifThenElse(tired)(three)(one)","pinned":true,"hidden":false,"mode":"ojs"},{"id":497,"value":"toNumber(coffeesToday)","pinned":true,"hidden":false,"mode":"ojs"},{"id":503,"value":"slide.html('small')`

\n\n

Booleans!

\n\n\nLet's cheat again and make a JS boolean converter: \n\n
\n`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":510,"value":"toBoolean = bool => bool(true)(false)","pinned":true,"hidden":false,"mode":"ojs"},{"id":520,"value":"toBoolean(troo)","pinned":true,"hidden":false,"mode":"ojs"},{"id":526,"value":"Logic = slide.html('small')`

\n\n

Logic!

\n\n\n

Negation: How do we negate a then/else branch-picker? 🤔

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":524,"value":"not = bool => thenDo => elseDo => bool(elseDo)(thenDo)","pinned":true,"hidden":false,"mode":"ojs"},{"id":532,"value":"toBoolean(not(troo))","pinned":true,"hidden":false,"mode":"ojs"},{"id":534,"value":"slide.html('small')`

\n\n

More Logic!

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":537,"value":"or = A => B => A(A)(B)","pinned":true,"hidden":false,"mode":"ojs"},{"id":539,"value":"toBoolean(or(troo)(falz))","pinned":true,"hidden":false,"mode":"ojs"},{"id":545,"value":"and = A => B => A(B)(A)","pinned":true,"hidden":false,"mode":"ojs"},{"id":547,"value":"toBoolean(and(troo)(falz))","pinned":true,"hidden":false,"mode":"ojs"},{"id":551,"value":"slide.md`\n\nCool, now we've got some math & logic **operators**! 🎉\n\nAnd we've got some integer & boolean **data** to operate on! 🎉\n\nWhat else would be useful? 🤔\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":569,"value":"DataStructures = slide.html('small')`
\n\n

Data Structures!

\n\n

Let's start with pairs of things

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":586,"value":"makePair = left => right => f => f(left)(right)","pinned":true,"hidden":false,"mode":"ojs"},{"id":587,"value":"getLeft = pair => pair(troo)","pinned":true,"hidden":false,"mode":"ojs"},{"id":590,"value":"getRight = pair => pair(falz)","pinned":true,"hidden":false,"mode":"ojs"},{"id":592,"value":"toNumber(getLeft(makePair(two)(three)))","pinned":true,"hidden":false,"mode":"ojs"},{"id":596,"value":"slide.html`\n\n

Data Structures!

\n\n

Now let's build lists out of pairs!

\n\nWhat can a list contain? 🤔\n

Nothing (empty, aka nil)
One thing
Multiple things

Our lists will be pairs of the form:
\n(empty?, listContents)

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":634,"value":"slide.html('small')`\n\n

Lists!

\n\n

A list has the form: (empty?, listContents)

\n\n

Only nil (the empty list) will have troo on the left

\n\n(the right doesn't really matter; let's make it troo too!)\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":616,"value":"isEmpty = getLeft","pinned":true,"hidden":false,"mode":"ojs"},{"id":627,"value":"nil = makePair(troo)(troo)","pinned":true,"hidden":false,"mode":"ojs"},{"id":629,"value":"toBoolean(isEmpty(nil))","pinned":true,"hidden":false,"mode":"ojs"},{"id":610,"value":"slide.html('small')`\n

Lists!

\n\n\n

To add an item, prepend it to the front of the list, so the new list is:\n
\n (empty?=falz, (newItem, oldList))

\n\n\n\n

Non-empty lists are then made of nested pairs, e.g.\n\n
[3, 2, 1] 👉 (empty?=falz, (3,(2,(1,nil))))

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":673,"value":"prepend = item => list => makePair(falz)(makePair(item)(list))","pinned":true,"hidden":false,"mode":"ojs"},{"id":678,"value":"singleItemList = prepend(one)(nil); // (falz, (1, nil))","pinned":true,"hidden":false,"mode":"ojs"},{"id":690,"value":"multiItemList = prepend(three)(prepend(two)(singleItemList)) // (falz, (3,(2,(1,nil))))","pinned":true,"hidden":false,"mode":"ojs"},{"id":692,"value":"slide.html('small')`\n\n

Lists!

Non-empty lists have the form: (empty?=falz, (head, tail))\n

\n\n

e.g. in our multiItemList: (falz, (3,(2,(1,nil))))\n\n
the head is 3,\nand the tail is (2,(1,nil))

\n\n

How can we grab the head and tail of a list? 🤔\n
How can we retrieve an arbitrary item, e.g. 2 ? 🤔

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":714,"value":"head = list => getLeft(getRight(list))","pinned":true,"hidden":false,"mode":"ojs"},{"id":716,"value":"tail = list => getRight(getRight(list))","pinned":true,"hidden":false,"mode":"ojs"},{"id":777,"value":"toNumber(head(tail(multiItemList)))","pinned":true,"hidden":false,"mode":"ojs"},{"id":794,"value":"Recap = slide.md`\n\n### Yay, look at all this stuff we made! 🎉\n\n- Data (numbers, booleans)\n- Arithmetic operators (add, multiply, power)\n- Logic operators (not, and, or)\n- Control flow (conditionals)\n- Data structures (pairs, lists)\n\n\n
\nRepresenting data & operations this way is called\n\n## Church Encoding\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":842,"value":"slide.md`\n\n\n### And there's still so much more we could do!\n\n- Subtract, Divide\n- Predicate functions\n- (In)equality\n- Characters (represented by their codes)\n- Strings (as lists of characters)\n- List operations (e.g. map, reduce, filter)\n\n\n...you know, **all of computation** 🤯\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":225,"value":"Thanks = slide.md`\n\n#### Try it yourself\n👩🏽‍💻 [observablehq.com/@anjana/the-universe-in-a-single-arrow](https://observablehq.com/@anjana/the-universe-in-a-single-arrow)
\n\n#### Learn more Lambda\n- [Lambda Calculus](https://en.wikipedia.org/wiki/Lambda_calculus) & [Church Encoding](https://en.wikipedia.org/wiki/Church_encoding) on Wikipedia\n- [Fun with Lambdas](https://leanpub.com/fun_with_lambdas) by Corey Haines\n\n
\n## Thank you!\n🐦 [@AnjanaVakil](https://twitter.com/anjanavakil)
\n✉️ [anjana@observablehq.com](mailto:anjana@observablehq.com)\n\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":52,"value":"Appendix = md`-----\n\n### Appendix: Slideshow helpers\n\nSlides built with [@visnup/slides](https://observablehq.com/@visnup/slides)\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":20,"value":"style","pinned":false,"hidden":false,"mode":"ojs"},{"id":70,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"keyBindings","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"import { slide, style, keyBindings } from '@visnup/slides'","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}