CC #2 Solution: Forth

This is the solutions to compilers challenge #2 about the Forth programming language. Much fun was had in making this video. We will have loops, recursion and we will see them animated to life. Enjoy! You can find all compiler challenges here: https://github.com/airportyh/compilers_challenge

Transcript

The following transcript was automatically generated by an algorithm.

00:11 : welcome to the solutions for compilers
00:13 : challenge number two in the challenge
00:15 : video you were given code challenges to
00:18 : be solved using the fourth programming
00:20 : language the grand challenge is to
00:22 : implement the fibonacci function in
00:24 : fourth
00:25 : which is an interesting challenge if
00:27 : you've never used a language without
00:29 : variables before what does the solution
00:32 : look like
00:33 : we'll review two solutions to the
00:35 : problem later in this video if you
00:36 : haven't seen the challenge video you can
00:38 : watch it for some context go to this
00:40 : link for a written description of the
00:42 : code challenges if you have already
00:44 : taken on the challenge regardless of
00:46 : whether you got all the right answers
00:48 : congratulations but if you just want to
00:50 : enjoy the show i shall review the
00:52 : solutions now
01:00 : i will first write the code skeleton for
01:02 : the subroutines to print out individual
01:04 : letters i'm heading over to
01:06 : asciitable.com o has a code of 111
01:10 : and d has a code of 100 so simply
01:13 : emitting a 1 11 and then 2 100 will
01:17 : print out the word odd let's test it
01:24 : that works there's an alternative way to
01:27 : do it which is to first push all three
01:29 : codes onto the stack
01:31 : and then call emit three times if you do
01:33 : it this way you have to push the codes
01:36 : in reverse order so first you push the
01:38 : two 100s for the d's
01:41 : and then you push the 111 for the o
01:43 : and then call emit three times will
01:46 : first emit the o and then the two ds
01:54 : let's test that
01:58 : that works as well
02:00 : now let's apply the same scheme to say
02:03 : even
02:07 : okay
02:27 : to tell if a number is odd or even we'll
02:30 : need to use the modulus operator which
02:33 : will perform a divide of two numbers and
02:35 : give you the remainder we know if a
02:37 : number is even if the remainder from
02:40 : dividing it by two is zero
02:42 : so say we get the number three on the
02:44 : stack we do two mod
02:47 : then we do zero equals to compare the
02:50 : result to zero in this case we will get
02:52 : zero a falsie value
02:55 : now we can use the if statement to
02:56 : either call say even or say odd
03:00 : let's test that
03:04 : that works but we forgot to print the
03:07 : number itself first which is part of the
03:09 : requirement let's go back to the
03:11 : definition and add dupe dot to the
03:14 : beginning the reason we need dupe is
03:16 : because the dot operator which prints
03:19 : the top value of the stack is
03:21 : destructive if we don't want it to take
03:23 : off the value we use the dupe operator
03:26 : to make a copy of it first
03:28 : let's test that
03:31 : and it works
03:53 : for this one we're going to use a do
03:55 : loop
03:56 : do loop takes two numbers from the top
03:58 : of the stack the n number and the start
04:01 : number to count from
04:03 : we're going to let the caller pass in
04:05 : the end number before calling into our
04:07 : subroutine so let's omit the n number in
04:10 : here
04:11 : and we'll start the counting from zero
04:14 : let's just try putting the counter i on
04:16 : the stack and call
04:18 : say odd or even on each iteration and
04:21 : see what happens
04:26 : okay
04:27 : there's a couple of problems one is that
04:29 : all lines have been jammed together into
04:31 : a single line another is that we're
04:34 : starting from zero going up to four
04:36 : instead of starting from one and going
04:38 : up to five
04:40 : let's fix one thing at a time
04:42 : to fix the lines being jammed together
04:44 : we can use the cr command to print a new
04:47 : line separating each printed line
04:50 : there we are
04:52 : now to fix the second problem we'll add
04:54 : 1 to i
04:55 : just before calling say odd or even
05:02 : that works
05:33 : okay for the grand challenge the
05:35 : fibonacci sequence
05:37 : we can solve it in one of two ways
05:39 : either using a loop or using recursion i
05:42 : will show the solution for both of them
05:44 : so that regardless of which one you did
05:46 : you can compare notes with my solution
05:49 : we'll start with the loop-based solution
05:52 : in a more traditional language this
05:54 : solution is based on two variables let's
05:56 : call them a and b
05:58 : both of them are initialized to one
06:00 : and then on each turn we update them a
06:03 : becomes b and b becomes the result of a
06:06 : plus b in python you can simply write it
06:09 : in one line like this we'll print out
06:11 : the value of a and b after this
06:14 : transformation a is now 1 and b is now
06:17 : 2. if we do this transformation over and
06:20 : over again we'll see the fibonacci
06:22 : sequence emerge since b contains the
06:25 : second number in the sequence from the
06:27 : start if we want the nth number in the
06:29 : sequence we simply need to repeat this
06:31 : transformation n minus 2 times
06:34 : and then read out the value of b
06:37 : for programming languages that don't
06:38 : support this swapping assignment syntax
06:42 : you can use a temporary variable to hold
06:44 : the result of a plus b
06:46 : and then assign b to a and then assign
06:48 : the value of temp to b
06:51 : now how do we do the same thing in
06:53 : fourth
06:54 : let's figure out how to do the
06:55 : transformation step first because
06:57 : everything hinges on that
06:59 : let's say we have the values of a and b
07:02 : on top of the stack like this
07:04 : and what we'd like to get is the next
07:07 : values of a and b let's call them a
07:09 : prime and b prime
07:11 : which will equate to a plus b on top and
07:15 : b on the bottom
07:16 : what sequence of instructions can be
07:18 : applied
07:19 : that will transform the stack from this
07:22 : into this
07:25 : well we want to add a to b
07:28 : and they're both on the stack but we
07:29 : don't want to do it now because if we
07:31 : did that now we would lose b so we
07:34 : probably need to use dupe to have an
07:36 : extra copy of b around
07:38 : now we want to get the result of a plus
07:40 : b but a is the third position in the
07:43 : stack so let's use rotate to move it up
07:46 : and now we're ready to add and we have
07:48 : achieved the desired state of the stack
07:51 : so dupe wrote and plus this is the
07:54 : sequence of instructions we need for the
07:56 : transformation
07:57 : and they're going to go into the loop
08:02 : there are two separate things we need to
08:03 : juggle here the setup for the n and
08:06 : start numbers for the do loop and the
08:08 : initialization of a and b
08:11 : what order should these numbers go
08:14 : well remember that immediately before
08:16 : calling do we have to put the n and
08:19 : start numbers on the stack for the do
08:21 : loop to consume so if we want a and b to
08:24 : be on the stack after the do loop
08:27 : consumes it
08:28 : we're going to need to put a and b on
08:30 : the stack before the nn start numbers so
08:32 : we push 1 and 1 for the values of a and
08:36 : b
08:37 : the first thing inside our subroutine
08:39 : but now we have a problem
08:41 : before the caller called our subroutine
08:43 : they had first put the value of n on the
08:45 : stack
08:46 : and now we've put 1 and 1 on top of it
08:49 : because the number n is what we want to
08:51 : use for the n number of the loop we now
08:54 : need to use rotate to move it back to
08:56 : the top
08:58 : and similar to the python version we
09:00 : also want to subtract 2 from it to get
09:02 : the desired n number for the loop before
09:05 : putting 0 as the start number
09:14 : now let's test it
09:16 : we're getting an extra number and that's
09:18 : because both a and b remain on the stack
09:21 : at the end
09:22 : from the perspective of the caller all
09:24 : they care about is the final value of b
09:27 : we should remove a from the stack
09:30 : to do this we first swap and then drop
09:34 : and now only b remains
09:38 : let's test that
09:42 : and it works
09:44 : [Music]
09:54 : do
09:58 : [Music]
10:23 : now let's do the recursive version to
10:26 : get a skeleton of what we need to do
10:28 : this is a recursive version in python
10:31 : the fib function returns 1 if n is 2 or
10:35 : lower otherwise we're going to
10:37 : recursively find the fib number at n
10:40 : minus 1 and n minus 2 and then add them
10:42 : together to get the final answer now
10:45 : whenever you use recursion there's this
10:47 : cool moment where before you're even
10:50 : done writing the function you take a
10:52 : leap of faith that recursively calling
10:55 : your own function will give you the
10:56 : correct answer for the sub problem and
10:59 : that moment happens with writing the
11:01 : fourth version of this as well
11:04 : so the caller put n on the stack before
11:06 : calling into our subroutine
11:08 : the first thing we'll check is if this
11:10 : number is less than or equal to two in
11:13 : js4 we only have less than so we'll use
11:16 : less than 3. again we want to use dupe
11:19 : first to save n for later
11:25 : let's suppose that n is less than three
11:28 : in this case we want to remove n from
11:30 : the stack and just return one
11:33 : we can do this with the instructions
11:35 : drop and then one now let's go back
11:38 : and we have n on the stack again
11:41 : but let's say this time it's not the
11:43 : case that n is less than three this is
11:45 : the case when we want to recurse
11:48 : first we recurse for n minus one
11:51 : and then we recurse again with n minus
11:53 : two
11:55 : when subtracting 1 we want to use dupe
11:57 : first to save it for the second
11:59 : recursion
12:01 : now we recurse and this is the magic
12:03 : moment when we take a leap of faith and
12:05 : assume the recursive call will do the
12:07 : right thing if it did it would leave the
12:09 : correct answer on the stack when it
12:11 : exits so we just imagined that that had
12:13 : happened and we'll get the answer f of n
12:16 : minus one we use that to mean the n
12:18 : minus first number of the fibonacci
12:21 : sequence now we want to recurse again
12:23 : with n minus 2 as the input
12:26 : now n is still on the bottom so let's
12:29 : bring it back up with a swap
12:31 : and then we'll minus 2
12:33 : and recurse
12:34 : again we imagine that the recursive code
12:37 : did the right thing
12:38 : and if it did it should give us f of n
12:41 : minus 2 on the stack and now we have the
12:43 : answers to this two separate sub
12:45 : problems and we're ready to add them
12:47 : together to get the final answer
12:50 : which you can verify is the end number
12:52 : of the fibonacci sequence
12:54 : so this is the sequence of instructions
12:57 : for the recursive fibonacci subroutine
13:04 : let's test it
13:10 : and it works
13:13 : [Music]
13:21 : [Music]
14:33 : so
14:40 : [Music]
15:00 : so
15:02 : [Music]
15:31 : do
15:35 : [Music]
16:00 : you