Some would add to this list verifiability, programmer productivity, efficiency readability, writability, learnability, predictability and extensibility.
|
FORTRAN
LISP
Pascal
Algol 60
|
PL/I
COBOL
Simula 67
C++
Ada
Smalltalk
|
(Spring 1994) Name and describe the major classes of languages, and give examples from each.
What is lazy evaluation, and what is the benefit of using it?
Lazy evaluation is a term used to describe a method by which expressions are evaluated, where no expression is evaluated until its value is needed, and no shared expression is evaluated more than once. Lazy evaluation is usually seen in functional languages, and functions that use it are often called "non-strict functions".
The benefit of using it is that it saves the cost of evaluating large expressions that are never used. If, for example, I call f(a,b,c) where b and c are computationally expensive to figure out, and the code looks like:f(a,b,c){
if(a)
return b
else
return c
}
Lazy evaluation ensures that only one of b and c are evaluated, not both.
A side effect of using it is that it allows the use of "infinite" data structures. Most of the time programs only use a finite portion of such a data structure, and lazy evaluation allows the language to provide the use of such structures without having to fully enumerate their values.
Why don't all functional languages use lazy evaluation?
Implementing eager evaluation is simpler and more efficient. Similarly, many optimizations use side-effects to save time, and lazy evaluation makes doing so more difficult. It is also nice to know when side-effects will occur, if the language has them. Lastly, in parallel computation, it is often better to start a computation as soon as one can.
What are continuations?
A continuation is a segment of code given to or returned from a function that is to be executed to cause program flow to change in a manner similar to a goto statement. In other words, a continuation can be passed to a function, and the function can execute the continuation instead of returning normally. Typically they are invoked to "continue" an interrupted operation.
An example might be an exception handler passed as a continuation, which would be executed only in the event of an exception being thrown, resulting in a change in the normal flow of control. They can be approximated in C/C++ with longjump. "A Gentle Introduction to Haskell" by Paul Hudak and Joseph H. Fasel define a continuation as "basically a (possibly nullary) function that maps an `intermediate value' (possibly empty) to `the rest of the program.'"
(Winter 1997) Give some examples of different calling conventions.
In call by name, the literal values of the arguments to a subprogram replace its formal parameters prior to execution. It isn't quite the same as a macro, however, since a formal parameter is treated differently from a local variable with the same name. Algol 60 allowed call by name, but it is no longer in use because of the difficulty of implementing it, its inefficient execution, and the fact that side effects during execution of subprograms can produce erroneous results.
In call by reference, the address of the arguments are given to the subprogram, which allows it to write to it directly. This method can be dangerous in that it allows the possibility of side effects in a subprogram execution. A benefit is that it is efficient compared to methods in which the data object is passed in. (Consider sending in a huge array, for example.)
Call by value is a mode of parameter passing in which the parameter is evaluated before execution of the subprogram. It is simple to implement and relatively safe in the sense that the called subprogram can not modify the actuals. On the other hand, it is impossible to directly write a function that swaps the values of its inputs.
In call by value-result, the values of the actuals are copied into the local variables of the called subprogram, and the results of the computations are then copied back into the variables just before exit.
(Winter 1997) What is a language that uses call by name?
Algol 60.
(Winter 1997) Provide an example of a situation where call by name would cause a problem.
Call by name can be thought of as macro expansion. In an expression like
a[f(i)] = a[f(i)] + 1
the function f() gets called twice. If it modifies i, then the result could be
a[1] = a[2] + 1.
Another example might be a swap function like the following:void swap (x,y) {
int t = x;
x = y;
y = t;
}
A call to swap (i,A[i]) would result in the the statements: t = i; i = A[i]; A[i] = t;
Give an example where call by reference could cause unexpected results.
Consider the following function, where both arguments are passed call by reference:int incadd (int &x, int &y) {
x++;
return(x+y);
}
When the following code is executed, the result will be 8, not 7: int x; x = 3; incadd (x,x);
Now give a similar example for call by value-result.
The problem that can occur is name collision, where it is unclear what the returning value of an argument to a function call to sub(x,x) should be:void sub(int a, int b) {
a = 1;
b = 2;
}
sub(x,x)
Should the values for x be assigned left to right?
(Winter 1997) Consider the following code. After returning from SUB, what is the value of LIST[2] using call by name, call by value, and call by value-result?
int GLOBAL;
int LIST[2];
void SUB (int PARAM) {
PARAM++;
GLOBAL := GLOBAL + 1;
PARAM++;
}
void main () {
LIST[0] = 1;
LIST[1] = 10;
GLOBAL = 0;
SUB (LIST[GLOBAL])
}
Call by name is 11, call by value is 10, call by value-result is 3.
Explain the problem that a user of a language that does not have static allocation is faced with.
Without static allocation, programmers are forced to place variables in larger scopes than should be necessary, which destroys the locality of the code.
What is the difference between static and dynamic scoping?
With static scoping, a subprogram is called in the environment in which it is defined. With dynamic scoping, the calling of a subprogram is defined at runtime.
How do you implement static scoping in a language like Pascal? What about dynamic scoping?
For static scoping, each procedure has an associated activation record which contains a pointer (called an access link) to the activation record that lexically encloses it. This pointer is initialized by the caller prior to the callee's execution. When a variable that is not in the local scope needs to be accessed, the chain of access links is followed until it is found.
Activation records have a control link, which is a pointer to the caller. It is normally used for returning control to the caller after the procedure is completed, but it can also be used to implement dynamic scoping in a manner similar to the static scoping scenario described above.
What is an activation record, and what information is typically stored in it?
An activation record (frame) is "an object holding all of the information relevant to one activation of an executable unit." (MacLennan, p. 257) It is used to store the state of an executable unit during subprogram calls, and contains the parameters of the unit, the address to return to after the subprogram execution, any local variables, a pointer to the calling activation record, any scoping pointers, and a storage space for the result of the subprogram's computation.
How is an activation record different in Pascal than in C? Fortran than in C?
Pascal allows procedures to be nested, which means that the lexical scoping is a bit more complex than C's. As a result, access links are used to follow the scoping chain toward the global scope when looking for variables external to the procedure. Procedures can not be nested in C, so most variables can be found in the local scope or the global scope, which means that access links are not needed.
Fortran does not have recursion, so local variables can occupy the same memory locations with every invocation of the procedures. Each activation record is known at compile time and is statically allocated before program execution.
(Spring 1995) What is structured programming and why is it important?
Structured programming is a programming style that emphasizes top-down program control flow, minimal branching, no backward references, no use of gotos, and a single entry and single exit point for every block. It makes programs easier to write, test, debug, and maintain by adhering to the overall philosophy that the static structure of the source code should reflect the run-time dynamics of the computations, thereby making the understanding of the program simpler.
Why are functional languages slower than imperative languages?
(Spring 1996) What is referential transparency?
Referential transparency, as often used in programming languages, means that a reference to a function can be replaced with the body of that function without changing the semantics. In other words, this means that functions do not have side effects, and every time a function is called with the same arguments, it always returns an identical result.
Lack of referential transparency makes it difficult to perform compiler optimizations such as inlining, and also makes it difficult to prove correctness because one can not reason about individual components. An analogous use of referential transparency is used in math, where one can substitute 7 in any case where 3 is added to 4.
What is a side-effect, and what limitations does it place on a language?
A side effect is a change to some state of the machine other than the value returned from an operation. Side effects means that the order of evaluation must be specified for the primaries of an expression, the subscripts of a variable, and parameters sent by value.
What is the difference between innermost and outermost evaluation in a functional language?
Innermost evaluation is the same as call-by-value. In an expression like successor(plus(2,3)), plus(2,3) is evaluated and the result is used as an argument to successor. Outermost evaluation is call-by-name, since the actual is substituted for the formal in the function body and then the body is evaluated.
Innermost evaluation is simple to implement and fast in execution since an argument is only evaluated once, but outermost evaluation can avoid situations in which evaluating one argument determines the result of the function, and thus the other (possibly non-terminating) argument does not have to be evaluated.
(Spring 1994) Describe some aspects of Common LISP that are not purely functional.
From a very pure standpoint, I/O is side-effecting, so the "format" function is not purely functional. Likewise "setf" is basically an assignment.
What is lambda calculus?
It is a function-oriented mathematical method for semantic analysis. It is the basis for modern functional programming languages. A major point of lambda calculus is that functions are treated in full generality as arguments to functions or the result of a function application, and recursion is allowed. Any algorithm in any language can be translated into the lambda calculus.
What are lambda expressions?
Lambda expressions are anonymous functions, in the sense that they can be
applied without giving them a name. The syntax (
.x.F)N means
that when this function is applied, the object to which it is applied
(N) is substituted for x where ever it occurs in F.
If the N already exists in F, then rename the occurrence in
F. We write this substitution as {N/x}F. A couple of examples:
y.y*y) 4 = {4/y}(y*y) =
16(4 is substituted for y in every occurrence in y*y)
(x.u+x) u = {u/x}(u+x) =
{u/x}(z+x) = (z+u)(First we rename u since it is in u+x, then we substitute u for x.)
What is curried notation?
Curried notation is a way of simulating functions of several variables in the
lambda calculus. It is useful for partial evaluation, where all of the arguments
for a function are not available at once. The curried form of the binary
operator * is xy.x*y.
What's a higher order function?
A function that can take another function as an argument or has as a function as a result.
What is the downward funarg problem?
Consider the following Pascal code:
var y : integer; procedure f(); begin writeln y; end; procedure g(h: function); var y: integer; begin h(); end; begin g(f); end.
The downward funarg problem occurs when we pass a function as an argument, and it references a variable outside of its scope. Even though y is declared in the activation record just above the current one, the one we are really interested in is declared two levels above, in the global scope.
It's difficult to implement first class functions in languages where this can occur since we have to pass the activation record (or at least the lexical scope level) of a function around with the name. The resulting structure is a directed acyclic graph rather than a stack.
What is the upward funarg problem?
The upward funarg problem occurs when a language allows functions to be returned from a procedure, as in the following Pascal-like code:
function f : function;
var y: integer;
procedure g();
var x;
begin
write x + y;
end;
begin
return g;
end;
begin
h := f;
h();
end;
When h() is executed, the value of x or y is not known because f()'s activation record has already been popped off the stack when h() is executed. In order to allow such statements, we would have to create the activation records for the procedures from the heap in a manner that is not strictly stack-like.
Why do parallel languages often provide support for non-determinism?
Many applications that lend themselves to parallel execution have the property that it is not possible to determine what the system will be requested to do at a given time. A good example is an operating system.
(Spring 1996) What are functional languages typically not parallel languages?
The problem with implementing functional languages in parallel is that it is difficult to efficiently partition the computations involved into separate pieces that can be run separately. It is often difficult to determine the computational size of a function a priori, so the computational overhead may be a high fraction of the actual execution time.
Why are functional languages nice for parallel computation?
Since almost all computations are function-oriented without side effects, it is theoretically possible to parallelize the evaluation of multiple parameters to a function.
(Winter 1998) What is garbage collection?
It is a means of automatically returning unused memory to the free memory list during the execution of a program. When there is no more storage to allocate, the runtime system determines the memory that is no longer used, and automatically deallocates it.
(Winter 1998) What methods have been used to implement it?
One method of implementation is mark and sweep, which initially sets all of the allocated memory to "unused", then attempts to reach all the memory by traversing all of the existing references on the stack or in global memory. During a second pass all of memory is scanned, and any memory that is not reached can not be used, and is therefore deallocated. This method requires one bit of extra data per memory unit allocated, and also requires one pass over the used memory, and another pass over all of memory.
Another method is to partition the available memory into two units, a working half and a free half. When all of the memory in the working half has been allocated, the system copies all of the data into the free half (traversing references as needed). Then all of the memory in the working half is marked as unallocated and the roles of the two memory regions switch.
(Winter 1998) When should the garbage collector be called?
What is another method of automatically reclaiming memory?
One can have a reference counter associated with each memory object, incrementing it when a pointer refers to it and decrementing it when the pointer no longer points to it.
(Winter 1999) What is a problem with reference counters?
Reference counting does not work for circular structures, because there is a reference to each component in the structure.
(Winter 1999) How can you find a circular data structure?
The "chasing the tail" algorithm. Traverse a list with two pointers, and, at each step, advance one pointer two by objects and the other by one. If, beyond the first step, the "faster" pointer is ever equal to the "slower" pointer, the list is circular. If the "faster" pointer hits a NULL link, the list is not circular.
You can also use a marking algorithm
(Winter 1999) Can chasing the tail be implemented for an arbitrary graph?
Explain how reference counting can violate a language design principle.
Unless a reference count is only kept when an object has a reference to it, the principle of localized cost will be violated, since ordinary variables will not need it.
What is the Church-Rosser Theorem?
The Church-Rosser Theorem says that if there is more than one possible way of evaluating an expression in a functional language, then it does not matter what order we choose to do the evaluation. This property is called confluence.
More accurately, the theorem states that if an expression E can be reduced to two different expressions E1 and E2, then there is another expression N that is the reduction of both of these. The Church-Rosser theorem does not provide guarantee of termination, nor does it say that we will be able to find such an answer if it exists.
Name two criticisms of the imperative style of programming.
There is a time dependency upon the order of execution of statements, which makes it hard to reason about the program. Likewise, the lack of referential transparency forces one to consider more than the program fragment at hand.
What is short-circuit evaluation?
Short-circuit evaluation is the name of a semantic interpretation of multiple expressions in a control construct, in which evaluation of the expressions halts once the overall value is known. Example:if ((j != 0) && (1/j == 3.14)) {
...
}
If one does not use short-circuit evaluation, then if j is zero, the second operand will result in a division by zero error.
What is a coroutine?
A coroutine is a subprogram that can be restarted where it was last stopped, which means the stack model does not work well. Typically the activation record is stored off of the stack. Coroutines usually work in pairs.
How is are coroutines different from general parallel processes?
With coroutines, only one is executing at any given time.
What is type inferencing?
Type inferencing is the determination of the type of an expression based on the type of the subexpressions. ML is a language that makes extensive use of type inferencing.
(Spring 1996) Give an example in ML where automatic type inferencing could result in unforeseen problems.
Consider the following code:
fun pow a 0 = 1.0
| pow a n = a * (pow a (n-1))
In the first line, specifying 1.0 specifies that pow is a function from reals to reals, which may not be what the programmer intended. The type error here really occurs when the programmer accidentally types 1.0 instead of 1. Unfortunately, this will not be caught until it is used in an integer context.
(Winter 2000) What is a type?
A type is a set of related values that have a set of operations defined for them.
(Winter 2000) Isn't this definition controversial?
Yes, some people actually prefer to use a more mathematical definition, and say that a type is just a set of related values, and that the operations permitted are not part of the type per se.
What is an object? A class?
An object is a collection of data and operations. A class is a set of objects having the same operations and data.
What does it mean for a language construct to be a "first class citizen"?
The term "first class citizen" means that a construct can be used in an identical manner to other similar constructs. There are no artificial limitations on its use. An example might be the type string, where, if it were first class, it could be used as the value of an expression, appear on the right side of an assignment, be denoted by a name, be used as a parameter, etc.
Why are strings usually second class data structures?
For languages that are static in nature (i.e. stack-based, compiled) it is very useful to know the size of data at compile time. An example of this is determining how much space to save in an activation record for arguments and return values of string type. The dynamic nature of the length of a string makes implementation more difficult. Furthermore, the standard operations on strings, such as concatenation, substring extraction, comparison, etc. are not directly supported by most computers, and are therefore inefficient compared to operations on basic types such as integers. Strings are also slow compared to other data types, which have constant time access and manipulations.
Ada says that programs that use aliasing are erroneous. Can a compiler check for this?
No. A counterexample is a function call such as fun(A[i],A[j]), where i and j were read in at runtime. This is no way for the compiler to determine if they are equal.
(Spring 1996) What is a strongly typed language?
A strongly typed language is one in which no programs that can result in type errors are allowed by the compiler.
What is a type error?
A type error occurs when an operation receives an argument of a type different from that which it was expecting. A program is type safe if it runs without type errors.
(Winter 2000) What is dynamic typing, and can a strongly typed language by dynamically typed also?
(This is different that dynamic type checking.) Dynamic typing means the ability to create and use objects of specialized types at run time when only the abstract type is known at compile time. Types are bound to values instead of identifiers, and each value must carry around some sort of identification. As long as a value can perform a particular operation, it does not matter what type it is. C++ is an example of a language that has strong type checking and dynamic typing, specifically its use of virtual functions.
(Winter 1999, Winter 2000) What are virtual functions in C++?
Virtual functions are object methods that allow subclasses to change the behavior of a function in an inherited class through dynamic binding. If a pointer of the superclass points to an object of the subclass, then a call on a virtual function in the superclass will result in invocation of the one in the subclass. In a sense, virtual functions reverse the order of function lookup at runtime.
(Winter 1999, Winter 2000) How do you look up the method? (i.e. How are they implemented?)
From the C++ FAQ:
That is, the member function is selected dynamically (at run-time) based on the type of the object, not the type of the pointer/reference to that object. This is called "dynamic binding." Most compilers use some variant of the following technique: if the object has one or more virtual functions, the compiler puts a hidden pointer in the object called a "virtual-pointer" or "v-pointer." This v-pointer points to a global table called the "virtual-table" or "v-table."
The compiler creates a v-table for each class that has at least one virtual function. For example, if class Circle has virtual functions for draw() and move() and resize(), there would be exactly one v-table associated with class Circle, even if there were a gazillion Circle objects, and the v-pointer of each of those Circle objects would point to the Circle v-table. The v-table itself has pointers to each of the virtual functions in the class. For example, the Circle v-table would have three pointers: a pointer to Circle::draw(), a pointer to Circle::move(), and a pointer to Circle::resize().
During a dispatch of a virtual function, the run-time system follows the object's v-pointer to the class's v-table, then follows the appropriate slot in the v-table to the method code.
The space-cost overhead of the above technique is nominal: an extra pointer per object (but only for objects that will need to do dynamic binding), plus an extra pointer per method (but only for virtual methods). The time-cost overhead is also fairly nominal: compared to a normal function call, a virtual function call requires two extra fetches (one to get the value of the v-pointer, a second to get the address of the method). None of this runtime activity happens with non-virtual functions, since the compiler resolves non-virtual functions exclusively at compile-time based on the type of the pointer.
[NOTE: This description is complicated by multiple inheritance, virtual inheritance, run-time type inferencing, etc. Also, Smalltalk uses a more dynamic method in which the class hierarchy is traversed bottom-up until the proper class is found.
(Spring 1996) What is a dataflow language, and to what class of languages does it belong?
A dataflow language is a language that is data-driven in the sense that data flows from one computational unit to another. Execution of a unit does not occur until its input data are available, and multiple units may be executed in parallel.
Dataflow languages are declarative, along with logic and functional languages.
(Spring 1996) What is an Ada rendezvous?
Ada rendezvous is a high level language construct designed to allow separate tasks to communicate. Tasks execute in parallel until a synchronization point is reached. A task containing an entry definition and an "accept...end accept" block halts at the accept statement until another task calls that entry, and a call halts until the receiver reaches an accept block. Consider the following example:
| Calling Task | Called Task |
:
T.E(actuals)
:
|
task T;
entry E(formals);
:
begin
:
accept E(formals);
: -- body
end accept;
:
end;
|
Conceptually, the calling task sends a message to the called task containing the actual parameters for the rendezvous, and the called task sends a message back after the body of the accept statement is completed. (This form of having the caller wait until the caller completes is called an extended rendezvous.)
Describe the select-accept mechanism in Ada.
Tasks in Ada perform a rendezvous in which one task will wait for the other for synchronization. Within a select clause are several accept clauses. Accept clauses may have guards on them in the form of "when <condition>". The select statement allows a choice among more than one accept statement, by determining which "when" conditions are true and arbitrarily selecting one of them.
(Spring 1996) What is the problem with Ada rendezvous and the way Ada implements exception handling?
Ada does not propagate exceptions outside of the boundaries of a task. As a result, there is no way for one task to know if another task has been aborted. If a task is at an accept block waiting for another aborted task, this can cause problems.
Ada has a method of dealing with this with the use of timed accept blocks. If a task does not call the associated entry within a certain time, then the accept block is not executed.
What is a module?
A collection of declarations, usually of both variables and procedures. A module has an interface and a separate implementation. In other words, a module has an abstract representation that shows how it should be used, as well as a concrete representation that implements the functionality.
How is a module different from a class?
A class can be used to create more than one instance, but a module has only one state, the local static state with no notion of instance individuality.
What deficiencies in Abstract Data Types caused the development of Object-Oriented languages?
Once defined, ADTs can not be easily altered to create new data types, and there is no mechanism for abstract the similarities between closely related data types. Both of these are provided by inheritance.
(Winter 2000) What are the issues with respect to types that a language designer has to tackle?
Here are a few:
(Spring 1995) What's an object-oriented language?
It's a language with encapsulation, polymorphism, and inheritance.
What do those terms mean?
Encapsulation is a method for abstracting complexity. You see this in the case of functions, and in object-oriented languages data is also encapsulated in an abstract data type. An abstract data type specifies a set of data and the operations defined on them. Polymorphism allows objects of differing types to perform the same operation. Inheritance is a method of creating new types of objects from existing ones. Typically one specializes the inherited attributes.
What are object types important for object-oriented languages?
Without types, objects are not first class citizens because they can not be sent as parameters to functions, returned from them, referred to by name, compared or be used on the right side of an assignment. One can instantiate multiple instances of the object, but the instances are independent of each other.
(Spring 1995) What are the primary benefits of object-orientation?
The primary benefit of OOP is that it provides a higher level of abstraction for the programmer. Ideally, programmers would be able to implement classes of objects and program with them instead of individual lines of code. Another benefit is that data is more stable that functionality, making modifications to a system easier and less error-prone overall. Similarly, OOP encourages the good programming techniques of information hiding, correct variable scoping, and modularity. Lastly, data-oriented design promotes code re-use through the use of proper class design and inheritance.
What are the downsides?
There is a loss of functional locality. One may have to look through several classes to find the meanings of methods, and a change to a superclass can have wide influence. In addition, the semantics of inheritance is very complex, so that it is difficult to reason about changes to members of the hierarchy without knowing the definitions of methods in other classes.
Everyone talks about object-oriented reuse, but we don't see a whole lot of it. How come?
There are several aspects to the problem. First, there is a tendency for programmers to not trust software that they did not make. Second, there are certain qualities about an object that are not always obvious from the interface, such as its memory and speed efficiency. Lastly, there is some support to show that the benefits of reuse are quickly lost if one has to learn and modify the internals of an object with which one is not familiar.
How is the object-oriented paradigm of Smalltalk different from that of C++?
In Smalltalk, everything is an object (including classes), and everything is part of the inheritance hierarchy. The data in objects are always private, but in C++ this is not necessary. Also, Smalltalk does not support multiple inheritance, and inherited variables can not be overridden. In C++, one can not assign an instance of a parent class to a variable of a derived class. (Smalltalk objects all have two member, isMemberOf and isKindOf, to avoid type errors.)
Classes in Smalltalk are run-time entities (objects) that are used to create objects and share data among objects, while in C++ classes are removed from run-time consideration (are types). Also, Smalltalk supports message passing, which is different from the C++ use of function calls because it allows the determination of which method to invoke to be determined at run-time. (Although virtual functions approximate this.)
(Spring 1995) What are two different styles of implementing inheritance?
Two main ways are that inherited members are available to classes that are further derived, or that they are not visible (public or private).
(Spring 1995) What are the tradeoffs? Can you name an example language for each?
C++ allows private inheritance, which stresses information hiding, as well as security by limiting access to the members. Smalltalk only has public inheritance, which is more flexible with respect to polymorphism, but can only be limited by redefining a member to call the "do not understand" method.
What are some of the costs of using inheritance?
There is some loss of speed with the use of general-purpose classes because one can usually write hand-crafted code that is faster. Likewise, there is often a penalty in terms of code size when one uses code from libraries. Lastly, there can be overhead when using a message passing mechanism (although this is greatly reduced in statically bound languages like C++).
In object-oriented programming, what is the difference between instance variables and class variables?
Class variables are shared by all instances of a class, but instance variables are independent of other objects of the same class. In C++, the keyword static is used to signify a class variable.
Does Ada have abstract data types?
In Ada, the package mechanism can be used to construct ADT's, since it consists of a specification and implementation. It also has the C++ equivalent of templates in the form of the generic package.
What does private and limited private mean for Ada classes?
If a class is declared private, then users are restricted to creation of instances, assignment, comparison, and passing to procedures or functions. (i.e. Users can not read or change the contents.) Limited private means that the users of a class are also prohibited from assigning or comparing instances of an abstract data type, unless they are provided by the class.
(Winter 1998) Explain the difference between static and dynamic type checking.
Static type systems perform type checking at compile time, while dynamic type systems do it at run time. Static type checking is generally preferred because it allows typing errors to be caught before execution begins. Snobol 4 is a language that used dynamic type checking.(Winter 1998) Do both methods catch the same errors?
What is the relationship between static typing and polymorphism?
A language that uses polymorphism allows run-time variance of the specific functions being executed, which causes a problem because in general we can not guarantee type safety before run time. C++ solves this problem by requiring that the types of all objects that could have an operation called on them support the operation.
Then what's the relationship between static typing and dynamic binding of function calls?
Static typing means that a variable's type must be known at compile time. Using static typing would mean that it would be impossible to allow run-time factors to influence the decision of the type of an object that would be used in an operation. Since dynamic binding means that the actual code for a function is not determined until run time, a language that used static typing would not be able to provide it.
(Spring 1995) How do you implement dynamic binding in a language such as Smalltalk or C++?
Dynamic binding in C++ is done using tables. At run time, the table indicates which version of the operation is executed based on the run time type of the object. As stated earlier, every object must support the operation according to the typing rules.
Smalltalk's runtime environment supports messages as a means of invoking operations indirectly on other objects. Invoking an operation (method) on an object consists of the run-time messaging environment locating the implementation of the receiver's method named in the message and then executing it. If the object's class does not support the method the method is passed up the inheritance hierarchy until "Object" is reached, at which time the result is a run-time error.
Why is dynamic binding hard to implement?
If a language uses dynamic binding, it is impossible to allocate a fixed amount of memory for the variables, since it is impossible to know which of the possible procedures will be called. One also has to carry the type of objects around at run-time to insure that a method being invoked is provided by the object. Lastly, resolving overloaded operators or functions must be done at run-time instead of compile time.
Explain the limitation on binding that recursion causes.
With recursion, local variables can not be bound to a memory location until runtime. There may be multiple activations of a procedure, which would require multiple storage areas for the variables.
What are the relative merits of dynamic binding and static binding?
In general, dynamic binding provides greater flexibility, while static binding provides faster execution. Dynamic binding tends to be more "object-oriented", as it greatly simplifies problems like general-purpose data structures. In static binding, if the compiler can determine a match between a message and method, then it can implement it as a simple procedure call and avoid the run-time overhead of a method lookup. Lastly, static binding allows the compiler to avoid run-time errors that occur when an object can not handle a particular message.
What is the difference between "protected" and "private" in C++?
Members of a class A that are declared or inherited as "protected" can be used within the class A and by classes that derive from A, but those declared or inherited as "private" can only be used within A.
Name two ways in which C++ violates the general Object-Oriented concept of data abstraction.
C++ allows one to place data in the "public" area of the class, thereby making it available to the rest of the program, and other classes and functions can be declared "friend", which allows them to manipulate any data in the class.
What is a Horn clause?
A horn clause is a clause containing at most one positive literal. For example, P if Q1 and Q2 and ... and Qk. Horn clauses can not represent negative information.
Does Prolog have disjunctive logic?
Yes. Disjunction is written as separate rules.
(Spring 1994, Spring 1995) Explain on a high level what logic programming is, and give an example.
Logic programming is a programming paradigm that attempts to separate the logic of a program from the control. Typically the world is modeled as a set of logical truths, and programs manipulate and query these assertions. Prolog is an example.
(Spring 1994, Spring 1995) What type of searching strategy does Prolog use, and what is the problem with this strategy?
It uses depth-first, which can result in infinite searching.
(Spring 1994, Spring 1995) Why is depth-first used instead of breadth-first?
Breadth-first would require exponential space to store the solution branches being explored. (It is not clear that there is a time penalty also.)
What is unification?
Unification is the matching operation that Prolog performs upon arguments during its search for solutions.
What is the cut operator? Give a use for it.
The cut operator tells the search engine that, if any subgoal beyond the cut operator fails, then fail this rule and all other rules with the same headgoal. This allows the programmer to "prune" the search tree, but is controversial because it causes Prolog to depart further from pure logic, which imposes no order upon logical statements.
It is most often used in Prolog systems to define the operator not:
not P :- P, !, fail. not P.
Explain Prolog's "closed world assumption".
Prolog assumes anything that it can't prove to be true is false. That is, it's world, in the form of a rule base, consists of only those facts that are given to it.
(Spring 1994, Winter 1997) What is polymorphism? Give some examples.
Polymorphism is the ability to treat different objects in a similar manner. Each object responds in its own way to identical messages. In Object-Oriented Programming, one can derive several classes from a common base class, and objects created from these derived classes will all respond to an invocation of a function defined in the base class. In most imperative languages, the "+" operator operates upon reals and integers, and sometimes on strings as well.
Describe four different methods of implementing polymorphism.
Cardelli and Wegner define four different kinds of polymorphism (see figure). With parametric polymorphism, a polymorphic function has an explicit or implicit type parameter that determines the type of the argument for each function application. In inclusion polymorphism (subclass polymorphism as in C++), an object is viewed as belonging to many different (possibly overlapping) classes. Parametric polymorphism is most similar to C++'s templates or Ada's generics; special code is generated for each use of a function (as in C++), or a single implementation is used. Overloading means that a symbol has different meanings in different contexts. Coercion is the automatic transformation of arguments into the types expected by the operation prior to the operation being applied.
Argue that templates in C++ are a form of ad hoc polymorphism.
The code for each class is generated at compile time by substituting the values of the types used. Since every use of the template is known, the compiler can generate multiple copies with slight variances. This is very similar to overloading in that separate sections of code are created for each class instantiation.
Now argue that templates in C++ are a form of parametric polymorphism.
From the programmer's viewpoint, there is no functional difference between these methods. There may be a problem with "code bloat" resulting from the multiple, nearly identical templates, but otherwise this method is transparent.
(Spring 1994) What is tail recursion, and why is it important?
Tail recursion is a recursive call that is the last statement of a function. It can not be part of an expression. It is important because a function that is tail recursive can have an optimization performed in which the recursion is removed and the function is turned into an iterative loop. Doing this removes the overhead of the function call.
Give an example of a tail recursive factorial function.
Here's some pseudo-code:fact (n) {
fact-tail (n,1,1);
}
fact-tail (int n, int i, int t) {
if (n == i)
return (t);
else
fact-tail(n,(i+1),(t*i));
}
What is the difference between the syntax and semantics of a language?
The syntax defines the allowable lexicographic constructs of the language, and is usually defined using a BNF-style grammar. The semantics defines the meaning of the constructs, essentially determining if a certain collection of syntactic elements "make sense".
Explain what it means for a grammar to be ambiguous, and give an example.
Here's a grammar similar to that of Pascal:S ::= if expr then S S ::= if expr then S else S
This grammar causes an ambiguous parsing for the statement if expr then if expr then S else S, since it is unclear which "if" the "else" corresponds to.
What is denotational semantics?
It is a means of accurately specifying the meanings of constructs of formal languages by giving the mathematical object that it denotes. Constructs in programs are treated as mathematical expressions (functions) and are usually expressed using lambda calculus. It allows one to reason about the behavior of programs, and to prove certain assertions about them. (For example, one can prove that if an expression is of a certain type, then the evaluation of that expression will have a result of the same type.)
What is operational semantics?
Operational semantics is an informal method of analyzing the semantics of a language. Typically a finite state machine is used to describe the meaning of a language based on the changes in the state based on a given input. In a way, one is describing a programming language using another programming language, which can result in circularities.
What is axiomatic semantics?
Axiomatic semantics falls between denotational semantics and operational semantics in terms of formality. Predicate calculus is used to analyze the pre- and postconditions of a particular sequence of code, and the semantics is based on the difference between the two. The state of the machine is not considered; rather, the constraints are the driving analytical construct. Typically one is interested in the weakest precondition that can be used and still guarantee the validity of the associated postcondition.
(Winter 2000) State the rule of consequence in axiomatic semantics.
{P}S{Q} P' => P, Q => Q'
-----------------------
{P'}S{Q'}
(Winter 2000) What is it used for?
Finding the weakest precondition.
What is function overloading?
Function overloading is semantic sugar that allows a programmer to use the same function name for arguments of different types. For example, the "+" operator could be overloaded to handle two arguments of type int, two of type float, or one of each. It is a form of ad hoc polymorphism.
Give an example of a situation in which function overloading and default parameters can be a problem.
If you have two functions defined as:
void func (int arg = 0);
void func (float arg = 1.0);
Give an example of a conflict between function overloading and coercion.
If there are two functions foo(float,int) and foo(int,float), a call to foo(5,5) will be ambiguous.
What are pointer semantics for assignment?
Pointer semantics means that when an assignment occurs, the variable being assigned to now refers to the object, as opposed to having a new copy made.
What is column-major and row-major?
Column-major and row-major describe the way arrays are laid out in memory. In a column-major layout, sequential memory locations vary the rows faster than the columns. (i.e. A[i,j] is adjacent to A[i+1,j] in column major.)
Which does FORTRAN use?
Column major.
Early versions of Pascal had an unfortunate aspect to the definition of arrays. What was that aspect, and what problem did it cause?
The bounds of an array was part of the type, making it impossible to write a library routine that took an arbitrary array as an argument.
Consider the following declarations:
type a = array [1..10] int; type b = a; type c = array [1..10] int;
In Pascal, given one variable each of types a, b, and c, which of the possible assignments are legal?
Pascal uses name equivalence (except for procedures, where structural equivalence is used), so assignments between variables of types a and b are legal, but no assignments to or from variables of type c are permitted. Pascal originally left the issue of name and structural equivalence ambiguous.
Ada and Modula-2 also use name equivalence, but Modula-3 uses structural equivalence.
What are the criteria for structural equivalence?
Structural equivalence is defined as:
What are variant records, and why are they useful?
Variant records are data structures similar to normal records, except there is a part that can vary between objects of that type. They are useful in situations in which many objects may differ in a small way, and one would rather not have to treat them separately for the normal situations. (There is usually a tag field indicating which variant is used.)
An example might be nodes in a binary tree. Each node has a data field and either one, two, or no pointers. The creation of nodes and accessing the data field could be treated uniformly, but the pointer interactions could be treated separately.
What problems do they cause?
They compromise type safety, since most compilers do not check that the tag is consistent with the state of the record, and tags are optional. (Pascal is a good example, Ada fixed them by requiring a discriminant.)
Describe some of the issues related to exception handling.
(Winter 2000) In which case a resumption model for exception handling would be preferred to a termination model?
Resumption allows the recovery to be performed in the handler, and then computation resumed. Otherwise, one has to explicitely check for recoverable failures in the enclosing scope. As a result, there is tight coupling between the caller and callee.
Name a benefit of visual languages.
They make the control flow of a program explicit. An "if" statement, for example would have one incoming and two outgoing lines representing a branch in the control path.
(Winter 1997) Java is a language that has become very popular in recent years. How does it compare to C++?
First of all, it can be byte-compiled into an intermediate form that is then portable across many platforms. (This has increased its popularity, especially among web-based applications.) Memory does not have to be explicitly allocated and de-allocated (has garbage collection). It also has an explicit name for abstract base classes, called "interface" classes. It also has a good graphics library, and supports exceptions, dynamic loading, and threads.
Back to the Comprehensive
Exam Study Guide.
Last changed January 30, 1997. David Coppit, david@coppit.org