1 00:00:05,970 --> 00:00:08,700 This video is called the Parlor Trick, and it's intended to mess with your mind 2 00:00:08,700 --> 00:00:13,443 a little bit. What I want to do is show you the power 3 00:00:13,443 --> 00:00:18,217 of representing information as data and get you to explore some of the data 4 00:00:18,217 --> 00:00:23,865 representation choices we maybe take for granted. 5 00:00:23,865 --> 00:00:27,740 It's going to be a little weird. You may need to watch it a few times to 6 00:00:27,740 --> 00:00:31,200 really enjoy it. So, the problem setup is, I don't know, 7 00:00:31,200 --> 00:00:34,156 maybe a little crazy. You've just gotten a new tablet and it 8 00:00:34,156 --> 00:00:38,020 runs a prototype version of Racket. Which is great. 9 00:00:38,020 --> 00:00:40,810 You can make your tablet do anything you want. 10 00:00:40,810 --> 00:00:43,771 But there's one problem, which is this prototype version of Racket doesn't 11 00:00:43,771 --> 00:00:48,775 include numbers as primitive data. There just are no numbers in it at all. 12 00:00:48,775 --> 00:00:54,295 Fortunately, it does have cons and first and rest and strings. 13 00:00:54,295 --> 00:01:00,500 And you know what the self-referential data definition is for numbers. 14 00:01:00,500 --> 00:01:06,044 And you know that it's based on the idea that add1 is kind of like cons, and sub1 15 00:01:06,044 --> 00:01:10,772 is kind of like rest. So, you actually know how to solve this 16 00:01:10,772 --> 00:01:13,640 problem and define your very own numbers from scratch. 17 00:01:13,640 --> 00:01:18,860 Here we go. We'll make a new type called NATURAL. 18 00:01:18,860 --> 00:01:22,340 I'm making it all uppercase to distinguish it from the old type called 19 00:01:22,340 --> 00:01:25,516 NATURAL. And we'll just say, like the old type, 20 00:01:25,516 --> 00:01:30,030 that it's going to be a well formed self-referential data definition. 21 00:01:30,030 --> 00:01:36,015 And it's going to look like this, we're going to say that it could be either 22 00:01:36,015 --> 00:01:43,036 empty or it could be cons. An exclamation mark, a string with an 23 00:01:43,036 --> 00:01:46,668 exclamation mark on NATURAL. So, you've got a well formed self 24 00:01:46,668 --> 00:01:52,288 referential data definition there. Empty is clearly the base case and cons 25 00:01:52,288 --> 00:01:57,184 exclamation mark natural is the self reference case. 26 00:01:57,184 --> 00:02:01,942 So, that's the type comment. But, in this case what's actually 27 00:02:01,942 --> 00:02:04,690 trickier than the type comment is the interpretation. 28 00:02:04,690 --> 00:02:08,905 What does that mean? Well, it just means this. 29 00:02:08,905 --> 00:02:19,300 It's a natural number, and the number of exclamation marks in the list is the 30 00:02:19,300 --> 00:02:27,381 number. Let's do some examples. 31 00:02:27,381 --> 00:02:37,743 So, NATURAL 0 is empty, and NATURAL 1 is cons, one exclamation mark onto NATURAL 32 00:02:37,743 --> 00:02:45,427 0. This is 1 and this is 0, N2 is just cons 33 00:02:45,427 --> 00:02:54,818 another exclamation mark on the N1, that's 2. 34 00:02:56,240 --> 00:02:58,697 Let's just run this for just a second and take a quick look if we go down here in 35 00:02:58,697 --> 00:03:02,574 the interaction window. N0 is empty. 36 00:03:02,574 --> 00:03:06,666 N1 is a list with one exclamation mark in it, and N2 is a list with two exclamation 37 00:03:06,666 --> 00:03:11,960 marks in it. So, they're cumbersome to look at. 38 00:03:11,960 --> 00:03:17,100 They'd be even more cumbersome to type but those are new natural numbers. 39 00:03:17,100 --> 00:03:22,140 They would be so cumbersome to write out in fact, that what I'm going to do is I'm 40 00:03:22,140 --> 00:03:27,340 going to use the magic of video editing to very quickly get a whole bunch more of 41 00:03:27,340 --> 00:03:32,832 them. Now, we've got natural numbers 0 through 42 00:03:32,832 --> 00:03:37,246 9 that are relatively easy to type. It's still a little weird looking at that 43 00:03:37,246 --> 00:03:41,366 cons. What's really going on here is that these 44 00:03:41,366 --> 00:03:46,020 are the primitives that operate on the new kind of NATURAL. 45 00:03:46,020 --> 00:03:50,556 One is the predicate zero, is something zero. 46 00:03:50,556 --> 00:03:55,596 And something is zero if what? Well, if it's empty. 47 00:03:55,596 --> 00:04:02,340 'Cuz that's what the type comment says. The type comment says. 48 00:04:02,340 --> 00:04:06,828 The type count plus the interpretation says that the way that we represent zero 49 00:04:06,828 --> 00:04:09,940 is with empty. So, that's one primitive. 50 00:04:09,940 --> 00:04:16,666 Another primitive is ADD1, and the way we're going to ADD1 to a natural is, 51 00:04:16,666 --> 00:04:26,741 well, we just do this cons thing. And another primitive is SUB1. 52 00:04:26,741 --> 00:04:33,280 And the way we're going to get the next smallest natural number is with rest. 53 00:04:35,520 --> 00:04:38,376 Even though these are primitives, let me just write the signatures for them off to 54 00:04:38,376 --> 00:04:41,865 the side so we'll have them. We've never defined primitives like this 55 00:04:41,865 --> 00:04:45,062 before. And see, zero question mark actually 56 00:04:45,062 --> 00:04:50,610 consumes anything. And it produces a Boolean to tell us 57 00:04:50,610 --> 00:04:58,380 whether what it consumed was the representation of zero. 58 00:04:58,380 --> 00:05:03,382 ADD1 consumes one of these newfangled naturals and produces one of these 59 00:05:03,382 --> 00:05:08,894 newfangled naturals. And SUB1 consumes one of these new kinds 60 00:05:08,894 --> 00:05:13,255 of naturals, but it has to be bigger than zero. 61 00:05:13,255 --> 00:05:19,060 That's a restriction that's kind of like the restriction that rest has, right? 62 00:05:19,060 --> 00:05:22,460 Rest won't take empty. Rest needs a cons. 63 00:05:22,460 --> 00:05:24,696 Rest needs a list that's at least one long. 64 00:05:24,696 --> 00:05:30,028 So, if you give SUB1 a natural that's at least one or bigger, you'll get back 65 00:05:30,028 --> 00:05:34,492 another natural. And if we want, we can pretty this up a 66 00:05:34,492 --> 00:05:41,256 little bit. So, there's our primitives. 67 00:05:41,256 --> 00:05:47,570 Now, let's do the template, we'll do it like this, fn-for-NATURAL n. 68 00:05:47,570 --> 00:05:54,552 Let's see, it's a one of. I won't write out the template rules 69 00:05:54,552 --> 00:06:00,450 used, I'll just say them as I go. That's what we're going to be doing 70 00:06:00,450 --> 00:06:03,311 starting next week. So, I'll do it in this last video of this 71 00:06:03,311 --> 00:06:07,421 week. Cond it's a one of, there's two cases, 72 00:06:07,421 --> 00:06:14,022 the first case is atomic distinct. Now, remember that empty really means 73 00:06:14,022 --> 00:06:16,407 zero. And the reason I wrote these primitives 74 00:06:16,407 --> 00:06:19,494 so that, was so that we wouldn't go crazy when we saw ourself calling empty on 75 00:06:19,494 --> 00:06:23,571 something that looked like it was supposed to be a natural. 76 00:06:23,571 --> 00:06:32,195 So, I'm going to say zero here. If the natural is zero, that's atomic 77 00:06:32,195 --> 00:06:40,517 distinct otherwise, dot, dot, dot, and we'll put in n because we know it's 78 00:06:40,517 --> 00:06:50,550 useful And we'll say fun for natural SUB1 of n. 79 00:06:50,550 --> 00:06:56,886 And of course, now that I have these primitives this template looks just like 80 00:06:56,886 --> 00:07:02,496 the template for ordinary natural numbers. 81 00:07:02,496 --> 00:07:08,355 Because I've got my own special version of zero and my own special version of 82 00:07:08,355 --> 00:07:11,835 SUB1. So, remember we're doing kind of of a 83 00:07:11,835 --> 00:07:14,880 weird thing here, we're recreating the numbers. 84 00:07:14,880 --> 00:07:17,125 We're recreating the numerals, in some sense. 85 00:07:17,125 --> 00:07:20,312 'Kay? We're recreating the representation of 86 00:07:20,312 --> 00:07:23,330 the natural numbers. So, there's the template. 87 00:07:23,330 --> 00:07:27,900 Now, let's do some functions. Well, we've got zero, ADD1, and SUB1. 88 00:07:27,900 --> 00:07:31,329 One thing we don't have is plain old add, right? 89 00:07:31,329 --> 00:07:35,070 We don't have a way of adding together two naturals. 90 00:07:35,070 --> 00:07:39,350 Let's do that. Well, it's a function that consumes two 91 00:07:39,350 --> 00:07:45,915 naturals, and it produces a natural. And its purpose is to produce a plus b, 92 00:07:45,915 --> 00:07:50,551 assuming that's the name of the two naturals. 93 00:07:50,551 --> 00:07:59,965 I'll do the stub, here, we'll call it ADD. 94 00:07:59,965 --> 00:08:09,474 So, let's do some examples. Now, this function is clearly going to be 95 00:08:09,474 --> 00:08:13,215 recursive on one of the numbers. That's what the template is for. 96 00:08:13,215 --> 00:08:16,278 I'm going to make it be recursive on the second number. 97 00:08:16,278 --> 00:08:19,342 It turns out that works out a little bit better later. 98 00:08:19,342 --> 00:08:22,094 It would have worked perfectly fine to make it recursive on the first number, 99 00:08:22,094 --> 00:08:25,320 then it'll just simplify things later if I do it this way. 100 00:08:25,320 --> 00:08:34,800 So, that means my first test should be with a base case for the second argument. 101 00:08:34,800 --> 00:08:39,630 So, I'll say N2 and N0. Zero is the base case. 102 00:08:39,630 --> 00:08:47,070 If I add 2 and 0 I should get 2. And just to make sure the first 103 00:08:47,070 --> 00:08:52,350 argument's treated alright, I'll also do something like this. 104 00:08:52,350 --> 00:08:55,560 That should be 3, because if I add 2 and 0 I get 2. 105 00:08:55,560 --> 00:09:00,710 If I add 0 and 3 I get 3. And now let's make one that actually does 106 00:09:00,710 --> 00:09:04,800 some more work. We'll add N3 and N4. 107 00:09:04,800 --> 00:09:11,190 This satisfies my at least two long rule, because 4 is bigger than 2. 108 00:09:11,190 --> 00:09:14,550 And we'll get N7. Sure is good that I made those constants 109 00:09:14,550 --> 00:09:17,120 so I don't have to type these naturals out all the time. 110 00:09:17,120 --> 00:09:22,580 Doing this with a bunch of constants would be a pain. 111 00:09:22,580 --> 00:09:29,276 Okay, let's take the template. We'll bring it down here. 112 00:09:29,276 --> 00:09:37,420 We'll rename it. We'll rename the recursion. 113 00:09:37,420 --> 00:09:41,410 We'll comment out the stub. And we need two parameters. 114 00:09:41,410 --> 00:09:43,890 So, I'm going to rename this parameter to b. 115 00:09:43,890 --> 00:09:51,980 And I'll add a parameter a. And in the recursion, I'll add the 116 00:09:51,980 --> 00:09:56,020 parameter a also. So, let's see. 117 00:09:56,020 --> 00:10:00,360 If I'm adding two numbers, a and b, and b is 0, this is the base case. 118 00:10:00,360 --> 00:10:03,862 What's the result? Well, I know from arithmetic and I also 119 00:10:03,862 --> 00:10:07,240 know from this example, that the result should be a. 120 00:10:07,240 --> 00:10:10,911 If you add a to 0, you get a no matter what a is. 121 00:10:10,911 --> 00:10:14,585 What did I do in this case here? Well, I don't know if you remember the 122 00:10:14,585 --> 00:10:17,975 way you were originally taught to add in kindergarten. 123 00:10:17,975 --> 00:10:23,570 But the basic idea was, you would get maybe two piles of sticks. 124 00:10:23,570 --> 00:10:27,794 And you would add them together by moving one stick at a time, from one pile to the 125 00:10:27,794 --> 00:10:33,436 other pile until you only had one pile. And if you counted while you did that, 126 00:10:33,436 --> 00:10:39,570 you got the right number. Well, that's what we can do, here. 127 00:10:39,570 --> 00:10:46,141 Here, we're taking 1 away from b. So, if at the same time, we just ADD 1 to 128 00:10:46,141 --> 00:10:51,255 a. And produced that as our result. 129 00:10:51,255 --> 00:10:58,453 Then that'll work because if, where b is going to get smaller and smaller and 130 00:10:58,453 --> 00:11:04,859 smaller. Each time b gets smaller by 1, a will get 131 00:11:04,859 --> 00:11:09,720 bigger by 1. Eventually, b will be 0 and a will be the 132 00:11:09,720 --> 00:11:13,378 sum. So, this is addition of two numbers 133 00:11:13,378 --> 00:11:16,910 together, one at a time. Let's try it. 134 00:11:18,380 --> 00:11:21,290 It works. I'll give you a little exercise to do 135 00:11:21,290 --> 00:11:24,690 now. If this is blowing your mind a little bit 136 00:11:24,690 --> 00:11:32,676 too much, then you don't have to do it. But you might have fun doing it. 137 00:11:32,676 --> 00:11:36,680 Finish this. And again, the suggestion I'll make to 138 00:11:36,680 --> 00:11:40,340 you is when you get to the template stage, set up the template on the second 139 00:11:40,340 --> 00:11:44,194 argument. And go ahead and work through this and 140 00:11:44,194 --> 00:11:47,361 then restart the video. Or if you don't want to work through it 141 00:11:47,361 --> 00:11:53,165 yourself, restart the video right away. So, here's my version of subtract, I've 142 00:11:53,165 --> 00:11:58,580 got two check expects. Base case one is first. 143 00:11:58,580 --> 00:12:03,270 Remember I'm templating on b, so 0 for the second argument. 144 00:12:03,270 --> 00:12:09,810 If you subtract 0 from 2 you get 2. If you subtract 2 from 6 you get 4. 145 00:12:09,810 --> 00:12:12,500 And subtract is a little different than add. 146 00:12:12,500 --> 00:12:15,560 Let me just change how I've formatted add here. 147 00:12:15,560 --> 00:12:19,955 I'll break that on two lines. The way add works is you add to a while 148 00:12:19,955 --> 00:12:26,224 you subtract from b. The way subtract works is you keep taking 149 00:12:26,224 --> 00:12:31,320 one away from both a and b until b gets to 0. 150 00:12:31,320 --> 00:12:34,460 So, that's add and subtract. Let's just look at 'em. 151 00:12:34,460 --> 00:12:36,750 The test passed, that's good. Watch this. 152 00:12:36,750 --> 00:12:45,887 Add N2 and N3, so that's adding 2 to 3, gets 5. 153 00:12:45,887 --> 00:12:51,165 One, two, three, four, five exclamation marks. 154 00:12:51,165 --> 00:12:57,661 Subtract 7, ADD 2 to N3. 2 plus 3 is 5. 155 00:12:57,661 --> 00:13:05,340 7 minus 5 is 2, there's 2. We're doing all this arithmetic without 156 00:13:05,340 --> 00:13:08,980 using any natural numbers that were given to us by Dr. 157 00:13:08,980 --> 00:13:11,780 Racket. We're using our own natural numbers. 158 00:13:11,780 --> 00:13:14,872 It's a little bit wacky. Let me just quickly show you how far you 159 00:13:14,872 --> 00:13:17,930 can go if you want to keep pushing on this. 160 00:13:17,930 --> 00:13:21,542 Here, I've got the famous factorial function. 161 00:13:21,542 --> 00:13:26,360 Right, factorial of zero is one. And factorial of everything else is the 162 00:13:26,360 --> 00:13:31,270 number. Times fact of one less than the number. 163 00:13:31,270 --> 00:13:35,170 If you don't know factorial, remember I promised there'd be no math. 164 00:13:35,170 --> 00:13:38,990 I promised there'd be no math. So, you can just ignore this little bit. 165 00:13:38,990 --> 00:13:42,440 That's factorial written for these new natural numbers. 166 00:13:42,440 --> 00:13:46,966 Zero is uppercase, it's our special primitive, SUB1 is uppercase, FACT is 167 00:13:46,966 --> 00:13:50,199 uppercase. but I'm calling times. 168 00:13:51,220 --> 00:13:54,470 We don't actually have times so you could do times, you could wish for times and 169 00:13:54,470 --> 00:13:57,300 then do it. In order to do times, you have to use a 170 00:13:57,300 --> 00:14:00,710 technique called an accumulator that we haven't learned yet. 171 00:14:00,710 --> 00:14:05,025 That'll be from part two of the course. So, I don't want to go into times. 172 00:14:05,025 --> 00:14:12,598 Let me just show you that this works. FACT of 0 is 1. 173 00:14:12,598 --> 00:14:24,470 FACT of 3 is 6. FACT of four is 24. 174 00:14:24,470 --> 00:14:32,620 If you count them, there would be 24. FACT of 8 mmmmmm. 175 00:14:32,620 --> 00:14:40,349 More, it takes a long time to print, long, long time to print. 176 00:14:40,349 --> 00:14:48,850 Very long time to print out this long list of exclamation marks. 177 00:14:48,850 --> 00:14:53,580 So, what's the moral of the story here? The most important thing is to know when 178 00:14:53,580 --> 00:14:59,780 we design programs we come up with data definitions that represent information. 179 00:14:59,780 --> 00:15:05,490 And we can take any data to represent any information we want. 180 00:15:05,490 --> 00:15:10,625 Now of course, the underlying hardware makes some primitive data faster than 181 00:15:10,625 --> 00:15:16,078 other primitive data. We still haven't finished printing out 182 00:15:16,078 --> 00:15:21,380 this representation of FACT of eight. This is a terrible representation of 183 00:15:21,380 --> 00:15:24,190 natural numbers. You would never want to use this. 184 00:15:24,190 --> 00:15:30,910 I just wanted you to see that you can take the bottom to be anything you want. 185 00:15:30,910 --> 00:15:34,580 You can come up with your own numbers. You can come up with your own strings. 186 00:15:34,580 --> 00:15:40,080 You can come up with your own lists. You can create any data you want. 187 00:15:40,080 --> 00:15:43,100 So, as I said at the beginning, that's a little wacky. 188 00:15:44,180 --> 00:15:47,652 Most of the time, nearly all the time, you're just going to work with whatever 189 00:15:47,652 --> 00:15:51,890 representation of numbers the programming language gives you. 190 00:15:53,030 --> 00:15:57,040 Still it's kind of fun to explore that. And you remember the lesson material this 191 00:15:57,040 --> 00:16:00,598 week is not wacky. And the rest of the material this week is 192 00:16:00,598 --> 00:16:04,580 essential representing arbitrary sizing formation. 193 00:16:04,580 --> 00:16:08,710 Well formed self referential type comments operating on lists and the 194 00:16:08,710 --> 00:16:13,090 reference rule. All of that's essential material. 195 00:16:13,090 --> 00:16:17,811 So, be sure to practice it a lot, and we'll see you again next week.