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
*computerphile...
The thing that really bothers me about talk about reverse polish notation and strict stack based programming is that nobody points out the obvious and equally important corollary: that normal polish notation corresponds to lazy graph reduction based programming. This is really important and relates to how real polish notation based languages like Forth use macros. Consider, the
:word. The:word starts a function definition in Forth. However, the:word is not used after a function definition, it is used before because it is a macro and needs to be sort of lazy. It just really bothers me that the equally important lazy graph reduction based reverse polish notation is never dwelt on when in fact it is really needed and important.I really think every programmer should write an infix to postfix converter sometime.
It's one of those challenges that pays off again and again over the years.
I could watch that guy teach me everything I already know without getting bored.
At my first year in uni when I was getting a handle on OOP I wrote a command line based calculator that took in-fix expressions, converted them to post-fix using the shunting yard algorithm, and then built a graph of the operators and operands from the RPN stack. That exercise and the "visualization" of full expressions in a tree did more for getting intimate with math than any teacher had done since 8th grade.
Folks interested in concatenative languages should check out the Factor language, which has great documentation and a lovely Smalltalk inspired, image based IDE. concatenative.org also has some great information on various languages in this group.
A very good explanation of the stack and RPN.
I'm looking forward to the followup videos on postscript – which is a really nice language.