Refactr2019 - How to Make a Programming Language

Transcript

The following transcript was automatically generated by an algorithm.

00:01 : [Music]
00:06 : thank you all welcome for coming here
00:10 : for for this talk which will be about
00:14 : how to make a programming language the
00:17 : aim of this talk for you is to come away
00:22 : getting a higher high-level
00:24 : understanding of what it means to make a
00:27 : programming language what kind of work
00:28 : is involved what are you doing when
00:31 : you're trying to invent a new
00:34 : programming language if if you is not
00:41 : meant to be like I will teach you how to
00:44 : do it yourself in 45 minutes however I
00:48 : will give you some pointers to get into
00:53 : afterwards if you like to do that okay
00:57 : so when it is this my cool working by
01:01 : the way oh it's not for the room okay so
01:04 : yeah alright so when when you're a
01:09 : developer and you're setting out to make
01:11 : a new programming language or or
01:13 : existing one make mimic an existing
01:16 : programming language work perhaps in
01:19 : another context than the one that's
01:22 : currently being used or something what
01:25 : you're still doing at the end of the day
01:27 : is you're writing a program and a
01:30 : program is got inputs and outputs so
01:32 : what is the input and output of this
01:34 : program the input is some code and the
01:38 : output is some more code the code on the
01:44 : input side is the user code is the code
01:47 : that you're expecting the developers of
01:51 : your programming language to write so
01:53 : the user code will be in the format of
01:56 : your programming language of your choice
02:00 : or the programming language of your
02:02 : invention or your dream programming
02:05 : language perhaps the code that gets spit
02:09 : out on the other side that is machine
02:11 : code
02:13 : what is machine code well machine code
02:16 : is actually code that gets executed
02:20 : directly on your CPU and and your CPU
02:27 : looks like this usually it says Intel on
02:35 : it but not always there's other brands
02:40 : of CPU - however the code that an Intel
02:44 : chip understands will look very
02:46 : differently from the code that a myth
02:48 : strip or I don't know a PowerPC trip so
02:55 : this brand of CPU will understand a
02:58 : different set of instructions if you're
03:01 : using this scheme then the program
03:03 : you're making is called the compiler so
03:08 : if you are able to if you can manage to
03:11 : take the code in your dream programming
03:14 : language and translate it into machine
03:18 : code that your CPU can directly
03:20 : understand then you can make a
03:21 : programming language work this is what
03:25 : user code looks like this is code in the
03:28 : C programming language this implements
03:31 : some Fibonacci sequence and if you ran
03:35 : that through the the C compiler a
03:40 : popular one would be CCC which stands
03:44 : for the good new C compiler so if you
03:47 : ran this code through the GNU C compiler
03:49 : you'd get some machine code which is
03:52 : gonna be in binary however after the
03:56 : sort of there there's a there's a form
03:59 : of of code called assembly language that
04:02 : more or less gets directly translated to
04:05 : that binary form and that looks like
04:07 : this so this is something like what
04:09 : machine code would look like and this in
04:11 : particular is the machine code for the
04:14 : Intel chip now that actually did
04:18 : compiler thing that the diagram that I
04:21 : drew there's only one type of
04:23 : programming language
04:24 : tech chure and there are others there's
04:28 : interpreted programming languages
04:30 : transpiling programming language and
04:32 : type bytecode compiled program languages
04:34 : I'll go through the other ones briefly
04:36 : also during the demo we're going to be
04:41 : making a program language that uses the
04:44 : transpiled programming language or the
04:46 : texture just so you know you might have
04:48 : heard of those terms so what's an
04:51 : interpreted programming language oh I
04:54 : skipped through some languages some some
04:58 : examples of languages that use this
05:00 : compiled architecture or C C++ and more
05:05 : recently go Rus haskell interpreted
05:09 : languages examples of these are Ruby
05:12 : Python JavaScript with an asterisk I'll
05:15 : explain the asterisk later PHP so in
05:19 : this architecture the program that
05:23 : you're making will still taking the code
05:25 : in the language of choice but this
05:29 : program is going to execute that code
05:31 : line by line directly such that the
05:34 : output of this program will be the
05:36 : results of the intended program we're to
05:41 : contrast this with the previous
05:42 : architecture you can look at this code
05:48 : this code is actually another program
05:50 : this code that got generated in machine
05:53 : code form this code is actually another
05:55 : program so a compiler is actually a
05:57 : program that generates another program
05:59 : isn't that awesome so this program is
06:02 : going to get some input and it's going
06:05 : to spit out some results right so when
06:11 : you're doing an interpreted architecture
06:13 : you're essentially skipping this middle
06:16 : step and going to the results directly
06:20 : yep
06:21 : like that another type of programming
06:23 : language architecture is transpiled
06:25 : programming languages this is where you
06:28 : take the code in your programming
06:31 : language of choice and then you
06:33 : translate it into code in another
06:36 : program language but not yet
06:38 : the machine programming language that
06:40 : your trip directly understand so and
06:44 : popular and this programming language is
06:47 : called the target language and popular
06:51 : choices for target languages rjs
06:55 : JavaScript and C because those are very
06:59 : popular programming languages and
07:01 : there's already great tools for taking
07:04 : code in that target language and do the
07:07 : next step to it because once you get to
07:09 : J S or C you still have another thing
07:12 : that has to make it work with a machine
07:14 : code right so but luckily for you you
07:18 : don't have to write that next step
07:19 : because that's already there and it's a
07:21 : there's really great JavaScript engines
07:25 : out there available with all the
07:27 : browsers and they're all free so you
07:28 : don't have to do that work and with C
07:31 : compilers there's also very widely
07:33 : available and great C compilers out
07:35 : there so what you do is you just make a
07:38 : translator from your language to one of
07:41 : these two or maybe another language
07:44 : that's also great for that and then this
07:46 : code gets fed into another program but
07:52 : you don't you didn't have to write this
07:53 : one isn't that awesome so we're going to
07:58 : be doing this one in the demo because I
08:01 : assume most people probably know
08:04 : JavaScript so I don't have to explain
08:09 : how machine code works in order for you
08:13 : to follow along this is a lass
08:17 : programming language architecture and
08:20 : this is this what Java and c-sharp and
08:24 : JavaScript uses JavaScript with Astra's
08:27 : JavaScript used to be in the interpreted
08:29 : programming language camp until the
08:32 : invention of the v8 JavaScript engine by
08:36 : Google and which coincided with when
08:40 : chrome the browser came out and that
08:43 : came out with great fanfare and that
08:46 : made JavaScript run much much faster and
08:49 : that's the promise one of the big
08:51 : of this bytecode interpreter
08:53 : architecture as it can make your code
08:56 : run much faster and in another way it's
09:00 : it's a hybrid between being an
09:02 : interpreted language and a compiled
09:04 : language because both of those things
09:05 : are happening so what you do it you
09:09 : actually to make this work you have to
09:11 : make two programs one to translate the
09:15 : code into an intermediary form call it
09:18 : the bytecode the bytecode is going to
09:21 : look something like machine code it's
09:23 : gonna be very low-level however it's not
09:26 : really machine code it's like some
09:29 : machine code looking language that
09:32 : somebody invented and that but but it's
09:37 : easily translated to machine code and
09:39 : also its CPU independent the bytecode so
09:44 : so doesn't matter if it's an Intel trip
09:46 : or a myth strip same bytecode and if
09:50 : you've heard of the term web assembly
09:56 : that is bytecode web web assembly is a
10:02 : type of byte code that's been is being
10:07 : standardized by multiple large browser
10:10 : vendors and they're basically saying I
10:13 : will make program number two for you
10:16 : programming root two will take the
10:18 : bytecode and execute it and get you the
10:21 : results you interpret the bytecode
10:23 : execute it and get you the results and
10:26 : their so they're saying hey you know
10:27 : what if you are making a program
10:29 : language if you can spit out web
10:31 : assembly you don't have to write program
10:33 : number two and that's pretty cool too
10:36 : okay
10:37 : oh and if you're wondering you've heard
10:39 : about the word jet jet stand for
10:44 : just-in-time compilation and it's I
10:47 : won't get into deep detail about it but
10:49 : essentially the internals of programming
10:51 : program number two here has to take this
10:55 : bytecode and translate it to machine
10:57 : code at some point so it's going to take
11:00 : this bytecode and then spit out this
11:05 : in red the machine code and all of that
11:12 : is happening inside this box called
11:14 : program to sew in it really is like it
11:18 : this is like a crazy Frankenstein
11:20 : monster we're not gonna do this one due
11:23 : to time constraints okay so now that you
11:28 : got that high level picture if you have
11:30 : any questions you can go ahead and shout
11:32 : it out I'll feel them as I get them I'm
11:38 : going to get into this box drill down
11:40 : into this box the program so whether
11:43 : this program is a compiler or an
11:45 : interpreter it will have these parts
11:48 : within it the first part is a parser a
11:52 : parser is a thing that's gonna
11:55 : understand your code that the code of
11:58 : your of the language of your choice it's
12:01 : going to convert your code into
12:02 : something called the ast abstract syntax
12:05 : tree which is a true representation of
12:09 : what that code is I'll give you an
12:12 : example in just a moment and then once
12:14 : that you got an AST you're going to send
12:17 : that to another thing and the the thing
12:19 : in the smaller the inner yellow box that
12:22 : is either an interpreter or a compiler
12:26 : that will generate machine code or the
12:29 : other the target code on the other end
12:31 : so regardless of what architecture
12:34 : you're using you're gonna have to write
12:36 : a parser and that's what we're doing
12:37 : next okay what does a parser do and what
12:43 : is an AST this is this is the ast on the
12:46 : right hand side this is AST of a
12:48 : JavaScript program the JavaScript
12:50 : program is a one-liner but the ast looks
12:54 : kind of complicated here but in reality
12:57 : it's pretty straightforward
12:59 : so what is this JavaScript program it is
13:03 : well it's a program so on the top it
13:06 : says this is a program a program has a
13:08 : body a program body is a bunch of
13:11 : statements so that's represented as an
13:13 : array of statements the statements are
13:16 : represented as an object actually
13:21 : I would actually like to do it do this
13:24 : guy life for you so this is from esprima
13:29 : org as prima is a JavaScript parser
13:31 : that's really available and they have
13:34 : this like playground thing here so if
13:36 : you type in code on the left hand side
13:38 : you get the ast on the left hand side so
13:42 : so this is saying oh this is a
13:45 : JavaScript program and it's it's body
13:47 : has it's got one statement just just one
13:49 : and that's represented by this object
13:53 : here and what is what type of statement
13:57 : is it it's a variable declaration well
14:00 : as you know variable declaration can
14:02 : have multiple declaration within it if
14:04 : you come at the limit them in JavaScript
14:08 : so it's like how many declarations are
14:10 : in there well this one and a kind is var
14:14 : by the way because there's different
14:15 : kinds of variables like let and now it's
14:20 : kind of let and that's cool there's also
14:22 : Const as the hipsters know and so okay
14:29 : so we got one declaration in here
14:31 : what is the declaration look like it's a
14:33 : variable declaration aim of the variable
14:40 : is answered that makes sense in it means
14:42 : the initial value of the variable what's
14:44 : the initial value the well it's the
14:46 : result of a binary expression the result
14:49 : of this guy here six times seven that's
14:51 : a binary expression and it's got a
14:54 : left-hand side and the right-hand side
14:55 : left-hand side is 6 right hand side
14:57 : seven and an operator is the
14:58 : multiplication sign so that's an ast
15:02 : question how does it know that it's a
15:18 : number or it's yeah it's based on the
15:23 : parser as it's parsing you'll get to see
15:26 : the parser in just a minute it sees that
15:28 : that six is a number literal read it
15:31 : rather than a string literal
15:35 : okay then it just won't have an initial
15:39 : value I think oh well you can't do that
15:42 : with comps you can yeah it in it is no
15:46 : no yeah
15:47 : all right let's keep going
15:50 : cuz we don't have a lot I have a whole
15:54 : programming language to make here
16:00 : alright so this is another visualization
16:03 : six it's a number literal there's an
16:06 : operator seven is also a number Lugo the
16:09 : parser is gonna combine them and say oh
16:10 : that's a binary expression and then vara
16:13 : and answer and equal sign those have
16:15 : their own names and then all together
16:17 : you combine a var keyword identifier an
16:20 : assignment operator and some expression
16:24 : in this case a binary expression that's
16:25 : a variable declaration that that's how
16:28 : it works and this is the job that the
16:30 : parser has to take the code in just a
16:33 : string format and generate this ast tree
16:36 : for you so how are you going to do that
16:38 : we're gonna be making a programming
16:40 : language actually work with my friend y
16:43 : kit on this I asked why kit hey I am
16:45 : giving a presentation I have to make a
16:47 : programming language at 45 minutes she
16:50 : said what really I said yeah
16:53 : so well it can't have that many features
16:55 : in it I said give me just enough to
16:57 : implement the Fibonacci sequence so this
17:01 : programming language is going to happen
17:02 : it can add subtract multiply and divide
17:04 : it has variables it's gonna have a while
17:07 : loop and can print stuff that's it
17:10 : and a transpiler to JavaScript this is
17:14 : what the programming language looks like
17:18 : that has all the feature this code
17:20 : snippet has all the features of the
17:21 : programming language alright let's get
17:25 : into it let's code so I asked Wieck it
17:30 : to write the code for me I'm just gonna
17:32 : replay what he did and explain it let's
17:37 : let's do this okay so first thing he did
17:40 : an NPM and net so now we got a package
17:43 : JSON file
17:46 : he's gonna install this module from NPM
17:50 : caught nearly nearly is an amazing tool
17:54 : is one of my favorite tools for
17:56 : generating parsers what you do is you
17:59 : write a grammar for the programming
18:01 : language you want and it'll generate a
18:04 : JavaScript parser for you
18:07 : I'll show you how that works there we go
18:11 : so that is a grammar rules we're gonna
18:15 : what we're making what we're writing in
18:17 : right now is called a context-free
18:20 : grammar so context-free grammar and a
18:26 : context-free grammar consists of a
18:30 : number of production rules and what you
18:34 : see here that is a production rule and a
18:38 : production rule has a left-hand side and
18:41 : our right-hand side and there's a little
18:43 : arrow the left-hand side is one symbol
18:49 : the right-hand side can be one or more
18:51 : symbols and what this is saying is a
18:56 : number what is the number the number by
19:00 : the way you can name it anything
19:01 : anything you want that the abstract
19:03 : symbols in the production you get to
19:06 : name them just like you get to name
19:07 : variables so I could call that number I
19:09 : could call that integer or a good coded
19:10 : digits whatever so I'm saying in my
19:13 : programming language a number is
19:15 : represented as one or more occurrences
19:19 : of digit between or the characters
19:22 : between 0 and 9 so and this Plus that
19:26 : which means one or more that that that
19:30 : is regular expression like however this
19:33 : actually doesn't have full feature of
19:35 : regular expressions so alright so we so
19:39 : far with this one production rule we
19:43 : have allowed the programming language to
19:45 : be able to parse numbers just just
19:48 : integers even not eight not even decimal
19:50 : numbers so what you're going to do is
19:52 : ask nearly that if you can see on the
19:55 : bottom of the screen
19:56 : ask the nearly to compile this grammar
19:58 : into a JavaScript file and get rid of
20:02 : that box into the JavaScript file you
20:04 : say please compile my grammar and
20:06 : generate a my PL dot J's file you do
20:10 : that and it happens and my P o J's file
20:13 : is here now that's what it looks like
20:15 : that's just a JavaScript representation
20:17 : of your grammar in reality so now oh and
20:25 : here like it put that in a npm script
20:29 : just to be able to call that come in a
20:31 : little more conveniently now now that
20:37 : you have this my p o dot java script you
20:39 : have to set up a node rias script to
20:43 : actually parse so what you do is import
20:46 : the thing important yearly and import
20:48 : the my PID is that you just generate it
20:51 : by running that come in and then you
20:53 : instantiate a nearly parser and you feed
20:56 : a string to the parser like that and
20:58 : then after you feed something to the
21:01 : parser parser will have results in it
21:05 : and will print it out to see what it
21:07 : looks like and because one two three is
21:09 : a integer it that should work so I
21:13 : called note that part note parsed duck
21:16 : yes and it's able to parse it and it's
21:18 : returning this array in an array and an
21:21 : array that's the abstract syntax tree
21:24 : but it's not in a very intuitive form
21:27 : right now I'm gonna hand wave over will
21:31 : fix it up a little bit later but I want
21:33 : to write a few more production rules
21:35 : first before I do that okay so now now
21:40 : if I put ABC in the string then the
21:43 : parser is gonna fail right so I'll do a
21:46 : little try catch to make the error
21:48 : message you look a little nicer so it's
21:50 : a saying unexpected a my my programming
21:54 : language doesn't understand a it only
21:57 : understand two digits from 0 to 9 ok so
22:03 : numbers were alphabet letters do not and
22:07 : he's just making the
22:09 : the message a little nicer at this point
22:12 : okay now what if we want to support
22:15 : decimal numbers that's important at the
22:18 : moment the language doesn't support it
22:20 : unexpected dots it doesn't understand
22:24 : the dot so what do you do let's call
22:27 : that digits well we had what we had
22:29 : before we're going to call that digit
22:31 : and a number is some digits and then a
22:32 : dot and then some more digits we'll
22:36 : recompile ijen regenerate the parser
22:39 : parse it and it succeeds let's keep
22:42 : going let's make a variable assignment
22:45 : now in this programming language weikath
22:49 : decided to use colon equals for the
22:51 : assignment operator
22:53 : maybe he I don't know is that from small
22:56 : talk maybe he stole that from small talk
22:58 : he's a connoisseur of programming
23:01 : languages huh it's Pascal yeah yeah yeah
23:06 : Pascal so so we're gonna say a variable
23:11 : assignment is an identifier and then a
23:13 : colon equals and then a number a for the
23:16 : moment we can only do numbers for the
23:19 : initial value it's gotta start somewhere
23:21 : so and what's an identifier an
23:23 : identifier is a string of letters didn't
23:28 : pretend a to Z let's keep it simple I
23:30 : know I know JavaScript you can do more
23:32 : but let's keep it simple here we got 45
23:34 : minutes so we tried to parse this
23:38 : variable but he made a typo there needs
23:41 : to be a colon he just forgot this is
23:44 : like I have this great idea oh I forgot
23:46 : about it so so so I it's able to parse
23:50 : variable assignments now so if it and
23:53 : again we'll ignore the fact that the ast
23:56 : looks really gnarly but just see that it
23:59 : says parse exceeded that means the
24:01 : language understands that string as
24:03 : something in the language so it's able
24:07 : to handle a variable variable assignment
24:11 : but at the moment it's not able to
24:13 : handle integers anymore he's gonna fix
24:18 : that but I'm actually just gonna skip
24:20 : that part
24:23 : dude Oh actually I'm gonna do this part
24:26 : first okay so now he's actually doing
24:30 : this new syntax you've seen the arrow
24:33 : sign syntax
24:34 : now there's the or bar syntax that means
24:38 : hey the symbol on the left side can be
24:40 : this thing or it can be this thing so
24:43 : using the the tab level input of what a
24:46 : program is a program can be a variable
24:48 : assignment or it can just be a number
24:50 : and now so previously you can't just put
24:54 : a number as the top-level thing in the
24:55 : string and now you can so you have to
24:58 : regenerate the parser again but now
25:01 : there's this she messed up the number so
25:04 : it can't support integers and now he
25:07 : fixed that so I'm gonna skip over that
25:09 : quickly all right now we're gonna fix up
25:11 : the ast the ast can't just look like
25:14 : crap like an array inside of an array
25:17 : why does it look like that currently
25:19 : well because currently the the way each
25:24 : symbol is represented is by an array
25:26 : containing each of the matched symbols
25:30 : on the right hand side so so you can
25:34 : actually interrupt with JavaScript here
25:36 : so you got data and then data is going
25:40 : to be array that contains an array of
25:43 : the matches of the symbols on the right
25:45 : hand side so data at 0 is gonna be the
25:48 : digits but the digits will have the
25:50 : individual digits in an array so I'm
25:52 : gonna join here to join them together
25:55 : and now you get a 12 there but we would
26:01 : still like to get rid of those nested
26:04 : arrays so what you do is say well if
26:07 : there's only one symbol on the right
26:09 : hand side just take the first one does
26:11 : this on an SD array and that will clean
26:16 : it up a little bit but because this
26:18 : pattern is pretty commonly used with the
26:21 : nearly parser generator they gave you a
26:24 : built-in function called ID to do that
26:26 : one so every rule where the right hand
26:30 : side is only one symbol will put ID on
26:32 : it
26:35 : and but for the rules that so now we
26:38 : just get one outer array the outer array
26:40 : is actually the array from the results
26:43 : so now let's see
26:48 : now let's fix up the decimal the the
26:51 : decimal numbers because the decimal
26:54 : numbers is on line number ten here and
26:58 : that guy has three parts in the array so
27:02 : we're gonna pick out the parts build a
27:06 : little number and then use the number
27:08 : constructor to parse that number to
27:10 : convert that string into a number so
27:12 : we'll have nice numbers in the ast and
27:15 : we'll do the same with the integer
27:16 : number for line 13 to 15 here and and
27:24 : now the ast is just a normal JavaScript
27:27 : number so you can have a lot of ability
27:30 : to customize what your AST looks like
27:33 : okay actually gonna skip some parts do
27:40 : the time all right I'm gonna skip to
27:46 : binary expressions so at this point at
27:50 : this point a program skipped ahead
27:52 : sometimes he also made a print statement
27:54 : work a print statement word print some
27:58 : mandatory whitespace and an expression
28:01 : and now we're gonna do binary
28:04 : expressions so you can add subtract
28:06 : multiply and divide so what's a binary
28:08 : expression well let's see first actually
28:15 : he wanted to distinguish between under
28:17 : II expressions and binary expressions so
28:20 : we're going to say an under II
28:22 : expression is just a number or an
28:24 : identifier which would be a variable
28:26 : reference
28:28 : what's a binary expression well a binary
28:30 : expression is an under II expression and
28:33 : then an operator the the underscore is a
28:36 : optional whitespace that's like I read a
28:40 : blog article by the author of nearly it
28:43 : was called how to grammar a good and he
28:46 : he recommended using a
28:49 : go underscore to represent optional
28:51 : whitespace and a double underscore to
28:53 : represent mandatory whitespace so so a
28:57 : binary expression is under expression
28:59 : some optional whitespace and operator
29:02 : optional whitespace and then another
29:03 : under operation under expression what
29:07 : our operators well we can add subtract
29:09 : multiply and divide we're gonna use the
29:11 : Unicode symbols so that because that's
29:13 : way cooler
29:14 : I know it's lab IDs on these because
29:18 : there's only one symbol on the right
29:20 : hand side and then we're going to
29:22 : represent a binary expression as a
29:24 : JavaScript object I'm gonna I'm gonna
29:26 : follow the lead of the JavaScript
29:28 : parsers usually JavaScript parsers have
29:30 : a type field that tells you what kind of
29:32 : thing this part of the ast is so I'm
29:36 : going to say this is thing is type
29:39 : binary expression it's got a left-hand
29:41 : side and a right-hand side and an
29:42 : operator and the way you get the value
29:45 : for those three things is by picking
29:47 : into the data array which represents
29:51 : each of the matched symbols over here on
29:55 : the right hand side so data at 0 that's
29:58 : the first under expression data at -
30:00 : that's the operator and data at 4 that's
30:03 : the last in the operation so we
30:06 : regenerate the parser let's try that
30:11 : didn't work but that's because he forgot
30:14 : - oh that's because he forgot to make a
30:18 : variable assignment I'm gonna go back he
30:23 : forgot to make a variable assignment be
30:24 : able to take an expression on the right
30:27 : hand side he still had it as number so
30:29 : it just flipped the number to expression
30:31 : and now it should be able to handle that
30:33 : and it does now the ast looks like that
30:37 : and it almost looks like what you see
30:39 : with esprima now so basically this is
30:42 : saying this line of code in my pl it's
30:49 : abstract syntax tree looks like that
30:52 : it's a as a variable assignment whose
30:56 : variable name is a and the value of the
30:58 : variable assignment is a binary
31:00 : expression the left hand
31:02 : one Operator plus and right-hand side -
31:06 : okay I'm actually gonna skip a little
31:10 : more how are you doing on time okay
31:13 : we're going to one all right I'm gonna
31:15 : skip to here okay all right at this
31:22 : point he wrote a little script here such
31:26 : that when you when you run the note par
31:31 : CAS it'll actually generate an ast file
31:34 : so the ast file will contain the ast in
31:41 : JSON format
31:43 : so now the next thing he's gonna do is
31:46 : allow multiple lines of code in the
31:49 : program whereas previously we were only
31:51 : parsing single lines of code that's not
31:53 : not very useful programs with only a
31:56 : single line so now you're going to say a
31:58 : program can be either a statement or it
32:06 : can be a statement a new line and then
32:08 : more statements and now we're making use
32:11 : of recursion so this recursion Oh
32:14 : actually statements rename program to
32:18 : statements that's recursion right now
32:21 : we're at recursion so statements caused
32:23 : itself
32:24 : Simmons is like I can be one statement
32:26 : and then there's more of me and then I
32:28 : can have even more statements inside me
32:31 : and then at the top level a program
32:34 : consists of a set of statements and that
32:38 : will generate the ast parts for that but
32:41 : what we the way we want to represent
32:43 : statement is with an array it's an array
32:46 : of statements right so this little arrow
32:48 : function in here it wants to return an
32:51 : array so if it's a single statement
32:53 : we're going to take the match the
32:56 : statement and then wrap it in there a
32:58 : but if it there's more statement we're
33:01 : going to take the match that came from
33:04 : this statements spread it that if you
33:08 : are familiar with this brett operator
33:10 : the hip kit here so it's busy
33:15 : copies everything in data at 2-2 this
33:19 : array literal that's being generated
33:22 : here a plus the array at zero at the fun
33:26 : of the array um and we'll add some
33:29 : optional white space here but that
33:32 : probably broke it because the optional
33:34 : ways please okay so now let's see if
33:38 : this works
33:39 : all right so it generated the ast file
33:43 : that broke he's gonna fix it and now it
33:50 : works now now a program that the ast for
33:52 : this program is an array of statements
33:54 : each statement is represented as an
33:56 : object so the first line right the first
34:02 : line is a assignment the second line is
34:04 : also an assignment then they're
34:05 : represented here and here the second one
34:09 : is more complex because the initial
34:10 : value is a binary expression all right
34:14 : let's actually want to skip to so we've
34:22 : been doing a lot of work with the parser
34:24 : I'm gonna skip to the next step
34:28 : okay at this point he has implemented
34:35 : the ast for while loops also so the
34:40 : parser is working for all of the
34:43 : programming language now but now we have
34:46 : to translate it to JavaScript so that
34:48 : something can actually execute the code
34:54 : so it's gonna make this little file to
34:58 : do that it's gonna basically read in we
35:05 : will have this par script at this point
35:07 : which takes a file in dot my PL format
35:12 : and generates a file in dot ASP format
35:17 : now we're gonna make a generate that yes
35:20 : script that takes a file in dot AST
35:23 : format and generate a file in j/s format
35:28 : so that that's this guy here so this guy
35:31 : reach in a file in that ast format
35:34 : because it's a JSON in JSON format we
35:37 : just use JSON dot parse to get you back
35:40 : into the JavaScript object realm and
35:43 : then once you have the AST which I know
35:46 : it's an array of statements right in the
35:49 : AST form we're gonna make a generate
35:51 : JavaScript function given that ast for
35:56 : now we'll do a little boy santos leite
35:57 : code that just generates hello world and
35:59 : then we'll output that into a file oh
36:04 : yeah
36:06 : so now if we did note note generate note
36:14 : generate yes example one ast an example
36:19 : one ast looks like this it was the ast
36:22 : for example one my PL here no actually
36:26 : it's not in any case it just generates
36:31 : this whole world at the moment so not
36:33 : very useful so gonna reparse let's see
36:39 : what's the result of the reparse okay
36:42 : now it's actually true to what it says
36:44 : but it still just generates a hello
36:46 : world so not not good enough yet we
36:48 : actually have to deal with ast in some
36:51 : form so I know the ast at the top level
36:55 : is an array of statement we're going to
36:56 : loop through it and I say if this
36:59 : statement if one of those statements is
37:02 : an variable assignment we're going to
37:05 : output that line of JavaScript right I
37:08 : know of our assignment object in the ast
37:11 : has a VAR name I know it has a value so
37:15 : just stick that in a format it as
37:18 : JavaScript and I know that if that
37:22 : JavaScript is correct then it can work
37:26 : so know generate example 1 ast to
37:30 : generate example 1 dot J yes and now
37:34 : example 1 dot yes looks like that that
37:36 : looks like JavaScript you can even run
37:39 : it if you want to
37:44 : he he did another thing he made a few
37:51 : more variable assignments just for fun
37:53 : and generated the ast and ast now looks
37:57 : like this and then let's generate a
38:00 : JavaScript file for that as well and
38:02 : that's the JavaScript file in the output
38:05 : so you can run this JavaScript let's do
38:09 : that run the job no output that's
38:12 : expected
38:13 : we didn't print anything out so now
38:15 : let's do it let's do binary expressions
38:19 : now binary exceed out was how do you
38:22 : generate JavaScript with binary
38:24 : expressions if we try to do that now you
38:30 : get that and that's not valid JavaScript
38:34 : unfortunately so you have to write some
38:36 : code to make that happen so we're out
38:40 : for expressions like we got statements
38:43 : and we got expressions expressions youth
38:45 : values right we're gonna make a separate
38:47 : function to generate the corresponding
38:49 : JavaScript expression given the my Pio
38:53 : expression so that looks like this is
38:57 : the expression if the expression is an
39:00 : object we're going to look at its type
39:03 : to see what kind of thing it is but if
39:05 : it's not an object I know it's either
39:07 : identifier or a number just return it
39:08 : right away so if it's a binary
39:10 : expression only recourse recursively
39:14 : call ourselves to get to generate the
39:17 : Jas for my left-hand side and right-hand
39:18 : side because left hands are aware hence
39:20 : I could be more complex expressions in
39:23 : of themselves so I'll do that that's
39:25 : this is where recursion and geeking out
39:29 : on CS really pays off here okay so now
39:35 : we're just going to put them together
39:37 : left-hand side the operator and then
39:40 : right-hand side and that should be valid
39:42 : JavaScript right no JavaScript doesn't
39:47 : support the multiplication symbol we're
39:49 : going to need a operator map and then
39:53 : we're going to look up the operator map
39:55 : to make that translation regenerate the
39:59 : JavaScript there this that looks like
40:03 : JavaScript that can actually work
40:05 : we need print statements now because you
40:08 : have to see your results otherwise it's
40:11 : not a very useful programming language
40:13 : so let's see what happened oh we've got
40:19 : the ast the ast no not this ast this ást
40:23 : ást has got print statements represented
40:27 : we generate the let's let's make that
40:31 : work
40:31 : let's before testing let's just make
40:33 : print statements work we're gonna the
40:35 : print statement is going to have an
40:37 : expression to be printed we're going to
40:39 : call out to generate js4 expression to
40:41 : render it in Jas format and then we'll
40:44 : console that lock easy easy that we know
40:47 : how to print generate the ast for this
40:52 : file and then take the ast o generate
40:55 : the Jas file from the ast file and then
40:58 : now you can run the run the program and
41:00 : actually give you output and this is the
41:03 : this is the resulting JavaScript file
41:06 : from that my ppl program what else let's
41:12 : see okay let's keep going let's make
41:18 : wild loops work Wow it's got a condition
41:22 : let's render that condition in
41:25 : JavaScript and it's got a body which is
41:28 : some more statements so we're gonna
41:31 : generate because generator is is this
41:34 : top level function that we're writing
41:35 : it's already expecting an array of
41:37 : statements to just just plug right in
41:39 : it's perfect for what we need here we
41:42 : have an array of statements that's the
41:44 : body feed it into generator yes we got
41:47 : the body and I'll put that into the wild
41:50 : loop he wants to do some indentation of
41:55 : the body
41:58 : and split the string up put some
42:01 : indentation and join it back okay that's
42:03 : cool no that's this one we got to wow
42:09 : them in JavaScript now but however as
42:11 : you can see there's a probably we
42:13 : redefine this variable that's not good
42:16 : how are we gonna stop that as you
42:19 : remember which variables are declared
42:21 : and we have to pass them down for the
42:24 : other call and so initially we don't
42:28 : have any variables but when you have a
42:31 : variable assignment statement you can
42:34 : check hey if that variable is already is
42:38 : not defined we're going to use the let
42:40 : statement to define it but if not or but
42:44 : it is already defined we're not gonna
42:46 : use the let statement it's a simple
42:48 : assignment so if you do that boom that
42:53 : works that looks like it works as
42:56 : actually run it oh my god please okay so
43:01 : now alright last thing last thing last
43:03 : thing what program I mean programming
43:07 : language will be complete if you cannot
43:09 : write the Fibonacci sequence in it all
43:16 : right so I 210
43:19 : so we're gonna get the Fibonacci
43:20 : sequence the numbers from 1 to 10 the
43:24 : sequence of them from 1 to 10 if I means
43:28 : the current value that you're dealing
43:30 : with FII is the current value plus 1 and
43:33 : then you just like add them together and
43:35 : then swap add them together swap right
43:37 : that's a while loop first we're gonna
43:39 : turn out fi until we get the wild herb
43:43 : is the while loop is unto I gets to n
43:45 : we're gonna keep going and then this is
43:47 : the classic swap operation we're gonna
43:50 : add fi and FII together and then fi is
43:55 : going to become fi I and if I I is going
43:57 : to become the result of F I I plus root
44:01 : of f i+ fi I let's run it
44:05 : he had an error because he forgot to
44:08 : increment I and now we have an infinite
44:11 : loop
44:13 : fix that boom
44:16 : Fibonacci sequence let's go - lets go -
44:22 : 25 boomers and and our job is done here
44:28 : one last thing one last thing so I hope
44:34 : you enjoy that I hope you have a high
44:37 : level understanding of what it is like
44:39 : to make a programming language I'm
44:42 : actually planning to work with white get
44:45 : more and to create a video series on
44:48 : YouTube to go into this in much more
44:51 : detail and if you're interested in that
44:54 : you can go to this bitly link bit ly /
45:01 : drive-by code all one word and that's
45:08 : all I've got for you today thank you
45:13 : [Applause]
45:15 : [Music]

Refactr2019 - How to Make a Programming Language - Toby Ho

Transcript