So, in the last lecture, we discussed the requirement for code optimization, types of optimizations and we also discussed the procedure for building a control flow graph. Today, we will continue with our discussion on value numbering and its use in local optimizations. To do a bit of recap, so here is the example that I showed you in the last lecture. This is a basic block containing 10 intermediate code statements and this is the directed acyclic graph corresponding to this basic block. The most important feature of this directed acyclic graph is that it can enable several optimizations. For example, here is 4 star a which is actually a constant because a is a constant. So, this constant propagation and constant folding can be performed using the directed acyclic graph representation. It cannot be so easily performed using the quadruple representation. Here is an expression i star j and here is another expression e star j, but both are equivalent because e receives the value of i during this execution. So, t 3 and t 1 are identical in value at all times and we can use t 1 instead of t 3 and delete quadruple number 8. So, this is called common sub expression elimination and this can also be performed using the directed acyclic graph representation. But, as I explained in the last lecture it is you know useless to try and build the directed acyclic graph using link data structures because every time we want to locate some node we will have to start from the top of the directed acyclic graph and search the entire graph as such. So, this is a waste of time the technique that is normally used is called value numbering. So, what we really do is we assign numbers to expressions in such a way that two expressions receive the same number if the compiler can prove that they are equal for all possible program inputs. We use hash tables then you know hashing techniques rather in this value numbering optimization and we assume that there are quadruples with binary or unary operators. So, there are three tables hash table value number table and name table. So, and the value numbering technique can be used to eliminate common sub expressions do constant folding and constant propagation in basic blocks. We can also take advantage of the commutativity of the operators addition of 0 multiplication of by 1 etcetera. So, here are the three you know data structures that we are going to use in our technique the first one is the hash table entry. So, the table will have records of this type the first field in the record would be the expression itself and the second field would be the value number. So, what we do is you know compute a hash value for the expression using a suitable hashing function. The hashing function must have you know must take into concentration not only the two operands of the expression, but also the operator itself the type of the operator and once we get a hash value we search the hash table and at that particular hash value we insert the expression and also a unique number called the value number itself. So, value number is nothing, but a unique number assigned to each expression. So, we are going to assign value numbers using a counter the second table entry is the Valnum table entry. So, this is the Valnum table and the record structure is shown here. So, this is indexed by the hash value of the name. So, there is name and then the value number. So, the difference between these two is that this stores expressions and this stores names. So, we cannot use the same hashing function for both expressions and names and that is the reason why we are using two different tables and two different hashing functions. The third table is the name table its entry is shown here. So, the entry has one field known as the name list another field known as the constant value and the third field known as the constant flag. So, this table is used to store the constant values of certain names. So, if there is more than one name which actually stores the same value then it is formed into a list. So, as I have written here the first name on the name list is the defining occurrence and it replaces all other names with the same value number with itself or its constant value. So, if there are five names here we really need to use only one of them in all places and the other four can be deleted from the program. If there is any computation associated with that name that can also be deleted along with it. So, if the name does not have a constant value associated with it then the constant flag will be false and the constant value a field does not have any relevance. If it indeed has a constant value then this will be said to true and the constant value can be read from this field. So, let us understand the algorithm using a you know an example program. So, let us assume that this is the high level language program that is given to us. So, a equal to 10, b equal to 4 star a, c equal to i star j plus b, d equal to 15 star a star c, e equal to i and then again c equal to e star j plus i star a. So, when we generate intermediate code you know for this sequence for this sequence it obviously it will be split into many instructions. For example, we may have a equal to 10 then b equal to 4 star a as it is. So, now the i star j goes into a temporary and then we have c equal to t 1 plus b then again 15 star a goes into another temporary and d becomes t 2 star c then e equal to i remains as it is t 3 is e star j t 4 is i star a and c becomes t 3 plus t 4. So, we have these 10 quadruples in our basic block. So, let me explain how the value numbering technique is applied on this program. So, we start with the first quadruple. So, remember that there are 3 tables the first one is the hash table for expressions, the second one is the name table for names, the third one is the rather the second one is the Valnum table for names, third one is the name table for constants. So, this is a equal to 10. So, the quadruple after value numbering remains the same what we do is enter this a into the Valnum table and also the name table because this is a constant and the effect of that is seen in the second quadruple itself. As soon as we have 4 star a you know and of course, I forgot to mention one thing. So, a is a new name that we have encountered. So, as soon as we enter it into the hash table we are going to generate a new value number for it and assign a that particular value number. So, when we have b equal to 4 star a the first thing we do is search for a in the Valnum table it is indeed found there and then you know we are using its value number we can search the name table and find the value to be a constant that is 10. So, immediately we know that 4 star a can be computed at compile time itself you know it does not vary during execution. So, 4 star a can be computed as 40 and the quadruple can be rewritten as b equal to 40. Now, b is a new name. So, we generate a new value number for it enter it into the Valnum table and assign it a new value number. So, this is the second thing that happens then we have the third one i star j similarly i is you know i and j are new names and they need to be entered into the appropriate entries into the table i star j is a new expression. So, we need a different value number for the expression also. So, the important thing is the name t 1 and the expression i star j will be assigned the same value number. So, whenever we find t 1 we know it is i star j and whenever we find i star j we know that it is t 1 itself and rather we can use t 1 for that i star j. So, now this quadruple remains the same the next one is c equal to t 1 plus b. So, t 1 is already in the tables b is also present in the tables we find that b is a constant it is actually from the name table. So, we can rewrite the quadruple as c equal to t 1 plus 40 and this new quadruple is now hashed into hashed and then entered into the hash table. The same thing happens with t 2 equal to 15 star a. So, a is found as a constant. So, it can for 15 star a becomes 150 and the quadruple is rewritten t 2 star c becomes 150 star c e equal to i remains the same the important thing here is e and i now get the same value number i had the same value some value number before. So, now e also gets the same value number now when we search for e star j in the quadruple t 3 equal to e star j the value number of e is the same as the value number of i and value number of j already exist. So, in fact we end up hashing e star j into the same slot as i star j because the value number of e is the same as the value number of i. That means this particular you know once the value number is the same the expression remains the same. So, essentially we can rewrite this t 3 a quadruple as t 3 equal to i star j. In fact, we can even delete this quadruple because all occurrences of t 3 can be replaced by t 1 you know because t 1 is also i star j then t 4 becomes i star j which is i star 10. And finally, we have another occurrence of c defining occurrence t 3 plus t 4 the old c is not relevant anymore. So, this c is given a new value number and entered to the tables and instead of t 3 we are going to use t 1 and t 4 remains as it is. So, 5 this particular t 2 equal to 150 is not necessary anymore because it is only use of t 2 was only in d equal to t 2 star c. And once we have expanded t 2 to 150 this quadruple is unnecessary this of course, is a common sub expression i star j has already been computed. So, we do not have to compute i star j again and we can use t 1 in place of t 3 we have already done that. So, quadruple number 8 can also be deleted. So, this is how we catch common sub expressions and this code is red code because we never use the value of t 2 again we can eliminate such red code and eliminate common sub expressions as well. And in the meanwhile we have all this has been possible because we propagated the value of a to these quadruples it was propagated to this place and this place and of course, this place. And here for 4 star a and 15 star a we also did constant folding that is evaluation of the expression at compile time. So, what I have written here is a record of what I just now explain. So, a equal to 10. So, a is entered into the valum table with a v n of say 1 and into the name table with a constant value of 10 then b equal to 4 star a. So, a is already found in the valum table its constant value is 10 in the name table. So, as I already explained we have performed constant propagation. So, we have evaluated 4 star a. So, that means we have performed constant folding. Now, b is entered into the valum table now a new value number say 2 is given to it and into the name table with a constant value of 40. T 1 equal to i star j. So, as I already said i and j are entered into the tables i star j is entered into the hash table and T 1 is entered into the valum number table with the same v n as i star j. Similar actions continue till e equal to i now e gets the same value number as i. So, in e star j e you know we have e and i with the same value number. So, e star j is nothing, but i star j i star j has already been entered into the table. So, we have got a common sufficient when we search for e star j. So, from now on T 3 it can be replaced by T 1 and this can be deleted. So, this of course T 3 plus T 4 already exist and have a new value numbers. So, T 3 plus T 4 is entered into the hash table the assignment is to c. So, c gets a different value number and the old c should be killed. So, quarter pulse are enumbered after the deletions. So, let me show you the tables after we have completed all the operations. So, i star j was entered into the hash table you know let us begin here. So, a got a value 1, b got a value 2 then we had i star j. So, a e and j got values of 3 and 4 then i star j was entered into the table with the value of 5. So, T 1 was assigned i star j. So, it gets a value of 5 then we had c. So, it got a value of 6 which is the same as T 1 plus 40 then I will explain 11 very shortly. So, T 2 gets a value 7 and this 150 star c gets 8 and d also gets the same value because it was an assignment. Then observe that e has the same value number as i. So, e has the same value as 3 which is i's value number. T 3 has the same value number as T 1. So, that is 5 and finally, T 4 has the value number 10. So, i star 10 has the value number 9 and i T 1 plus T 4 has the value number 11. So, this is how the value number table is used for the various optimizations. Now, I mentioned that it is possible to exploit the commutativity of operators. So, in other words if we have an expression i plus j in the hash table or let us say j plus i in the hash table and we try searching for the other. So, we search for an expression i plus j it fails then try searching for j plus i may be j plus i was already present in the table and i plus j was not present, but plus is commutative. So, whether we use i plus j or j plus i the value remains the same and therefore, we can conclude that i plus j and j plus i are equivalent in all cases. So, searching for one of the two forms and then using the value number of that particular expression which was found in the hash table will not change in the value or rather the result of produced by the program. So, they can be deemed as equivalent and given the same value number. So, we do not even have to enter it into the hash table. So, because we always search both i plus j and j plus i in this hash table if one of them is found we assume that there is an equivalence. If there is a quadruple i plus 0 it can be replaced with the quadruple x equal to i and similarly, the quadruple j star 1 can be replaced with j. So, the assignment becomes y equal to j. So, in both these types of replacements the value number of x becomes the value number of i and value number of i becomes the value number of j. So, quadruple x host left hand side variables are used later can be marked as useful all other unmarked quadruples can be deleted at the end. So, I also mentioned that c gets a new value number 11 because it was assigned again the old value of 6 is not used anymore.  So, the value number 6 never be used again. So, it should be the value 11. So, that is how you know there could be possibilities of i and j getting changed you know. So, and then we recompute the value of i star j. So, in such cases the second occurrence of i star j cannot be the same as the first occurrence. So, as soon as there is a there is some you know i star i and j are changed. So, we need to make sure that we do not use the old values of i star j. So, that is another thing that we need to keep in mind when we are using the value numbering technique. Of course, sometimes it happens automatically as soon as the variable i is reassigned value the old value number of i is thrown away. So, we will never hash into the same location as the old value of hash value of i star j. So, that is in some sense automatically taken care of if we do this killing for the old value of c. The next important thing is how to handle array references. Scalar variables do not pose this problem at all, but consider the assignment of arrays. So, we have the first quadruple x equal to a i and then we have another quadruple following it a j equal to y. So, it is not necessary that these two are in the same you know immediately after one another there could be other quadruples between one and two which have nothing to do with either x or a. So, in that sense this is the next quadruple which is relevant to this first statement a j equal to y suppose i and j are the same. So, then this quadruple really is a i equal to y that means the old value of a i has changed. So, when we take another quadruple z equal to a i and suppose i and j were the same we really cannot use the old value of a i which is available in x. So, in other words we cannot replace the above sequence by x equal to a i j j equal to y and z equal to x. So, we are trying to do common sub expression elimination here by not using a i by rather using reusing the value of a i which is present in x, but this is illegal because most of the time we do not know whether i can be equal to j or not equal to j. If we definitely know that i and j cannot be the same then we can use this sequence, but if we have no idea whether i and j are equal or not equal then it is not possible to rewrite the sequence in this fashion. So, the effect is when a j equal to y is processed during value numbering all the references to r a a so far are searched in the tables and are marked as killed. So, there could be many such references in above this as soon as we get a j equal to y this is an assignment to a. So, there will be many references to a i a f k a f l etcetera above this a j equal to y all these references will have to be killed they cannot be reused anymore because we do not know whether j equals any of those index values which have occurred earlier. So, in this sense the x equal to a i quadruple will also be killed once it is killed the automatically z equal to a i will not replace it as will not be replaced by z equal to x. So, as I already mentioned the fresh table entries have to be made for z equal to a i and unless we know i is not equal to j we cannot really do this comma section elimination. A similar problem arises when we handle pointers and also procedure calls. So, first let us look at pointer references. So, there is x equal to star p and then after a couple of statements which do not affect x or p we have star q equal to y. So, suppose p and q could be pointing to the same object. So, in that case we really in effect have star p equal to y which implies that the object p is pointing to has changed. Therefore, even though x stores the object pointed to by p we cannot say z equal to star p becomes z equal to y rather z equal to x. So, in this sequence is illegal that is because in most cases we have no idea whether p and q are pointing to the same object or not pointing to the same object. If pointer analysis has been carried out then the result of that pointer analysis may affirmatively say p and q do not point to the same object. So, in such a case this sequence can indeed be replaced by this sequence otherwise we cannot. So, if we do not know whether p and q point to the same object as soon as we process star q equal to y all the table entries created so far will have to be killed. So, p and q can point to any object in the basic block because we have no idea what p and q point 2. So, we must assume that it can point to any object in the basic block. So, every one of the entries in the table up to this point will have to be marked as killed that means the table is automatically emptied and when we use when we process z equal to star p the killed quadruples are not used for commons of expression elimination. Fresh table entries have to be made for z equal to star p and of course, as I already said if we know that a priori which objects p and q point 2 then table entries corresponding to only those objects need to be killed. We do not have to kill all the objects all the statements and all the objects in the table. Procedure calls are handled in a similar way they also have similar side effects for example, if we did not analyze the program the analysis is called data flow analysis. We need to assume that a procedure call can modify any object in the basic block how can this happen. Suppose we have call by reference parameters and we change them call by reference parameters when they are changed the originals also get changed. So, the variables which are accessed in the basic block will also or anywhere else you know with the same name as the call by reference parameter will get changed. Similarly, if there are global variables within procedures and the global variables are changed within the procedures they will also affect the other variables of the basic block because global variables may be used anywhere in the program they will also be used in the basic block. So, all these will affect the variables in the basic block. Why are we looking at only the basic block the reason is the value numbering technique restricts itself to the basic block. So, its effect will not percolate to other basic blocks. So, we do not have to worry about we are not detecting common sub expressions across basic blocks at this time. So, we do not really have to worry about the effect of all this beyond the basic block, but if the procedure call can be separated into a different basic block then this problem automatically gets eliminated because we do not consider effects across basic blocks. If that is not so, if the procedure call is in the midst of a basic block then all the table entries created so far for that basic block will have to be marked as killed and no common sub expressions can be detected and used. Therefore, usually we make a procedure call into a separate basic block along with its parameter evaluation and so on. So, now having done this local optimization on basic blocks. So, is it possible to actually process a sequence of basic blocks and say look let me do you know common sub expression elimination value numbering etcetera on these extended blocks. It is indeed possible, but before that we will have to define what we mean by an extended basic block. A sequence of basic blocks B 1, B 2 etcetera B k such that B i is the unique predecessor of B i plus 1. So, if we have B 1 and B 2, B 1 must be the unique predecessor of B 2, B 2 must be the unique predecessor of B 3 etcetera etcetera. And B 1 is either the start block or has no unique predecessor. So, then you know it must be the start block or it should have no unique predecessor. So, we will see what that really means. Extended basic blocks with shared blocks can be represented as a tree. I will show you an example of doing this as well. And shared blocks in extended blocks requires coped versions of the hash tables, name tables and valum tables. The new entries must be purged and change entries must be replaced by old entries. So, we use a pre-order traversal of the extended basic block in order to perform the value numbering. So, now let me give you an example of extended basic blocks and then continue. Here is a flow graph. So, there are many basic blocks start then B 1, B 2, B 3, B 4, B 5, B 6, B 7, B 8. So, let us form extended basic blocks from this particular flow graph. So, we start at the first basic block and then we go to the next basic block which it leads to which is B 1. And now start and B 1 are indeed in the same extended basic block. Now, let us try going to B 2. Unfortunately, B 2 does not have a unique predecessor in B 1. It also has another predecessor which is B 7. So, therefore, we cannot include B 2 into the same extended basic block as start and B 1. So, that is why we have separated start and B 1 into a different you know extended basic block. So, now we again begin at B 2. We go to B 3. B 3 has a unique predecessor B 2. Then we go to B 5. B 5 has a unique predecessor B 3. We go to B 7. B 7 unfortunately has other predecessors as well. So, our search for extended basic block must blocks which can be included in the extended basic block stops here. So, we have B 2, B 3 and B 5 as another extended basic block. So, it is listed here. So, if we take the other path we have B 2, then B 3, then B 6. Again it has a unique predecessor B 3, but we cannot go to B 7 for the same reason that it has many predecessors. So, B 2, B 3 and B 6 will be another extended basic block. Then we have B 2, B 4 and we cannot include B 7 because of the same reason that it has many predecessors. So, B 2 and B 4 will form a separate extended basic block. Finally, B 7 and stop will form the last extended basic block. So, we have five such extended basic blocks out of which start comma B 1, B 7 comma stop do not share blocks with any others. So, these two are separated as two different extended basic blocks. Now, the other three share blocks for example, B 2 is shared and then B 3 is shared. So, we can actually represent these extended basic blocks using a tree structure. So, B 2, B 3, B 5 is one extended block, B 2, B 3, B 6 is another extended block. So, they share not only B 3, they also share B 2 and B 2 is shared between these two extended basic blocks and also this B 2, B 4 extended basic block. So, this forest of trees represents the set of extended basic blocks that can be formed out of this flow graph. How do we apply value numbering on such trees? That is our question. Applying value numbering on this tree which consists of start and B 1 is straight forward. We really can merge all the information in rather quadruples in B 1 with start and apply hashing. The same applies to B 7 and stop as well, but the middle one is a little more complicated. We must perform a pre-ordered traversal starting from the root of the tree. So, we will start at B 2. Now, the old value numbering technique can be applied to the contents of B 2. Absolutely no problem there because it is just one single basic block. After the processing of B 2 is complete, we go to B 3. Now, because B 3 has a unique predecessor B 2, there is nothing wrong in detecting common sub expressions using an information and tables available in from B 2. So, B 2 and B 3 in some sense can be combined together to give you more benefit. So, we apply, we just extend the hash tables and other tables of B 2 by including the entries of B 3 as well, but a lot of caution here we may want to undo this effect little later as I will explain. So, we must keep these entries separated from the entries of B 2. So, B 2 and B 3 together now you know detect common sub expressions. So, there may be something here which is reused here. So, we do not have to keep that quadruple anymore. So, once the processing of B 3 is completed, we go to B 5. The same argument holds here as well. The quadruples of B 2 and B 3, the tables of B 2 and B 3 can be reused to give advantage in B 5 as well. So, expressions which are available in B 2 and B 3 can be reused here. So, common sub expression detection becomes even more effective. So, we extend the tables of B 2 and B 3 with the entries of B 5, but I already mentioned that we need to keep them separate even though virtually logically they are connected to the tables of B 2 and B 3, we will have to mark them as new entries. The reason is once the processing of B 5 is completed, we go back to B 3 and the pre-order traversal now takes us to B 6. So, that means the effect of B 5 will have to now be undone. The reason is the effect of B 2 and B 3 can be seen in B 6, the sub expressions of B 2 and B 3 can be still reused in B 6, but the tables of B 5 are not useful in processing B 6. Obviously, the control in the control flow graph will either go from B 2 to B 3 to B 5 or go from B 2 to B 3 to B 6. It will never go from B 5 to B 6 and therefore, the tables of B 5 will have to be thrown away, the tables of B 2 and B 3 alone will have to be kept and if anything has been marked as killed in B 2 and B 3 that effect will have to be undone and the tables which were present just before the entry to B 5 took place will have to be restored. Now, we can process B 2, B 3 and the entries of B 6 can take advantage of these. So, we do that and then we the pre-order traversal goes back unwinds goes to B 2 and then it will visit B 4. Now, it is time to undo the effects of not only B 6, but the effect of B 3 as well. So, the entries of B 3 and B 6 will have to be thrown away, the changes which were done to B 2 because of the processing of B 3 and B 6 will have to be undone. The old table which was present just before the entry to B 3 took place will have to be restored and then we enter B 4 process B 4 completely taking advantage of the entries of B 2. So, this is what I meant here when we said the shared blocks in extended basic blocks required scoped versions of tables. So, these are very similar to the scoped versions of symbol tables which we used when we processed blocks nested blocks and nested procedures. So, now the function visit ebb tree for you know does the value numbering on these extended basic block trees. So, it is quite simple. So, whenever we enter the enter a particular node and function visit ebb tree is called on that node, the new names will be entered with a new scope into the tables. When searching the tables we always search beginning with the current scope and move to the enclosing scope. In other words when we are processing B 5 we must search the tables for B 5 first and then the tables for B 3 and then the tables for B 2. So, this is very similar to the processing involved in symbol tables for lexically scoped languages. Now, so we call value number e dot b. So, process the block e dot b using the basic block version of the algorithm. So, let us assume that this does that. Now, these two are nothing but the pre-order traversal lines. If e dot left not equal to null then visit ebb tree on e dot left and then the right one if e dot right not equal to null visit ebb tree e dot right. So, after these two left and right sub trees have been visited we remove the entries for the new scope from all the tables and undo the changes in the tables of enclosing scopes. So, the main calling routine simply says for each tree t do visit ebb tree t. So, we just do this for all the trees in that forest and that completes the value numbering. So, this brings us to the end of the lecture on local optimizations. So, welcome to the lecture on machine code generation. So far in the previous lectures we have studied you know lexical analysis syntax analysis intermediate code generation semantic analysis and then we also saw some of the simple optimizations which can be local optimizations which can be done on the intermediate code. So, now it is time to understand how machine code can be generated from the intermediate code and after this long session on machine code generation we will move on to the machine independent optimizations and so on and so forth. So, in this lecture we will first understand the main issues in machine code generation. We will look at a few samples of generated code consider very simple code generators two of them to be very precise and then we consider the very important topic called optimal code generation which you know in fact generates the best possible code. We study three types of optimal code generators. The first one is the classical code generation algorithm due to Seti and Ullman dating back to 1970. The second one is the dynamic programming based algorithm again this is this dates back to 1976 or so, but it is still in use today. The third is the tree pattern matching based algorithm for machine code generation which uses dynamic programming and also tree patterns and after this we will understand how to generate code from directed acyclic graphs. The reason is we definitely you know do local optimizations using directed acyclic graphs. So, what we get after the optimization of the basic block is still a DAG. So, we must know how to generate machine code from DAG and then we will look at a special class of optimizations called people optimizations which are carried out on the machine code. So, here what exactly is machine code generation it is a transformation it is a transformation from intermediate code to machine code. So, when we say machine code machine code could be in binary form or it could be in assembly form this really does not matter to us because both assembly code and binary code are equally useful. It is just that if we generate assembly code we need to use an assembler to transform the assembly code to binary whereas, if we want to generate binary code directly then we may end up doing all the work of the assembler itself. So, in our lectures we will assume that we are generating assembly code and not binary. Of course, as usual we will assume quadruples and the control flow graph to be available to us. So, that we can process them to generate code. So, that is the transformation we talk about intermediate code to machine code. So, in this transformation which instructions should we generate the problem is for some of the quadruples it is you know definitely correct to have more than one sequence of machine code in this transformation. For example, take a simple increment a equal to a plus 1 it increments the value of location a. So, for this quadruple we may actually generate a single machine instruction called increment a if such an instruction exists in the machine. In some machines increment operation cannot be carried out on memory it can be carried out only on registers. So, in some other machines there may be no instruction for increment at all. So, in such machines we may want to generate load a comma r 1 this is the risk architecture style then either add 1 to r 1 or increment r 1 then store r 1 to a. The reason we had to do this was the machine performed all the arithmetic only on registers the only operations from and to memory were the load and store. So, we had to bring the operand into the rather the a there is nothing, but the operand of the right hand side we had to bring it into a register alter its value and put it back into the location. So, one of these you know obviously this decision will be based on the machine. So, this is 1 to many mapping which mapping is really good for us will have to be chosen by the code generator. One sequence actually may be faster than the other sequence in certain cases in this case of course, increment a if we had both options we would want to generate increment a because this is just one instruction and much faster than executing three instructions. So, the implication is there is a cost attached to the execution. So, if we are able to take care of compute the cost of the instructions which are generated then or the rather may be generated we may be able to make a decision regarding the sequence that is to be generated. The next one the next issue is in which order should the machine instructions be emitted. So, some orders may use fewer registers and or may be faster. So, in such a case the again the cost implication comes into picture and the number of registers used etcetera comes into picture the compiler would like to evaluate these possibilities and do its best. The next issue would be which registers are to be used in the machine code that is generated. So, optimal assignment of registers to variables is very difficult to achieve. In fact, the problem is very famous it is called as the register allocation problem. So, this will say certain variables it will the allocation algorithm will decide on which variables should be placed in registers and which variables need not be placed in registers. So, optimal assignment of such registers is such you know registers to variables is a very hard problem NP complete. So, there are heuristics which can be used for that purpose. We will study these heuristics at a later point in time. Should we optimize for memory time or power? So, I already mentioned in the lecture on optimization that we can optimize the space the time or energy it power consumed by the program. Is the code generator easily retargetable to other machines? The problem is code generation is very tricky and very difficult. So, if we are able to actually write a specification of the machine for which we want to generate code and the code generator can be produced automatically from the specifications of the machine that is the best scenario. So, in such a case we simply have to you know have a code generator generator for which you know processes the different machine specifications and then easily we can generate code generators for any type of machine. So, in the absence of that we will end up writing machine code generators for each one of the machines by hand. So, let us look at some of the samples of generated code to begin with I have listed actually the more complicated types of statements here straight forward quadruples such as a equal to b plus c are very easy to handle. So, let us look at the more complicated ones such as involving arrays and pointers and conditional statements and so on. So, this is a quadruple b equal to a i. So, first of course, this means we will have to take the ith element of the base address a from the base address a. So, remember this a i it does not mean it is a single dimensional array. We have already understood how to translate you know multi dimensional array references to single dimensional memory reference. So, this a really can be the base address or the starting address of a multi dimensional array it need not be the starting address of a single dimensional array, but for our purpose it really does not matter at this point it is a sequence of bytes and we simply want to take the you know appropriate byte from starting from the address a and rather the appropriate 4 or 8 bytes from the starting address a and then put it into b. Let us see how the machine code for this looks like. So, we load i into the register r 1 and then we multiply the value of i by 4 the reason is we are assuming that every entry in the array a corresponds to 4 bytes. So, we say r 1 equal to r 1 star 4 then we use indexed mode of addressing. So, starting from the base address a this is the index a of r 1 comma r 2. So, take the contents of a plus r 1 and put it into r 2 finally, store r 2 into b. So, we have to generate 4 instructions just for this one intermediate code. The same is true for x j equal to y as well we have load y comma r 1. So, no problem load j comma r 2. So, that is the left hand side part then multiply r 2 by 4. So, that takes us to the appropriate place within the array where we can load y and then store r 1 comma x of r 2. So, x of r 2 gets r 1. So, this is the indexed assignment. So, this is the sequence of instructions generated for just one intermediate code here.  Star glue equal to y is similar.  So, again this is the indirect mode of addressing.  So, this is the sequence which appropriately you know performs gives you the same effect as if x less than y go to l. So, now let us look at slightly more complicated scenario involving activation records static allocation dynamic allocation sub routine jump etcetera etcetera. The three address code has say code for this is the code for function f 1. So, this is these are the two functions that we have. So, within the code for function f 1 we have some action code segment a number of instructions in intermediate code and then there is a procedure call. So, in this example we are concentrating on the procedure call and activation records etcetera the rest of the intermediate codes are not very important to us at this point. So, there is a call f 2. So, we are calling this function f 2 action code segment 2 after the return we execute this piece and then halt code for function 2 has an action code segment and then a simple return. So, we are looking at a static allocation and we assume that there are no jump sub routine instructions in the machine instruction set. So, we will have to actually do a jump. So, because we have to do a jump we also need to store the return address in the activation record itself. So, the activation record is a static activation record in other words it will never change you know the same static the activation record is used for all invocations of the function f 1 and f 2 no recursion is possible with static allocation. So, this does not create a problem for us. So, here is the first one in the offset 0 we starting from the top we store the return address then we have a data array a we have the variable x and variable y. So, totally 48 bytes are needed for this f 1 similarly for f 2 we require 76 bytes return address there is a parameter as well then another an array and a variable m. So, here is the code that may be generated by a compiler code for function f 1. So, say we start from address 200 then there is the code for segment 1. Now, it is time to call the function. So, we have to you know move hash 264 comma 648 264 is nothing, but the address of the return address where we need to return then the parameter is moved into the location 652 which is the place for the parameter then we have a jump which is the call to this you know this 400 is the function right and then we have in this function when we want to return we take the return address from the stack and then jump at 648 648 stores the return address. So, we come back to this action code segment for 2 execute it and then we halt. So, and here is the activation record format for f 1 600 to 647 and then the action activation record for f 2 648 to 723. So, we will stop the lecture here and continue in the next class. Thank you.


