Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: b54b7a6fa1
Fetching contributors…

Cannot retrieve contributors at this time

2051 lines (1416 sloc) 75.256 kb
<!doctype html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<title>My Slides</title>
<link rel="stylesheet" type="text/css" media="screen, projection, print"
href="slidy.css" />
<script src="showdown.js"></script>
<script src="slidy.js"></script>
<style>
.def {
color: blue;
}
.current {
color: red;
}
</style>
</head>
<body>
<script type=text/markdown>
<!--
#Back to BASICs: Primordial Programming
Getting **REALLY** close to the metal with untyped Lambda Calculus
<br>
<br>
<br>
<code>
<b>cflip</b> = <span class="def">λn</span> . n e s a2 a1 m
<b>flip</b> = func-to-row cflip
<b>allFlip</b> = row-to-func flip
<b>start</b> = <span class="def">λstatef</span> . statef gridStart shipStart t slowest
<b>checkDir</b> = <span class="def">λgrid left?</span> . left? (grid isAllFirstEmpty) (not (grid isAllLastEmpty))
<b>next</b> = <span class="def">λgrid ship left? ctr statef</span> . (<span class="def">λdir</span> . statef (ctr cTrue (grid (dir allLeft allRight) allFlip) grid) ship dir (ctr cNext)) (checkDir grid left?)
<b>moveLeft</b> = <span class="def">λgrid ship left? ctr</span> . next grid (ship (ship onFirstEmpty left)) left? ctr
<b>moveRight</b> = <span class="def">λgrid ship left? ctr</span> . next grid (ship (ship right onFirstEmpty right)) left? ctr
<b>stay</b> = <span class="def">λgrid ship left? ctr</span> . next grid ship left? ctr
<b>fire</b> = <span class="def">λgrid ship left? ctr</span> . next (missile grid ship) ship left? ctr
</code>
***
#Disclaimer: I'm not selling a language or a paradigm
Languages are tools and they all have advantages and disadvantages
I think programmers should know more languages, because they open your mind to different ways to solve problems
To understand a language, you need to program something nontrivial in a way that depends on that language's "goodies"
Examples of some fairly uncommon languages that can teach you interesting things (this list is not exhaustive)...
<table>
<tr><td>LISP (macros, code is data)
</td><td>Scheme (continuations)
</td></tr><tr><td>Haskell (lazy evaluation, monads, etc.)
</td><td>Scala (OO + functional, actors)
</td></tr><tr><td>Erlang (actors)
</td><td>Go/Oberon (implicit interfaces)
</td></tr><tr><td>TCL (dual-ported objects, uplevel)
</td><td>Smalltalk/Squeak/Scratch (foundational OO)
</td></tr><tr><td>OPS5 (forward chaining)
</td><td>Prolog (unification/backtracking)
</td></tr><tr><td>Icon (goal-directed execution/backtracking)
</td><td>FORTH/PostScript/Factor (stack languages, compile-time execution)
</td></tr><tr><td>Lua (meta model)
</td><td>Self/Io (pure prototype-based OO)</td></tr>
</table>
***
#Part 1: Concepts
#Part 2: Implementation
***
#Lambda Calculus is a Functional Programming Language
Alonzo Church (Alan Turing's professor) created Lambda Calculus around 1928.
***
#Lambda Calculus is a Functional Programming Language
Alonzo Church (Alan Turing's professor) created Lambda Calculus around 1928.
It's not the oldest programming language
***
#Lambda Calculus is a Functional Programming Language
Alonzo Church (Alan Turing's professor) created Lambda Calculus around 1928.
It's not the oldest programming language
Some Indian guy named Pāṇini beat him to the punch, when he made a grammatical system for Sanskrit that is actually a "turing equivalent" programming language
***
#Lambda Calculus is a Functional Programming Language
Alonzo Church (Alan Turing's professor) created Lambda Calculus around 1928.
It's not the oldest programming language
Some Indian guy named Pāṇini beat him to the punch, when he made a grammatical system for Sanskrit that is actually a "turing equivalent" programming language
Around 400 BC
***
#Lambda Calculus is a Functional Programming Language
Alonzo Church (Alan Turing's professor) created Lambda Calculus around 1928.
It's not the oldest programming language
Some Indian guy named Pāṇini beat him to the punch, when he made a grammatical system for Sanskrit that is actually a "turing equivalent" programming language
Around 400 BC
But I still think LC is truly primordial, based on its simplicity (very few "moving parts")
***
#Lambda Calculus is a Functional Programming Language
It's very simple
I think it's ideal for teaching CS concepts
There's just so little to get in the way
***
#Neato things that are easy to do in Lambda calculus
* custom control structures
* computed streams of data
* generators/iterators
* infinite streams
* deep code factoring (combinators)
* extensible syntax (parsing tricks can make this even more powerful)
* ***parallel computing*** (ooh... ahh...)
***
#Neato things that are easy to do in Lambda calculus
* custom control structures
<span class="current">ex: pattern matching "switch", comprehensions (that transform structures), visitors, ...</span>
* computed streams of data
* generators/iterators
* infinite streams
* deep code factoring (combinators)
* extensible syntax (parsing tricks can make this even more powerful)
* ***parallel computing*** (ooh... ahh...)
***
#Neato things that are easy to do in Lambda calculus
* custom control structures
ex: pattern matching "switch", comprehensions (that transform structures), visitors, ...
* computed streams of data
<span class="current">transformable collections of values produced by functions</span>
* generators/iterators
* infinite streams
* deep code factoring (combinators)
* extensible syntax (parsing tricks can make this even more powerful)
* ***parallel computing*** (ooh... ahh...)
***
#Neato things that are easy to do in Lambda calculus
* custom control structures
ex: pattern matching "switch", comprehensions (that transform structures), visitors, ...
* computed streams of data
transformable collections of values produced by functions
* generators/iterators
<span class="current">present datastructures as streams</span>
* infinite streams
* deep code factoring (combinators)
* extensible syntax (parsing tricks can make this even more powerful)
* ***parallel computing*** (ooh... ahh...)
***
#Neato things that are easy to do in Lambda calculus
* custom control structures
ex: pattern matching "switch", comprehensions (that transform structures), visitors, ...
* computed streams of data
transformable collections of values produced by functions
* generators/iterators
present datastructures as streams
* infinite streams
<span class="current">simple and complex streams of infinite values are good for loops and some computations</span>
* deep code factoring (combinators)
* extensible syntax (parsing tricks can make this even more powerful)
* ***parallel computing*** (ooh... ahh...)
***
#Neato things that are easy to do in Lambda calculus
* custom control structures
ex: pattern matching "switch", comprehensions (that transform structures), visitors, ...
* computed streams of data
transformable collections of values produced by functions
* generators/iterators
present datastructures as streams
* infinite streams
simple and complex streams of infinite values are good for loops and some computations
* deep code factoring (combinators)
<span class="current">types of code factoring that you don't really see in mainstream languages (C/C++/Java/C#/Python)</span>
* extensible syntax (parsing tricks can make this even more powerful)
* ***parallel computing*** (ooh... ahh...)
***
#Neato things that are easy to do in Lambda calculus
* custom control structures
ex: pattern matching "switch", comprehensions (that transform structures), visitors, ...
* computed streams of data
transformable collections of values produced by functions
* generators/iterators
present datastructures as streams
* infinite streams
simple and complex streams of infinite values are good for loops and some computations
* deep code factoring (combinators)
types of code factoring that you don't really see in mainstream languages (C/C++/Java/C#/Python)
* extensible syntax (parsing tricks can make this even more powerful)
<span class="current">create Domain Specific Languages (DSLs)</span>
* ***parallel computing*** (ooh... ahh...)
***
#Neato things that are easy to do in Lambda calculus
* custom control structures
ex: pattern matching "switch", comprehensions (that transform structures), visitors, ...
* computed streams of data
transformable collections of values produced by functions
* generators/iterators
present datastructures as streams
* infinite streams
simple and complex streams of infinite values are good for loops and some computations
* deep code factoring (combinators)
types of code factoring that you don't really see in mainstream languages (C/C++/Java/C#/Python)
* extensible syntax (parsing tricks can make this even more powerful)
create Domain Specific Languages (DSLs)
* ***parallel computing*** (ooh... ahh...)
<span class="current">Haskell (and other functional languages) have tools for massively parallel programs (20,000+ threads)</span>
***
#Neato things that are easy to do in Lambda calculus
* custom control structures
ex: pattern matching "switch", comprehensions (that transform structures), visitors, ...
* computed streams of data
transformable collections of values produced by functions
* generators/iterators
present datastructures as streams
* infinite streams
simple and complex streams of infinite values are good for loops and some computations
* deep code factoring (combinators)
types of code factoring that you don't really see in mainstream languages (C/C++/Java/C#/Python)
* extensible syntax (parsing tricks can make this even more powerful)
create Domain Specific Languages (DSLs)
* ***parallel computing*** (ooh... ahh...)
Haskell (and other functional languages) have tools for massively parallel programs (20,000+ threads)
<span class="current">You can do some of these things in a lot of other languages, but they probably won't be as straight-forward. They can still be very useful and powerful, though. One example of this is the [Functional Java](http://functionaljava.org/) library, which bolts functional capabilities onto Java.</span>
***
#Lambda Calculus is Primordial
How primordial is it?
***
<table style="position: absolute; height: 100%; width: 100%"><tr><td style="vertical-align: center"><h1 style="text-align: center; font-size: 64px">
THERE ARE NO NUMBERS
</h1></td></tr></table>
***
<table style="position: absolute; height: 100%; width: 100%"><tr><td style="vertical-align: center"><h1 style="text-align: center; font-size: 64px">
THERE ARE NO BITS
</h1></td></tr></table>
***
<table style="position: absolute; height: 100%; width: 100%"><tr><td style="vertical-align: center"><h1 style="text-align: center; font-size: 64px">
THERE ARE NO COMPARISONS
</h1></td></tr></table>
***
<table style="position: absolute; height: 100%; width: 100%"><tr><td style="vertical-align: center"><h1 style="text-align: center; font-size: 64px">
WHAT THE?
</h1></td></tr></table>
***
<table style="position: absolute; height: 100%; width: 100%"><tr><td style="vertical-align: center"><h1 style="text-align: center; font-size: 64px">
YOU CAN'T EVEN REASSIGN VARIABLES
</h1></td></tr></table>
***
<table style="position: absolute; height: 100%; width: 100%"><tr><td style="vertical-align: center"><h1 style="text-align: center; font-size: 64px">
WHAT THE?
</h1></td></tr></table>
***
<table style="position: absolute; height: 100%; width: 100%"><tr><td style="vertical-align: center"><h1 style="text-align: center; font-size: 64px">
THERE ARE NO LOOPS
</h1></td></tr></table>
***
<table style="position: absolute; height: 100%; width: 100%"><tr><td style="vertical-align: center"><h1 style="text-align: center; font-size: 64px">
SH**...
</h1></td></tr></table>
***
<table style="position: absolute; height: 100%; width: 100%"><tr><td style="vertical-align: center"><h1 style="text-align: center; font-size: 64px">
THERE ISN'T EVEN RECURSION
</h1></td></tr></table>
***
<table style="position: absolute; height: 100%; width: 100%"><tr><td style="vertical-align: center"><h1 style="text-align: center; font-size: 64px">
F*******!
</h1></td></tr></table>
***
#It's not as bad as it seems
It's actually very powerful
It's easy to use, once you get the hang of it
(and modern versions of typed LC, like Haskell do give you primitive numbers and comparisons)
***
#It's not as bad as it seems
No numbers or comparisons &rArr; students can implement them themselves
How do you define bits, numbers, and ">" in C or even in assembly?
Students can even implement recursion themselves!
This is the primoridal value of LC
But even at this low level, you can still do "real" things...
***
#It's not as bad as it seems
To show this, I started on a version of [Space Invaders in Lambda Calculus](http://tinyconcepts.com/invaders.html)
55 lines of code, so far (including definitions for numbers and comparisons)
Uses JavaScript to display the state and get events
***
#Evaluator
To run it, I made a [Lambda Calculus evaluator](evaluator.html) in JavaScript
It can run Lambda Calculus 3 different ways...
1. compile into JavaScript
1. interpret in JavaScript and show the substitution steps
1. compile into virtual machine bytecode (and run it)
I'm working on an LLVM code generator to compile into native machine code (and let you link with libraries)
The idea here is to give people insight into how compilers, interpreters, and VMs work
***
#Brief Overview
Teaching and experimentation
The things in this talk also work in Haskell
Haskell has proven to be practical and fast (DARCS DVCS is written in Haskell)
Maybe untyped LC could be too
**LC gives you a lot of power and productivity, even though it's low-level**
* LC uses "lazy evaluation" -- function arguments are never evaluated until they are used (and this is transitive)
* LC is only functions -- data is also functions, which means data is also lazy
* LC allows "currying" -- calling a 3-arg function with only the first 2 args returns a 1-arg function that "saves" the first 2
Lazy evaluation + currying + data/functions can be very powerful
Most languages don't support this
***
#Brief Overview: Functions
LC is only functions and functions are like subroutines
***
#Brief Overview: Functions
LC is only functions and functions are like subroutines
Here's a JavaScript function: `function(argument) {return body}`
***
#Brief Overview: Functions
LC is only functions and functions are like subroutines
Here's a JavaScript function: `function(argument) {return body}`
In Lambda Calculus, you would say this: <code><span class="def">λargument</span> . body</code>
***
#Brief Overview: Functions
LC is only functions and functions are like subroutines
Here's a JavaScript function: `function(argument) {return body}`
In Lambda Calculus, you would say this: <code><span class="def">λargument</span> . body</code>
<br>
<br>
A function body can...
* return a function: <code><span class="def">λa</span> . <span class="def">λb</span> . a</code>
***
#Brief Overview: Functions
LC is only functions and functions are like subroutines
Here's a JavaScript function: `function(argument) {return body}`
In Lambda Calculus, you would say this: <code><span class="def">λargument</span> . body</code>
<br>
<br>
A function body can...
* return a function: <code><span class="def">λa</span> . <span class="def">λb</span> . a</code>
* return an argument: <code><span class="def">λb</span> . a</code>
***
#Brief Overview: Functions
LC is only functions and functions are like subroutines
Here's a JavaScript function: `function(argument) {return body}`
In Lambda Calculus, you would say this: <code><span class="def">λargument</span> . body</code>
<br>
<br>
A function body can...
* return a function: <code><span class="def">λa</span> . <span class="def">λb</span> . a</code>
* return an argument: <code><span class="def">λb</span> . a</code>
* call a function with a value (and the result with another value, etc.): <code><span class="def">λa</span> . <span class="def">λb</span> . <span class="def">λf</span> . f a</code>
***
#Brief Overview: Functions
LC is only functions and functions are like subroutines
Here's a JavaScript function: `function(argument) {return body}`
In Lambda Calculus, you would say this: <code><span class="def">λargument</span> . body</code>
<br>
<br>
A function body can...
* return a function: <code><span class="def">λa</span> . <span class="def">λb</span> . a</code>
* return an argument: <code><span class="def">λb</span> . a</code>
* call a function with a value (and the result with another value, etc.): <code><span class="def">λa</span> . <span class="def">λb</span> . <span class="def">λf</span> . f a</code>
Values can be functions or undefined
***
#Brief Overview: Functions
A function which returns another function acts like it takes another argument
<code>t = <span class="def">λa</span> . <span class="def">λb</span> . a</code>
Calling `t` with `1` substitutes `1` for `a` in the body: <code>t 1 &rArr; <span class="def">λb</span> . 1</code>
When you call that function with any argument, you get 1, because that's the body: <code>(t 1) 2 &rArr; 1</code>
LC is "left associative" and lets you say `t 1 2`, instead of `(t 1) 2`
(So `t 1` is really currying `t 1 2`)
When people make multiple argument functions this way, they smash them together:
<code><span class="def">λa</span> . <span class="def">λb</span> . a</code>
becomes
<code><span class="def">λa b</span> . a</code>
It's less of a pain
***
#Brief Overview: Data
<code>PERSON = makePerson fred 777-2344</code>
<code>getName PERSON &rArr; fred</code>
<code>getNumber PERSON &rArr; 777-2344</code>
PERSON is a function, because everything in Lambda Calculus is a function.
***
#Brief Overview: Data
Here's how you can define our simple "person record"...
<code>makePerson = <span class="def">λname number f</span> . f name number</code>
***
#Brief Overview: Data
Here's how you can define our simple "person record"...
<code>makePerson = <span class="def">λname number f</span> . f name number</code>
Calling `makePerson` with a name returns a function that takes a number and returns another function:
<code>makePerson fred &rArr; <span class="def">λnumber f</span> . f fred number</code>
***
#Brief Overview: Data
Here's how you can define our simple "person record"...
<code>makePerson = <span class="def">λname number f</span> . f name number</code>
Calling `makePerson` with a name returns a function that takes a number and returns another function:
<code>makePerson fred &rArr; <span class="def">λnumber f</span> . f fred number</code>
You can call that with a number to get a "person record":
<code>(makePerson fred) 777-2344 &rArr; <span class="def">λf</span> . f fred 777-2344</code>
***
#Brief Overview: Data
Here's how you can define our simple "person record"...
<code>makePerson = <span class="def">λname number f</span> . f name number</code>
Calling `makePerson` with a name returns a function that takes a number and returns another function:
<code>makePerson fred &rArr; <span class="def">λnumber f</span> . f fred number</code>
You can call that with a number to get a "person record":
<code>(makePerson fred) 777-2344 &rArr; <span class="def">λf</span> . f fred 777-2344</code>
Lambda Calculus is "left associative" to make this easier:
<code>makePerson fred 777-2344 &rArr; <span class="def">λf</span> . f fred 777-2344</code>
***
#Brief Overview: Data
**Wait -- what just happened?**
***
#Brief Overview: Data
**Wait -- what just happened?**
We used currying to create a "person record"...
***
#Brief Overview: Data
**Wait -- what just happened?**
We used currying to create a "person record"...
<code>makePerson = <span class="def">λname number f</span> . f name number</code>
<code>makePerson fred 777-2344 &rArr; <span class="def">λf</span> . f fred 777-2344</code>
***
#Brief Overview: Data
**Wait -- what just happened?**
We used currying to create a "person record"...
<code>makePerson = <span class="def">λname number f</span> . f name number</code>
<code>makePerson fred 777-2344 &rArr; <span class="def">λf</span> . f fred 777-2344</code>
See how `makePerson` defines this `f` argument, but we aren't using it?
***
#Brief Overview: Data
**Wait -- what just happened?**
We used currying to create a "person record"...
<code>makePerson = <span class="def">λname number f</span> . f name number</code>
<code>makePerson fred 777-2344 &rArr; <span class="def">λf</span> . f fred 777-2344</code>
See how `makePerson` defines this `f` argument, but we aren't using it?
When I send only 2 arguments to `makePerson`, I get back a function that takes an `f`
***
#Brief Overview: Data
**Wait -- what just happened?**
We used currying to create a "person record"...
<code>makePerson = <span class="def">λname number f</span> . f name number</code>
<code>makePerson fred 777-2344 &rArr; <span class="def">λf</span> . f fred 777-2344</code>
See how `makePerson` defines this `f` argument, but we aren't using it?
When I send only 2 arguments to `makePerson`, I get back a function that takes an `f`
The fact that I can send in `f` later allows the "person record function" to work
***
#Brief Overview: Data
**Wait -- what just happened?**
We used currying to create a "person record"...
<code>makePerson = <span class="def">λname number f</span> . f name number</code>
<code>makePerson fred 777-2344 &rArr; <span class="def">λf</span> . f fred 777-2344</code>
See how `makePerson` defines this `f` argument, but we aren't using it?
When I send only 2 arguments to `makePerson`, I get back a function that takes an `f`
The fact that I can send in `f` later allows the "person record function" to work
LC uses currying for a LOT of things
***
#Brief Overview: Data
<code><span class="def">λf</span> . f fred 777-2344</code>
This "person record" takes a function `f` and applies it to the name and number
You could define `getName` to return the name of the person
***
#Brief Overview: Data
<code><span class="def">λf</span> . f fred 777-2344</code>
This "person record" takes a function `f` and applies it to the name and number
You could define `getName` to return the name of the person
<code>getName = <span class="def">λperson</span> . person (<span class="def">λname number</span> . name)</code>
***
#Brief Overview: Data
<code><span class="def">λf</span> . f fred 777-2344</code>
This "person record" takes a function `f` and applies it to the name and number
You could define `getName` to return the name of the person
<code>getName = <span class="def">λperson</span> . person (<span class="def">λname number</span> . name)</code>
<code>getName (<span class="def">λf</span> . f fred 777-2344) &rArr; fred</code>
***
#Brief Overview: Data
<code><span class="def">λf</span> . f fred 777-2344</code>
This "person record" takes a function `f` and applies it to the name and number
You could define `getName` to return the name of the person
<code>getName = <span class="def">λperson</span> . person (<span class="def">λname number</span> . name)</code>
<code>getName (<span class="def">λf</span> . f fred 777-2344) &rArr; fred</code>
This is a lot like `struct person p = {"fred", "777-2344"};` in C
***
#Brief Overview: Data
<code><span class="def">λf</span> . f fred 777-2344</code>
This "person record" takes a function `f` and applies it to the name and number
You could define `getName` to return the name of the person
<code>getName = <span class="def">λperson</span> . person (<span class="def">λname number</span> . name)</code>
<code>getName (<span class="def">λf</span> . f fred 777-2344) &rArr; fred</code>
This is a lot like `struct person p = {"fred", "777-2344"};` in C
but later, we'll see some powerful differences.
***
#Custom Control Structures: Booleans/Ifs
You can use booleans in LC as if-then statements, kind of like how C uses && and ||
* <code>true = <span class="def">λa b</span> . a</code>
* <code>false = <span class="def">λa b</span> . b</code>
***
#Custom Control Structures: Booleans/Ifs
You can use booleans in LC as if-then statements, kind of like how C uses && and ||
* <code>true = <span class="def">λa b</span> . a</code>
* <code>false = <span class="def">λa b</span> . b</code>
true really just means "choose the first one"
***
#Custom Control Structures: Booleans/Ifs
You can use booleans in LC as if-then statements, kind of like how C uses && and ||
* <code>true = <span class="def">λa b</span> . a</code>
* <code>false = <span class="def">λa b</span> . b</code>
true really just means "choose the first one"
false really just means "choose the second one"
***
#Custom Control Structures: Booleans/Ifs
You can use booleans in LC as if-then statements, kind of like how C uses && and ||
* <code>true = <span class="def">λa b</span> . a</code>
* <code>false = <span class="def">λa b</span> . b</code>
true really just means "choose the first one"
false really just means "choose the second one"
kind of like an if-then statement
***
#Custom Control Structures: Booleans/Ifs
You can use booleans in LC as if-then statements, kind of like how C uses && and ||
* <code>true = <span class="def">λa b</span> . a</code>
* <code>false = <span class="def">λa b</span> . b</code>
true really just means "choose the first one"
false really just means "choose the second one"
kind of like an if-then statement
Suppose you have three variables, `v1 = true`, `v2 = false`, and `v3 = false`
***
#Custom Control Structures: Booleans/Ifs
You can use booleans in LC as if-then statements, kind of like how C uses && and ||
* <code>true = <span class="def">λa b</span> . a</code>
* <code>false = <span class="def">λa b</span> . b</code>
true really just means "choose the first one"
false really just means "choose the second one"
kind of like an if-then statement
Suppose you have three variables, `v1 = true`, `v2 = false`, and `v3 = false`
<code>v1 (v2 a b) (v3 c d) &rArr; b</code>
***
#Custom Control Structures: Booleans/Ifs
You can use booleans in LC as if-then statements, kind of like how C uses && and ||
* <code>true = <span class="def">λa b</span> . a</code>
* <code>false = <span class="def">λa b</span> . b</code>
true really just means "choose the first one"
false really just means "choose the second one"
kind of like an if-then statement
Suppose you have three variables, `v1 = true`, `v2 = false`, and `v3 = false`
<code>v1 (v2 a b) (v3 c d) &rArr; b</code>
This doesn't evaluate several things, like in `(v1 && ((v2 && a) || b)) || ((v3 && c) || d)`
***
#Custom Control Structures: Booleans/Ifs
You can use booleans in LC as if-then statements, kind of like how C uses && and ||
* <code>true = <span class="def">λa b</span> . a</code>
* <code>false = <span class="def">λa b</span> . b</code>
true really just means "choose the first one"
false really just means "choose the second one"
kind of like an if-then statement
Suppose you have three variables, `v1 = true`, `v2 = false`, and `v3 = false`
<code>v1 (v2 a b) (v3 c d) &rArr; b</code>
This doesn't evaluate several things, like in `(v1 && ((v2 && a) || b)) || ((v3 && c) || d)`
Lazy evaluation makes **everything** use "short-circuit" evaluation, like C's && and ||
***
#Custom Control Structures
Control structures are all about choosing what to do
Lazy evaluation lets you define your own control structures, like if, for, while, switch, etc.
There are some pretty useful control structures that aren't in C or Java
(like Scala's pattern matching "switch" and powerful "for")
***
#Custom Control Structures: Enums/Switches
Maybe you already guessed this...
***
#Custom Control Structures: Enums/Switches
Maybe you already guessed this...
If you can represent a boolean by a function that applies its argument to two values, what about more than 2?
***
#Custom Control Structures: Enums/Switches
Maybe you already guessed this...
If you can represent a boolean by a function that applies its argument to two values, what about more than 2?
* <code>sunday = <span class="def">λsun mon tue wed thu fri sat</span> . sun</code>
***
#Custom Control Structures: Enums/Switches
Maybe you already guessed this...
If you can represent a boolean by a function that applies its argument to two values, what about more than 2?
* <code>sunday = <span class="def">λsun mon tue wed thu fri sat</span> . sun</code>
* <code>monday = <span class="def">λsun mon tue wed thu fri sat</span> . mon</code>
* <code>tuesday = <span class="def">λsun mon tue wed thu fri sat</span> . tue</code>
* <code>wednesday = <span class="def">λsun mon tue wed thu fri sat</span> . wed</code>
* <code>thursday = <span class="def">λsun mon tue wed thu fri sat</span> . thu</code>
* <code>friday = <span class="def">λsun mon tue wed thu fri sat</span> . fri</code>
* <code>saturday = <span class="def">λsun mon tue wed thu fri sat</span> . sat</code>
***
#Custom Control Structures: Enums/Switches
Maybe you already guessed this...
If you can represent a boolean by a function that applies its argument to two values, what about more than 2?
* <code>sunday = <span class="def">λsun mon tue wed thu fri sat</span> . sun</code>
* <code>monday = <span class="def">λsun mon tue wed thu fri sat</span> . mon</code>
* <code>tuesday = <span class="def">λsun mon tue wed thu fri sat</span> . tue</code>
* <code>wednesday = <span class="def">λsun mon tue wed thu fri sat</span> . wed</code>
* <code>thursday = <span class="def">λsun mon tue wed thu fri sat</span> . thu</code>
* <code>friday = <span class="def">λsun mon tue wed thu fri sat</span> . fri</code>
* <code>saturday = <span class="def">λsun mon tue wed thu fri sat</span> . sat</code>
<code>dayName = <span class="def">λday</span> . day Sunday Monday Tuesday Wednesday Thursday Friday Saturday</code>
***
#Custom Control Structures: Enums/Switches
Maybe you already guessed this...
If you can represent a boolean by a function that applies its argument to two values, what about more than 2?
* <code>sunday = <span class="def">λsun mon tue wed thu fri sat</span> . sun</code>
* <code>monday = <span class="def">λsun mon tue wed thu fri sat</span> . mon</code>
* <code>tuesday = <span class="def">λsun mon tue wed thu fri sat</span> . tue</code>
* <code>wednesday = <span class="def">λsun mon tue wed thu fri sat</span> . wed</code>
* <code>thursday = <span class="def">λsun mon tue wed thu fri sat</span> . thu</code>
* <code>friday = <span class="def">λsun mon tue wed thu fri sat</span> . fri</code>
* <code>saturday = <span class="def">λsun mon tue wed thu fri sat</span> . sat</code>
<code>dayName = <span class="def">λday</span> . day Sunday Monday Tuesday Wednesday Thursday Friday Saturday</code>
<code>dayName thursday &rArr; Thursday</code>
***
#Custom Control Structures: Enums/Switches
So, OK, it's like a switch. But can we get the next or previous day?
***
#Custom Control Structures: Enums/Switches
So, OK, it's like a switch. But can we get the next or previous day?
* <code>nextDay = <span class="def">λday</span> . day monday tuesday wednesday thursday friday saturday sunday</code>
* <code>prevDay = <span class="def">λday</span> . day saturday sunday monday tuesday wednesday thursday friday</code>
***
#Custom Control Structures: Enums/Switches
So, OK, it's like a switch. But can we get the next or previous day?
* <code>nextDay = <span class="def">λday</span> . day monday tuesday wednesday thursday friday saturday sunday</code>
* <code>prevDay = <span class="def">λday</span> . day saturday sunday monday tuesday wednesday thursday friday</code>
<code>dayName (nextDay monday) &rArr; Tuesday</code>
<code>dayName (prevDay monday) &rArr; Sunday</code>
***
#Computed Streams of Data
`nil` is an empty list
***
#Computed Streams of Data
`nil` is an empty list
`cons a b` makes a list with a as the "head" and b as the "tail"
***
#Computed Streams of Data
`nil` is an empty list
`cons a b` makes a list with a as the "head" and b as the "tail"
The tail is usually either `nil` or another cons, which makes a chain of values
***
#Computed Streams of Data
`nil` is an empty list
`cons a b` makes a list with a as the "head" and b as the "tail"
The tail is usually either `nil` or another cons, which makes a chain of values
`nil` &rArr; `[]`
***
#Computed Streams of Data
`nil` is an empty list
`cons a b` makes a list with a as the "head" and b as the "tail"
The tail is usually either `nil` or another cons, which makes a chain of values
`nil` &rArr; `[]`
`cons A nil` &rArr; `[A]`
***
#Computed Streams of Data
`nil` is an empty list
`cons a b` makes a list with a as the "head" and b as the "tail"
The tail is usually either `nil` or another cons, which makes a chain of values
`nil` &rArr; `[]`
`cons A nil` &rArr; `[A]`
`cons A (cons B nil)` &rArr; `[A, B]`
***
#Computed Streams of Data
`nil` is an empty list
`cons a b` makes a list with a as the "head" and b as the "tail"
The tail is usually either `nil` or another cons, which makes a chain of values
`nil` &rArr; `[]`
`cons A nil` &rArr; `[A]`
`cons A (cons B nil)` &rArr; `[A, B]`
`cons A (cons B (cons C nil))` &rArr; `[A, B, C]`
***
#Computed Streams of Data
`cons A (cons B (cons C nil))` &rArr; `[A, B, C]`
Here are the LC definitions:
* <code>cons = <span class="def">λh t f</span> . f h t</code>
* <code>head = <span class="def">λlist</span> . list (<span class="def">λhead tail</span> . head)</code>
* <code>tail = <span class="def">λlist</span> . list (<span class="def">λhead tail</span> . tail)</code>
* <code>nil = <span class="def">λa b</span> . b</code>
* <code>null = <span class="def">λlist</span> . list (<span class="def">λhead tail DUMMY </span> . false) true</code>
***
#Computed Streams of Data
`cons A (cons B (cons C nil))` &rArr; `[A, B, C]`
Here are the LC definitions:
* <code>cons = <span class="def">λh t f</span> . f h t</code>
* <code>head = <span class="def">λlist</span> . list (<span class="def">λhead tail</span> . head)</code>
* <code>tail = <span class="def">λlist</span> . list (<span class="def">λhead tail</span> . tail)</code>
* <code>nil = <span class="def">λa b</span> . b</code>
* <code>null = <span class="def">λlist</span> . list (<span class="def">λhead tail DUMMY </span> . false) true</code>
Null returns whether or not a list is `nil` and uses a currying trick to do it...
***
#Computed Streams of Data
`cons A (cons B (cons C nil))` &rArr; `[A, B, C]`
Here are the LC definitions:
* <code>cons = <span class="def">λh t f</span> . f h t</code>
* <code>head = <span class="def">λlist</span> . list (<span class="def">λhead tail</span> . head)</code>
* <code>tail = <span class="def">λlist</span> . list (<span class="def">λhead tail</span> . tail)</code>
* <code>nil = <span class="def">λa b</span> . b</code>
* <code>null = <span class="def">λlist</span> . list (<span class="def">λhead tail DUMMY </span> . false) true</code>
Null returns whether or not a list is `nil` and uses a currying trick to do it...
if list is empty, then it's "false", and it will just ignore the first argument, so that's "normal"
***
#Computed Streams of Data
`cons A (cons B (cons C nil))` &rArr; `[A, B, C]`
Here are the LC definitions:
* <code>cons = <span class="def">λh t f</span> . f h t</code>
* <code>head = <span class="def">λlist</span> . list (<span class="def">λhead tail</span> . head)</code>
* <code>tail = <span class="def">λlist</span> . list (<span class="def">λhead tail</span> . tail)</code>
* <code>nil = <span class="def">λa b</span> . b</code>
* <code>null = <span class="def">λlist</span> . list (<span class="def">λhead tail DUMMY </span> . false) true</code>
Null returns whether or not a list is `nil` and uses a currying trick to do it...
if list is empty, then it's "false", and it will just ignore the first argument, so that's "normal"
but what if list is not empty?
***
#Computed Streams of Data
`cons A (cons B (cons C nil))` &rArr; `[A, B, C]`
Here are the LC definitions:
* <code>cons = <span class="def">λh t f</span> . f h t</code>
* <code>head = <span class="def">λlist</span> . list (<span class="def">λhead tail</span> . head)</code>
* <code>tail = <span class="def">λlist</span> . list (<span class="def">λhead tail</span> . tail)</code>
* <code>nil = <span class="def">λa b</span> . b</code>
* <code>null = <span class="def">λlist</span> . list (<span class="def">λhead tail DUMMY </span> . false) true</code>
Null returns whether or not a list is `nil` and uses a currying trick to do it...
if list is empty, then it's "false", and it will just ignore the first argument, so that's "normal"
but what if list is not empty?
list (<span class="def">λhead tail DUMMY</span> . false) true</code><br>
&rArr; (<span class="def">λDUMMY</span> . false) true</code><br>
&rArr; false
***
#Computed Streams of Data
`cons A (cons B (cons C nil))` &rArr; `[A, B, C]`
Here are the LC definitions:
* <code>cons = <span class="def">λh t f</span> . f h t</code>
* <code>head = <span class="def">λlist</span> . list (<span class="def">λhead tail</span> . head)</code>
* <code>tail = <span class="def">λlist</span> . list (<span class="def">λhead tail</span> . tail)</code>
* <code>nil = <span class="def">λa b</span> . b</code>
* <code>null = <span class="def">λlist</span> . list (<span class="def">λhead tail DUMMY </span> . false) true</code>
Null returns whether or not a list is `nil` and uses a currying trick to do it...
if list is empty, then it's "false", and it will just ignore the first argument, so that's "normal"
but what if list is not empty?
list (<span class="def">λhead tail DUMMY</span> . false) true</code><br>
&rArr; (<span class="def">λDUMMY</span> . false) true</code><br>
&rArr; false
Lazy evaluation makes computing a list in LC like making a Java/C++ iterator or a Python generator
***
#Computed Streams of Data
What cons does...
***
#Computed Streams of Data
What cons does...
<code>cons A nil &rArr; <span class="def">λf</span> . f A nil</code>
***
#Computed Streams of Data
What cons does...
<code>cons A nil &rArr; <span class="def">λf</span> . f A nil</code>
<code>cons B (cons A nil) &rArr; <span class="def">λf2</span> . f2 B (<span class="def">λf</span> . f A nil)</code>
***
#Computed Streams of Data
What cons does...
<code>cons A nil &rArr; <span class="def">λf</span> . f A nil</code>
<code>cons B (cons A nil) &rArr; <span class="def">λf2</span> . f2 B (<span class="def">λf</span> . f A nil)</code>
Right?
***
#Computed Streams of Data
What cons does...
<code>cons A nil &rArr; <span class="def">λf</span> . f A nil</code>
<code>cons B (cons A nil) &rArr; <span class="def">λf2</span> . f2 B (<span class="def">λf</span> . f A nil)</code>
Right?
Let's look at the replay...
***
#Computed Streams of Data
What cons does...
<code>cons A nil &rArr; <span class="def">λf</span> . f A nil</code>
<code>cons B (cons A nil) &rArr; <span class="def">λf2</span> . f2 B (<span class="def">λf</span> . f A nil)</code>
Right?
Let's look at the replay...
<code>cons B (cons A nil) &rArr; <span class="def">λf2</span> . f2 B (cons A nil)</code>
***
#Computed Streams of Data
What cons does...
<code>cons A nil &rArr; <span class="def">λf</span> . f A nil</code>
<code>cons B (cons A nil) &rArr; <span class="def">λf2</span> . f2 B (<span class="def">λf</span> . f A nil)</code>
Right?
Let's look at the replay...
<code>cons B (cons A nil) &rArr; <span class="def">λf2</span> . f2 B (cons A nil)</code>
`cons A nil` doesn't get evaulated until you "use" it, like `head (tail (cons B (cons A nil)))`
***
#Computed Streams of Data
You can produce a new list by:
* Transforming the elements of the original
* Discarding some of the elements of the original
* Inserting elements into the original
* Merging several lists together
* Combining the above operations
Kind of like SQL, only for lists
***
#Generators
Whenever you make a list, the head and tail remain "in stasis" because of lazy evaluation
(this is true for all data structions in LC, of course, since they are just functions)
So, lists in LC act a lot like generators and iterators do in Python/JavaScript/Java/C++
Except that a list is a "regular" data structure; you can reaccess it
***
#Generators
Whenever you make a list, the head and tail remain "in stasis" because of lazy evaluation
(this is true for all data structions in LC, of course, since they are just functions)
So, lists in LC act a lot like generators and iterators do in Python/JavaScript/Java/C++
Except that a list is a "regular" data structure; you can reaccess it
`append X X` works if X is a list
***
#Generators
Whenever you make a list, the head and tail remain "in stasis" because of lazy evaluation
(this is true for all data structions in LC, of course, since they are just functions)
So, lists in LC act a lot like generators and iterators do in Python/JavaScript/Java/C++
Except that a list is a "regular" data structure; you can reaccess it
`append X X` works if X is a list
`append X X` does not if X is a generator
***
#Generators
Here's an example tree traversal
<code>traverse (nd 1 (nd 2 nil nil) (nd 3 nil nil)) &rArr; [1,2,3]</code>
***
#Generators
Here's an example tree traversal
<code>traverse (nd 1 (nd 2 nil nil) (nd 3 nil nil)) &rArr; [1,2,3]</code>
`[1,2,3]` is ***lazy***
***
#Generators
Here's an example tree traversal
<code>traverse (nd 1 (nd 2 nil nil) (nd 3 nil nil)) &rArr; [1,2,3]</code>
`[1,2,3]` is ***lazy***
* <code>nd = <span class="def">λvalue left right f</span> . f value left right</code>
* <code>traverse = rec <span class="def">λtr tree</span> . tree (<span class="def">λv l r D</span> . cons v (append (tr l) (tr r))) nil</code>
***
#Generators
Here's an example tree traversal
<code>traverse (nd 1 (nd 2 nil nil) (nd 3 nil nil)) &rArr; [1,2,3]</code>
`[1,2,3]` is ***lazy***
* <code>nd = <span class="def">λvalue left right f</span> . f value left right</code>
* <code>traverse = rec <span class="def">λtr tree</span> . tree (<span class="def">λv l r D</span> . cons v (append (tr l) (tr r))) nil</code>
Nodes are like conses -- they let you access their parts (`v`, `l`, and `r`, for "value", "left", and "right")
***
#Generators
Here's an example tree traversal
<code>traverse (nd 1 (nd 2 nil nil) (nd 3 nil nil)) &rArr; [1,2,3]</code>
`[1,2,3]` is ***lazy***
* <code>nd = <span class="def">λvalue left right f</span> . f value left right</code>
* <code>traverse = rec <span class="def">λtr tree</span> . tree (<span class="def">λv l r D</span> . cons v (append (tr l) (tr r))) nil</code>
Nodes are like conses -- they let you access their parts (`v`, `l`, and `r`, for "value", "left", and "right")
`Traverse` uses the same currying trick that `null` used to handle empty trees
***
#Generators
Here's an example tree traversal
<code>traverse (nd 1 (nd 2 nil nil) (nd 3 nil nil)) &rArr; [1,2,3]</code>
`[1,2,3]` is ***lazy***
* <code>nd = <span class="def">λvalue left right f</span> . f value left right</code>
* <code>traverse = rec <span class="def">λtr tree</span> . tree (<span class="def">λv l r D</span> . cons v (append (tr l) (tr r))) nil</code>
Nodes are like conses -- they let you access their parts (`v`, `l`, and `r`, for "value", "left", and "right")
`Traverse` uses the same currying trick that `null` used to handle empty trees
(rec is a function which uses the "Y-combinator" to define a recursive function, so "tr" becomes the recursive name for "traverse")
***
#Generators
`[1,2,3]` is really just <code><span class="def">λf</span> . f (node-value) (traverse-the-rest)</code>
It continues the tree traversal as you get more elements from the list
Lazy evaluation makes this automatic
***
#Generators
Only the parts of the list you access are actually computed
The rest remain _virtual_
This brings us to...
***
#Infinite Streams
* natural numbers
* whole numbers
* even numbers
* random numbers
* ...
***
#Infinite Streams
* natural numbers
* whole numbers
* even numbers
* random numbers
* ...
You can use infinite streams in a loop to generate values
**`map FUNC (remove (not prime) naturals)`**
// this would be kind of like: for (i in naturals - !prime) {FUNC}, if `-` and `!` worked
***
#Infinite Streams
* natural numbers
* whole numbers
* even numbers
* random numbers
* ...
You can use infinite streams in a loop to generate values
**`map FUNC (remove (not prime) naturals)`**
// this would be kind of like: for (i in naturals - !prime) {FUNC}, if `-` and `!` worked
**`map FUNC (map square naturals)`**
// this would be kind of like: for (i in square * naturals) {...}, if `*` worked
***
#Infinite Streams
* natural numbers
* whole numbers
* even numbers
* random numbers
* ...
You can use infinite streams in a loop to generate values
**`map FUNC (remove (not prime) naturals)`**
// this would be kind of like: for (i in naturals - !prime) {FUNC}, if `-` and `!` worked
**`map FUNC (map square naturals)`**
// this would be kind of like: for (i in square * naturals) {...}, if `*` worked
**`map FUNC (map square (remove (! (prime || ten || even)) naturals))`**
// this would be like for (i in squares * (naturals - !(prime || ten || odd))) {...}, if `|` worked
// so naturals - ((!prime & !ten) | even) is all naturals which are prime or odd or multiples of 10
***
#Deep Factoring
You can transform and filter lists, just like you can in Smalltalk, LISP, Haskell, etc.
"Currying" when mapping or filtering produces a new function that operates on any list
You can compose them with other functions that operate on lists:
<code>mogrify = <span class="def">λfunc l</span> . map func (map square (remove (! (prime || ten || even)) l))</code>
`mogrify bob` uses currying to make a combinator you can use on lists or in other list combinators
This makes it easy to create and reuse functions that transform lists
You can use these techniques for things other than collections, too, like "parser combinators"
***
#List Buffers
Successively append items to a list.
empty &rArr; &lt;an empty buffer&gt;<br>
add buf element &rArr; &lt;a new buffer with element added to the end&gt;<br>
buffer nil &rArr; &lt;the buffer's list&gt;<br>
***
#List Buffers
Successively append items to a list.
empty &rArr; &lt;an empty buffer&gt;<br>
add buf element &rArr; &lt;a new buffer with element added to the end&gt;<br>
buffer nil &rArr; &lt;the buffer's list&gt;<br>
<code>add (add ident 1) 2 nil &rArr; [1, 2]</code>
***
#List Buffers
Successively append items to a list.
empty &rArr; &lt;an empty buffer&gt;<br>
add buf element &rArr; &lt;a new buffer with element added to the end&gt;<br>
buffer nil &rArr; &lt;the buffer's list&gt;<br>
<code>add (add ident 1) 2 nil &rArr; [1, 2]</code>
<code>empty = <span class="def">λx</span> . x</code><br>
<code>add = <span class="def">λbuffer element nextElements</span> . buffer (cons element nextElements)</code>
***
#List Buffers
Successively append items to a list.
empty &rArr; &lt;an empty buffer&gt;<br>
add buf element &rArr; &lt;a new buffer with element added to the end&gt;<br>
buffer nil &rArr; &lt;the buffer's list&gt;<br>
<code>add (add ident 1) 2 nil &rArr; [1, 2]</code>
<code>empty = <span class="def">λx</span> . x</code><br>
<code>add = <span class="def">λbuffer element nextElements</span> . buffer (cons element nextElements)</code>
'Empty' is the identity function
'Add' returns a function that puts one more cons in the list when you only pass in two of the three arguments
***
#Difference Lists
Like list buffers, but you can append lists instead of just adding elements, so we use the same technique, but with 'append' instead of 'cons'. Why use these instead of regular lists? They append in O(n) instead of O(n^2).
empty &rArr; &lt;an empty buffer&gt;<br>
dl list &rArr; &lt;a difference list&gt;<br>
addDl dl1 dl2 &rArr; &lt;a new difference list that appends the two lists&gt;<br>
&lt;d-list&gt; nil &rArr; &lt;the difference list's list&gt;<br>
***
#Difference Lists
Like list buffers, but you can append lists instead of just adding elements, so we use the same technique, but with 'append' instead of 'cons'. Why use these instead of regular lists? They append in O(n) instead of O(n^2).
empty &rArr; &lt;an empty buffer&gt;<br>
dl list &rArr; &lt;a difference list&gt;<br>
addDl dl1 dl2 &rArr; &lt;a new difference list that appends the two lists&gt;<br>
&lt;d-list&gt; nil &rArr; &lt;the difference list's list&gt;<br>
<code>addDl (addDl ident (dl [1,2,3])) (dl [4,5,6]) nil &rArr; [1,2,3,4,5,6]</code>
***
#Difference Lists
Like list buffers, but you can append lists instead of just adding elements, so we use the same technique, but with 'append' instead of 'cons'. Why use these instead of regular lists? They append in O(n) instead of O(n^2).
empty &rArr; &lt;an empty buffer&gt;<br>
dl list &rArr; &lt;a difference list&gt;<br>
addDl dl1 dl2 &rArr; &lt;a new difference list that appends the two lists&gt;<br>
&lt;d-list&gt; nil &rArr; &lt;the difference list's list&gt;<br>
<code>addDl (addDl ident (dl [1,2,3])) (dl [4,5,6]) nil &rArr; [1,2,3,4,5,6]</code>
or, since difference lists just append their agrument,
<code>addDl ident (dl [1,2,3]) [4,5,6] &rArr; [1,2,3,4,5,6]</code>
***
#Difference Lists
Like list buffers, but you can append lists instead of just adding elements, so we use the same technique, but with 'append' instead of 'cons'. Why use these instead of regular lists? They append in O(n) instead of O(n^2).
empty &rArr; &lt;an empty buffer&gt;<br>
dl list &rArr; &lt;a difference list&gt;<br>
addDl dl1 dl2 &rArr; &lt;a new difference list that appends the two lists&gt;<br>
&lt;d-list&gt; nil &rArr; &lt;the difference list's list&gt;<br>
<code>addDl (addDl ident (dl [1,2,3])) (dl [4,5,6]) nil &rArr; [1,2,3,4,5,6]</code>
or, since difference lists just append their agrument,
<code>addDl ident (dl [1,2,3]) [4,5,6] &rArr; [1,2,3,4,5,6]</code>
<code>empty = <span class="def">λx</span> . x</code><br>
<code>dl = append</code><br>
<code>addDl = <span class="def">λdl1 dl2 newDl</span> . dl1 (dl2 newDl)</code><br>
***
#Extensible Syntax
We've been using '[ 1 , 2 , 3 ]' to represent cons 1 (cons 2 (cons 3 nil))
***
#Extensible Syntax
We've been using '[ 1 , 2 , 3 ]' to represent cons 1 (cons 2 (cons 3 nil))
But [ 1 , 2 , 3 ] can be **normal** lambda calculus -- really!
***
#Extensible Syntax
We've been using '[ 1 , 2 , 3 ]' to represent cons 1 (cons 2 (cons 3 nil))
But [ 1 , 2 , 3 ] can be **normal** lambda calculus -- really!
Actually, `[`, `,`, and `]` are just functions
***
#Extensible Syntax
We've been using '[ 1 , 2 , 3 ]' to represent cons 1 (cons 2 (cons 3 nil))
But [ 1 , 2 , 3 ] can be **normal** lambda calculus -- really!
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
We've been using '[ 1 , 2 , 3 ]' to represent cons 1 (cons 2 (cons 3 nil))
But [ 1 , 2 , 3 ] can be **normal** lambda calculus -- really!
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
We've been using '[ 1 , 2 , 3 ]' to represent cons 1 (cons 2 (cons 3 nil))
But [ 1 , 2 , 3 ] can be **normal** lambda calculus -- really!
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
Want to see how we can define list constructor functions? :D
***
#Extensible Syntax
Want to see how we can define list constructor functions? :D
[ 1 ] = cons 1 nil
[ 1 , 2 ] = cons 1 (cons 2 nil)
[ 1 , 2 | list ] = cons 1 (cons 2 list)
***
#Extensible Syntax
Want to see how we can define list constructor functions? :D
[ 1 ] = cons 1 nil
[ 1 , 2 ] = cons 1 (cons 2 nil)
[ 1 , 2 | list ] = cons 1 (cons 2 list)
Remember the list buffer? This is a sort of like it, but a bit more indirect...
***
#Extensible Syntax
Want to see how we can define list constructor functions? :D
[ 1 ] = cons 1 nil
[ 1 , 2 ] = cons 1 (cons 2 nil)
[ 1 , 2 | list ] = cons 1 (cons 2 list)
Remember the list buffer? This is a sort of like it, but a bit more indirect...
<code>[ = <span class="def">λitem c</span> . c <span class="def">λrest</span> . cons item rest</code>
<code>, = <span class="def">λf item c</span> . c <span class="def">λrest</span> . f (cons item rest)</code>
<code>] = <span class="def">λf</span> . f nil</code>
<code>| = <span class="def">λf rest g</span> . f rest</code>
***
#Extensible Syntax
We can make it even more convient if we allow two lame syntax extensions -- tokens and groups...
***
#Extensible Syntax
We can make it even more convient if we allow two lame syntax extensions -- tokens and groups...
This lets you say <code>append [1,2,3] [4,5,6]</code> instead of <code>append ([ 1 , 2 , 3 ]) ([ 4 , 5 , 6 ])</code>
***
#Extensible Syntax
We can make it even more convient if we allow two lame syntax extensions -- tokens and groups...
This lets you say <code>append [1,2,3] [4,5,6]</code> instead of <code>append ([ 1 , 2 , 3 ]) ([ 4 , 5 , 6 ])</code>
so we want ...{group-start}...{group-close}... to be the same as ... ( {group-start} ... {group-close} ) ...
and ...{token}... to be the same as ... {token} ...
***
#Extensible Syntax
We can make it even more convient if we allow two lame syntax extensions -- tokens and groups...
This lets you say <code>append [1,2,3] [4,5,6]</code> instead of <code>append ([ 1 , 2 , 3 ]) ([ 4 , 5 , 6 ])</code>
so we want ...{group-start}...{group-close}... to be the same as ... ( {group-start} ... {group-close} ) ...
and ...{token}... to be the same as ... {token} ...
=.= makes a "token" function that doesn't need spaces to delimit it
=(?= makes a "group begin" function and specifies the end group function name (the '?')
=)= makes a "group end" function that closes a syntax group
***
#Extensible Syntax
We can make it even more convient if we allow two lame syntax extensions -- tokens and groups...
This lets you say <code>append [1,2,3] [4,5,6]</code> instead of <code>append ([ 1 , 2 , 3 ]) ([ 4 , 5 , 6 ])</code>
so we want ...{group-start}...{group-close}... to be the same as ... ( {group-start} ... {group-close} ) ...
and ...{token}... to be the same as ... {token} ...
=.= makes a "token" function that doesn't need spaces to delimit it
=(?= makes a "group begin" function and specifies the end group function name (the '?')
=)= makes a "group end" function that closes a syntax group
<code>[ =(]= <span class="def">λitem c</span> . c <span class="def">λrest</span> . cons item rest</code>
<code>, =.= <span class="def">λf item c</span> . c <span class="def">λrest</span> . f (cons item rest)</code>
<code>] =)= <span class="def">λf</span> . f nil</code>
<code>| =.= <span class="def">λf rest g</span> . f rest</code>
***
#Monads
* monads let you sequence functional operations
***
#Monads
* monads let you sequence functional operations
* let you appear to program imperatively (with the right syntactic sugar)
***
#Monads
* monads let you sequence functional operations
* let you appear to program imperatively (with the right syntactic sugar)
* but actually, you are programming functionally
***
#Monads
* monads let you sequence functional operations
* let you appear to program imperatively (with the right syntactic sugar)
* but actually, you are programming functionally
* interact smoothly with external environments, like IO and window systems
***
#Monads
* monads let you sequence functional operations
* let you appear to program imperatively (with the right syntactic sugar)
* but actually, you are programming functionally
* interact smoothly with external environments, like IO and window systems
* handle exceptions
***
#Monads
* monads let you sequence functional operations
* let you appear to program imperatively (with the right syntactic sugar)
* but actually, you are programming functionally
* interact smoothly with external environments, like IO and window systems
* handle exceptions
* (Uh, other stuff...)
***
#Monads
* monads let you sequence functional operations
* let you appear to program imperatively (with the right syntactic sugar)
* but actually, you are programming functionally
* interact smoothly with external environments, like IO and window systems
* handle exceptions
* (Uh, other stuff...)
Haskell example:
do printStr "Please enter your name: "
name <- getLine
name <- return (name ++ " Jr")
printStrLn ("Your actual name is: " ++ name)
***
#Monads
* monads let you sequence functional operations
* let you appear to program imperatively (with the right syntactic sugar)
* but actually, you are programming functionally
* interact smoothly with external environments, like IO and window systems
* handle exceptions
* (Uh, other stuff...)
Haskell example:
do 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) λ_ . bind (prompt name) λnm . bind (return [nm, Jr]) λnm . alert [Your, actual, name, is, nm]
***
#Monads
* monads let you sequence functional operations
* let you appear to program imperatively (with the right syntactic sugar)
* but actually, you are programming functionally
* interact smoothly with external environments, like IO and window systems
* handle exceptions
* (Uh, other stuff...)
Haskell example:
do 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) λ_ . 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)
λ_ . bind (prompt name)
λnm . bind (return [nm, Jr])
λnm . bind (alert [Your, actual, name, is, nm])
***
#Monads
* monads let you sequence functional operations
* let you appear to program imperatively (with the right syntactic sugar)
* but actually, you are programming functionally
* interact smoothly with external environments, like IO and window systems
* handle exceptions
* (Uh, other stuff...)
Haskell example:
do 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) λ_ . 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)
λ_ . bind (prompt name)
λnm . bind (return [nm, Jr])
λnm . bind (alert [Your, actual, name, is, nm])
This looks like it's reassigning nm, but it's not! (they're just nested functions with variables of the same name)
***
#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 commands from the old one, plus 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 commands from the old one, plus 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 commands from the old one, plus 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 display to the user
***
#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 commands from the old one, plus 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 display to the user
* 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 commands from the old one, plus 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 display to the user
* 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 <span class="current">does</span>
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:
* 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:
* 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:
* 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
***
#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:
* 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
* 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
***
#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>
Hey, all of the commands are really the same!
***
#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>
Hey, all of the commands are really the same!
The JavaScript driver code uses the function to identify which command is which.
***
#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>
Hey, all of the commands are really the same!
The JavaScript driver code uses the function to identify which command is which.
Later, we'll use the Lambda Calculator to step through some monads
***
#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
That means another thread can't change it underneath you
The way you make "changes" is to return "transformed replacements"
***
#Parallel Computing
Isn't creating new data instead of changing existing data inefficient?
***
#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
***
#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)
***
#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
***
#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
***
#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?
Those stream operations we talked about, before: transforming, discarding, inserting
Those are a lot like Google's map/reduce (because it's based on functional concepts)
Google's Map/reduce operates "in the large", on server farms
Functional programming languages can do this "in the small" (like on your laptop)
***
#Parallel Computing
Map is a function that transforms a list of values by applying a function to each element:
<code>map twice [1,2,3] &rArr; [2,4,6]</code>
(i.e. <code>map (<span class="def">λitem</span> . times 2 item) [1,2,3]</code>)
Parallel functional languages (like Haskell and Scala) support parallel list transformations
So they would send each element of the list to a different processor (if you have that many processors)
This works on other types of collections, besides streams, of course (trees, arrays, etc.)
***
#Part 1 Conclusion
So, I think we've seen how utterly brilliant and simple Lambda Calculus is.
***
#Part 1 Conclusion
So, I think we've seen how utterly brilliant and simple Lambda Calculus is.
Maybe if alien beings wanted to send messages to an unknown civilization, they would start with Lambda Calculus, instead of math...
***
#Part 2
Speaking of alien "communication," here is some of [Space Invaders in Lambda Calculus](invaders.html)
***
#Part 2
Speaking of alien "communication," here is some of [Space Invaders in Lambda Calculus](invaders.html)
And here is the [Lambda Calculus evaluator](evaluator.html), again :)
***
# The End
<img src="qrCode.png" alt="qrcode">
***
#Resources
* Documents about functional programming and lazy evaluation
* Talk on Why Functional Programming Matters: [http://www.infoq.com/interviews/john-hughes-fp](http://www.infoq.com/interviews/john-hughes-fp)
* Why Functional Programming Matters paper: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.63.7911&rep=rep1&type=pdf](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.63.7911&rep=rep1&type=pdf)
* Tim Sweeney's (of Epic Games) talk on the future of graphics programming: [http://www.cs.princeton.edu/~dpw/popl/06/Tim-POPL.ppt](http://www.cs.princeton.edu/~dpw/popl/06/Tim-POPL.ppt)
* The Real Point of Laziness: [http://existentialtype.wordpress.com/2011/04/24/the-real-point-of-laziness/](http://existentialtype.wordpress.com/2011/04/24/the-real-point-of-laziness/)
* More Points for Lazy Evaluation: [http://augustss.blogspot.com/2011/05/more-points-for-lazy-evaluation-in.html](http://augustss.blogspot.com/2011/05/more-points-for-lazy-evaluation-in.html)
* Martin Odersky's [talk on Scala and parallel computing](http://www.parleys.com/#st=5&id=2184)
* My [parallel collection Go library](https://github.com/zot/seq)
* Tools for easy slide presentations, like this
* QuickSlides: [http://tobyho.com/Quick-and-Dirty\_Presentations\_in\_Markdown](http://tobyho.com/Quick-and-Dirty_Presentations_in_Markdown)
* Slidy: [http://www.w3.org/Talks/Tools/Slidy2/scripts/slidy.js.gz](http://www.w3.org/Talks/Tools/Slidy2/scripts/slidy.js.gz)
* Slidy CSS: [http://www.w3.org/Talks/Tools/Slidy2/styles/slidy.css](http://www.w3.org/Talks/Tools/Slidy2/styles/slidy.css)
* Showdown: [http://softwaremaniacs.org/playground/showdown-highlight/](http://softwaremaniacs.org/playground/showdown-highlight/)
-->
</script>
<script>
var scripts = document.getElementsByTagName('script');
for (var i = 0; i < scripts.length; i++){
var script = scripts[i];
if (script.type != 'text/markdown') continue;
var md = script.innerHTML.replace(/^\s<!--*/, '')
.replace(/-->\s*$/, '');
var markup = new Showdown.converter().makeHtml(md);
var slides = markup.split('<hr />');
for (var j = 0; j < slides.length; j++)
document.write('<div class=slide>' + slides[j] + '</div>');
}
w3c_slidy.add_listener(document.body, "touchend", w3c_slidy.mouse_button_click);
</script>
</body>
</html>
Jump to Line
Something went wrong with that request. Please try again.