This list of question was from a Slashdot post. Here are my answers.

Do you remember what LALR stands for?

This is a form of grammer parser. Look Ahead Left to Right. It accepts/parses Context sensitive grammers.
Can you calculate the cost of a pipeline bubble or a branch misprediction? What information would you need to do so?

You can calculate the cost of a specific misprediction under some architectures. You would need to know what the instructions to be executed in the incorrect case are, how long they take, and whether you can undo them or not. For instance in the sample code:

if     (i){   do_x();  } else{  do_y(); }

If both do_x and do_y are non, inlined functions, you know that a function call will happen.  Assume i has to fetched from memory, if  the addresses of do_x and do_y must also be fetched from memory, there is a likelihood of fetching the wrong address for the call operation.  If, on the other hand, do_y is inlined, and the compiler determines this to be the likely path, the cost will be whatever work do_y executes while waiting on the fetch of (i).

Deeper pipelines have even worse issues, as the “most likely path” may only be executed in it’s entirety a relativelyfew number of times, meaning much of the work done by deeper pipeline stages gets discarded.

How is depth-first/breadth-first related to stacks/queues related to LIFO/FIFO?

a stack is a last in first out (LIFO) data structure

a queue is a first in first out (FIFO) data structure.

In a depth first search, traversing down the the search tree is analogous to pushing values onto a stack. A depth first search is easily implemented using recursion, where the stack is the actual program stack.

In a bredth first search, you traverse across all of the children of the start node. As you search each child, you add it to a queue. Once the current node has no more children, you remove the item at the head of the queue and process it in the same manner. Continue until you meet the search criteria or there is nothing left in the queue.

What is the stack pointer?

The element of the register file that indicates where the top of the stack is for a process/thread.

What is the frame pointer?

On some architectures, a separate register points to a location on the stack that indicates where the currently executing function’s scope begins. On x86 and later architectures, there is no frame pointer register. However, the concept of frame pointer is still valid, as the return location of the current function will be pushed onto the stack with a call operation. To return from a function, this value is popped off the stack and put in the instruction register.

An interesting note is that this value may not always refer to the calling function. For example, assume you have three functions main, outer and inner. Outer and inner have identical parameter lists, for this example, a single integer value x.

void inner(int x){

}

void outer(x){

inner(x)

}

main(){

int x;

outer(x);

}

The generated assembly for main will be something like:

mov X,%ebp
call <outer>

But for main it can be

jmp <inner>

The reason is that there is no need to clean up the paramters after the call to inner. When inner completes, the return value stored on the stack will be from main, one after the call to outer. This is called a tail call and is a very common compiler optimization.

What is an interrupt?

An indication of an asynchronous event that the operating system must handle. There are two forms of interrupts, hardware and software. Examples of events which generated interrupts are: request I/O is avaialble from a device, a clock tick has occured, a user has typed a key on a keyboard. Typically, the OS handles the interrupt in two steps, a top half and a bottom half. The Top half is everything that must happen immediately, the bottom half is everything that must be done eventually. In the top half, the systems does things like recording the type of the interrupt, and scheduling the bottom half by placing it on a queue. The bottom half is what would be responsible for reading the data from the network device or linking up the key pressed to the appropriate TTY.

What are the three primary elements of OOP?

I don’t know if I would say there are three. Really, there are only two. Encapsulation and Polymorphism. Inheritance is in most forms of object oriented programming languages, but I agree with people who call this “Class Oriented Programming.” Protype based object oriented languages such as javascript may or may not be described as having inheritance. In this kind of language, a new object is created only by cloning the original object, and then modifying it. Since this is a shallow copy, it will have the same set of functions listed as methods of the object. These can be overloaded by replacing them. This is a instance of the Prototype design pattern.

Encapsulation means that you only have access to the interface of the object, not the underlying implementation. I would argue that Javascript provides no method to hide a method or property, and thus does not really encapsulate. Then again, java provides the entire introspection API, so there are often ways to get around encapsulation using dirty VM tricks as well. In C++, you can alwyas cast the object instance to get access to the underlying implementation. It is safe to say no languages encapsulation is effective against a truely determined effort to violate it.

There are two distinct forms of polymorphism. The first is that the same symbol can point to multiple functions. In C++ this is done using a table of function pointers. The second form is that two functions of the same name can take different sets of parameters and point to differnent implementations. This requires compiler support. In C++ this is implemented via Name mangling, where the types of the parameters and the return value are added to the symbol name. In Java, all inheritance is performed via a V table, and is scoped on the class name of the class that originally defined it.

What is modus ponens/tolens (sp)?

Forms of logical arguments. A->B A Therefore B is a modus ponens argument.

A modus tollens is a logical argument of the form A->B not(B) therefore not(A).

The truth table for A->B is:

A B==A->B

0 0 ==1

1 0 ==0 (logical contradiction)

1 1 ==1

0 1 ==1 (not(a) does not imply not(b))

What kinds of race conditions are there?

Wikipedia has a write up of these, but I never learned these terms.

What is a critical section?

A section of code that can only have a single thread of execution at a given point in time. Access to a critical section is controlled by a lock.

What is the difference between a monitor and a semaphore?

Both are methods of concurancy control. A semaphore performs concurrency control by keeping a counter of requests. THe counter is implemented using an atomic test and set. When the semaphore is 0, another process is granted the permission requested. All others will be required to wait.

A monitor is a compiler generated construct that controls access to a resource. A call to code that is a critical section will have code generated that acquires the lock, and then releases the lock after exiting the critical section.

The third form of concurrency control is message passing. These three forms are all equivalent. Each can be implemented in terms of the other two.

Define NP-complete.

A problem is NP if there is a solution that can be performed in polynomial time by a non-determinisitic turing machine. A solution to the problem can be verified in polynomial time by a deterministic Turing machine. A problem is NP complete if every other problem in NP can be reduced to that problem. NP-complete problems are the hardest problems in NP.