And Michael, doesn't this get back to why so many parents feel like they have to remove their kids from public schools? You've got disruptive and even potentially violent kids that have really no repercussions. How can any normal kid learn right after a while? They can't. Yeah, you can't. And we had a situation in our family where a child was actually being bullied and she got in trouble with the principal because of the particular dynamics involved. It was just a very unfair situation. Discipline has become kind of a four-letter word in a lot of schools because of the fear of overuse of it with certain types of folks. And it's hurting everybody in the classroom if it's disrupted to learning.


It's a video that I've never done before. Abby and I didn't used to do them but I had such a successful January that I thought I would share all the things that I made in January. Some of these things I've already done videos on so I'll be playing some of that footage throughout this video to show you what it looks like on other ones that I haven't filmed or I don't plan on filming. I'm going to throw on my mannequin and you can see what they look like there but I thought it'd be a fun way to kind of recap the month and show you all the things that I have been making. So the first thing is the top that I'm wearing and you can't see because the the shot is so tight but it's got the amazing sleeves that I am just so in love with and this is McColl's 7542. It has one, two, three, four other versions and honestly I want to make all of the other versions. They're all so cute. I don't know if I'm brave enough for B which has these very dramatic sleeves but I think it could be a lot of fun in the right fabric and if I'm going to the right place like I probably couldn't eat dinner in those because your sleeve would just be in your food the whole time but this top also can easily easily easily become a dress or a peplum top so don't feel like it's just going to be a top. I might make one of these into like a sheath dress. I can see myself combining the tunic bible tunic dress with these sleeves that would be a lot of fun but anyways we're not talking about plans we're talking about what I actually made so this fabric is I think I don't I'm so bad about writing down the fabrics that I get at Joann's. I got to get better at at least taking a picture of the end of the bolt but I think it's like a poly lycra it does have some stretch to it but this was in their clearance section so I got it for like 250 a yard and made just like something that I can wear to work with just black pants and some ballet flats super simple quick outfit that has like some pizzazz to it because I love those sleeves so so so much. The next project you guys have all seen by now it looks like I've got makeup on it darn it is the toaster sweater by sewhouse seven in cable knit from cali fabrics so yeah I sewed up this project early early this month it was the sew my style project for january so I got a head start on it I'd gotten this fabric from cali fabrics probably in december it's sold out by now you cannot get it anymore but it's a nautica cable knit and it's backed with like a cotton so it's very very stable um so yeah I love this I've worn it um a couple times obviously because the makeup got on it um and yeah it's it's been really great I haven't got a ton of compliments on it but I think that's because it sort of just looks so ready to wear that people don't assume that I made it you know what I mean like it just looks like some look so much like something you would buy in the store that they that no one really says anything about it I will say the downside to the toaster sweater and a knit like this is that when it rolls over your neck just the friction of it rubbing against your neck there is causing it to pill a little bit and like I said when I because I put my makeup down this far on my neck I have to remember when I wear this to not do that that's why I've gotten makeup on it um but other than that it's incredibly wearable and I really love it it's very very warm which I haven't needed a ton of lately because we just haven't had any cold weather but for those couple of days that we have it's been really nice um this one I've just worn with jeans I might have worn it with like some navy there's like a it's like a navy print um pant that like ankle pant that I got from and tailor um next up is my blank slate patterns project um it is the tulip top basically literally 100 stolen um from sobon diversion except mine has short sleeves so it was the theme for blank slate was recycle so um I took an old top that I didn't like um it was one that I had made and just wasn't very flattering and I turned it into this um with so I used that top and then I also used some scrap fabric I had about half a yard maybe a yard of fabric left over um this fabric came from Joanne's originally it was maybe fall of 2015 I doubt they have it anymore I feel like a lot of people went out and bought this though whenever it did come out um but yeah this is a fun project I got to use um all three of my sewing machines I got to use my regular sewing machine my serger and my cover stitch um so I always love getting to use the cover stitch I got a lot of good practice on it um and yeah this top comes together super super quickly and easily um I want to make another version um you can get the tulip to go in the front or in the back and then there's also like many many sleeve versions so I could make another top and it totally wouldn't look like this one at all so yeah loved making this project for blank slate um the next project comes from so art gallery fabrics was super super kind and they sent me um a couple of fabrics one is the voile that I've been talking about um lately actually I have it right here this voile here um that is the the name is escaping me oh but um and the designer is Katrina Rochella voile bird songs moon from art gallery so they sent me that I'm gonna make um a kimono top we've talked about that before but they also sent me some of so carolines new fabric and at first when I got it I was like what the heck am I gonna do with neon flowers like I don't know this just it was like I didn't know about wearing this out in public I didn't know about making it into a garment even I was trying to think like what I could even turn this knit into like okay I can make it a skirt but would I ever really wear a neon floral skirt I'm not sure it's no it's not something I would have picked up for myself but when I came across um M 7517 in the new um McCall spring catalog um I was like okay I can make that into some really cute pajamas so I actually made a pajama romper and some of you out there might think that's a little bit weird um to sleep in a romper but I'm telling you it is so comfortable I mean it is a little weird getting up in the middle of the night to have to pee and you're basically completely undressing um to go to the bathroom it was a little bit cold I remember but other than that it was super super comfortable I lived in this for a whole day and a whole night um and just really loved it I even ran and I had to go to the pharmacy which is like a drive through so I just put a coat on over this and wore this to the pharmacy drive through I didn't actually get out of the car but um but yeah it was great to just like throw a coat on and go out in it it was fine um because you're all covered up but yeah it's just really comfortable it's really cute the pattern was really easy to put together it's just basically like a knit top with like binding and you have your sleeves and then you have your sleeve um um cuff and then you attach the top to the shorts and the shorts have a cute little pocket in the back which is impractical for sleeping but it's just a cute design and then the front of the shorts also have pockets so this isn't a pajama pattern it's like just a regular kind of athleisure type of pattern but I made it into pajamas so this isn't something you'll see a video on simply because I'm not going to do a video on my pajamas I don't even know like I'm not going to go outside to film that so um I thought I would talk about it here so here you go love this I'll get on the mannequin so you all can see too and then the last one is the stash builder box pajama set that I made which I am obsessed with um it's these adorable shorts with the ruffle so I used all three fabrics um I used one for the bodice one for the shorts and then another one for all the different like accents so the bindings um there's a little pocket on the front and then the ruffle hem on the short and also of course the sleep mask because you can't have pajamas set without a matching sleep mask um this is pattern in six eight four eight and yeah this is super cute and comfortable I will say though the top is too big um I got the large or pattern size for the shorts and I should have gotten the smaller pattern she's bought both patterns the smaller and the larger and made a medium top instead of a large top but I was thinking that I could you know alter it and make it work but um the arm size like gigantic I mean it's not horrible it's just especially for bed it's no big deal but if I do make it again I think that I'll spring for the two dollar macaw sale at joann's and get the medium size as well so yeah so those are my projects from january like I said it was a very successful month and I had a ton of fun making all these things I had a location so I actually had a week off where I could do nothing but sew and cut out things and all of that so um that's how it's able to get so much done but I want to know what you've been sewing this month so leave a comment um to let me know I don't know if you blog or vlog but um leave a comment with a link to that or um tag me in like your on your facebook picture um or you know leave a picture on the inside the him facebook page or tag me on instagram show me what you've been making I would love to see like maybe your favorite project that you've made from this month that would be super cool so yeah thanks so much for watching and I will see you guys very soon bye


