Compilers Challenge #2: The Language with No Variables

Welcome to the second compilers challenge, a series of compilers related code challenges. This episode is about the Forth programming language, which is interesting in the way that it is simple. In future challenges, we plan to build a simple Forth interpreter, but in this episode, I challenge you to write programs in Forth. I walk you through the basic concepts in Forth and then set you off on your adventure. Enjoy. You can find all compilers challenges here: https://github.com/airportyh/compilers_challenge.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello
00:02 : i want to tell you about a programming
00:03 : language
00:05 : it's a bit eccentric but it's a great
00:08 : language to learn if you're interested
00:10 : in compilers because it shares the same
00:12 : interpreter architecture as many
00:14 : mainstream languages such as python
00:19 : for one thing it doesn't have variables
00:25 : i can show you let's have a stroll
00:37 : welcome to the second compilers
00:38 : challenge in the last challenge we
00:41 : covered the reverse polish notation
00:43 : where arithmetic operators go after
00:46 : their operand for example the compound
00:48 : operation 3 plus 4 in parentheses times
00:52 : 5 would instead be written 3 4 plus 5
00:56 : times we saw how we can implement a
00:58 : stack-based machine to evaluate
01:00 : arithmetic operations written this way
01:03 : basically we scan the sequence of tokens
01:05 : from left to right whenever we encounter
01:08 : a number we push it onto the stack
01:11 : whenever we encounter an operator we
01:13 : execute the operation on the top two
01:15 : numbers of the stack it's a bit like
01:18 : casting a spell
01:19 : the stack is the place where you place
01:21 : the required ingredients
01:24 : and the operator is the spell you cast
01:27 : and when you cast it the ingredients
01:29 : become the result that you're after
01:32 : another way to look at this sequence of
01:34 : tokens is to treat each token as an
01:37 : instruction this is more of a cpu
01:40 : analogy an operator is an instruction to
01:44 : carry out some kind of arithmetic and a
01:46 : number is simply an instruction to load
01:49 : that number onto the top of the stack
01:52 : it turns out that you can extend this
01:54 : simple scheme into a general purpose
01:56 : programming language simply by adding
01:58 : more operators
02:00 : and allow programmers to define their
02:02 : own custom operators or subroutines
02:06 : fourth is a programming language that
02:07 : does precisely that
02:09 : although fourth is not known as a
02:12 : mainstream language it has enjoyed
02:14 : grassroots support since its inception
02:17 : in the 1970s
02:19 : fourth was invented by chuck moore and
02:22 : to him the language was a response to
02:25 : his frustration with existing software
02:27 : tools which he viewed as a sort of tower
02:30 : of babel the typical compiler
02:33 : architecture has a hierarchical
02:35 : structure like this
02:36 : each layer in the hierarchy communicates
02:39 : to their previous layer and their next
02:42 : layer via a specific language designed
02:44 : for that purpose
02:45 : this means that in order to understand
02:47 : how the entire compiler works one must
02:50 : understand each of the languages
02:52 : involved and how they relate to each
02:54 : other moore came up with an architecture
02:56 : that has only one single layer
02:59 : dramatically simplifying the
03:01 : construction of the compiler
03:03 : fourth simplicity makes it a good
03:05 : starting point for learning the art of
03:07 : compilers if you have done the first
03:09 : compilers challenge then you're already
03:11 : halfway there towards implementing an
03:13 : interpreter for fourth if you haven't
03:16 : yet it's never too late we'll build a
03:18 : simple fourth interpreter in upcoming
03:20 : episodes
03:22 : but if you're going to implement a
03:23 : programming language you should know
03:25 : that language and have an appreciation
03:27 : for that language
03:29 : in this episode i challenge you to write
03:31 : programs in fourth fourth is probably
03:34 : gonna feel a little different from the
03:36 : languages you are used to but it's not
03:38 : difficult
03:40 : think of it like going to an adventure
03:42 : in a foreign land take it easy and soak
03:45 : up their unique scenery and culture
04:00 : in order to get fourth you can download
04:02 : a version of swift fourth for your
04:05 : operating system from fourth.com
04:09 : or you can use the interactive coding
04:11 : environment on replic.com
04:14 : replit allows you to use an
04:16 : implementation of fourth called jsforth
04:19 : in your browser without you having to
04:21 : install anything on your own system
04:24 : here's how to do it with replied first
04:26 : you need to log into replit via your
04:29 : google account github account or
04:31 : facebook account
04:33 : once you're logged in you'll click
04:35 : create reply
04:37 : then search and select fourth
04:40 : and then click create reply
04:44 : and now you're ready to start coding in
04:46 : fourth
04:47 : these are the features of fourth i'm
04:48 : going to cover here after that i would
04:51 : describe the code challenge and set you
04:53 : off on your adventure if you'd like to
04:56 : have a book for learning fourth i highly
04:58 : recommend starting fourth which is a pdf
05:01 : you can get on fourth.com i will also
05:04 : link it in the description
05:06 : in fourth the concept of the stack is
05:08 : central to the language almost every
05:11 : operation works based on the current
05:13 : values of the stack the reverse polish
05:16 : notation expressions we've already seen
05:19 : are valid statements in fourth and they
05:21 : will produce results on the top of the
05:23 : stack in the js fourth repel the
05:25 : contents of the stack is displayed each
05:28 : time after executing a statement
05:31 : to print the top item of the stack you
05:33 : can use the dot operator
05:36 : you can add the dot operator to the end
05:39 : of a sequence to explicitly print the
05:42 : result
05:43 : the dot operator is destructive
05:46 : because it removes the result that it
05:48 : prints from the top of the stack
05:51 : so you can also use it to clear out the
05:53 : stack if there are any unwanted values
05:56 : there
06:00 : for the purpose of debugging there's
06:02 : also the
06:03 : s operator capital s which prints the
06:06 : contents of the entire stack without
06:08 : destroying it
06:10 : on replied the repo already does that
06:12 : for you in its normal operation but if
06:14 : you're using swift fourth which doesn't
06:17 : do that dot s will come in handy you can
06:20 : also print a character by its ascii code
06:23 : value using the emit subroutine
06:27 : you can find the ascii code value for
06:29 : any character on your keyboard at
06:32 : asciitable.com which might be handy for
06:34 : writing a hello world program
06:37 : it's possible to write text literals but
06:40 : i'm gonna skip that because who needs
06:42 : them when you have ascii
06:44 : we're going spartan
06:47 : the cr subroutine can also be useful it
06:50 : prints a carriage return to the terminal
06:52 : creating a new line to help you with
06:54 : formatting
07:07 : like other languages fourth allows you
07:09 : to define your own subroutines a
07:11 : subroutine is defined starting with a
07:14 : colon and ending with a semicolon
07:16 : the first thing after the colon is the
07:18 : name of the subroutine
07:20 : then you write the list of instructions
07:23 : you want executed whenever the
07:25 : subroutine is called
07:26 : for example this defines a star
07:29 : subroutine which prints a asterisk to
07:31 : the screen s42 is the ascii code for an
07:35 : asterisk don't forget to put a space
07:38 : after the colon and just before the
07:40 : semicolon at the end very important
07:43 : let's define it in the repo
07:45 : now to call it we simply type star and
07:48 : hit enter
07:50 : subroutines do not have parameters
07:52 : instead values are passed to subroutines
07:55 : by putting them on the stack immediately
07:57 : before calling the subroutine for
07:59 : example this is the definition for the
08:01 : increment subroutine which adds 1 to the
08:04 : passed in number it expects the number
08:06 : to be incremented to have been placed on
08:09 : the stack before it's called when it is
08:11 : called it puts one on top of the stack
08:15 : then executes the plus operator now when
08:17 : the subroutine exits and the control is
08:20 : returned back to the caller they will
08:22 : have the result ready for use
08:24 : to call this routine
08:26 : a programmer would simply type the
08:28 : number they'd like to increment followed
08:30 : by increment
08:32 : note that a subroutine is called in
08:34 : postfix notation just like normal
08:36 : operators different subroutines may
08:39 : expect a different number of values to
08:41 : be passed to it on the stack they may
08:43 : also produce a different number of
08:45 : results to be left on the stack when
08:48 : they're done
08:49 : for example let's say there's a
08:50 : subroutine called sum3 that sums the top
08:53 : three numbers on the stack
08:55 : to use it i would first put the three
08:57 : numbers i want to sum on the stack
09:00 : and then i would call sum three
09:03 : sum three would be implemented like this
09:05 : with two plus operators the first plus
09:08 : to add the first two numbers on the
09:10 : stack and then the second one to add
09:13 : their result to the third number
09:16 : it is often helpful for users of your
09:18 : subroutines to document what values your
09:21 : subroutine takes from the stack and what
09:23 : values it puts back to the stack in
09:26 : other words its inputs and outputs
09:29 : in fourth there is a convention of using
09:31 : the following notation
09:33 : parenthesis in force are ignored by the
09:36 : interpreter and considered a comment so
09:39 : this notation is more for humans than it
09:42 : is for the machine
09:43 : we have two dashes in the middle
09:46 : the inputs are on the left of the dashes
09:49 : and the outputs are on the right of them
09:52 : and you can name them as you wish
09:55 : with the input list the rightmost input
09:57 : is the one expected to be on the top of
10:00 : the stack
10:01 : one more thing don't forget to put a
10:03 : space after the opening parenthesis and
10:06 : before the ending parentheses
10:20 : in some situations you may wish to
10:22 : manipulate or rearrange the items on the
10:24 : stack in order to prepare it for an
10:26 : upcoming operation
10:28 : the built-in subroutines dupe swap wrote
10:32 : over and drop do just that
10:35 : dupe duplicates the value on the top of
10:38 : the stack it can be used to implement a
10:40 : square function by first duplicating the
10:43 : value to b squared and then applying the
10:45 : multiply operator another situation to
10:48 : use dupe is when you need the same value
10:51 : in multiple steps within a calculation
10:54 : for example with this equation
10:56 : we start with an a on the stack then we
10:59 : apply dupe to get two a's on the stack
11:03 : now we apply two plus
11:05 : to get a plus two on top
11:08 : and then finally apply multiply to get
11:11 : the final answer
11:12 : if we define a subroutine for this
11:14 : formula
11:16 : it will look like this
11:18 : the swap subroutine swaps the top two
11:21 : items on the stack
11:23 : the root subroutine rotates the third
11:26 : item from the stack to the top pushing
11:29 : the top two items down
11:31 : the drop subroutine removes the top item
11:34 : of the stack
11:35 : the over subroutine duplicates the
11:37 : second item of the stack and puts it on
11:39 : top
11:40 : here's an example to demonstrate the
11:42 : usefulness of these stack manipulation
11:45 : routines let's say you want to make a
11:47 : subroutine to calculate this formula
11:49 : the values a b c are provided for you on
11:52 : the stack like this with a on top
11:55 : initially how would you do this
11:58 : well in order to square a we have better
12:00 : make a copy of it
12:02 : in fact we need to make two copies of it
12:05 : two of them to calculate a squared but
12:08 : the third one we need to save it off to
12:11 : use to multiply it to be later
12:13 : so we call dupe twice to get three
12:16 : copies of a next we multiply to get the
12:19 : square of a
12:21 : and now we move on to multiplying a to b
12:25 : but a and b are not on the top of the
12:26 : stack
12:27 : so we're going to use row twice
12:30 : to rotate both of them to the top of the
12:32 : stack to get ready
12:34 : and now we multiply
12:36 : now we have the results of a squared and
12:38 : a times b on the top of the stack so we
12:41 : can add them together with the plus
12:43 : operator
12:46 : next we want to divide the current
12:48 : result by c but the divisor operator
12:50 : requires their order be reversed
12:53 : so we use swap to switch their position
12:56 : and now we're ready to divide and get
12:58 : the final result
13:00 : so this is the full sequence of
13:02 : instructions we use to calculate our
13:04 : formula what a piece of code
13:22 : in fourth an if statement cannot be used
13:24 : directly in the rebel but instead must
13:26 : appear within a subroutine definition
13:29 : this is an example here we assume ok is
13:33 : a subroutine already defined that prints
13:35 : ok
13:36 : 20 greater than will determine if the
13:39 : value on the stack is greater than 20
13:41 : and put a truthy value or a falsie value
13:45 : on the stack fourth treats any non-zero
13:48 : value as truthy and 0 as farsi why they
13:52 : decided to use negative 1 as the truth
13:54 : value by default i'm not sure about that
13:58 : then we encounter the if operator which
14:01 : will execute the sequence coming after
14:03 : it but before the then if the result was
14:06 : truthy
14:08 : the if statement in fourth may look a
14:10 : bit awkward consider that it is in
14:13 : reverse polish notation so the condition
14:16 : goes before the if
14:18 : and the part that precedes the then is
14:21 : the consequent action
14:24 : if we add in the else clause then we
14:27 : have an added alternate action that goes
14:30 : between else and then
14:44 : similarly to if statements a loop must
14:47 : appear within a subroutine definition
14:50 : this subroutine calls the hollow routine
14:52 : five times it creates a counter
14:55 : internally and initializes it to 0. then
14:58 : it increments it until it reaches 5.
15:05 : so the two numbers you put on the stack
15:07 : before calling the do loop are the
15:10 : starting and ending values for the
15:12 : counter in reverse order
15:15 : the sequence of instructions between do
15:17 : and loop are repeated for each iteration
15:21 : if you want to access the counter value
15:23 : you can use the symbol i anywhere
15:25 : between do and loop
15:27 : and it will put i on the stack
15:31 : let's print out i using the dot operator
15:37 : here you can see that the starting value
15:39 : 0 is included but the ending value of 5
15:42 : is not
15:44 : because do loop is based on the current
15:46 : values of the stack you can ask the
15:48 : caller of your subroutine to pass in how
15:51 : many times they want loop to run for
15:53 : example they could write 10
15:55 : space count
15:57 : and we could implement the current
15:59 : subroutine like so
16:01 : this way count will count up to whatever
16:04 : number is specified by the caller
16:25 : recursion and force is done with the
16:27 : word recurse if you try to write the
16:30 : name of the current subroutine
16:32 : fourth will get confused
16:34 : so you write recurse instead
16:37 : this infinite subroutine will print
16:39 : hello to the terminal indefinitely
16:43 : although don't try this in reply because
16:45 : it will completely lock up your browser
16:48 : in swift fourth it will actually do it
16:50 : it just won't stop until you type
16:52 : control c
16:54 : here's a more practical example that
16:56 : counts down from a given number first it
16:59 : prints the number
17:01 : dupe is used to preserve the number
17:03 : despite it being consumed by the dot
17:05 : operator
17:07 : then it decrements the number by one
17:09 : then it checks to see if the number is
17:11 : greater than zero
17:13 : again dupe is used to preserve the
17:15 : number despite being consumed by the
17:18 : comparison operator
17:19 : finally if the previous check was truthy
17:23 : which will be negative one
17:25 : then we recurse which means we call the
17:28 : countdown subroutine again in a nested
17:31 : fashion
17:33 : now pay attention as we watch how this
17:35 : recursive countdown subroutine works
17:38 : step by step with the starting value of
17:40 : 3 put on the stack
17:43 : [Applause]
17:55 : do
18:17 : so
18:33 : do
18:39 : [Music]
19:31 : it's time for the challenge
19:34 : i have written up three warm-up
19:36 : exercises followed by one grand
19:39 : challenge
19:40 : challenge number one
19:43 : write two subroutines
19:45 : say odd and say even
19:48 : say odd prints the word odd to the
19:50 : screen and say even prints the word even
19:53 : to the screen
20:00 : challenge two
20:02 : write a subroutine
20:04 : say odd or even
20:06 : this subroutine takes a number from the
20:08 : stack
20:10 : it prints that number and then if the
20:12 : number is odd it calls say odd otherwise
20:16 : it calls say even
20:23 : challenge number three
20:25 : write a subroutine
20:27 : say odd or even up to
20:30 : this subroutine takes a number from the
20:32 : stack counts from 1 up to that number
20:36 : and for each number encountered it calls
20:39 : say odd or even
20:47 : finally for the grand challenge
20:50 : the grand challenge is to implement the
20:52 : fibonacci subroutine the fibonacci
20:54 : sequence if you haven't seen it is a
20:56 : sequence of numbers that starts with one
20:59 : and one
21:00 : but starting the third number of the
21:02 : sequence we can calculate its value as
21:05 : the sum of the previous two numbers
21:08 : this subroutine takes a number i from
21:10 : the stack and replaces it with the
21:12 : number at the i's position in the
21:14 : fibonacci sequence
21:27 : you're worried that you might not be
21:28 : able to solve the challenge first of all
21:30 : even if you don't get a working answer
21:33 : it's not a failure just trying to solve
21:35 : the problem will help you learn better
21:37 : when you're learning the solution later
21:39 : i will present my solution in about a
21:41 : week
21:42 : secondly my son said this to me about
21:45 : overcoming challenges he said when i
21:48 : encounter something challenging i think
21:50 : more deeply about the problem starting
21:53 : from what i know
21:54 : the thing i take away from his comment
21:56 : is you're not as helpless as you think
21:59 : take your time to get your brain going
22:01 : and you start making progress
22:05 : i have all these challenges written up
22:07 : in a github repo and i will link them in
22:09 : the description
22:11 : you may join our discord channel if you
22:13 : want to chat with me or others who are
22:15 : working on these challenges