This video is called the Parlor Trick, 
and it's intended to mess with your mind 
a little bit. 
What I want to do is show you the power 
of representing information as data and 
get you to explore some of the data 
representation choices we maybe take for 
granted. 
It's going to be a little weird. 
You may need to watch it a few times to 
really enjoy it. 
So, the problem setup is, I don't know, 
maybe a little crazy. 
You've just gotten a new tablet and it 
runs a prototype version of Racket. 
Which is great. 
You can make your tablet do anything you 
want. 
But there's one problem, which is this 
prototype version of Racket doesn't 
include numbers as primitive data. 
There just are no numbers in it at all. 
Fortunately, it does have cons and first 
and rest and strings. 
And you know what the self-referential 
data definition is for numbers. 
And you know that it's based on the idea 
that add1 is kind of like cons, and sub1 
is kind of like rest. 
So, you actually know how to solve this 
problem and define your very own numbers 
from scratch. 
Here we go. 
We'll make a new type called NATURAL. 
I'm making it all uppercase to 
distinguish it from the old type called 
NATURAL. 
And we'll just say, like the old type, 
that it's going to be a well formed 
self-referential data definition. 
And it's going to look like this, we're 
going to say that it could be either 
empty or it could be cons. 
An exclamation mark, a string with an 
exclamation mark on NATURAL. 
So, you've got a well formed self 
referential data definition there. 
Empty is clearly the base case and cons 
exclamation mark natural is the self 
reference case. 
So, that's the type comment. 
But, in this case what's actually 
trickier than the type comment is the 
interpretation. 
What does that mean? 
Well, it just means this. 
It's a natural number, and the number of 
exclamation marks in the list is the 
number. 
Let's do some examples. 
So, NATURAL 0 is empty, and NATURAL 1 is 
cons, one exclamation mark onto NATURAL 
0. 
This is 1 and this is 0, N2 is just cons 
another exclamation mark on the N1, 
that's 2. 
Let's just run this for just a second and 
take a quick look if we go down here in 
the interaction window. 
N0 is empty. 
N1 is a list with one exclamation mark in 
it, and N2 is a list with two exclamation 
marks in it. 
So, they're cumbersome to look at. 
They'd be even more cumbersome to type 
but those are new natural numbers. 
They would be so cumbersome to write out 
in fact, that what I'm going to do is I'm 
going to use the magic of video editing 
to very quickly get a whole bunch more of 
them. 
Now, we've got natural numbers 0 through 
9 that are relatively easy to type. 
It's still a little weird looking at that 
cons. 
What's really going on here is that these 
are the primitives that operate on the 
new kind of NATURAL. 
One is the predicate zero, is something 
zero. 
And something is zero if what? 
Well, if it's empty. 
'Cuz that's what the type comment says. 
The type comment says. 
The type count plus the interpretation 
says that the way that we represent zero 
is with empty. 
So, that's one primitive. 
Another primitive is ADD1, and the way 
we're going to ADD1 to a natural is, 
well, we just do this cons thing. 
And another primitive is SUB1. 
And the way we're going to get the next 
smallest natural number is with rest. 
Even though these are primitives, let me 
just write the signatures for them off to 
the side so we'll have them. 
We've never defined primitives like this 
before. 
And see, zero question mark actually 
consumes anything. 
And it produces a Boolean to tell us 
whether what it consumed was the 
representation of zero. 
ADD1 consumes one of these newfangled 
naturals and produces one of these 
newfangled naturals. 
And SUB1 consumes one of these new kinds 
of naturals, but it has to be bigger than 
zero. 
That's a restriction that's kind of like 
the restriction that rest has, right? 
Rest won't take empty. 
Rest needs a cons. 
Rest needs a list that's at least one 
long. 
So, if you give SUB1 a natural that's at 
least one or bigger, you'll get back 
another natural. 
And if we want, we can pretty this up a 
little bit. 
So, there's our primitives. 
Now, let's do the template, we'll do it 
like this, fn-for-NATURAL n. 
Let's see, it's a one of. 
I won't write out the template rules 
used, I'll just say them as I go. 
That's what we're going to be doing 
starting next week. 
So, I'll do it in this last video of this 
week. 
Cond it's a one of, there's two cases, 
the first case is atomic distinct. 
Now, remember that empty really means 
zero. 
And the reason I wrote these primitives 
so that, was so that we wouldn't go crazy 
when we saw ourself calling empty on 
something that looked like it was 
supposed to be a natural. 
So, I'm going to say zero here. 
If the natural is zero, that's atomic 
distinct otherwise, dot, dot, dot, and 
we'll put in n because we know it's 
useful And we'll say fun for natural SUB1 
of n. 
And of course, now that I have these 
primitives this template looks just like 
the template for ordinary natural 
numbers. 
Because I've got my own special version 
of zero and my own special version of 
SUB1. 
So, remember we're doing kind of of a 
weird thing here, we're recreating the 
numbers. 
We're recreating the numerals, in some 
sense. 
'Kay? 
We're recreating the representation of 
the natural numbers. 
So, there's the template. 
Now, let's do some functions. 
Well, we've got zero, ADD1, and SUB1. 
One thing we don't have is plain old add, 
right? 
We don't have a way of adding together 
two naturals. 
Let's do that. 
Well, it's a function that consumes two 
naturals, and it produces a natural. 
And its purpose is to produce a plus b, 
assuming that's the name of the two 
naturals. 
I'll do the stub, here, we'll call it 
ADD. 
So, let's do some examples. 
Now, this function is clearly going to be 
recursive on one of the numbers. 
That's what the template is for. 
I'm going to make it be recursive on the 
second number. 
It turns out that works out a little bit 
better later. 
It would have worked perfectly fine to 
make it recursive on the first number, 
then it'll just simplify things later if 
I do it this way. 
So, that means my first test should be 
with a base case for the second argument. 
So, I'll say N2 and N0. 
Zero is the base case. 
If I add 2 and 0 I should get 2. 
And just to make sure the first 
argument's treated alright, I'll also do 
something like this. 
That should be 3, because if I add 2 and 
0 I get 2. 
If I add 0 and 3 I get 3. 
And now let's make one that actually does 
some more work. 
We'll add N3 and N4. 
This satisfies my at least two long rule, 
because 4 is bigger than 2. 
And we'll get N7. 
Sure is good that I made those constants 
so I don't have to type these naturals 
out all the time. 
Doing this with a bunch of constants 
would be a pain. 
Okay, let's take the template. 
We'll bring it down here. 
We'll rename it. 
We'll rename the recursion. 
We'll comment out the stub. 
And we need two parameters. 
So, I'm going to rename this parameter to 
b. 
And I'll add a parameter a. 
And in the recursion, I'll add the 
parameter a also. 
So, let's see. 
If I'm adding two numbers, a and b, and b 
is 0, this is the base case. 
What's the result? 
Well, I know from arithmetic and I also 
know from this example, that the result 
should be a. 
If you add a to 0, you get a no matter 
what a is. 
What did I do in this case here? 
Well, I don't know if you remember the 
way you were originally taught to add in 
kindergarten. 
But the basic idea was, you would get 
maybe two piles of sticks. 
And you would add them together by moving 
one stick at a time, from one pile to the 
other pile until you only had one pile. 
And if you counted while you did that, 
you got the right number. 
Well, that's what we can do, here. 
Here, we're taking 1 away from b. 
So, if at the same time, we just ADD 1 to 
a. 
And produced that as our result. 
Then that'll work because if, where b is 
going to get smaller and smaller and 
smaller. 
Each time b gets smaller by 1, a will get 
bigger by 1. 
Eventually, b will be 0 and a will be the 
sum. 
So, this is addition of two numbers 
together, one at a time. 
Let's try it. 
It works. 
I'll give you a little exercise to do 
now. 
If this is blowing your mind a little bit 
too much, then you don't have to do it. 
But you might have fun doing it. 
Finish this. 
And again, the suggestion I'll make to 
you is when you get to the template 
stage, set up the template on the second 
argument. 
And go ahead and work through this and 
then restart the video. 
Or if you don't want to work through it 
yourself, restart the video right away. 
So, here's my version of subtract, I've 
got two check expects. 
Base case one is first. 
Remember I'm templating on b, so 0 for 
the second argument. 
If you subtract 0 from 2 you get 2. 
If you subtract 2 from 6 you get 4. 
And subtract is a little different than 
add. 
Let me just change how I've formatted add 
here. 
I'll break that on two lines. 
The way add works is you add to a while 
you subtract from b. 
The way subtract works is you keep taking 
one away from both a and b until b gets 
to 0. 
So, that's add and subtract. 
Let's just look at 'em. 
The test passed, that's good. 
Watch this. 
Add N2 and N3, so that's adding 2 to 3, 
gets 5. 
One, two, three, four, five exclamation 
marks. 
Subtract 7, ADD 2 to N3. 
2 plus 3 is 5. 
7 minus 5 is 2, there's 2. 
We're doing all this arithmetic without 
using any natural numbers that were given 
to us by Dr. 
Racket. 
We're using our own natural numbers. 
It's a little bit wacky. 
Let me just quickly show you how far you 
can go if you want to keep pushing on 
this. 
Here, I've got the famous factorial 
function. 
Right, factorial of zero is one. 
And factorial of everything else is the 
number. 
Times fact of one less than the number. 
If you don't know factorial, remember I 
promised there'd be no math. 
I promised there'd be no math. 
So, you can just ignore this little bit. 
That's factorial written for these new 
natural numbers. 
Zero is uppercase, it's our special 
primitive, SUB1 is uppercase, FACT is 
uppercase. 
but I'm calling times. 
We don't actually have times so you could 
do times, you could wish for times and 
then do it. 
In order to do times, you have to use a 
technique called an accumulator that we 
haven't learned yet. 
That'll be from part two of the course. 
So, I don't want to go into times. 
Let me just show you that this works. 
FACT of 0 is 1. 
FACT of 3 is 6. 
FACT of four is 24. 
If you count them, there would be 24. 
FACT of 8 mmmmmm. 
More, it takes a long time to print, 
long, long time to print. 
Very long time to print out this long 
list of exclamation marks. 
So, what's the moral of the story here? 
The most important thing is to know when 
we design programs we come up with data 
definitions that represent information. 
And we can take any data to represent any 
information we want. 
Now of course, the underlying hardware 
makes some primitive data faster than 
other primitive data. 
We still haven't finished printing out 
this representation of FACT of eight. 
This is a terrible representation of 
natural numbers. 
You would never want to use this. 
I just wanted you to see that you can 
take the bottom to be anything you want. 
You can come up with your own numbers. 
You can come up with your own strings. 
You can come up with your own lists. 
You can create any data you want. 
So, as I said at the beginning, that's a 
little wacky. 
Most of the time, nearly all the time, 
you're just going to work with whatever 
representation of numbers the programming 
language gives you. 
Still it's kind of fun to explore that. 
And you remember the lesson material this 
week is not wacky. 
And the rest of the material this week is 
essential representing arbitrary sizing 
formation. 
Well formed self referential type 
comments operating on lists and the 
reference rule. 
All of that's essential material. 
So, be sure to practice it a lot, and 
we'll see you again next week.