Polyphenols are valuable compounds found in plants with antioxidant, anti-inflammatory, and anti-cancer properties. However, they are unstable and difficult to deliver in a stable form. Encapsulation is one method used to protect polyphenols from degradation and improve bioavailability. Physical, physicochemical, chemical, and related stabilization techniques can be used to encapsulate polyphenols. Applications include pharmaceutical, food, and cosmetology. This article was authored by Florence Edwards-Levy and Audnenin.


Well it was a celebratory afternoon in Brainerd today as Brainerd Lakes and statewide organizations held the 15th annual Lake and River Friendly Awards. The awards ceremony is held each year to recognize homeowners, business owner, contractors and local units of government that have implemented policies or practices to protect lakes and rivers. The ceremony was sponsored by a number of businesses and multiple awards were given out including the Shoreland Stewardship Award and the Protection Strategy Award. I want our Cascone AIS prevention program to be considered a model that the state can follow and my plan is to continue to work with all the partnerships that we've worked so hard to create and continue to grow the scope of our projects. The ceremony was kicked off by a presentation on Minnesota Loons and the Deepwater Horizon Oil Spill by Carol Henderson of the Minnesota DNR Non-Game Wildlife Program. If you've enjoyed this segment of Lakeland News, please consider making a tax-deductible contribution to Lakeland Public Television.


