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

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