cs262 »

CS262 Lesson 6: Building a Web Browser

Interpreting HTML and JavaScript

Contents

Web Browser Architecture

We describe the software architecture of our web browser. Our HTML lexer, parser and interpreter will drive the main process; our JavaScript lexer, parser and interpreter will serve as subroutines.

Welcome back.

This is Lesson 6 of Programming Languages.

And the story, thus far, is that we started with a big Web page that might contain embedded JavaScript.

And we did Lexing or Lexical Analysis to break it up into a list of tokens.

And once we had that list of tokens, we did Parsing to check those tokens against a formal grammar and produce a Parse Tree.

More recently, we've learned how to do Interpreting to walk up and down a parse tree-- with an environment--and figure out what the final result is supposed to be.

We often call that Meaning or Semantics.

In this Lesson, we're going to put that all together to build a unified Web browser, and it's going to require all the tricks that we've learned, up to this point--including things like how to debug or what can go wrong if you interpret a program with an infinite loop.

Web Browser Architecture 1.png

Let's talk about the Architecture for our Web browser.

Just as engineers or architects that build buildings in the Real World like to have blueprints or plans--or some notion of how that design is going to come together-- we try to do the same thing in software engineering.

We want to have a software architecture, a list of major components, and a design that incorporates all of them.

Web Browser Architecture 2.png

Our first step is to find our Web page and lex it and parse it until we have an Abstract Syntax Tree.

Most commonly, our HTML interpreter will walk over the Abstract Syntax Tree that we got from the parsing, and it may find elements in there that are embedded JavaScript.

So then we'll have to call the JavaScript interpreter on them.

In most cases, at some point the JavaScript code from the user will call "write" or "document.write", and that's that function that says: If I'm in JavaScript, display this on the resulting Web page.

Because the meaning of a JavaScript program that calls "write" is that that text should be displayed, we'll definitely want to store all of the text from "write" so that we remember to include it in the Web page later.

Eventually, the JavaScript fragments will be done executing and will be back to the HTML interpreter, which will have received all of those strings from "write", and it will take them-- plus all of the normal HTML elements-- and call the graphics library to make a pretty picture of them.

Eventually, at the end of the day-- we end up with an image of the Web page, and that's what we wanted from our simple Web browser.

Quiz: Web Browser Process

Let's make sure that we all have the same idea about how that architecture is going to go--with a quiz.

I'm going to write down candidate steps--or candidate parts-- of our algorithm's design, and you're going to tell me which parts are wrong or if there's a part that's shown in the wrong order.

So here I've written 5 possible steps, in a particular order, that our Web browser might follow and I want you to put a check mark--in this multiple multiple choice quiz-- next to each step that's either erroneous or out of order.

Web Browser Process.png

Solution

Fitting Them Together

We change our HTML lexer to recognize embedded JavaScript fragments as single tokens. We'll pass the contents of those tokens to our JavaScript lexer, parser and interpreter later.

So we just said, in our particular architecture, that the HTML interpreter is going to call the JavaScript interpreter--but not the other way around.

So they're kind of like two pieces to a puzzle that totally fit.