Now, I am going to shed some light on research and multiple role relationships. Dependent relationships are characterized by a disparity in power and status between the researcher and research participants that compromises the ability of participant to provide free consent to participate or withdraw from a project they are already participating in. At times, our research participants are in such a situation that they cannot choose from their own free will whether they want to be a part of some research or not. For example, if a professor of psychology is going to conduct a research on students' classroom behavior and he tells his own classroom students that this is your assignment, that you have to be the part of this research for a three-month time period, they have to be the part of that research because their professor has given them this assignment and he is studying their behavior. So, the situation there is that they cannot withdraw from it. Multiple ethical obligations arise when the research participants are also current and previous clients of the researcher. Now, a mental health professional is doing his research and at the same time he is using his clients as participants in the research. So, for the previous or current clients, it is very difficult or challenging to withdraw yourself from that mental health professional. We have seen a lot of new herbal medicines in the research of neuropsychology. So, the practitioners of neurology or neuropsychology try different elements like Parkinson's or dementia. They also test the herbal medicines in different experiments to see if they are getting good results or not. And the participants, because they are being the clients, they cannot say yes or no. They have to take them. However, their participation could jeopardize the therapeutic services being rendered. But in this way, if a client is asked to withdraw from their research, when you take it as an experiment, then your therapeutic practice can basically disturb it because it is not considered a good thing. Problems typically arise when participants at the student or client feel obliged to participate or not to withdraw or are likely to have a reasonable belief that might experience this benefit even if the relatively minor by declining to participate or by withdraw. This situation becomes very intense when a student or a client feels that he is not getting any benefit from this research. However, if he refuses to participate in this, then he will be very upset because his teacher or therapist will be upset. So, this situation becomes very critical. Dependent relationship can be particularly impactful when working with vulnerable populations. Now, as we talked about the teacher-student relationship, we talked about the different role of the teacher-student relationship. We also talked about the therapist or client. There are different roles and relationships. So, dependent relationships become more impactful when we talk about vulnerable groups. Researchers should ensure that appropriate consents are obtained from any gatekeepers to participants. For example, school principal, parents, or legal guardians. That means that we should take every individual who is from a small to a large level in some research and that is a part of this research. We should take their informed consent, their permission, without thinking that their position is very small in our research. Then, dependent relationship should be definitely very impactful when working with vulnerable groups. Now, to avoid further unethical problems and current and previous clients should not be included into research unless needed benefits are likely or not otherwise available. We can only make our clients part of our research at that time when we are sure that we do not have any other population and this research will create a very high benefit and we should not stop it in any way and the unavailability of any other potential participants are to be seen for this research. So, some research on clients can be done by keeping ethical guidelines in front of them. Even here, care should be taken to present a sincere opportunity to decline the participation in research. If even your client is participating in your research, still he should have this privilege that he can say to withdraw from that research. Special safeguards such as participant advocate should be introduced when the power differential between the researcher and the potential participants is especially large. A situation where a relationship is developing that a therapist or a client is a research participant, an advocate should be there who supports the rights of the participant that if he wants to withdraw in a situation, he can get proper legal support and his mental health professional or therapist can never be disturbed by any position or can't stop his treatment or can't harm him in any other psychological way. So, when we talk about multiple roles in research, it is very important to see that if these roles are overlapped, then because of them, no potential dignity should be harmed and these roles should be proceed in very ethical manner.


