We want to talk in some depth about this language called Postscript and how important it is
but it's in the very nature of Postscript that it uses a
notation called Postfix and
that in turn
relies for its execution
rnvironment on this notion of a stack.
Now we haven't covered stacks so far in computerphile
So before getting into postscript full-blown as it were I have got to tell you something about stacks
And we may be in a position to put this out as a separate film in its own right
Doing a bit about stacks first of all mentioning postscript from time to time
But it's important that you realize that stacks have a much wider application
in computer science than just Postscript
A plus B
What could be more commonplace than that in any language that you program then and that plus in the middle is an operator
It takes in this case a couple of operands it combines them together it does the addition
So these of course things like plus minus multiply divide raise [to] the power of our examples of arithmetic
operators, but they need the
Operands to work on
notice that the operator the addition comes in between the
Operands the a and the B and because it's inserted and inscribed inside the two operands
That's why this is called an inner fix
Use well, we're all very familiar with inner [fixit's] what we taught at high school and what we use most of the time
It's perfectly possible to write like that using a prefix plus. [you'll] say plus a b
That's prefix notation
Basically if you read it out, you're saying add together a and B
yeah, you're putting the plus at the start so it precedes the operands so it's prefix and
Just to make it clear that this is something you are familiar with sometimes if you have a language that defines
addition not so much with an operator, but with a
function call you say add add a comma b and the
Arguments or the operands are in parentheses? What happens if you write it so that it comes?
after the Operands ah we're here at last this is Postfix a
Gentleman who was a mathematical logician from poland called [triangular] spelling right? [I] think his name is pronounced on [and] like
[yanukovych] because that [hell] becomes a faint soft w sound with the crossbar he was a
Mathematical Logician and what he said was do you know if I write stuff out like this as either?
Prefix or PoStfix
It's so much easier [for] me [to] prove mathematical theorems with tell you [I] [know] [its]
Net result of all this was that people being unable to pronounce his name correctly and getting all the stresses and accents wrong
Decided that rather than pronouncing what they found hard they would call this
Polish notation
Now actually polish notation applies to using anything that isn't in fixed I've seen prefix notation being called
Forward Polish notation I've seen this a B-Plus
given its traditional name or of
reverse
Polish notation
But that's where it came from the gentleman who invented it
sometimes this is even
Abbreviated to a thing you may also have seen [RPN] reverse polish notation
It saves the interpreter or the compiler an awful lot of effort in actually
Executing the expressions that you write write down. Let's keep very simple again [2a] plus b
If [I] write a plus b
Like that and let's say, we'll see what the C language compiler would do to it
What would they have to do to it? How would it translate it into binary?
I don't want to do strings of meaning as binary with you
But I'll tell you what I will do I'll try and translate [that] as if I was the C compiler into assembly code
now the assembly code will depend on whether on an arm chip and intel chip or whatever and
Some of you will know the GCC compiler
gives a flag on there as well [as] an option which says show me the assembler code that you would produce for this and
Here goes. I'm making this up it might not correspond to any particular assembly you know, but I hope you'll get the idea
Load register R1
[with] a
The compiler will store off the values of a and b in memory, but as you all know before they can be added together
They've got to be lifted into the central processor unit of the computer
And then when they're added you call up the arithmetic unit inside the CPU load register command
Register - this time with B
add
What is in register [1] - what is in register 2 and put the answer in Register 3?
Roughly similar to the last assembler language. I taught which was for the arm chip don't castigate here forgot some of the details wrong
But I hope that's just to give you the idea
Just look at what it has to do it has to get a get b
And do the addition
You have to do it that way because you can't do anything with something until you get them first and lift it into the cPU
And put it in registers
Just look at this what it does it gets a into a register it gets B into another register. It adds them together puts
the answer somewhere in the third register a
B add a [B] [plus] its Postfix notation
For even more complicated things it has to convert it into reverse polish
explicitly or implicitly in order to decide what code to generate and
What the cache of it's really loved about this absolutely [thought] it was ace when he discovered it is the following
Suppose we now write a plus b. Star C. Which one of these addition or multiplication
operators takes precedence answer it's the multiply the multiply must be done first everybody knows that and
If you don't want it to be done first you have to
Deliberately force it to be done the other way
So let's be clear this one says multiply the b by C
Because multiply is more powerful than ad and when you've got the answer there add it to a this one
Says I want you to add a and B, and then multiply by C. What will cash of each said this is fantastic
He said in my proofs
I hate parentheses they mess things up
But you realize that you don't have to parentheses because in reverse polish
this comes out to be a b c
Star Plus
Whereas this one comes out to be a b plus C
Star [I'm] telling you that a plus [b]
Times C or to translate that in Postfix reverse Polish whatever you want to call it
The reason it does you've got to be careful here
Let me remind you of what [you] will all have been taught at high school
Is that multiply is a stronger operator than add?
multiplication takes precedence as the phrase goes
so in here to get the right answer you multiply b times C first of all and
Then you do the add because it's of lower precedence
So if all these are fives a being say they all represent the number 5 you get 5 times 5 is 25
25 plus 5 is 30 [the] way that this is represented in a reverse polish is as follows a
[b] [C]
[multiply] [+] and the way that this works is [that] when you get an operator it is going to apply to the each foo
immediately
Preceding operands because that's what those fix is all about the more you look at that the more you realize
And computer scientists when they looked at reverse polish notation in the late forties and early fifties
Just thought all their christmases have come up once not only was this what we need did for
Compiling stuff and getting use of usage of registers and cpus absolutely, right?
But also, it related very much to a data structure that they're in the process of realizing its power
the stack
Now there's a lot of computer science depends on stacks
[I] sometimes think that stacks and trees is just about all computer science is about but it's the first time we've mentioned them
I think on computer file, so I'll try and go very very gently with you about this. This is a stack
Why is it a snack? It's a start because you can [so-called] push things on it
I'm going to push something else on to the top of the stack
Notice that I can only access things by taking them off this Rod
So therefore, it's a last thing in first thing out
Storage mechanism, I'm going to push the light
Able to stack with three objects on it
The only easy one to get out is the top of the stack and if I take it off like that?
That's called popping a stack
So you push it on the top and you pop the top of the stack like that?
Let's be clear in all of this [word] [that] I shall be doing now with disks and stacks
I'm using these disks here to be of
different sizes
Simply so you can see which is which on the stack. I'm producing. There's no
Implication that the biggest disk represents the biggest integer or anything like that
I'll try and be clear as I as I go along as to which one represents a which one represents B
Which one represents C or maybe which one represents some partial?
Intermediate result William multiplied two things together or whatever so don't get mesmerized
Too much by the size of these [things] this is a case where size doesn't matter [you've] just got to remember which is which
Well if we're pushing and popping then how does that relate to this?
reverse Polish this Postfix for that expression let's call this big one here the a
And on to push a so the rule then for interpreting reverse polish notation is if it's an operand push it on the stack
Be is that an operand yes, push it on the stack
See another operand push it on the stack
next one
multiply our well the rule about interpreting reverse polish on a stack is to say if
You hit an operator
Think to yourself how many operands does this got then take them off the stack those two operands in this case?
Do the operation and push the answer back so I take off C and I take off it B
Multiply them together so I've got a b times C intermediate result now which I represent with this smaller one here
remember this one is the b times C sub of result and
Having done that multiply the rule is [you] push the intermediate answer back on the stack?
Coming to the end of the reverse polish string here. You'll see as a final plus. What does plus mean plus means it's
Expects two operands, and we're fortunate we've got it, right
There's two things on the stack as our original a and as the intermediate result that we've pushed back on of doing B
Times C. So for the plus you take them both off
You do an ad like that
you produce the final answer which is this very small disk here and
In postscript and in most of the systems when you've got the final answer you leave it at the top of the stack like that
so the answer for a plus b times C has been
evaluated using a stack and reverse polish and the final answer has appeared on top of the stack, so
[for] interpreted languages with expressions of this sort
reverse Polish
Postfix is its other name don't forget and stacks. They just go together perfectly
They were built in heaven for one another without a question
You've got a third a third a third we have coped with that
We've cope with that if you get a choice of either that pair or that pair of thirds
[it] doesn't matter which actually okay, so now we've got one sort of list