Make Your Own Language 10: Coding Challenge

This is the tenth episode of a series where you build your first programming language, using these videos as a guide. We’ve setup the syntax for a small programming language. You can clone this project and start getting to work. The project repository is https://github.com/airportyh/smallang. In this episode, we struggle through the roman numerals coding challenge, and see if this programming language is worth anything.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : hello this is toby welcome back to the
00:02 : series where we make a programming
00:04 : language
00:05 : um so we're making the programming
00:08 : language called smalling
00:09 : this is the stage where we're putting
00:11 : the finishing touches on this
00:13 : language small as it may be and the way
00:16 : i
00:17 : usually try to find holes in the
00:20 : language is by
00:21 : writing various programs in it and one
00:24 : way to get to do that is by
00:25 : solving coding challenges so i chose
00:28 : this roman numerals
00:30 : encoder challenge from codewars.com last
00:33 : time
00:34 : i started on it and i ran into some
00:37 : issues with the language ran into an
00:38 : ambiguous
00:39 : grammar issue and i had to fix that
00:43 : and at this point we have this program
00:46 : that is going through with an if
00:48 : statement to determine
00:50 : what roman numeral to produce given a
00:53 : single digit number and at this point
00:55 : i'm thinking
00:57 : gosh this code is going to be very
00:58 : tedious is there a better way to do it
01:01 : so i decided to take a look at the
01:03 : problem from a higher level
01:05 : so let's look at the roman numerals
01:07 : chart from
01:08 : 1 to 100 interestingly zero is
01:12 : not defined they don't have a way of
01:14 : saying zero
01:15 : in roman numerals great um
01:19 : so the way i see it the roman numerals
01:22 : is based on two digits right it's based
01:25 : on
01:27 : one five there's a version of one
01:31 : and five in the tens and there's uh
01:35 : i believe there's also a version of five
01:37 : for the hundred
01:38 : uh yes that's d so d
01:42 : means 500 m means
01:46 : one thousand let's say there's a
01:49 : ones place there's a tens place
01:52 : there's a hundreds place and there's a
01:56 : thousands although i'm not sure if
01:59 : there's
01:59 : a letter symbol for five thousand
02:01 : defined or not
02:02 : um so for each one of these places
02:06 : there's a symbol defined for one
02:09 : and five right this should be c and d
02:13 : and then m and maybe there's a five
02:16 : thousand
02:17 : i'm not sure for each one of these cases
02:20 : you can
02:20 : break down the digits for the
02:24 : ones place tens place hundreds
02:28 : thousands so for ones is i
02:31 : i i i i i
02:35 : why did i miss eight i don't know
02:38 : so i'm gonna stick eight in here this is
02:41 : terrible maybe i should use a
02:42 : spreadsheet to do this
02:44 : and for tens i believe we have this
02:47 : exact same thing as in we
02:50 : cannot take the five
02:53 : four tenths which is l and put the one
02:58 : to the left of the l for the four
03:01 : and then five is l l stands for 50
03:05 : as we see here and then we have l
03:09 : x l x x l
03:12 : x x x l x x
03:15 : x x let me verify these actually so
03:19 : 80 is l x x x
03:23 : yes and 90 is oh
03:26 : i got nine wrong this is actually
03:29 : x minus one and this is going to be
03:32 : c minus x
03:40 : if there isn't a 5000 symbol let me
03:44 : google it
03:44 : there is it's v is there more yes
03:48 : it's just v with a bar on the top
03:51 : holy crap and then for ten thousand if
03:54 : there's it's
03:55 : x with a bar on the top so 5000 is going
03:58 : to be a
03:59 : v with a bar minus one thousand
04:07 : so each of these columns follow the
04:09 : exact same rule
04:11 : as far as i can see in terms of
04:14 : the the pattern in which it first uses
04:17 : the ones
04:18 : and then when it gets up to the four it
04:20 : does the five
04:21 : minus the one and then when it's five it
04:24 : uses the five symbol and then it's
04:26 : five plus until it's the nine then it
04:29 : uses
04:30 : the or the one from the next column
04:33 : minus
04:33 : one in this column so all of these
04:36 : follow the exact same pattern
04:39 : if you have multiple digit the way to
04:41 : handle that
04:42 : is to like if you have like 56
04:46 : then you just split these two guys up
04:49 : and then
04:49 : you can say render each digit
04:52 : individually
04:54 : you render the six in terms of the
04:57 : you in terms of the ones column and you
05:00 : render the five
05:01 : in terms of the tens column and then you
05:05 : jam them together so uh
05:08 : six would be a v
05:11 : and an i and then a 5 in terms of the
05:14 : tens column
05:16 : would be a is it an l 50 is an
05:20 : l yes 50 is an l so then you
05:23 : then you just concatenate those two
05:25 : strings together
05:27 : and then you get l v i
05:30 : is that right yes you get lvi
05:33 : 28 we're gonna split them up and then
05:36 : eight
05:37 : we're gonna do it in terms of once
05:40 : v i i and then for two we're gonna
05:44 : do that in terms of tens which we're
05:47 : gonna get x
05:48 : x so the result is x x
05:51 : v i i i for 28
05:54 : yes and that's right so so i think
05:57 : that's how we're going to do it
05:59 : we're going to use a recursive algorithm
06:01 : because we don't have loops
06:02 : in this language um
06:06 : if you're using a lisp or lisp like
06:09 : language
06:10 : then recursion is all you got uh you
06:12 : better get good at that recursion man
06:15 : um basically the algorithm is gonna be
06:18 : take
06:19 : the number we're going to find the digit
06:22 : in the in the ones place by doing a
06:25 : modulo
06:26 : do we have a modulo we're going to add
06:28 : it uh
06:29 : we'll probably encounter a lot of things
06:31 : that we don't have so we'll the number
06:35 : mod 10 and we'll we'll get the
06:38 : ones place digit actually we don't
06:41 : necessarily know what place we are
06:43 : and i think that we need to be passed in
06:46 : as a parameter
06:47 : i'll just say this is the digit you you
06:50 : might
06:51 : tend to get the digit in the current
06:54 : place
06:54 : and the place might need to be passed in
06:57 : as a parameter to your function so you
07:00 : have your digit
07:02 : we need another function that will take
07:04 : this digit
07:05 : and the place number and give us
07:09 : i'm gonna call it render roman
07:12 : maybe i don't know or it's like a helper
07:16 : function
07:17 : they'll take a digit a place and then
07:20 : give you the
07:21 : roman notation and then we're gonna take
07:24 : the remaining number
07:26 : remaining is probably not a good name
07:28 : but basically the result of dividing by
07:30 : 10
07:31 : which like if we have a number like this
07:33 : 128
07:35 : we're dividing it up we're peeling one
07:37 : digit off this is the digit
07:39 : and we're calling it this the remaining
07:42 : remaining might be okay
07:43 : so the remaining we recursively call
07:46 : ourselves
07:46 : so this is just rendered render
07:49 : a digit render roman digit uh and you
07:52 : give it a place
07:53 : so it depends depending on if the place
07:56 : is
07:56 : one then it'll render
08:00 : like that but if the place was
08:05 : two maybe um then it'll render
08:08 : l x x x for the digit
08:12 : 8. so that's the plan let's try to make
08:15 : this happen
08:16 : i'm gonna just start over i'm gonna
08:20 : first make this function the the easy
08:23 : one
08:23 : i'm gonna call it a convert digit to
08:25 : roman and
08:27 : that is a function that takes a digit
08:31 : which which is a number between 0
08:34 : and 9 i believe in a place
08:37 : um let's put a line of comments digit is
08:40 : a number between zero to nine
08:42 : and place is a number
08:47 : representing what
08:49 : place uh one means once
08:53 : two means tens three
08:56 : means hundreds and
08:59 : four means thousands
09:03 : let's do it like that so we have our
09:05 : comments
09:07 : hopefully that helps so given a digit it
09:10 : depends on the place
09:11 : uh so i actually want to make a separate
09:15 : helper function for one and five
09:19 : so one i think this will help so based
09:22 : on the place
09:23 : if the place is one then
09:27 : i want to return i else if
09:30 : so so this one function will give me
09:34 : either a i or in the ones case
09:37 : or a x in the tens case
09:40 : and a hundred i believe is c yeah
09:43 : c or a m it'll return one of those
09:48 : four things actually i'm thinking
09:50 : instead of doing this
09:51 : there's a faster way of doing this i'm
09:54 : just gonna make an array
09:55 : no not even an array i'm just gonna make
09:57 : a string like this
09:59 : and then use array indexing to access it
10:02 : i'll make a function called
10:04 : at which you pass in an index it'll
10:07 : index into this string okay and then
10:11 : this we just have to subtract one
10:14 : to the place to to make it zero indexed
10:18 : uh that's it now i'll make another one
10:22 : for five for five it'll be v
10:25 : l 500 is a d
10:29 : and then for five thousand is v with a
10:32 : bar
10:33 : on top oh that's not a symbol
10:36 : okay use this guy i'm going to use this
10:38 : crazy
10:39 : looking symbol this looks like a d
10:42 : with a smaller d inside of it that looks
10:45 : awesome
10:45 : actually wait where's the 500 500 is d
10:48 : okay there's a normal d and then the d
10:51 : with the inner d
10:52 : okay so that's how you get a five and
10:55 : now i believe i can say
10:56 : so if digit is zero then we're just
11:00 : returning an empty string else
11:03 : if the digit is one
11:07 : we're gonna return a
11:10 : one for that particular place
11:14 : else if the digit is
11:18 : two then it will say can cap
11:21 : together
11:26 : we could actually do use recursion here
11:29 : would that help
11:30 : me though would that help me write less
11:32 : code
11:33 : so if i did it like this i'll need an or
11:36 : if it's a two or three we're gonna just
11:40 : subtract one and and then make it
11:42 : recurse like this
11:44 : else if the digit is
11:48 : four then let's do uh
11:53 : i feel like this might be like a little
11:56 : bit
11:56 : indirect here maybe do it like
11:59 : have a repeat function maybe if it's one
12:03 : two or three let me do it like this so
12:05 : that we just have
12:06 : less nesting because this nesting is
12:08 : kind of bothering me
12:10 : so it's one two or three and i could
12:13 : make up whatever function i want i'm
12:16 : gonna
12:16 : implement them as long as they're not
12:19 : too difficult to implement
12:20 : i'm just gonna implement these functions
12:22 : as we go
12:24 : so say if the digit is one two or three
12:26 : we're going to repeat
12:27 : digit number of times and that kind of
12:31 : allows us to take care of three with one
12:34 : clause
12:35 : although that does make me think that
12:37 : perhaps we need some sort of a way
12:39 : to have if else statements
12:42 : or perhaps we simply indent it
12:45 : differently
12:46 : maybe we just indent it like this
12:52 : yeah we could just indent it like this
12:54 : so that
12:55 : this huge if statement isn't quite
12:59 : so onerous um okay
13:03 : it's still kind of onerous what about if
13:06 : the if statement could
13:08 : take any number of conditionals and the
13:11 : javascript
13:13 : runtime function can test to see if it's
13:16 : a conditional
13:19 : i actually don't like that idea because
13:21 : that because
13:23 : um unless we wrap the conditionals into
13:27 : from another function that's gonna sort
13:29 : of prematurely calculate
13:31 : all of the conditionals and i do not
13:33 : want that that will make it impossible
13:35 : to do
13:36 : cards and stuff like that i'm going to
13:38 : go back to this
13:40 : very very nested way of writing this
13:42 : code
13:43 : and just hope we can get through this
13:45 : alive so if it's
13:46 : a four then it should be five
13:50 : of this place concat it
13:54 : with the one of this place
13:58 : else if the digit is a
14:01 : 5 then we just want the 5
14:04 : for this place else if the digit is a 6
14:08 : then we want to concat the 5 of this
14:11 : place
14:14 : for 6 7 and eight we could do this
14:17 : same thing
14:20 : we can concat the five in that place
14:24 : with the repeat of the digit
14:27 : minus five of the ones place
14:30 : you can do it like that and then
14:33 : finally for the nine we're gonna concat
14:37 : one for this place and then we're gonna
14:40 : concat that with the one of the next
14:42 : place which is place plus one
14:45 : and if it's none of these uh if there's
14:48 : a way to throw an exception i probably
14:50 : would but
14:51 : lacking that i'm gonna return an
14:53 : exclamation point
14:55 : and now we need to close all these
14:56 : parentheses
14:58 : but i have written code in lisp before
15:02 : and this reminds me of that i'm going to
15:05 : try to test this function here
15:07 : so if i convert the digit to roman for
15:10 : 5 for the first place
15:14 : uh let's see if this works
15:17 : no it does not syntax error
15:22 : oh i tried to use a minus
15:25 : sign we don't have
15:28 : operators in this language
15:32 : at least not yet
15:37 : okay unexpected r brace token
15:40 : i did open a left brace though
15:44 : so i'm gonna do a test case
15:45 : simplification to try to solve this
15:49 : oh there might be a problem in my parser
15:52 : unless i'm missing something
15:54 : i mean this should parse um so let me
15:58 : put this code back but i want to
15:59 : simplify this so i'm going to make a new
16:02 : file
16:03 : call it roman 2 for debugging purposes
16:06 : i'm going to delete this if statement
16:08 : i'm going to simplify this code by a lot
16:11 : so i narrow down the source of this
16:13 : problem
16:14 : here so it is able to parse example
16:20 : 4 which looks like this but it's not
16:24 : able to parse
16:26 : roman 2.
16:30 : okay so what's the difference here is it
16:34 : the name
16:37 : of the variable no what is the
16:40 : difference
16:41 : okay i'm gonna put i'm gonna put
16:44 : example for small into room and too
16:48 : small
16:49 : i call this the bug sandwich so this one
16:52 : works i'm gonna reduce it down
16:56 : this still works
17:01 : this still works
17:05 : oh so without
17:09 : a statement inside
17:13 : it breaks
17:18 : oh this works but having just a one
17:22 : doesn't work
17:23 : oh but having an if statement works
17:26 : right yes okay so one thing that doesn't
17:31 : work is
17:32 : an expression i think i do
17:35 : i should unify statements versus
17:38 : expressions
17:39 : i probably just shouldn't have the
17:41 : concept of statements in the first place
17:44 : all statements or expressions would
17:46 : allow
17:48 : you to do something like this because
17:50 : this should be allowed
17:52 : just returning a one but the thing that
17:55 : did not work is this if statement here
18:00 : oh it's probably this wanting to return
18:03 : this
18:04 : string that didn't work uh maybe
18:07 : like what if i did this so i'm going to
18:10 : try
18:11 : a start simple here and put
18:15 : this in here it should like it if it's
18:18 : just a function
18:19 : called expression
18:22 : oh now there's an error in oh because i
18:25 : have
18:25 : an extra paren i closed off this print
18:30 : so it's a parenthesis matching problem i
18:33 : think we're in the middle of a
18:34 : fun very big function called expression
18:37 : that didn't close off properly so i
18:41 : think what i might
18:42 : do is to try to do it section by
18:45 : section so this works so it's in here
18:48 : somewhere
18:54 : this works so it's in here somewhere
19:02 : this works so it's in here somewhere
19:09 : and that works so it's in here somewhere
19:15 : that broke so i think it's probably
19:19 : here i have too few parentheses
19:22 : is my guess oh now that worked so
19:25 : the problem is with the mismatching of
19:28 : parenthesis
19:29 : in this very very large if statement um
19:33 : let's try to run it at the moment the
19:35 : programming language is
19:37 : not giving you very good error messages
19:42 : when when you make a mistake and
19:45 : that is something that i plan to cover
19:48 : in the future how to
19:51 : how to give user better better feedback
19:53 : better error messages
19:55 : when they make mistakes but at the
19:57 : moment
19:58 : it's pretty bad
20:01 : all right i think we're in business it's
20:03 : saying or
20:04 : is not defined so we'll just define a
20:07 : function
20:08 : called or
20:12 : and we'll probably be fine let's define
20:15 : a function in the runtime
20:25 : at so at is for indexing and called
20:32 : hat
20:38 : whoa okay four
20:41 : for the ones place that's correct so
20:44 : what about for the tenths place it's
20:47 : xl yeah that looks good to me uh
20:50 : tess uh it has a few more like one
20:54 : through nine
20:57 : on the tens place
21:00 : repeat we're going to need a repeat
21:02 : function
21:05 : so let's make a result and
21:08 : we'll just say i'll start it as a an
21:11 : empty string and then we'll just loop
21:16 : here's our plus equals string and then
21:18 : return the result
21:20 : there's your repeat function
21:24 : in javascript we actually need commas
21:29 : so that's looking good to me and if we
21:32 : change the place back to once
21:38 : awesome uh okay so we can convert
21:42 : a number to roman for one digit
21:45 : now let's do it for any number of digits
21:48 : so i'll call this convert
21:50 : number to roman how about that
21:54 : and convert number to roman takes a
21:56 : number
21:58 : we may need a helper function because we
22:00 : need to a starting place
22:02 : so i'll make a helper function here
22:04 : which will take a number and a
22:06 : place we'll start it at the
22:09 : ones place and then it'll gradually
22:13 : increase
22:14 : okay so take the number and mod
22:17 : it modulus the number by 10
22:21 : to get the current digit
22:25 : and then uh we're going to
22:28 : convert that digit using this function
22:31 : we already have
22:32 : i'll say the left part oh this
22:35 : would be the right part actually
22:38 : right part would be convert that digit
22:42 : to roman
22:44 : at this current place and then we'll
22:47 : take
22:47 : the left part would be divide
22:51 : the number by 10 we want
22:54 : integer division so we need to floor it
22:57 : i think
23:00 : unless it's an integer but in javascript
23:02 : it is an integer and we are using
23:04 : javascript underneath
23:06 : so it could have a decimal there so
23:09 : we're gonna floor it
23:10 : and then the left part we're gonna
23:12 : recursively call ourselves
23:14 : to convert the left part based on
23:17 : uh place plus one we're gonna add one to
23:21 : the place convert
23:23 : the the left part like feel
23:26 : weird calling this left and then calling
23:29 : this
23:29 : left part how can we call this remaining
23:32 : even though it's not a good name for it
23:35 : i'm still gonna do
23:36 : it and then finally we're gonna
23:37 : concatenate
23:39 : the left part together with the right
23:41 : part and that
23:42 : is our answer see if that works i'm
23:45 : gonna comment
23:46 : out this code and print let's convert
23:50 : this number to
23:51 : roman uh what's 45
23:55 : modulus we need a modulus function in
23:58 : the runtime
24:03 : we also need a floor function
24:09 : maximum cost exercise exceeded uh we're
24:12 : trying to do recursion without
24:14 : a terminal case why do i do that i think
24:18 : the terminal case would be if the number
24:20 : is
24:21 : zero so if number zero
24:25 : then we're just going to return an empty
24:28 : string
24:30 : else we will do all of this stuff
24:33 : okay see if this works oh
24:37 : yeah 45 yeah that's a 5
24:41 : and that is a 40. i'm gonna look it up
24:46 : and yeah it's xlv so we have 45
24:51 : i'm tempted to want to print this table
24:54 : out at this point
24:55 : and in order to do that you need some
24:57 : more runtime functions
24:59 : maybe in the style of python we might
25:02 : have a range
25:03 : function that starts from 1
25:06 : goes to 100 and then we're gonna each
25:10 : over that range
25:14 : and then for each number we'll convert
25:17 : it to
25:17 : roman and then print out
25:21 : the number and then equal sign
25:24 : and then the roman numeral value
25:28 : and in order to force that to work we're
25:31 : going to need a couple more functions
25:33 : so we need the each function we need a
25:35 : range function as well
25:37 : range detection start an
25:41 : n number and we'll say
25:45 : we'll make an array of numbers
25:48 : starting at the start and i think in
25:51 : python and just test it out in python
25:56 : one to a hundred converted to a list
26:01 : it includes the one but not the 100
26:05 : okay let's follow suit that i
26:09 : equals start and then do it until
26:12 : i less than end
26:16 : and then we'll push the i into this
26:19 : result
26:20 : and return the result so that's our
26:22 : range function
26:24 : let's have an each function it takes an
26:27 : array
26:28 : in a function
26:31 : and we'll just use javascript for each
26:38 : so oh that
26:41 : is looking good uh let's format the
26:44 : strings
26:45 : maybe i'll use concat a couple of times
26:51 : this is looking pretty good to me
26:55 : i'm gonna do some inspections of the
26:57 : value
26:58 : to verify if it's right
27:10 : we didn't include 100
27:13 : okay let's include 100 by bumping this
27:16 : to 101.
27:19 : okay 100 is c indeed
27:22 : while we're at it why don't we go up to
27:28 : ten thousand
27:31 : oof ouch we have undefined
27:36 : we have a five thousand defined but we
27:38 : don't have a ten thousand defined
27:40 : let's define ten thousand then for the
27:43 : one now we can define the yeah i don't
27:46 : think that symbol is
27:48 : recognized by the browser i'll stop
27:50 : there
27:55 : that looks weird and beautiful
27:58 : okay so i'm happy i'm happy with the
28:01 : result of this coding challenge
28:03 : i would say this is a programming
28:06 : language now uh if you can solve
28:08 : something non-trivial
28:10 : like converting a number into roman
28:12 : numeral then
28:14 : i would say this is good enough to be
28:17 : a legit programming language
28:20 : is it a good programming language well
28:23 : no however that's why you are
28:27 : doing this you made your own programming
28:29 : language
28:30 : so that you can make changes to it
28:33 : yourself
28:33 : so you have the power to improve this
28:37 : programming language
28:38 : this is going to conclude this series
28:41 : however
28:42 : the long journey is not done i plan to
28:47 : put out more content on this channel
28:50 : as well as in the how to make a
28:52 : programming language series
28:54 : there's a lot of issues that if you want
28:57 : to make a
28:58 : robust programming language that you
29:01 : expect to be able to
29:02 : use comfortably that you need to solve
29:05 : and i
29:06 : plan to cover those topics