Happy holidays, and welcome to the Endless Knot! Today, we're taking to the skies with everybody's favorite bunch of flying ruminants! Let's start with the word reindeer itself. The second element is simple enough, right? A deer is a member of the family Servidae, a type of ruminant mammal, except the word deer didn't always refer to that animal. The Old English form of the word is deor, and could be used to refer to any sort of animal. This use may have even survived into early modern English, as in the line from Shakespeare's King Lear, mice and rats and other such small deer, though this may have been something of a joke. Interestingly, the Proto-Indo-European root of deer means to blow, or puff, or rise in a cloud as dust, vapor, or smoke, and has a great many English derivatives such as fume, thyme, in reference to its strong smell, dizzy, deaf, dumb, and dumkopf, literally dumbhead in German, in reference to defective perception or wits, and dove for its smoky color. Naturally, a deer is a breathing thing, and the word animal, from Latin, has the same semantic progression, coming from a root meaning breath. And isn't it appropriate that the reindeer is a cognate of dove, another Christmas-related animal that frequently appears as a tree ornament symbolizing peace? But what about the first part of reindeer? Well, it has nothing to do with reins as in the harness for a horse, though Santa does use reins to steer his reindeer. In fact, it's a reference to the antlers from a root care, meaning horn, which also gives us the word horn, as well as the cladistic family name servidae, from Latin, carewous, deer. Indeed, that first element as Old English, ran, and Old Norse, harain, were used by themselves to refer to reindeer. Another word we get from the root care is heart, not the blood pumping organ, but the word for a male deer. The Old English form of this word is herret, which was also the name of the hall of the Danes under King Hrothgar in the epic poem Beowulf, described as high and horn gable, either because the gables were adorned with horns or looked like antlers. Speaking of antlers, reindeers are the only species of servids in which both males and females grow them. What's more, the male reindeers lose their antlers after the mating season in late fall, whereas the females keep them until they have the following summer. And the antlered females have the highest rank in the feeding hierarchy during that period, useful since they're gestating offspring. So if you see a picture of Santa's reindeer with antlers, you can be sure they're all female. But before we leave behind the etymology of reindeer, I should point out that another word for the species, usually used in Canada, is caribou, coming from the mikmak word kalipu, which means literally it shovels snow because the animals kick the snow in order to feed on the moss and grass underneath. So we should all be referring to them as caribou since Santa at the North Pole lives in Canada, he even has a Canadian postal code H0H0H0, where you can send your wish list to Santa and get a reply. So turning to Santa's reindeer in particular, well, originally they weren't. Reindeer that is. Earlier depictions of old St. Nick had him going about on foot or on a white horse. In fact, still to this day in the Dutch tradition, Sinterklaus rides a white horse called Amerigo. It wasn't until an obscure 1821 anonymous poem published in a New York magazine called The Children's Friend that Santa was connected with reindeer, but just one reindeer. The poem goes, Old Santa Claus with much delight, his reindeer drives this frosty night, or chimney tops and tracks of snow, to bring his yearly gifts to yo, uh, you. Now the first question is, why reindeer? Where did the New York poet get that idea, as it wasn't part of the traditional St. Nicholas legends, and New York is a long way from reindeer. Well, one suggestion is that it might come from Lapland legends of a kind of old man winter who would drive his reindeer down from the mountains bringing the snow with them. This is a general winter figure, though, not a Christmas gift-giver. But the name of the Finnish Christmas gift-giver, now more or less conflated with the North American Santa Claus, Yulupuki, literally means yule goat. Yule was originally the Old Germanic pagan, specifically Norse, mid-winter festival that eventually got subsumed into Christmas, when Christianity arrived on the scene. In Norse myth, Thor's chariot is pulled by two goats, called Tan Grisnir, Teethbearer, and Tan Gnoster, Teethgrinder. And these names are sometimes rendered into English as Cracker and Nashor, perhaps reminiscent of the first two reindeer names, Dasher and Dancer. But we're getting ahead of ourselves here. In any case, I suppose goats are notionally closer to reindeer than horses. Maybe? The second question is why eight reindeer? That 1821 poem only mentions one, so how did the number grow? Well, you may have already guessed that it was in the famous poem Twas the Night Before Christmas, actually titled A Visit from St. Nicholas, that we first hear of eight tiny reindeer, who all have names, Dasher, Dancer, Prancer, Vixen, Comet, Cupid, Donor, Blitzen. Now, leaving aside the indication that they and St. Nicholas himself were tiny, guess that's how we fit down the chimneys, why specifically eight reindeer? And why those names? To answer this, we need to take a quick look at the poem's author. Originally published anonymously in 1823, the poem was later attributed to scholar Clement Clark Moore, Professor of Greek and Hebrew, and also writer of a huge ancient Hebrew dictionary. In keeping with all the scholarly learning, the reindeer names contain a number of rather learned illusions. And in addition to the possible goats of Thor I mentioned earlier, it may be a reference to another Norse god, Odin, that gives us the number eight. You see Odin, who is sometimes known by the name Yolnir, or Yulfigur, is one of the possible forerunners of the Christmas gift-giver figure. And Odin wrote an eight-legged horse named Slipnir, which literally means slippy. Eight legs, eight reindeer? Well, let's have a look at the names of those eight reindeer. First up is Dasher. Dash probably comes from a Scandinavian source, meaning beat or strike, hence dash to pieces, as well as move quickly, hence the hundred yard dash. The punctuation mark, dash, comes from the notion of a hastily written pen stroke. And from there, the expletive dash at all, because the curse word dam would be reproduced in print as D dash dash M, so as not to corrupt the innocent. A dashboard was the barrier in front of a carriage or sleigh which prevented mud from being dashed up from the horse's hooves and ruining the clothes of those riding in the vehicle. When the automobile or horseless carriage was invented, the dashboard was kept to protect the passengers from the dirt of the wheels. And once the engine was placed in front of the car, the dashboard protected the passengers from the heat and oil of the motor. And eventually the car's various instruments were located on the dashboard, which has kept the same name in spite of the changes in meaning. The first mass produced automobile, the Oldsmobile curved dash, was so named because its dashboard was curved, resembling that of a sleigh. I suppose Santa's sleigh must have a dashboard too, but presumably he doesn't have to worry about mud since his sleigh flies. Another related word is dashing, meaning fashionable and showy, as in a dashing young man. This use comes from the 18th century colloquial expression to cut a dash, which I suppose you might want to do on the dance floor. Speaking of which, next up is dancer. The etymology of dance is a bit uncertain. The word comes into English from old French danse. Ultimately, it either comes from Frankish dintion to tremble or from the Proto-Indo-European route 10, meaning to pull or stretch, suggesting dancing in a line or file. I guess the reindeer are stretched out in lines when pulling Santa's sleigh, but really they should be dancing in a circle as the word carol, possibly coming from Latin corolla, meaning little crown, originally referred to a kind of circle dance performed to a particular type of lyric song. So maybe dancer was also a singer. I suppose prance might suggest a motion similar to dancing, appropriate since prancer is our next reindeer. Funny thing is, historically speaking, prancer shouldn't be a reindeer but a horse. The word prancer was originally from the 1560s, thieves slang for a horse. Again, it's a bit uncertain where prance comes from, but it has been possibly linked to Middle English prankin' to show off from Middle Dutch, prankin', and thereby related to the word prank. But lest you think that pranking is rather more related to another holiday, April Fool's Day, Christmas too has its own tradition of pranking in Miss Rule. During the late Middle Ages and early modern periods, there was a tradition of appointing a peasant as the Lord of Miss Rule, a kind of mock king who oversaw the Feast of Fools during Christmastide. This would generally involve drunkenness, wild partying, disguises, and other types of topsy-turvy revelry. It's been suggested, though not without some debate, that this custom dates back to the ancient Roman festival of Saturnalia, celebrated at the same time of year, which featured gift giving and a carnival atmosphere in which masters serve their slaves. Well, if prancer should've been a horse, vixen should've been a fox, and a girl. Because you see, vixen is the feminine form of fox. In Old English, as in modern English, while the male was a fox, the female was a vixen, with the feminine ending ien causing the vowel to mutate, as also seen in Old English pairs like wolf, male, and wolfen, female. Guess that's further evidence, along with the antlers, that the reindeer were all female. As for the root of the words vixen and fox, this is a matter of some debate. We know it can be traced back as far as proto-Germanic fuchsaz, feminine fuchsigno, as there are cognates, meaning fox, in the various Germanic languages. But fuchsaz does not come from the usual word for fox in proto-Indo-European, wolfay, which leads to Latin wolfays, and thereby the scientific name for the fox. So where did fox and its cognates come from? Well, it seems to have been a taboo replacement. Instead of using the fox real name, which might invoke the pestilent creature itself, a taboo replacement name is used instead. This is a common process with animal names, such as with the word bear, which literally means brown one. The original proto-Indo-European root, referring to the bear, does survive in Latin, ursus, giving us the constellations, ursa major and ursa minor, which mark out the arctic, a word which comes from the Greek derivative of that same root. Well, Santa and the reindeer do live in the arctic at the North Pole, after all. Interestingly, the word bear gets swapped out again in the name of the hero beowulf, whose name literally means beowulf, a stand-in for the word bear. So all that being said, what is the literal meaning of the word fox? Well, there are a number of suggestions, but the most likely is that it refers to the fox's distinctive tail, coming from the root puke, meaning tail. By the way, in another instance of sly and foxy name replacement, in French, which originally had a word descended from Latin Woolpays, the standard word now is renard, which comes from a popular folk character in medieval literature, renard, an anthropomorphic trickster figure who is always up to no good. Indeed, the slinus of the fox is its main cultural association. I suppose that might lie behind the compound word foxfire, a kind of eerily bioluminescent fungus, which is associated with the will of the wisp and the original sense of jack-o'-lantern, mischievous fairies that lead nighttime travelers to their doom. But this is all leading us astray to yet another holiday, Halloween. So let's return to our foxy roots, specifically the one that gives us Latin Woolpays. It is so close to the root that lies behind English wolf and Latin lupus that there appears to be something linguistically sly going on behind the scenes. And indeed, sometimes the words for foxes and wolves are used interchangeably. And as a final point on the cultural associations of the animals, in English, foxy is a word that is applied to sexually attractive women. Vixen, which had the earlier sense of an ill-tempered, quarrelsome woman, seems now to be gaining the sense of a sexually aggressive woman. And in Latin, the feminine form lupa refers to a prostitute. But lest we cast any aspersions on our reindeer Vixen, let's move on to the next reindeer in line. And that is comet. As an object flying through the heavens, the word comet seems an appropriate name for one of Santa's team. Comet comes ultimately from Greek in the expression aster kometes, meaning literally hairy star, on account of the long tail of the star, which was thought to look like hair. Cometes comes from Greek kome, meaning hair of the head. And that's the end of the line as we don't know where that word comes from. In addition to comets looking hairier than other stars, they were also notable to ancient observers for being temporary moving stars. Since they came and went like that, they were often taken as portents of important events. And to bring this all back to Christmas again, it has been speculated that the star of Bethlehem, which marked the birth of Jesus, was in fact a comet. Though other astronomical objects, such as an unusual conjunction of planets or even a supernova have been suggested. The Magi or wise men, as they are sometimes known, were in this case likely astrologers following the star. But moving on from stars in the heavens to gods, next up is the reindeer Cupid. Cupid is of course the Roman god which the Romans associated with the Greek god Eros. Latin Cupido, desire or love, comes from the verb cupura, to desire, which goes back to a Proto-Indo-European root quep, meaning to smoke, cook, move violently, be agitated emotionally. So I suppose you could say that Cupid is really smoking. The English derivative cupidity generally refers to desire from money, not sex, but the related concupiscence does indicate sexual desire. Also possibly from this root, through Latin vapor, steam, are the words vapor and evaporate, and through vapidos, English vapid, literally that has emitted steam or lost its vapor, flat or poor. Greek eros, by the way, may come from the root ere, meaning to separate or adjoin, which also gives us rare, through Latin rares, having intervals between, hence full of empty spaces, and thus rare. If this is the root of eros, it would then come from the Greek verb erasthai, to love, from the idea of being separated from. Well, absence does make the heart go fonder, or perhaps that should be fondler, since we're talking about erotic love here, eros also leading to English erotic and erogenous. Today, of course, we associate the god Cupid with that little cherub who flies about shooting love hours at people around St. Valentine's Day. But as we again stray into yet another holiday, I'll bring it back to wolves and Roman traditions, because some have tried, not very convincingly, to trace a line between Valentine's Day and the Roman festival Lupercalia, which just happens to fall on the 13th to 15th of February. Lupercalia, which draws its name from Latin lupus, wolf, is a kind of pastoral festival associated with fertility, hence the supposed connection with Valentine's Day, in which, according to the historian Plutarch, young men ran through the streets naked, hitting women who wished to become pregnant or have an easier pregnancy with shaggy thongs. Always with the men hitting on the women, it seems, certainly makes you wonder what Cupid and Vixen were getting up to. Our next reindeer in the pantheon is Donner, or is it? In the original Clement Clarke Moore poem, it's Dunder, though you needn't feel like a Dunderhead, a related word, or a Dumkopf, for that matter, for not knowing that, as Donner is today the most common form of the reindeer's name. You see, Dunder is the 19th century Dutch spelling for the word, which means thunder, and which goes back to the proto-Indo-European root, stenae, meaning thunder. And I'm sure you'll be stunned and astonished, also related words, to hear that English thunder also comes from this root. Donner is the German form of the word. Also related is Thor, Old English Thunor, the Norse Lord of Thunder. Oops, that should be God of Thunder. Sorry, Thor. And since there appear to be wolves after me in this video, I may as well mention in Norse myths, Thor's father Odin meets his doom in the jaws of the monstrous wolf Fenrir, whose name means Fen-dweller. So I guess wolves are after them, too. And what goes along with thunder? Well, lightning, of course. And that's the sense behind the next reindeer name, Blitzen. Only again, the original poem had the Dutch form Blixen. The ultimate proto-Indo-European root behind the word is bel, which means shine, flash, or burn, and gives us such words as bleach, blonde, and flame, as well as belting, the Celtic Mayday celebration, yet another non-Christmas holiday. Blitzen also has some more closely related cognates in English, such as Blitzkrieg, meaning lightning war, the World War II German attack strategy, which employed surprise and speed to overwhelm the opposing forces. This was then shortened simply to Blitz, especially in reference to the Blitz, the German bombing raids against Britain in World War II. But this is also not a suitable topic for Christmas, so we'd best move on. Move on? But weren't there only eight reindeer? What about the most famous reindeer of all? Well, the story of Rudolph the Red-Nosed Reindeer was written by Robert May, drawing on the memories of his own painfully shy childhood, as a free Christmas promotion in 1939 for the Montgomery Ward department store, where he worked in the advertising department. Almost two and a half million copies were given out that Christmas season, and the story became a big hit virtually overnight. And in a remarkable show of corporate loyalty, the store turned over the rights to the poem to May, and it subsequently became a commercially published book. May then handed the poem over to his brother-in-law, Johnny Marks, to turn into a song, which became a hit for Gene Autry, the singing cowboy, after it was turned down by the likes of Bing Crosby and Dinah Shore, and was eventually made into a Christmas TV special in 1964. As for songwriter Marks, although he was Jewish, as was May, he made something of a career out of writing Christmas songs, composing such hits as Rockin' Around the Christmas Tree, A Holly Jolly Christmas, and Run Rudolph Run, the last for rock and roll legend Chuck Berry. As for the name itself, well, it looks like the wolves have finally caught up with us and are dressed in reindeer's clothing, because Rudolph means glory wolf. The second element we've already seen, the Germanic root that produces wolf. The first element is from hruad, a Germanic root meaning glory or fame, a common name element also found in the name Roger. That name appears in Old English as Hrothgar, literally glory spear, the name of the king in Beowulf, king of the Danes and Lord of the Hall Herod that we saw at the beginning of this video. Rudolph too has an Old English form, Hrothulf, who is mentioned briefly in Beowulf as the nephew of Hrothgar. These legendary figures also appear in an Old Norse saga as Hrothgar and Hrulfer, with the latter playing the larger role, gathering about him a court of 12 accomplished warriors, one of whom, Balfar Bjarke, whose name means warlike little bear, is often connected with Beowulf himself on account of his bearish name. Balfar Bjarke's father was magically turned into a bear and he seems to have inherited this connection from his father as he is able to project his spirit as a giant bear in order to fight for Hroth with bear-like powers. So it seems there's more to those tiny reindeer than meets the wondering eye, from a wild menagerie to Norse myth, Roman festivals and Old English epic. Probably then a good idea to leave a carrot or two beside the cookies for Santa to keep on their good side. Thanks for watching. If you've enjoyed these etymological explorations and cultural connections, please subscribe and click the little bell to be notified of every new episode. And check out our Patreon where you can make a contribution to help me make more videos. I'm at alliterative on Twitter and you can visit our website, alliterative.net for more language and connections in our podcast, blog and more. Happy holidays.


