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.