Recall that we treat JavaScript as a single HTML token. And the reason for this is that things like (5 < 7) or (a > b those can appear in JavaScript. But they would confuse us in HTML because we'd think the Less Than and Greater Than were part of tags.

For example, this is totally valid JavaScript.

<script type = "text/javascript">write(a<b);<script>

Assuming (a) and (b) are defined somewhere, this should either print out True or False. But if you look at it carefully, this (< b) is sort of indistinguishable from the (< b) that might come in legitimate HTML-- like: (<b> bold).

So that's why we took all of this text and we didn't interpret it in our HTML parser. Instead, we saved it for later.

Well--now's the time! Let me just remind you of how we defined our tokens related to JavaScript.

def t_javascript(token):
        r'\<script\ type=\"text\/javascript\">'
        token.lexer.code_start = token.lexer.lexpos
        token.lexer.level = 1
        token.lexer.begin('javascript')

Here I have our rule for beginning the tokenization of JavaScript. Remember, these backslashes are Escape sequences. You should read right over them. In some sense, the first character I want to match is this Less Than sign-- but just in case that has special meaning for regular expressions, I'm going to put a backslash before it to Escape it so that they know I mean exactly this backslash.

Just like over here, I mean exactly this space, exactly this double quote, exactly this forward slash, exactly this double quote, and exactly this Great Than sign.

So we're requiring JavaScript to start with: <script type="text/javascript&gt; and when it does, we move our lexer into a slightly different world. And we talked about this before; we just have multiple finite state machines and then-- whoop--we're down at the one at the bottom now.&lt;/p&gt; &lt;pre&gt;&lt;code class=" prettyprint"="">def t_javascript_end(t): r'</script>' t.value = t.lexer.lexdata[t.lexer.code_start:t.lexer.lexpos-9] t.type = "JAVASCRIPT" t.lexer.lineno += t.value.count('\n') t.lexer.begin('INITIAL') return t

And then down here, I have my rule for ending JavaScript lexing. We're looking for this, but just in case any of these 3 special symbols have special meaning to regular expressions, I have put the backslash and Escape sequence in front of all of them. This is probably not actually necessary, but it's what's known as "defensive programming". It can't hurt, might help.

I want the token.value to be all of the string data, all of the embedded JavaScript code.

I'm going to use a variable we haven't told you about yet. It's possible to get the entire input string from the lexer in: (token.lexer.lexdata). Don't worry too much; I'm just going to assert that this works.

This is the entire big string, and I'm going to get it, starting at the position we recorded earlier. Back up here--when we found the javascript(token) we wrote down the current lexer position and stored it in a little variable we made up called (code_start).

So let's say 50 characters into the file we started the javascript. We'll just store that 50 right here in (code_start). That's going to let us pull out, starting at Character 50, up to where we currently are. Let's say that there are 100 characters of JavaScript-- now we'd be at 150--and I'm subtracting out 9.

Why am I subtracting out 9? it's the size of this ending token. I don't want this </script> to be in it. So I've set the value correctly. I say the type of this token is 'JAVASCRIPT'.

For accurate debugging information, we want to keep track of which line we were on in case we want to report errors later.

Here's a trick: the JavaScript embedded code probably had new lines in it. I want to make sure that all of those count, so I'm going to count up the total number of new lines--or character returns or whatnot-- found in the embedded JavaScript code and increment my own line count by that amount.

And then we go back and move to the 'INITIAL' state of the lexer where we can get HTML tokens, like 'LANGLE', 'LANGLESLASH', 'RANGLE'.

So this is just gathering up the raw string for embedded JavaScript, and storing it as a single HTML token.

One last important thing to remind you of:

Note that we stripped off the final </script> from the end. And because of the way lexpos works, it measures the value after we match the token. We actually end up stripping off the <script type="text/javascript"> from the beginning as well.

Quiz: Token Value

So let's say that this is part of the Web page we receive.

It's our HTML input and we're going to run our Lexer over it.

Let's just make sure we understand how this embedded JavaScript is passed down the line, by having you tell me what token.value-- the string eventually associated with the token--will be?

I've listed 4 possible options, but only 1 of them can be right. Check the one that you think corresponds to token.value for this HTML input.

Token Value.png

Solution

Extending Our Html Grammar

We extend our HTML parser to handle our special token representing embedded JavaScript

So we just learned how to do that JavaScript token in lexical analysis.

Now we need to know how to handle that special JavaScript token.type when we're parsing.

Just to review a bit, this is how we did basic HTML parsing or our basic HTML grammar.

def p_element_word(p):
        'element : WORD'
        p[0] = ('word-element',p[1])

We say it's a parsing rule, with p_. This is the kind of thing we're trying to parse--an element-- and then we write down here, the rule from the grammar, and where we would normally write an arrow, they ask us to write a colon.

So element can be rewritten to word. And then p[0] is the final parse tree. And p[1] is the child parse tree. And we build the final parse tree out of the child parse tree, growing a bigger tree, over time.

Well--actually, our handling of JavaScript elements is very similar.

We just indicate that an HTML element can consist of a JavaScript token, and we build up our parse tree by noting that it's a JavaScript token and then including the text.

And you see this word here--JAVASCRIPT--in all capital letters. Back here, when we were lexing the JavaScript token, in t_javascript_end, we said: token.type is JAVASCRIPT, in all capital letters. Those intentionally match. This is the linkage we're making between the lexer and the parser.

In fact, they have to match; otherwise, it won't work.

So let me show you a concrete example.

Let's say my HTML input is:

hello my
<script type="text/javascript">document.write(99);</script>
luftballons

Let me show you what the Abstract Syntax Tree-- or what the parse tree--will look like for this.

And we'll recall that HTML is a list of elements, and here we have 4 elements:

  1. hello
  2. my
  3. <script> ... </script>
  4. luftballons

    [("word-element", "hello"), ("word-element", "my"), ("javascript-element", "document.write(99)"), ("word-element", "luftballons") ]

The first is the word_element, hello. The next is the word_element, my. The next is the javascript_element containing only the important text-- not all of this tag stuff. And the last is the word_element, luftballons.

This is the parse tree, a list of HTML elements.

It just so happens that none of these are nested, but they could have been if there were some tags in here.

And here: 99 luftballons is perhaps more commonly known as-- in English--as 99 Red Balloons. It was a protest song, in German, written around 1983.

Quiz: Calling The Interpreter

So let's work together to extend our HTML Interpreter to handle these new JavaScript elements-- just like we saw a few seconds ago.

Just like we saw in the last example, typically, the parse tree for HTML will be a list of elements. So we'll just run down and process each one, in turn.

# HTML Interpreter on JavaScript elements
def interpret(tress): # AST
        for tree in trees:
                treetype = tree[0]
                if nodetype == "word-element":
                        graphics.word(node[1])
                elif treetype == "javascript-element":
                        jstext = tree[1]; # "document.write(55);"
                        jslexer = lex.lex(module=jstokens)
                        jsparser = yacc.yacc(module=jsgrammar)
                        jstree = jsparser.parse(jstext,lexer=jslexer)
                        # jstree is a parse tree for JavaScript
                        result = jsinterp.interpret(_________)
                        graphics.word(_______)

How we process it depends on its type.

Is it a word, a tag, JavaScript? One of the easiest cases for us is if it's a word_element, we just call our graphics library and add that word to the final Web page.

We've already seen what to do with <tag>_ elements in a previous quiz, so let's just do JavaScript now.

We can get the text of the embedded JavaScript fragment out of the Abstract Syntax Tree. That's going to be something like: "document.write(55);"-- could be more complicated, calling Fibonacci functions-- doing arbitrary computation, in fact.

Here "js" stands for JavaScript, and this is the text of the program. This next bit is a bit arbitrary. I'm going to walk through all the steps, but you should not worry about having to guess these. These come out of nowhere or come from library integration.

Let's say that we've written down our JavaScript token definitions in some other file called: jstokens. I'm going to need to build a lexer to break this string down into tokens.

Similarly, let's say I've put all of my JavaScript grammar rules somewhere else. I'm not showing them right here, but they're saved somewhere else on the disc, in a file called: jsgrammar.

Once I break this text down into tokens, I'm going to need to check and see if it's valid JavaScript and build a parse tree. "lex" is the name of our library module for doing lexing. "yacc" is the name for our library module for doing parsing.

"yacc" does not sound like it should be doing parsing. It stands for: Yet Another Compiler-Compiler, a tool for making compilers or interpreters. In fact, just like the JavaScript interpreter that we're making now. For now, this name is just a historical accident.

Here's the real exciting part: I'm going to call our JavaScript parser and ask it to parse the text from the embedded JavaScript fragment, using the lexer--the token definitions--from jslexer.

So jstree now holds a parse tree for JavaScript.

And now the quiz for you is just to fill in these two blanks.

I have this parse tree for JavaScript, and now I want to do something. I want to call our JavaScript interpreter and ask it to interpret (something--you tell me) and then, eventually, I want to call the graphics library and draw some word in the Web page. Which word should it be? Let's fill in the blanks.

Yacc, or yet another compiler compiler, is the prototypical parser generator.

Solution

Evil Problem

A JavaScript program may contain zero, one or many calls to write(). We will use environments to capture the output of a JavaScript program.

So we just filled out that previous code integrating our HTML interpreter with our JavaScript interpreter, assuming that our JavaScript interpreter returns a string.

The basic idea is that if the embedded JavaScript code called document.write(x), we'd notice that x and save it and return it back to you.

Unfortunately, there is an evil problem. This is a little more complicated than it looks.

This is totally legitimate JavaScript code.

document.write("hello";
var x = 5;
document.write("world!");

Note that I have one call to document.write and then another call to document.write. Somehow I'm going to need to paste together "hello" and "world" and return both of them.

So the basic problem here is that there may not be just one call to write. There may be many more or actually there may be 0, but we want to get out of this "hello world!"

So we have to store text printed by write, but we may find that as we execute or interpret the JavaScript program, the amount of output grows.

Well, if we want to store values that may change-- boy, if only we already had some way to do that--oh wait! We totally do. We went to all that trouble to learn about how environments work in nested environments and variable updates.

Let's reuse that. That was really powerful!

Quiz: Javascript Output

So to make this work out, we'll just make a little contract with ourselves.

Let's assume that when we're interpreting JavaScript and we come across a call to write we'll just figure out what the argument is--that will be some string-- and we'll append it to a special "javascript output" variable that we'll store in the global environment.

Global because you could call write from anywhere.

Everyone has to be able to see it.

So here is our glorious JavaScript interpreter, or at least the parts of it that you haven't already written.

def interpret(trees):
        global_env = (None, {"javascript output" : ""})
        for elt in trees:
                eval_elt(elt,global_env)
        return (global_env[1])["javascript output"]

We're given the abstract syntax tree, which contains a list of JavaScript elements.

The first thing we do is make a global environment. Global environments have no parent pointers. This would be a parent pointer, but instead it's none. We're going to start it out with the variable "javascript output", mapping to the empty string.

Then for every element in the embedded JavaScript code, we evaluate that element--you've already seen how to do that--in the global environment.

This might make changes to it over time through calls to environment update.

At the end of the day, the string we return is, well, we have the global environment right here.

We get its 1th element, which is this mapping, and we get out the current value of "javascript output," which hopefully has changed.

So it's quiz time. You've seen our assumption, and we've written out the code for the JavaScript interpreter, at least at the top level.

Here I've written 3 sentences. We could rename "javascript output" to anything as long as we're consistent. "Javascript output" is a good choice because it has a space in it, and "javascript output" starts empty, mapping to the empty string to support 0 calls to write. Multiple, multiple choice--check each one of these that's true.

Javascript Output.png

Solution

Quiz: Updating Output

Well, our previous approach only works if we treat calls to "write" specially, and we're careful to notice every call to "write" and append to this "javascript output" variable in the global environment.

So let's work it out together. I'll do the first bit, and you'll finish it off.

We're going to go back to our JavaScript interpreter and finish up our handling of "write," a special function call.

Well, function calls are expressions, so we're in evaluating expression. Here's the abstract syntax tree or the parse tree for the expression. Here's the current environment. We need to figure out the type of the expression. We've already seen how to do binops, numbers, that sort of thing. So the one we really care about this time is function calls.

def eval_exp(tree,env):
        etype = tree[0]
        if etype == "call":
                fname = tree[1] # myfun in myfun(a,3+4)
                fargs = tree[2] # [a,3+4] in myfun(a,3+4)
                fvalue = env_lookup(fname,env)  # None for write
                if fname == "write":
                        argval = eval_exp(fargs[0],env)
                        output_sofar = env_lookup("javascript output",env)
                        env_update("javascript output",______ + str(______),env)
                        return None

So this is what we had before.

A function call has a name and some actual arguments. Looks a bit like this.

myfun in myfun(a,3+4)

If the function call is myfun(a, 3+4), the function name is myfun, and the arguments are a list of expressions.

[a,3+4]

We're going to go look up the function name in the environment.

Now "write" is one of those special functions that users get to call, but they never actually provide a definition for.

So we're not going to find it in the environment. Our environment lookup returns none if the function is "write," but it also returns none if the function is just unknown, so we'll check for "write" specially.

If so, "write" should have a single argument, so we'll evaluate it.

We'll get the current output that the user has written through previous calls to "write." I'm doing an environment lookup in the current environment instead of the global environment. Here's a trick though. Remember how environment lookups work. If I don't have it in my pockets, I check my hotel room. I check back home. I ask my parents. I look around on the web. I keep going back until eventually I hit the global environment.

Because we've specially picked a variable name with a space in it, noone else can possibly make this variable. So even if I'm not in the global environment, I won't have it. My hotel room won't have it. My house won't have it. Eventually, I'll get back to the global environment, which we know has it because we were careful to put it in explicitly starting as the empty string last time.

So the quiz for you is to fill in these 2 blanks. We figured out the output so far, and now we want to update the environment so that "javascript output" takes on a new value. What should go in here to make that work out?

Solution

Contrived Example

An example of a webpage with embedded computation is shown.

So we've just seen how to integrate JavaScript and HTML in our interpreter in our web browser.

Let me show you a more complicated example.

We'll see how it plays out in real life.

Contrived Example.png

We often use this tag to begin a webpage. It's not strictly necessary, but it's very good practice.

We're going to use this tag to begin a paragraph.

Just to remind us, it's possible to have comments in HTML. The lexer strips them out, so we're not going to see them at the interpreter level.

Here I've put in a list of word elements, This is a, and then here's a tag element, and inside it, nested are 3 more word elements and then the tag element ends.

This is an anchor tag, making a link to Google.

Let's say I want to write a webpage about John Searle's famous Chinese Room thought experiment, in which he argues against or at least puts forth positions that cause one to consider artificial intelligence. It's fun stuff. But I don't remember exactly when he made the experiment.

I will in a totally contrived example. Super contrived.

Use Javascript to compute this.

So let's say I can't remember exactly when he came out with the Chinese Room thought experiment, but I do know that the date was equal to 1,260 + 6 factorial. If only there were some way I could carryout this computation on my webpage. Whoa is me!

So I've written some Javascript to do just that. I compute 6 factorial + 1,260 and write it out and then we finish out with the rest of our webpage text.

So this whole bit here is an embedded JavaScript fragment.

Over here, we see the final result. This is a link to Google. John Searle's italicized Chinese Room thought experiment from 1980-- oh! that's when it was. How silly of me not to remember!-- argues against artificial intelligence.

And you may notice that since there's some space here at the end of the script, this comma doesn't line up exactly with the 1980. Let's not worry about that for now.

Quiz: Counting Frames

So now, there's a quiz.

Our JavaScript interpreter is going to have to compute the value of 6 factorial, a function call within a function call within a function call. It's turtles all the way down.

Counting Frames.png

How many different environment frames will be created by the interpreter for factorial 6 above?

Include the global frame in your answer. How many total environment frames will we be juggling at the same time? Fill in the blank.

Question 2--In how many of those frames will n have the same value? So if you could find 3 frames where n was 77, then the answer here would be 3.

Solution

Quiz: Debugging

A good test case gives us confidence that a program implementation adheres to its specification. In this situation, a good test case reveals a bug.

In a project as big as a JavaScript interpreter in a web browser, we will make mistakes.

And in fact, even a single word flip can be deadly.

Consider this hypothetical utterance from Joan of Arc:

I would rather have a sandwich then be burned alive.

The meaning of this single word really, really matters in this sentence. Then actually means "and subsequently."

For most of us, I would rather have a sandwich and subsequently be burned alive is not actually what we would go for.

So the difference between then and than--a single word in a natural language-- changes the meaning almost entirely.

Joan of Arc was a French national heroine and martyr, and although it's easy to imagine these sorts of single word flips in natural languages, we're going to see the same problem in constructed languages like JavaScript or HTML.

We're going to have to get every word right in order for the meaning to be correct, and this is a big project.

That means we will need to focus some of our efforts on removing or finding mistakes, and that process is called debugging in computer science.

For example, suppose when we were writing out the if-then-else part of our JavaScript interpreter we made a single mistake.

Debugging 1.png

We pull the conditional expression from the oneth element of the tree, we pull the then branch from the second element of the tree, and we pull the else branch from the third element of the tree.

Then we evaluate the conditional expression in the environment, and if it's true, we execute the else statements, and if it's false, we execute the then branch statements.

Did you catch the mistake? We've swapped these 2 lines.

If the conditional comes out true, we will mistakenly go to the else branch. If the conditional comes out false, we'll mistakenly go to the then branch.

We'll get almost every program incorrect.

But not actually every program, and this is a skill in debugging.

What we want to do is make a test case, a sample JavaScript programmer web page, that will show off this mistake, where the answer won't be what we expected.

So here I've written down 4 candidate JavaScript programs that we might use as test cases to notice this mistake.

In this multiple multiple choice quiz, what I would like you to do is select each test case that will actually show off the mistake.

That is, imagine our interpreter has this bug in it and we feed it this input. Will we get the same answer we expect from reasoning in our minds, or will we get something different? If we get something different than what we expect, then we know there's a bug, and we can get started on fixing it. Which of these inputs will highlight this bug?

Debugging 2.png

Solution

Testing

We use testing to gain confidence that an implementation (a program) adheres to it specification (the task at hand). If a program accepts an infinite set of inputs, testing alone cannot prove that program's correctness. Software maintenance (i.e., testing, debugging, refactoring) carries a huge cost.

Testing just means checking a program to gain confidence that it's correct.

More formally, in a software engineering class we'd say that we want to gain confidence that the implementation adheres to the specification as refined from the requirements.

I'm not going to spend much time on these words in this class.

You may have a chance to learn about them later.

But the implementation is your source code and the specification and requirements come from the problem statements--whatever you were told to do in the quiz or in the homework or by your boss or some such.

This is a bit of a personal aside, but in my mind, one of the most important things about testing is noticing that it only gains you confidence. It's not a proof.

If you have a big program like a web browser and you try it on 10 web pages and it seems good, that is not a proof that it's always going to work perfectly in the future, but it does give you more confidence than only trying it on 1 web page. Probably. It depends on how cool that web page is.

So typically, programs are very big and accept an infinite set of inputs. There are an infinite number of possible web pages out there.

We know that because the grammar for web pages is recursive and allows for infinite creativity. We could write down any work of literature and have it be a web page.

So we're not going to test them all in finite time; we're only going to gain confidence by testing a few.

And because we can't test everything, we have to pick the things to test well.

Just like in the previous quiz, we don't want to waste time on test cases that aren't going to get us a debug. In the real world, in commercial software engineering testing is a huge cost.

In fact, maintenance often accounts for 90% of the life cycle cost of software. We spend very little time writing a program originally and a huge amount of time maintaining it, refactoring it, making it better in the face of changing ideas of what the users want, all that sort of thing. So testing is massive.

Quiz: Testing Knowledge

Let's test our knowledge of testing--yes, all my puns are that bad--with a quiz.

Mark all true statements.

  1. Part of testing a program feature is running the program in a way that exercises that feature--and then verifying the output.
  2. Testing can give us absolute certainty that our JavaScript interpreter is correct.

  3. One test input, or test case, is just as good as another.

Solution

Quiz: Code Coverage

We've seen a little bit of testing, but let's look at testing from another angle.

Let's say this is the program or the thing that we're considering testing.

We want to test our JavaScript interpreter, and we're going to feed it this factorial definition and this call to document write. And by thinking hard about the problem, we know the answer we should get is 120.

Here's the quiz.

Let's say this is our test case and that's the input we're comparing against.

I want to know which parts of the program we gain confidence about.

So here I've written 6 important parts of our JavaScript interpreter:

  • handling function calls;
  • handling environment lookups for variable values;
  • handling string constants like hello;
  • local variable declarations like var temp = 3;
  • assignment statements like z = 2;
  • binary operations like addition.

And what I want to know is, if this is our test input and we're comparing the answer to 120, which of these features in our interpreter will be tested? If something isn't tested, we can't hope to find a bug in it.

As a hint, another way of looking at this problem is to imagine, let's say, that our code for function calls totally didn't work. Would we get 120? If the answer is no, then we're testing function calls.

Code Coverage.png

Solution

Testing In Depth

Let's continue our exploration of testing.

As part of this class we're going to be working on a final project together-- for example, a web browser for HTML and JavaScript.

You'll want to ensure that it's correct, that it does what it's supposed to do.

  • One of the best ways to make that happen is to stop and think before you write anything and plan and reason about how the program will go. It's like designing a building before you set out to build it. If you have even the most rudimentary blueprints, your odds of success go up quite a bit.
  • But often we don't spend the time we would like or we don't have the resources to plan everything in meticulous detail, so at some point we just go out and write the source code, at which point you want to test the implementation.

Let me give you another example of mistakes in testing by imagining that I'm going to make a mistake when writing our code to look up a variable in the environment.

Remember that our environment is a tuple of a parent pointer and then a Python dictionary that maps variable names like x or y to values like 22 or 33.

So when it comes time to look up a variable in the environment, we check and see if the variable name is in the dictionary. That's the oneth component of this tuple. And if it is, we just return it. So there are 3 cases.

  • One possibility is we have a value for the variable.
  • Another possibility is we are the global environment-- our parent pointer is None--so if we don't have it, no one does. We'll just return None. There is no value.
  • Otherwise, we call ourselves recursively and look up this same variable in our parent environment.

Testing in Depth 1.png

So these lines represent the correct code, but let's say I make a mistake and I do the following implementation.

When it comes time to look up a variable in the environment, if it's in my environment, I give you the answer. Otherwise, I return None. I never ask the parent. We know this is a bug because I'm making a big deal about it, but it's easy to make mistakes when you're writing the code on your own.

Testing in Depth 2.png

Let's remember this mistake that I'm not going to look in my parent frame.

Let's go through this program and get a feeling for what it should be in our mind.

Testing in Depth 3.png

A is 1, and we call mistletoe with 5, so baldr has the value 5. Now I assign it, we look up the old value, A gets a + 2, so 1 + 2 is 3, so our variables are 6 and 3. Baldr gets 6 + 3, so baldr is 9. So the answer should be 9.

However, with the bug we're going to get an error because at some point we'll try to look up this variable a, and it won't be in our current environment frame. Current environment frame only has baldr. And instead of looking it up in our parent frame, we'll just return None and then we'll try to add None to numbers and we'll get the wrong result. We will be super sad.

Baldr was a god in Norse mythology-- so beautiful, so perfect that as a child his mother asked all of the other things in the world to promise not to hurt him. That's quite the protection deal. But she forgot to ask mistletoe, so everything in the world bounced off Baldr except for mistletoe. And in one of the stories in Norse mythology--it's variously told different ways-- Loki, the trickster god, convinced another god to throw mistletoe at Baldr. Actually, a common element in the story is that they were having fun by chucking things at him--throwing rocks. They'd just bounce off or whatnot. That's a little morbid, but I guess if you're invulnerable it could be fun. The person being asked to throw didn't understand the situation, threw the mistletoe at Baldr, killing Baldr--very sad. In fact, Baldr is sometimes compared and contrasted to Achilles in Greek mythology, who famously was invulnerable on all parts of his body except the heel.

So anyway, this program should print 9, but instead it's going to raise an error. Let's say we don't know where the bug is. We don't know it's in environment lookup. What can we do to refine this test case so that it more closely points to exactly what's going on?

A common approach is actually just to comment out lines in your test case and see if it still breaks.

Testing in Depth 4.png

For example, if I comment out these 3 lines in my test case so that mistletoe just returns baldr, we expect to write 5, and we will.

So now we know the bug is triggered or the problem lies in 1 of these 3 lines.

This is sometimes called fault localization because we're trying to zoom in on--localize--where the problem is.

Quiz: Fault Localization

So here's the quiz question for you to give you a little more practice with this sort of advanced testing and debugging.

We've got these 4 boxes here. Each one corresponds to a single line. Which of these lines could I remove, comment out one at a time, and still see the exception?

I know that if we remove all of them, we don't see the exception.

So what I want to know is, which of these lines are essential to the bug? Which of these lines really show off the bug?

Fault Localization.png

Solution

Testing At Mozilla

Steve Fink of Mozilla talks about testing in the real world. The "range error" example he mentions is related to array bounds checking, a critical language feature for both correctness and security. He argues for simple test cases with obvious control flow, and talks about removing parts of a test case to help localize the fault.

Now that you've gotten a bit of a taste for this, let's check in with someone who toils in the trenches of the real world.

I'm here at Mozilla with Steve Fink, and one of the topics that we cover in class is debugging or testing-- making small, convenient test cases that are going to lead us to a bug or a defect in our program.

That's tricky even for small classroom examples. It can be really difficult in the real world.

Steve, have you run into problems like this in your job?

Sure, and in fact right now I'm dealing with a particular test program that went to a great deal of effort to kind of re-implement the algorithm that it's testing, which is great in terms of comparing the C++ implementation and this JavaScript test program and giving you a yes/no answer-- it works/it doesn't work.

But if you actually do have a bug, it can be a bit of a pain tracking it down just because, okay, you have a failure somewhere in the test; now you have to figure out what the test program is actually doing to figure out why it made the particular invocations into the C++ engine that resulted in the behavior that it's actually testing. So in many cases, it's actually easier just to have a brain dead, simple series of call this, call this, call this, call this rather than for each of these items call this if this is true and expect this output if-- This is where the re-implementation of the algorithm comes.

Let me give a specific example. This was a test of typed array code, and if you access outside of the bounds of a typed array, then it should give you a range error.

An exception.

Yeah, an exception, which of type range error. And so this test program just went through an array of different possible inputs and then said, "Well, based on this logic, if this index is higher than this number, "then expect range error; otherwise, expect this value that it pulled out of the array." So the actual test invocation right there is array element i should be retrieved from this typed array, and then you should get the result based on element j of this array. And it turns out, no, I didn't throw the right error. There was a problem. But figuring out, "Okay, so what exact element were you looking for "and what did you actually expect to find based on this other array?" was very indirect, very difficult. It would have been easier if it was just a dumb, simple series of statements saying, "Pull this element out, expect this error. Pull this element out, expect this value." And in fact, that's kind of what I plan to do is instrument the test case itself to generate a series of silly, stupid linear statements and generate a new test case out of that and then throw away the original because as clever and as easy to modify as it is, it's not actually helpful when you're trying to track down a particular bug."

It's an excellent point. In one of the things we cover in class you'll notice that in class most of our test cases are relatively small and simple. And this is good advice. Sometimes it's better to have 2 test cases--1 for each feature-- than to try to combine them together and then have to tease apart an interaction later on.

  • Yeah. It also makes it much easier to do, for example, binary search. You can whack off half of the test file if it is a very simple, straightforward test file. If it's all interrelated, then it's really hard to take off half at a time.

Exactly. We'll get a chance to see in class commenting out parts of a test file to see if it still causes an error. In a linear test file or just a sequence of assignments, that's much easier to do than if there's a lot of complicated control flow.

Quiz: Anonymous Functions

It can be difficult to test nested or anonymous functions. We will add support for them to our JavaScript interpreter.

One of the cool features of our JavaScript interpreter is that it supports anonymous or nested functions.

However, these features can be very hard to test, so let's try it out together.

You'll recall this Python example from before where we had a nested function definition of greeter that we returned, and the final output of this program would be "hello" "gracie".

I'm going to write this same program in JavaScript. Aside from some minor syntactic differences, the content is the same.

Anonymous Functions 1.png

We make a variable, greeting, initialize to "hola". Variable greeting is "hola".

We're going to define this makegreeter function of 1 argument called greeting, define the makegreeter function of 1 argument called greeting.

Then we're going to make this sort of nested function greeter that takes an argument, person, and here the local variable greeter is a function that takes an argument, person.

So where in Python we used another def, in JavaScript we're using this function keyword.

Argument person is the same.

Instead of print we call write or document.write and we return the greeter. Sayhello is a variable of makegreeter("hello"), variable sayhello is the result of calling makegreeter on "hello" and then we do it at the end.

So the real exciting part is here.

In JavaScript you can use the word function to make a new function anywhere without really giving it a name, although we assigned it to the variable greeter almost immediately.

So you can use it at the top level to make a function with a name, or you can use it lower down. See, here we just have function and then we're listing the arguments. We didn't put a name in here. This is sometimes called an anonymous function because it doesn't immediately have a name.

So as a quiz, let's add support for those anonymous functions to our JavaScript interpreter.

I'll write the first part, you fill in the key details.

Anonymous functions are expressions. We know that since they can come on the right-hand side of something like this.

var x = function(..) { .. }

Anything on the right-hand side of a var or an assignment statement is an expression.

So there are a bunch of different types of expressions-- numbers, strings, binary operators. Let's just handle the function part for now.

So as a running example, let's say we have a function of 2 variables, x and y, that's going to return their sum.

The abstract syntax tree we get for that will have function in this sort of identifier position telling us what this sort of node is, then it will have a list of the parameters, and then it will have the body list of statements.

("function", ["x", "y"], [("return", ("binop", ...)])

And what I'd like you to do for this quiz is fill in these 4 blanks. We want to return a particular value-- value corresponding to a function.

Anonymous Functions 2.png

This is going to require you to think back to how we treated function definitions and function calls earlier in our interpreter.

But here's a hint: A function was a for tuple containing the word function at the beginning and then also listing in some order the body, the environment, and the parameters. Fill it in.

Solution

Quiz: Mistakes

Well that time we got it right but suppose we made a mistake.

Suppose we had access to the global environment so this is actually defined, and instead of passing in the current environment, whenever we make a function, we're going to pass in the global environment instead.

return ("function", fparam, fbody, global_env)

This is a bug. This is not correct.

Let's try to reason forward about what might go wrong, and how we could see this bug or how it would behave.

I'm going to write some statements and you're going to tell me which ones are true.

Here I've written four claims, and in this multiple choice test I'd like you to note which ones are true.

  • The first, no test input with only one function can show the bug.
  • The second, we need at least three variables in the global environment to see the bug. Here--see the bug, show the bug, expose the bug--all mean the same thing.
  • We can show the bug with only two functions, each of which is separately declared at the top level, and finally,
  • we can show the bug with one function nested inside another function.

Mistakes.png

Solution

Quiz: Hola

So here's that javascript code from before, with the anonymous function assigned to "greeter" nested inside "makegreeter."

I'm going to draw the environment much more formally.

Hola.png

In our global environment, "greeting" points to "hola." "Makegreeter" is a function with three other components that I'm not showing right now, and "sayhello"--well, to figure out its value, I'm going to have to call "makegreeter" on "hello."

Whenever I call a function, I make a new frame with just enough room for all of the formal parameters.

Then inside this frame I'm adding a new local variable, "greeter," which is a function with one parameter.

And even with our environment bug, even with the bug that we've been considering, this is still going to point back to the global frame.

So this value of "greeter"--this function defined here--will be copied back. And these things I've marked in green have the same value. This was the return value of "makegreeter," so it's what "sayhello" currently has.

And now we're going to call "sayhello" on "gracie." So we're going to make a new frame where a person points to "gracie" pointing back to the global frame.

And here's the question for you-- one of these arrows, or possibly both, is incorrect, if we have the bug we've currently been talking about.

We have the bug.

Check the arrow--check the parent pointer edge that would be different if we didn't have the bug. If we fixed the bug, how does the world change--quiz?

Solution

Debugging In The Real World

So we've just had a chance to learn a bit about debugging, which is made up of testing and then trying to localize or isolate the fault and then fixing it.

I actually had a chance to work at a lovely company in Santa Barbara, Green Hills Software, where my job was to do just that for just the sort of interpreter that you're writing. Every day I'd come in and there would be a stack of input programs on my desk, and our interpreter--or our compiler--was currently computing the wrong answers for them.

And I would do this sort of hypothesis testing that we've been considering here. I'd say, oh; what if the bug is in the top half of the program? Then I can comment out the bottom half, and I should still see the bug. Oh, that didn't work. Maybe I'll hypothesize now that the bug is in the bottom half of the program. I'll comment out the top half and we'll still see the bug.

And I could refine my way down--maybe it's in the top fourth, maybe it's in the top eighth, until eventually I had a very small input that still showed the bug. And then it was easy for me to localize the fault and fix it.

The process was relatively lockstep, so lockstep in fact that a few years ago a researcher, Andreas Zeller, published a technique for automating it.

His approach, called Delta Debugging, makes it systematic-- does this systematic hypothesis testing by dividing a program input in half and half again until it finds the smallest input that still reproduces the bug.

In fact, looking back on it now, the job that I had is almost completely automated.

When you run into defects or bugs in your code, and you probably will-- I certainly do all the time--I want you to apply that same level of formal reasoning. Think about where the bug might be. Make a test case that probes or falsifies that hypothesis. Localize the defect. And then move in to fix it.

My old job localizing compiler bugs by shrinking test cases is now almost completely automated by Delta Debugging, Andreas Zeller's scientific approach to debugging. On a personal note, Udacity will be offering a course on debugging by Andreas Zeller in a bit. I highly recommend that you take it — Andreas is a great guy and he explains things clearly.

Optimization

An optimization improves the performance of a program while retaining its meaning (i.e., without changing the output).

So now that we have a better understanding of how to check that our program is correct and test it to gain confidence, let's talk about optimization--making our program faster.

Over on the right, I've doodled the tortoise and the hare. You can tell this is a hare and not, let's say, a mutated donkey because of the label; those labels are always correct. This bears reference to one of Aesop's fables--a Greek writer from times long ago-- in which the hare, although in some sense faster was relatively lazy and was eventually beaten out by the tortoise.

In the real world, performance matters. We've heard, for example, that if you don't render a web page in 6 seconds or less shoppers will go to another website.

For the vast majority of applications, things in this class: airline autopilots, banking transactions, things related to energy or power or transportation, performance matters less than correctness.

  • Job one--test it, debug it, get the right answer.
  • Job two--make it fast.

In this sense, optimization refers to improving the performance of our code. Can we make our web browser take less time to render the same web pages? A lot of modern interpreters, from JavaScript interpreters to Python, use a technique known as Just-in-Time Improvement, which is sometimes abbreviated as JIT, to fix up or improve code right before they run it so that it's faster but gets the same output.

So our basic optimization idea is going to be to replace the input webpage--the HTML or JavaScript fragment-- with one that takes less time to process but has--and this is super critical-- I cannot emphasize this enough--exactly the same meaning.

We must produce the same output with optimizations on and with optimizations off, aside from the time it takes.

We absolutely can't change the meaning. We have to be correct.

In that sense, optimization for programming languages is somewhat similar to editing for conciseness in natural languages.

If you say something redundant and it's possible to remove that redundancy without changing the meaning, you can strike it from written text.

We're going to do the same thing with optimization.

Here I've written JavaScript code to compute the factorial function, and this code is correct.

function factorial(n) {
   if (n == 0) { return 1; }
   return 1 * n * factorial(n-1);
}

Now, of course, as soon as I say that there's going to be one minor typo, but let's just assert that this code is correct. It actually computes factorial.

But it's a little slower than it needs to be.

You may have noticed that I wrote 1 times N times factorial of N minus 1 instead of just N times factorial of N minus 1. This is correct--multiplying something by 1 doesn't change its meaning-- but it's slower than necessary.

If we're talking about arithmetic, whenever you see 1 times N, you could just replace it by N, and now you're saving time because we're removing notes from our abstract syntax tree. This means it takes less time to do our recursive walk and interpret it, and we have fewer multiplications. And multiplication is an arithmetic operation that this CPU has to perform; it takes some amount of time. In fact, especially in something like factorial, if I'm asking for the factorial of 10, we're going to call this function a large number of times. So even though it may not seem like I'm saving much, I save it every time we're in this loop.

And this is why I suggested earlier that performing such a simplification or optimization is like editing someone's writing so that it's more concise.

If I just edit that part away, this factorial is still correct; it just takes a little less time.

function factorial(n) {
   if (n == 0) { return 1; }
   return n * factorial(n-1);
}

Quiz: Platos Republic

So you may already have a good intuition for these sorts of optimizations.

Let me give you a chance to show that off. So here I've written a function in JavaScript called Plato's Republic.

It's a function of 2 variables: A and B. A gets A times 1, B gets B + 0, A gets A + B, B gets B + 2, and then finally we return A.

There are 5 possible statements here.

Which of them can be simplified or removed without changing the result?

And here I really want you to mostly focus on removing, and note that this is a little trickier than it looks. So give it some thought.

Platos Republic.png

Solution

Quiz: Implementing Optimizations

Okay, well that sounds great, so far. We have an idea of when we can possibly remove things based on mathematical truths.

But how do we actually implement them in our JavaScript interpretor--in our web browser?

Well, step 1 is to think of a big library of optimizations. For example, X times 1 is always equal to X, and X+0 is always equal to X. So if I see one of these expressions, I could just replace it with the simpler one on the right.

And I'm going to do that by transforming the parse tree directly.

But before we talk about transforming the parse tree, we're going to need to be certain about what sort of optimizations we want.

Remember, we can only do optimizations that don't change the meaning of the program. We have to get the same answer, just in less time.

So here I'm going to have you take a look and evaluate or tell me about some candidate optimizations. I want you to fill in each of these 4 blanks.

Write the simplest expression you can to make the equality true. So can I replace X times 1 with something simple that fits in this box? Write the simplest expression you can that retains the meaning in all cases.

This is a little trickier than it looks, so try it out.

Implementing Optimizations.png

Solution

Optimization At Mozilla

Steve Fink of Mozilla talks about optimization in the real world. Mozilla's JavaScript interpreter is called SpiderMonkey, and it has gone through a number of different just-in-time (JIT) optimization architectures. He reminds us that you must always be aware of the cost of an optimization. He also notes that it is rare that a software engineer spends the entire day writing new code — looking over old code is very important and time-consuming.

So one of the topics that we cover in this class is optimization, making a program faster but having it compute the same result, and I like optimization a lot. It is a lot of fun to think of cool ways to speed up the code, but it turns out that often getting the right answer or maintaining the code later, having the code be well documented, making it easy to debug the code, these things might all trump optimization. Steve, have you seen anything like that in Mozilla or other projects you've worked on?

[Steve] Constantly. With the SpiderMonkey JavaScript engine these days, I kind of feel like we spend half of our time removing old optimizations to make way for refactoring; future engines. I think we've been hit particularly hard because we switched our JIT engines several times at this point. TraceMonkey was our original optimization-- well, our original JIT engine, which had a particular style of optimization that it covered, and we have since entirely removed the TraceMonkey JIT engine and replaced it with JagerMonkey, which is kind of the next generation JIT engine, except now, it's the previous generation JIT engine itself, and it is slated to be replaced by IonMonkey, we like monkeys.

I was going to there is referring monkey theme.

[Steve] Yes. And it turns out that the sorts of optimizations that are really helpful for a tracing style JIT are really obnoxious when you get into a different style of JIT, because they just get in the way, and it prevents you from--you know-- making a lot of code simplifications that makes it straight forward to do a JIT in a different style, and so there are many, many different optimizations that we've had to just rip out wholesale, and unfortunately, it's at least as much work to remove some of these--some of these optimizations as it was to make them in the first place, and really anytime you do an optimization, you have to be very aware of the cost of that optimization. You may be saving some runtime, but you are adding complexity to everybody who comes by and tries to read and understand that code. You are preventing some refactoring, some restructurings of that code because it would-- it would break the optimization--you know-- the optimization was made with certain assumptions, that's almost the definition of an optimization is that if we assume certain things, then we don't have to do some of these operations, and that's the way to make things faster is to not do some of the things that you were previously doing. And so there are all kinds of--you know-- hidden costs to an optimization, and it can actually be very damaging to put certain optimizations in the code because they're going to prevent other optimizations, they are going to prevent--you know-- simplifications of the code, they are going to prevent changing the semantics of what you've implemented because the optimization is based on certain assumptions that you may want to change in the future, and so we sent a lot of time--you know-- trying to find the right balance today, which is actually different from the balance yesterday, and so even if a previous optimization made total sense in the past world, it may actually get in the way in the current world. So yeah, we see a lot of this.

Excellent, now you mentioned something that caught my ear, and I wonder if I might put you on the spot with a bit of a surprise question. You mentioned that you're looking over old code and refactoring it, and I'm just wondering throughout your average day, let's say you spend some amount of time reading code and some amount of time writing new code. What's that ratio or how many hours is fixing bugs and code, looking over old code, and how much is writing new code?

[Steve] It varies a lot from day to day. Some days are actually spent 100% writing new code, and those days are happy days and rare days. The vast majority really is looking at existing code, sometimes code that I wrote, much more often code that other people wrote, and here at Mozilla, we have a rule that every line of code that goes into the tree must be reviewed by another person so-you know--in terms of you have a sealing of 50% of time is spent on new code because every line of new code is going to be viewed by at least one other person, and often you'll go through multiple rounds of review, and so--you know--multiple people or the same person are looking at that line of code several times, but even if you're going to write new code, you always have to understand the context in which you're placing that code, and so you really have to understand what comes before, and you will spend much, much of your time doing that, far more of your time doing that than kind of going into a green field and putting something brand new in place.

And this idea that you have to understand the context in which your adding code is one of the reasons why understanding the meanings of programs, their semantics, is so important.

Optimization Timing

In this class we will optionally perform optimization after parsing but before interpreting. Our optimizer takes a parse tree as input and returns a (simpler) parse tree as output.

So how are we going to fit optimization into our JavaScript interpreter?

The basic plan is to change the parse tree before interpreting. That way we'll save time, especially if the optimization we made was in the inside recursive call of Fibonacci or factorial or something like that.

So recall our general plan, the outline of our interpreter, we start with program text, which is a string, and we use lexical analysis to break it up into tokens, or important words. This is implemented with regular expressions. Then we use parsing based on context-free grammars and dynamic programming to check and see if those tokens are in the right order. Are they valid syntactically? Do they form a sentence? If so, we end up with a parse tree, also called an abstract syntax tree.

And now--here's the new part--we're going to do optimization, which will also yield a parse tree but hopefully a simpler one. If all else fails, do no optimizations and return the same one. Then we do our interpreting, and that gives us the meaning of the program, the final result.

Optimization Timing 1.png

So we're going to fit optimization in after parsing but before interpreting.

Optimization is always optional.

You don't have to do it, typically, unless you're in some sort of company where timing really, really matters, like, say, a car's anti-lock brake system, where you might have to respond within a certain number of milliseconds. But for the vast majority of applications, optimization is optional, so often we do it last.

In fact, let me show you a simple Python example of how a JavaScript optimizer might go.

For now I'll just optimize expression trees. We'll do these arithmetic optimizations we've been thinking of, and for now I'm going to focus on expressions that have expression type "binop"-- binary operator.

For example, maybe it's something like A * 1 and I just want to replace that with A. Well, here's a real simple way to do that.

Optimization Timing 2.png

I'll just check and see if the operation is star, and I'll check and see if the right-hand side is literally the number 1. If it is, then I can just return A; otherwise I'll return the original tree unchanged.

Maybe it was something more complicated like 5 times 3 or 5 times X that we couldn't reason about.

We could certainly put in more optimizations here, but now we have at least one. And the basic plan is right before we interpret an expression, we call optimize on it.

Just to show this pictorially, let's say our input is 5 times 1. We're just going to replace that with 5.

Optimization Timing 3.png

In our Python interpreter, that abstract syntax tree would show up as nested tuples: binop involving multiplication. A binop where the left child is a 5, there's some multiplication, and then the right child is 1.

And if these two parts match a pattern we've already established, then we'll just hoist this part out and return it unchanged. So we've gone from 5 times 1 to just 5 by looking at our Python abstract syntax tree, checking to make sure the optimization is legal-- an optimization is only legal if it doesn't change the semantics of the program, doesn't change the meaning of the result-- and then once it is legal, we just replace the tree with a simpler tree.

The way I've written it, we're officially returning a new tree. Potentially, if we wanted it to be a little more efficient, we could change it in place, but returning a new copy of the tree is fine for us.

Quiz: Optimization Phase

So let's go back to our simple optimizer. Currently, it only handles A times 1. The quiz for you is to add in support right about here for A times 0 and A + 0.

# Optimization Phase

def optimize(tree): # Expression trees only
    etype = tree[0]
    if etype == "binop":
        a = tree[1]
        op = tree[2]
        b = tree[3]
        if op == "*" and b == ("number","1"):
            return a
        # QUIZ: It only handles A * 1
        # Add in support for A * 0  and A + 0

        return tree

print optimize(("binop",("number","5"),"*",("number","1"))) == ("number","5")
print optimize(("binop",("number","5"),"*",("number","0"))) == ("number","0")
print optimize(("binop",("number","5"),"+",("number","0"))) == ("number","5")

Solution

Quiz: Optimizer Check

So let's see how well you really understand the optimizer we just wrote.

Here I've written out 5 candidate optimizations-- A times 1 gets replaced by A--and what I'd like you to do in this multiple-multiple choice quiz is check all of the ones that our optimizer, as we just wrote it, will perform.

Optimizer Check.png

Solution

Rebuilding The Parse Tree

We desire an optimizer that is recursive. We should optimize the child nodes of a parse tree before optimizing the parent nodes.

Let's take a look at that last example in a little more detail.

What we would really like to do is start at the top and call ourselves recursively to optimize both children. Once I figure out that 5 times 0 can be replaced by 0 and A can only be replaced by A I rebuild my abstract syntax tree and now I'm in a great position to rewrite this to be just A. So there's going to be

  1. Step 1: recursive calls.
  2. Step 2: Look for patterns.
  3. And then, finally, Step 3: We are done.

In order for this to work out, our optimizer has to be recursive just like our evaluator and our interpretor. This is not a coincidence. Recursion--iteration--is really central to computer science. It's fundamental.

Rebuilding the Parse Tree.png

Quiz: Fix It Up

All right, so for our final quiz in this unit, I want you to fix up this code so that it handles--it optimizes-- A plus 5 times 0 recursively.

# Optimization Phase

def optimize(tree): # Expression trees only
    etype = tree[0]
    if etype == "binop":
        # Fix this code so that it handles a + ( 5 * 0 )
        # recursively! QUIZ!
        a = tree[1]
        op = tree[2]
        b = tree[3]
        if op == "*" and b == ("number","1"):
            return a
        elif op == "*" and b == ("number","0"):
            return ("number","0")
        elif op == "+" and b == ("number","0"):
            return a
        return tree

print optimize(("binop",("number","5"),"*",("number","1"))) == ("number","5")
print optimize(("binop",("number","5"),"*",("number","0"))) == ("number","0")
print optimize(("binop",("number","5"),"+",("number","0"))) == ("number","5")
print optimize(("binop",("number","5"),"+",("binop",("number","5"),"*",("number","0")))) == ("number","5")

Solution

Creativity In Optimization

So now our optimizer will correctly change this to ethos times zero plus zero, that's going to be zero, pathos times 1 times 1, that'll be pathos, and logus times 2 plus 5 will be logus times 2 plus 5, and you might have already spotted places where we could add other optimizations.

Creativity in Optimization.png

For example, wouldn't it be nice to just replace this with 7 right now. So there's plenty of room for creativity in optimization.

So we could do better with optimization, but it takes creativity because we need to know what we want to change and also when it's legal.

Bending The Rules

Genetic Programming uses evolutionary algorithms inspired by biological notions to find computer programs that have certain properties. It is possible to use such evolutionary computation to automatically repair defects in programs.

So we've touched on Optimization-- the notion that you could take part of one Abstract Syntax Tree and replace it with something else, in order to make the program faster or use less power.

The cardinal rule of Optimization was: You can't change the meaning of the program.

You have to respect the formal semantics or at least, that's what I've always told you.

But what if we break that law? What if we want to change the meaning of a program? For example, what if your program currently has a bug and I want to change it so that the bug isn't there? What if I want to fix your program-- Optimize it so that it is more correct, instead of being faster?

I've worked on just this sort of research project.

We call it Evolutionary Program Repair. It involves using genetic algorithms or genetic programming-- computational analogs of Real World biological processes, like Crossover and Mutation.

We maintain a population of candidate programs that may fix your bug-- just like you can imagine a population of animals on an island and then survival of the fittest allows some of them to stay, and the rest to die out.

If you're interested in this sort of research-- I affectionately call it Building Skynet because we're building a program that builds other programs-- you can check the links above.

But one of the things that I want you to take away is that the concepts that we're covering in this class-- notions like Abstract Syntax Trees or replacing one expression with another-- can be used in different contexts, to great effect. It just requires creativity to know when you can bend the rules without breaking them. That creativity is the essence of engineering.

Wrap Up

All right; let's wrap this up.

Over the entire course, we've seen

  • lexing,
  • parsing;
  • we just saw optimizing.
  • We've seen interpreting.
  • And just in case anything goes wrong, we know how to do debugging.

Lexing was based on regular expressions. They specify sets of strings, and they can be implemented under the hood with finite state machines.

Parsing uses context-free grammars, which can capture behavior like balanced parentheses that regular expressions can't. And we saw how to implement those with dynamic programming, that is, writing ourselves little memos in a chart, and parse states.

Optimizations are great; they make the programs simpler and conserve some important resource like time or power or heat dissipation. But they're only valid if they retain the meaning.

In general, interpreting refers to walking the abstract syntax tree recursively and computing the final value.

In our particular web browser, our HTML interpreter calls the JavaScript interpreter, and our HTML interpreter calls the graphics interpreter.

And in debugging and testing we can gain confidence that our program adheres to its specification by thinking very hard about which parts of the input or which parts of the program might be wrong and carefully crafting them, paying attention to all the information we have available.

Wrap Up.png

In the homework or the class final projects, you'll finish the browser, and unit 7 will be review for the final exam.

Solutions

Web Browser Process Solution

Let's go through it together--the Web page is broken down into words and trees.

That's lexing and parsing, and we do that first. This is right; the Web page is then interpreted--that's True. Some of the fragments or elements that we come across might be JavaScript--embedded JavaScript-- so then we have to call the JavaScript interpreter. So thus far, the first 3 seem pretty good.

Eventually, the user's JavaScript code on the Web page may call: write()--at which point we'll have to store all of that output so that we can display it on the Web page. That's good.

Ah! But then here we're suggesting that the JavaScript interpreter calls the graphics library.

This is an erroneous step; in our particular architecture, the JavaScript interpreter returns all of the strings to the HTML interpreter and that interpreter, then, calls the graphics library.

This is what's known as a Design Decision. For our particular Web browser, only the HTML interpreter is going to call the graphics library. That's not the only way to do it. Just like there's more than one way to build a house, there's more than one way to build or design a Web browser. We've just decided for this particular one, that only the HTML interpreter's going to call the graphics library. I claim that's going to simplify the amount of code we'd have to write.

Web Browser Process.png

Token Value

Well, we just saw the code for processing these tokens, and we know that it went to a bit of trouble to store the beginning position, lexps, and then the ending position, but then--phwoomp--subtract out 9.

So this is way too much. We went to a lot of trouble to drop <script type"--blah,="" blah,="" blah--so="" this="" first="" one="" doesn't="" match.<="" p="">

Similarly, this second one doesn't match.

This third one looks perfect! It has stripped out the tag at the beginning and the tag at the end.

This fourth one still has the tag at the end, so it's not right.

Token Value.png

In the particular example we're using, the Satasai or Bihari Satsai are 700 verses from the 17th century. They're written in Hindi and they cover topics from morality to devotion, to love. Good stuff!

Calling The Interpreter

Well, we've seen that interpreters always work over Abstract Syntax Trees.

My JavaScript interpreter should be called on our JavaScript parse tree-- our JavaScript Abstract Syntax Tree-- and it's going to arrange to return to us a string corresponding to what the user was going to print out as a result of calls to write, like this string containing (55).

So that result is exactly what we want to display on the Web page.

If this tripped you up because it was almost too simple, don't worry about it. Much of the detail in the integration is in knowing exactly the right way to call the lexar and the parser.

But those aren't endearing concepts that I really want you to know after that class.

Those are mere implementation details.

Instead, the architecture-- the fact that we can only call interpreters on Abstract Syntax Trees and that we've decided to pass string results back and then display them, using our graphics library-- that's important; that's a design decision.

This, lex and yacc --this is a historical accident. That's why I gave all of you these, for free, and asked you to tell me about these conceptual bits.

Javascript Output

Well, let's go through them together.

We could rename "javascript output" to anything as long as we're consistent.

This is very tempting (1). Why don't I change this ugly space to an underscore. Well, the reason is that if the user knew that, in their embedded JavaScript fragment, they could assign to the variable "javascript_output" and because we're piggybacking on our environment, they'd find it, and they'd collide with it. So rather than printing out the right answer, we'd print out whatever the value was for this variable "javascript output." It's super unlikely, very unlikely that the user would happen to name a variable "javascript_output," but it's a security problem and officially there exists at least a few programs that won't compute the right answer if we change it to a variable that the user can collide with. So we can't actually rename it to anything. We have to be careful.

When this feeds into the second one, "javascript output" is a good choice because it has a space in it--yes! If you think back to our lexer rule for identifiers, it looks something like this. Every javascript identifier contains upper or lowercase letters and possibly an underscore but can't contain a space. So this means there is no way for the user to have a variable name that has a space in it, so no way for them to collide with the rest of the environment. We could also have made a different design decision and had some global variable that's stored the "javascript output," but this approach, first, piggybacks on something you've already done, and second, illuminates cool issues like this.

Finally, "javascript output" starts empty to support 0 calls to write. That does end up working out. Imagine that trees is the empty list. They just said begin Javascript, end JavaScript and didn't do any work. We would want to return a real value rather than having some sort of exception or look-up error problem. If I didn't initialize "javascript output" to the empty string, when we went to look it up here, there might not be anything there.

Javascript Output.png

The sort of name collision discussed here is a significant concern in computer security. It would be safer to use a separate variable or channel to communicate such strings back to our interpreter.

Updating Output

We want to concatenate everything the user has previously written, and then on the end of it, put the new current value.

So I'm going to put all of the output we've gathered up so far from previous calls to document.write and then just turn the value of the argument into a string and paste it on the end. And that's it.

We handle calls to document.write specially, and all of our previous code for function calls now goes else: if function name is not "write" then do whatever we had previously.

Counting Frames

It's going to turn out that there are 8.

There's the global frame. There's our call factorial 6. There's factorial 5, 4......1, and in fact, if you look carefully--this was a bit of a trick-- at our termination condition for this recursive procedure, we actually call in here when n is 0. So that's 8, if we include the global frame.

And how many of those will n have the same value? None of them. It's 6, and undefined. It's never the same. We're honestly doing different computation going through different values.

Counting Frames.png

Debugging

Now let's go through each one of them.

  1. Writing "potato" may be fun, but it does not involve any sort of if-then-else processing, so it won't show off our defect. The expected answer is that the web page shows potato, and the answer we'll get is the web page shows potato. So this is not a good test case.
  2. Over here, if x is less than y write "tomato", else write "eggplant". We need a little more in this test case like values of x and y, but this is the right idea. Let's say that x is something like 0 and y is something like 1. We then expect it to print out "tomato" but because we've made this bug over here, it will print out "eggplant" instead. So the observed behavior will differ from our intuition or from our specification of what should really happen, so then we know there's a mistake.
  3. Over here return 2 + 3. Again there's no conditional control flow, so this is not a very good test for us.
  4. Finally, over here factorial does involve an if in determining whether or not the program terminates. This is a very good test because almost immediately, factorial of 5, we're going to see, oh, is 5 equal to 0? It's not. Bug. We'll return 1. We won't actually make any recursive calls. We'll get the wrong answer really fast. So this is a good test case for us.

Testing Knowledge

  • This first one, part of testing a program feature is running the program in a way that exercises that feature, that was the last quiz. Yes, that is part of testing. We have to exercise the feature and then compare the observed output to what we expected. And if they're different, that indicates a bug.
  • Testing can give us absolute certainty. No. Testing can give us confidence that our JavaScript interpreter is correct. Because our JavaScript interpreter could potentially accept an infinite number of inputs-- there are an infinite number of possible JavaScript programs out there-- we don't have time to test them all. We can't be absolutely certain based on testing, but it can give us confidence.
  • Finally, one test input is just as good as another. No. This was the previous quiz. We need a test input that exercises the feature. And if we have a bunch of features in our program, we would want a suite of test inputs that cover all those features.

Code Coverage

Let's go through our program and just notice everything we end up using.

One of the first things we do is call the function write, and its argument is based on calling the function factorial of 5, so then we have to get up here and start determining if n is equal to 0.

So function calls are definitely critical to getting the output to this test case correct.

One of the first things we have to do is look up and see if n is equal to 0, and we'll change from 5 to 4 to 3 to 2 to 1 to 0 depending on which environment frame we're in.

We will definitely end up doing environment lookups.

If we can't do them, we don't know what the value of n is, so we're going to start getting this wrong.

Eventually, as time goes by, we're comparing n to 0, we're multiplying n by the result of this function call, and we're subtracting 1 from n. Those are all binary operators. The equality check, the multiplication, and the subtraction-- those are all binary operator expressions. So we are testing at least some of our binary operators.

But for the rest of these elements of our interpreter, we're not testing them explicitly. Even though we end up calling write, there are no string constants. The word here, constant, is very important, like "hello" in this program.

You could argue that we're building up a dynamic string, 120, but that's not a string constant. There are also no local variable declarations.

A local variable declaration is different from a function's formal parameter, and this matters because we're trying to find bugs in our interpreter code. Since we have different Python code to handle parameters than we do for local variable declarations, if we mistakenly think they're the same thing, we'll have more confidence in our program than we should.

We might miss bugs. So we're not testing this sort of thing--var temp = 2.

That's a local variable declaration. We don't see anything like that over here.

Finally, assignment statements. There are no assignment statements in this program. Now, we'll end up associating with n the value 5 or 4 or 3 or 2 or 1, but that's handled by our function call code.

We don't see anything like this--x = 2--in this input, so we're not testing it. So while this is a good test case and it checks many things, it does not give us confidence that we've exercised every feature of our interpreter. We'd need a few more test cases to do that.

https://www.udacity.com/wiki/w/edit?page=cs262/unit_6

Fault Localization

Starting from the bottom, if I remove the last line, we never actually call mistletoe, so our program just declares a variable, declares a function, and then exits, so we don't see the exception. So we can't remove this line.

Let's take a look up here (1). What if I comment out baldr is baldr + 1? Well, with our bug in environment lookup, this line a gets a + 2 will still cause us to die. So we can remove baldr is baldr + 1 and still see the exception.

How about this one?(2)If I remove a is a + 2, we'll still see the exception down here in baldr is baldr + a. We'll look up the value of a and not find it. So I can remove that line.

Similarly, if I remove this third line, we can still die on line 2. So now, potentially, we have a lot of information available to us. We know that we need to make this call, we know that these 3 lines are important, and in a more fully formed integrated development environment or interpreter like the Python interpreter, we'd get an exception backtrace that would point us to this line or, if we've commented out that line, point us to the next one. So with all of this information, we get a better feel for what's actually required.

Fault Localization.png

Anonymous Functions Solution

The first part of our return value is just the word function.

Anonymous Functions.png

This is to separate it from a number like 3 or 4 and to allow us to tell if the user mistakenly tries to call something that's not a function later.

We then list the parameters which we got right from the abstract syntax tree, the body of the function, which we also got right from the abstract syntax tree, and the environment in which it was defined--this one, env.

And we're passing in env here instead of some global environment or whatnot and this is what's going to allow local functions to see local variables.

This is why things like makegreeter work. They can refer back to variables that were currently in scope when they were defined.

Many of you may notice a striking similarity between this and our previous code for handling function declarations. In fact, our previous code just had 1 more step where we added this value to the environment.

For an anonymous function, we don't add it to the environment unless the user assigns it.

But this code should look really, really familiar. We have something almost exactly like it for handling functions at the top level as JavaScript elements.

Mistakes

Well, let's take a look.

  • The first one is actually true. With only one function in our program, we'll have our top level global environment and then the environment for our new function, and we're making its declaration, or its parent pointer, go back here to the global environment. That's where it should go, but that's also where the bug is putting it, so we won't be able to tell the difference.

Now if this weren't an anonymous function but were instead a recursive function like factorial, we might be able to see the bug with only one. But with just one anonymous function, we can't quite see the bug.

  • We need at least three variables in the global environment to see the bug. This isn't really true. One variable in the global environment--one local variable-- maybe even no variables in the global environment--should be totally fine. The only time the parent pointer matters is when we're looking up a variable in a child environment and we don't find it locally. So we should be able to construct a test case that has just one such variable, like the "a" in the Balder example we did earlier. We won't need three.
  • We can show the bug with only two functions, each separately declared at the top level. If I have another function, function two, declared at the top level, its parent pointer should point back to global and because of the bug, it will point back to global anyway. So this won't let us see the bug.
  • We can show the bug with one function nested inside another. This is the plan. Let's say we have function one with function two nested inside of it. The parent pointer for function one, or this pointer, should go back to global. The bug will make it go back to global. Function two should point back to function one but the bug will make it point to global. So all I have to do is put some variable "a" in here, and have function two refer to it. Then in my test case we won't find it and we'll get an error, but in the real world we should find it and that will allow me to pin down the defect.

Mistakes.png

Hola

The edge that should be different is the one on the left.

Let's trace through it to see why. We know when we run this program that it should say "hello gracie."

When we're running a function, our official rule is you take the function body--here's the function body-- "right greeting" plus "person"--and you evaluate it in that frame-- "right greeting" plus "spaces" plus "person."

We go to look up "greeting." Do we have it? No. Let's go ask our parents. Oh, our parents do have a greeting--it's "hola." Look up "person"--do we have it? Yes, it's "gracie." With the bug, this program will mistakenly print out "hola gracie." That's not what we wanted.

That doesn't match the semantics.

If instead I erase this edge and draw it correctly, having this function point back to the environment in which it was defined, now when I try to write "greeting" plus "person," do I have "greeting?" No. How about my parent? Oh, my parent does, and it's "hello." How about "person," "gracie?" We'll write out "hello gracie."

So with the bug we get "hola gracie." Without the bug we get, correctly, "hello gracie."

Hola.png

Platos Republic

Let's go through the lines 1 at a time.

  • A times 1. This is the same as A=A because anything times 1 is just itself. So this assigns the new value of A to be equal to the old value of A. So this is actually equal to just doing nothing. So I could totally remove this line without changing the result of Plato's Republic.
  • B gets B+0. This is the same sort of theory. This reduces to B gets B because adding 0 to something doesn't change its value. So I could just drop this statement entirely.
  • A=A+B. That looks like something important might be going on. Let's hold on to that for a bit. In fact, let's go down here and see. Eventually we're returning A. I can't remove this line because we actually need to return A to have the same value. And if I'm going to return A, then I need to keep this line-- A gets A+B--so that I know what the right value of A is supposed to be. But--and this is the potentially tricky bit-- I can remove B=B+2. Even though there's no arithmetic simplification that I can perform, I just don't need the line! B isn't part of the return value. No one else can ever see it. We throw it away after this point.

Platos Republic.png

Formally in computer science we call this "dead code". It has no effect on the rest of the program. So I could drop these 3 lines, and all that Plato's Republic is really doing is summing its 2 variables together, returning the result.

Plato's Republic is a dialogue written in about 380 BCE that talks about the definition of justice. The phrase "who watches the watchers" often comes up in discussions or criticisms of Plato's Republic.

Implementing Optimizations

  • Well, X times 1 is just equal to X regardless of the value of X. If X was 55, 55 times 1 is 55. If X was 0, 0 times 1 is 0. If X was negative 2, negative 2 times 1 is negative 2. Excellent.
  • X times 0 is always equal to 0. This is one of those mathematical identities. 55 times 0 is 0. Negative 1 times 0 is 0.
  • X times 2 can be rewritten as X + X. This may not immediately seem like a useful optimization, Formally, we call it "strength reduction" in the sense that multiplication was a stronger, harder-to-compute operation than addition. On some CPUs or on some hardware platforms, it takes less time, fewer cycles, less energy to compute addition than it does to do multiplication. So even though both of these have 2 operands and they are both binary operators, this 1 might be faster on many platforms.
  • Finally, we get to the last one and the one that probably is the most controversial: X divided by X cannot safely be replaced with anything smaller. You'd REALLY like it to just be 1. Negative 2 divided by negative 2 equals 1. Seems like it's always 1, except for this 1 corner case: 0/0 And the golden rule of Optimization Club is: "Always keep the same semantics." If there's a possibility that on some inputs we could raise an exception, we can't rule out that exception with our optimization. You'd think, "Why would anyone want to divide by 0?" You can't change the meaning of the program. You have to keep it exactly the same when you're doing optimizations. So 1 is very tempting, but it's too aggressive. There's a single case where it's wrong, so we can't use it for optimization.

Implementing Optimizations.png

Optimization Phase

Let's walk through a possibility together.

Let's handle A times 0. In such a case, we want to return B or the number 0, whichever you prefer.

Anything times 0 is 0. [return tree] And the other thing I am supposed to handle is A + 0, at which point I just return A.

I could have been more complicated potentially and changed the if condition up here so that we're returning A in only 1 place, but for optimizations, readability is more important. because we really want to make sure we're getting the right answer. So we've added in support for 2 new optimizations.

And presumably--now you can imagine how if we had a bunch of these we could just write them all out here, or maybe we could have a slightly more concise system for checking patterns and replacing them.

# Optimization Phase

def optimize(tree): # Expression trees only
    etype = tree[0]
    if etype == "binop":
        a = tree[1]
        op = tree[2]
        b = tree[3]
        if op == "*" and b == ("number","1"):
            return a
        elif op == "*" and b == ("number","0"):
            return ("number","0")
        elif op == "+" and b == ("number","0"):
            return a

        # QUIZ: It only handles A * 1
        # Add in support for A * 0  and A + 0

        return tree

print optimize(("binop",("number","5"),"*",("number","1"))) == ("number","5")
print optimize(("binop",("number","5"),"*",("number","0"))) == ("number","0")
print optimize(("binop",("number","5"),"+",("number","0"))) == ("number","5")

Optimizer Check

  • We'll definitely replace A times 1 with A. We wrote the code for that.
  • And we'll definitely replace A times 0 with 0.
  • This next one--0 times A--looks super tempting but if you switch back for just a moment, you'll notice that our optimizer is not symmetric. We're only checking for the B--the right position-- to be the constant number. That means we will not perform this optimization.
  • Similarly, A times 1 times 1 is going to depend a bit on what the input abstract syntax tree is, but at the end of the day, this will actually produce something like A times 1. We apply the rule once, but since we don't call ourselves recursively we're not going to notice that 1 times 1 is 1, and then also A times 1 is A. Currently, our optimizer can only do 1 optimization.
  • Similarly, here we'd really like to reason that 5 times 0 is 0 so A + 0 should be A, but our optimizer only checks 1 thing at the top level so it won't notice that yet.

Optimization Check.png

Fix It Up

This change may be hard to think about, but it's relatively simple to implement.

Our procedure was named "optimize." So now, instead of having A be just tree 1 and B be tree 3, we're going to call ourselves recursively on our subchildren, and then, only once they've both been optimized do we check for the pattern.

This will correctly handle A plus 5 times 0.

I may need 1 more return tree at the bottom, but that was assumed.

So it was as simple as adding 2 recursive calls before we check for the pattern.

A fuller answer would replace return tree with return (etype, a, op, b) at the end. The question only asked you to handle a+(5*0), but we would really like to be more general as well.

# Optimization Phase

def optimize(tree): # Expression trees only
    etype = tree[0]
    if etype == "binop":
        # Fix this code so that it handles a + ( 5 * 0 )
        # recursively! QUIZ!
        a = optimize(tree[1])
        op = tree[2]
        b = optimize(tree[3])
        if op == "*" and b == ("number","1"):
            return a
        elif op == "*" and b == ("number","0"):
            return ("number","0")
        elif op == "+" and b == ("number","0"):
            return a
        return tree
    return tree

print optimize(("binop",("number","5"),"*",("number","1"))) == ("number","5")
print optimize(("binop",("number","5"),"*",("number","0"))) == ("number","0")
print optimize(("binop",("number","5"),"+",("number","0"))) == ("number","5")
print optimize(("binop",("number","5"),"+",("binop",("number","5"),"*",("number","0")))) == ("number","5")

End