Going on everyone Sam here with late in sports cards have been 23 tops chrome baseball logo for actor edition 10 box break number 4 random team style look again at your random results as always you can find those all on the website under the results tab as Well as a link in chat. Let's do it Good luck here everybody Here we go. Yeah. Oh f1s gigantic man.  I Saw you I looked out and you were you're going back where it's dragging it Well too heavy too heavy Not a good look Anthony Volpe future stars rice terrain rookie and Oswald for Oz a rookie He never has it easy on Wednesday night sits Battle there dude walking into the shield and we're just firing arrows I For a five-color chase clay pool patch. Well, you already got one of those Let's go Scott Scottie Josh, you know those are on channel two tonight, right Scott? I want to make sure Oh yours is only three damn, okay good. Good. I don't want to make sure I just want to make sure Anami the other one go during now Wondering those the halls Scary really scary overall Linda walls Robin Corning cabbage Cabbage right Max Scherzer as a purple JT Real Muto to 250 Got a Benny Pascantino to 199 of the rookie the Royals Fulton Varshio and Gary Cole. He's a follow Rory Langliers Rosario von Grissom your don and Jordan Walker.  Yeah People don't want to sit next to them anymore. I Don't blame them That's gonna find a Nemo backpack on And they're in their 20s What are we doing? I'm still not convinced he makes his own sandwiches. I'm really not I'm really not convinced he makes Does the same thing Potato bread peanut butter Jonathan Aranda Oswald Cabrera got an auto change April a day going to the Marlins That's on that Marlins Michael Toglia and Kate Cavalli God, Jack Peterson Green Wander to 99 a Gabby Morena future stars Spencer steer and Lou Bob Now your son now at play says Severely messed up with sandwiches. He's brought in one time. He brought in a sandwich. That was just the two ends of the bread the other time he guess I guess Roma ran out of Bread so there was only rolls and he brought like a sandwich like a hot dog Just like lead I'm like really we couldn't abandon the peanut butter sandwich for one day Michael Harris You were there, right? You were there for one of them for sure he got oh My god slam them for that Awesome, dude, I love it man. Absolutely love it. It's awesome. Try it one time Don't knock it till you try it on that one. Don't put it in for two minutes. It's not frozen dinner. Oh, yeah He was there for it for a minute. Yeah, Jordan Walker rookie Currently having ice cream that was not microwave near loser I Ban him, please get him out. I'm out and tired of jumbo tired of jumbo already We ever part of that discussion ship. I feel like you weren't there that night Tell Marte Matt Olson blue DL Hall for the Orioles the 150 Jeremy Pena and Corey Seeger Yeah, oh absolutely. Absolutely Scott. I don't even care Morel, Miggie gold Jonathan Aranda for the raise the 50 Oswald Parazza and Anthony Volpe Me this is like the rare thing that Vaughn and I are on the same side for two me and Vaughn and Jayce Me Vaughn and Jayce are like the three biggest like Truthers for microwave ice cream Was privileged to miss out on that one fair fair. That's what I'm talking about fair Eric picking up a spot Brandon P with a tiered spot. Thank you, buddy. Well, we had some a couple other Orders coming. I just want to see what they were Kyle what I hadn't deleted them. Come on Martin Z with a couple of personals Kevin C with a prime spot Michael with a spot and then like I said Brandon with a tiered spot So two to go on the second to last iMac tier break now two to go Two to go and then tend to go on the last one and then we'll be in the prime racing tonight everybody That'll be the main focus we prime racing It should be a good time and I'm excited random hit style leave our sport coming up as well Random hit style Riley green So what's your take on it? Shipe you ever put ice cream in the microwave for 10 seconds. Yes or no very important and you're You're welcome this to this channel Long trip. Hey have a good one Patrick. Thank you, buddy. Save travel. Yes. It travels man. They've travels You're welcome this on this channel is that stick not ever done that before well shite's gone. It's nice knowing you shite Hey, thanks for thanks for everything shite appreciate it man. Yeah. Goodbye No, shite. You're just normal Vaughn grissom. It's called normal Corbin Carroll Future stars Jacob Grom and Jordan Grosjean's See there you guys said he's not against it necessarily gets the see if shite gets the vision at least I'm in on that Oh, hoppy Vargas purple trout to 250. There you go angels We got a blue of Joey Manessus rookie to 150 and then a mookie bets. I take back my boo Do you do that? No, I cut that connects three cards together. That's dope dude. Add the roachman. That's actually really freaking cool It's good. It's a good little It's a good little product man. It's gonna be I'm excited to rip some we don't have a lot of it So we're gonna do a few breaks of it But I am excited Reia Francisco Alvarez to 99 that is Jose Ramirez and Tim Anderson. Yeah, this this conversation of the ice cream has been going on since Saturday Sandy Alcantra. We got an orange Clayton Kershaw purple Fernando Tate's junior to 250 You've got orange Jose L2 V for the straws on the color match 13 to 25 Grats on that Houston and Adley rookie. Oh, yeah, the J. J. Bladette. Bladette, mate We had two croissants and one packed yesterday So I got to do it quite good a paper base and a chrome base That's so great. That was good. It was really good Yoshida rookie Akunya buyback Gunner Henderson rookie yellow bow nailer to 75 for the Guardians a rally green and Cal Mitchell. Oh, yeah, I came up with a new one. It's a hit a bow nailer all dayler That's a good one, man all dayler bow nailer Nick Prado to 150 Brian veil Nice one there for the Red Sox. There you go stripes their face and Josh young rookie and von PC's them So I got to ruin I got to ruin his PC a little bit Marvin and with a spot in 13 Thank you, buddy Joel the spot in 14 and Eric with a bunch of panther spots So we're down to one to go one and nine to go now everybody one and nine one and nine Let me have one thing Not ruining everything with sticks the one What has to happen fortunately what has to happen during Walker whoa? I'll be your side Get this guy out here get Michael out of here base and base Mark Vientos Logan Ohapi and Nick Castellana Michael Jordan Oh Who buys scopes Brown Francisco Alvarez Trout and Brett Beatty Rookie Excited man Lenin Sosa Corbin Burns to 199 For the brew crew green Carlos Greta 99. I Was thinking it. Oh, yeah Yeah, I'm you two and Tati's top shorts Shorts what up? What's up Tony? Hey, thank you Christopher with spotting each of the primes So we're under 30 to go in the first prime now everybody. That's awesome. Oh, Tony buyback What's fam up there you go, Tony? Oh, well, what's fam up mix it in water? No, Tony. God. It's only 509. Hey, I'm assuming where you are.  I don't know. Nice. Nice. That is nice. Brett Beatty 250 on the purple the Mets Hit Alonzo and kind of wall the Chuck shapes boy Hell yeah, can let's go baby We're creating man.  Let's go Dodgers as well lead into it. Yeah, true It really does man. These logo for active breaks are freaking awesome. Yeah 10 boxes of them shot it buybacks in random team Good stuff the grade Yeah, get all the base rooks one for a regular boss. I think it's 150 Okay, and then it's 60 bucks a spot for a spot in 10. Oh really? Yeah And then we do it like we have that this in a museum break. It's 2699 They're like to buy or not museum of stadium club. It's like two and two or something like that What I sang it stop with the Wii. No, we know we we're gonna win or see you go to 250 Let's go Dodgers Gosher Gonzalez and Nelson bless cuz I literally was telling cuz and candler knows candler is Candler grades a lot of stuff. He knows man Take it from take it from anybody who's not me take it from candler. He knows his stuff Buxton estuary Ruiz. He likes the Dodgers fire and bucks and no, he's not like the Dodgers and Riley green He's not a bandwagon. He didn't know anything like you my whole life All right, we've got purples the 250 Corey seager Brett Beatty for nanopathies junior Mike trout We all muto Adley ruchman for 199 and Corbin Carroll Steven Kwan Pascantino to 150 Brian Bayo DL Hall Joey Manessus Brett Beatty to 99 wonder Franco Carlos, Korea Francisco Alvarez 75 bow nailer gold to 50 Jonathan Aranda orange to 25 was a L2 vay and then JJ bleday bleday mate on the auto What am I? What am I? I'll do it for the break everybody. Thanks again for the fill icons coming up next