Chapter 15 Answers

Review Questions

2. What does a lambda expression specify?
The predicate function is often given as a lambda expression, which in ML is defined exactly like a function, except with the fn reserved word, instead of fun, and of course the lambda expression is nameless.

5. Explain why QUOTE is needed for a parameter that is a data list.
To avoid evaluating a parameter, it is first given as a parameter to the primitive function QUOTE, which simply returns it without change.

6. What is a simple list?
A list which membership of a given atom in a given list that does not include sublists.

7. What does the abbreviation REPL stand for?
REPL stand for read-evaluate-print loop.

11. What are the two forms of DEFINE?
The simplest form of DEFINE is one used to bind a name to the value of an expression. This form is
(DEFINE symbol expression)
The general form of such a DEFINE is
(DEFINE (function_name parameters)

13. Why are CAR and CDR so named?
The names of the CAR and CDR functions are peculiar at best. The origin of these names lies in the first implementation of LISP, which was on an IBM 704 computer. The 704’s memory words had two fields, named decrement and address, that were used in various operand addressing strategies. Each of
these fields could store a machine memory address. The 704 also included two machine instructions, also named CAR (contents of the address part of a register) and CDR (contents of the decrement part of a register), that extracted the associated fields. It was natural to use the two fields to store the two pointers
of a list node so that a memory word could neatly store a node. Using these conventions, the CAR and CDR instructions of the 704 provided efficient list selectors. The names carried over into the primitives of all dialects of LISP.

18. What is tail recursion? Why is it important to define functions that use recursion to specify repetition to be tail recursive?
A function is tail recursive if its recursive call is the last operation in the function. This means that the return value of the recursive call is the return value of the nonrecursive call to the function. It is important to specify repetition to be tail recursive because it is more efficient(increase the efficiency).

19. Why were imperative features added to most dialects of LISP?
LISP began as a pure functional language but soon acquired some important imperative features to increased its execution efficiency.

26. What is type inferencing, as used in ML?
Type inference refers to the automatic deduction of the type of an expression in a programming language. If some, but not all, type annotations are already present it is referred to as type reconstruction.

29. What is a curried function?
Curried functions a function which a new functions can be constructed from them by partial evaluation.

30. What does partial evaluation mean?
Partial evaluation means that the function is evaluated with actual parameters for one or more of the leftmost formal parameters.

32. What is the use of the evaluation environment table?
A table called the evaluation environment stores the names of all implicitly and explicitly declared identifiers in a program, along with their types. This is like a run-time symbol table.

33. Explain the process of currying.
The process of currying replaces a function with more than one parameter with a function with one parameter that returns a function that takes the other parameters of the initial function.

Problem Set

2 . Give a general form of function declaration in ML.
Function declarations in ML appear in the general form
fun function_name(formal parameters) = expression;

4. Refer to a book on Haskell programming and discuss the features of Haskell.
Haskell features lazy evaluation, pattern matching, list comprehension, type classes, and type polymorphism.

8. How is the functional operator pipeline (|>) used in F#?
The pipeline operator is a binary operator that sends the value of its left operand, which is an expression, to the last parameter of the function call, which is the right operand.

9. What does the following Scheme function do?
(define (y s lis)
((null? lis) ‘() )
((equal? s (car lis)) lis)
(else (y s (cdr lis)))
y returns the given list with leading elements removed up to but not including the first occurrence of the first given parameter.

10. What does the following Scheme function do?
(define (x lis)
((null? lis) 0)
((not (list? (car lis)))
((eq? (car lis) #f) (x (cdr lis)))
(else (+ 1 (x (cdr lis))))))
(else (+ (x (car lis)) (x (cdr lis))))
x returns the number of non-NIL atoms in the given list.


Chapter 14 Answers

Review Questions

6 . What is exception propagation in Ada?
Exception propagation allows an exception raised in one program unit to be handled in some other unit in its dynamic or static ancestry. This allows a single exception handler to be used for any number of different program units. This reuse can result in significant savings in development cost, program size, and program complexity.

9. What is the scope of exception handlers in Ada?
Exception handlers can be included in blocks or in the bodies of subprograms, packages, or tasks.

10. What are the four exceptions defined in the Standard package of Ada?
There are four exceptions that are defined in the default package, Standard:

11. are they any predefined exceptions in Ada?
Yes, they are.

12. What is the use of Suppress pragma in Ada?
The suppress pragma is used to disable certain run-time checks that
are parts of the built-in exceptions in Ada.

14. What is the name of all C++ exception handlers?
Try clause.

30. In which version were assertions added to Java?
Assertions were added to Java in version 1.4.

31. What is the use of the assert statement?
The assert statement is used for defensive programming. A program may be written with many assert statements, which ensure that the program’s computation is on track to produce correct results.

32. What is event-driven programming?
Event-driven programming is a programming where parts of the program are executed at completely unpredictable times, often triggered by user interactions with the executing program.

33. What is the purpose of a Java JFrame?
The JFrame class defines the data and methods that are needed for frames. So, a class that uses a frame can be a subclass of JFrame. A JFrame has several layers, called panes.

34. What are the different forms of assert statement?
There are two possible forms of the assert statement:
assert condition;
assert condition : expression;

Problem Set

1 . What mechanism did early programming languages provide to detect or attempt to deal with errors?
Early programming languages were designed and implemented in such a way that the user program
could neither detect nor attempt to deal with such errors. In these languages, the occurrence of such an error simply causes the program to be terminated and control to be transferred to the operating system. The typical operating system reaction to a run-time error is to display a diagnostic message, which may be meaningful and therefore useful, or highly cryptic. After displaying the message, the program is terminated.

2. Describe the approach for the detection of subscript range errors used in C and Java.
Java compilers usually generate code to check the correctness of every subscript expression (they do not generate such code when it can be determined at compile time that a subscript expression cannot have an out-of-range value, for example, if the subscript is a literal).
In C, subscript ranges are not checked because the cost of such checking was (and still is) not believed to be worth the benefit of detecting such errors. In some compilers for some languages, subscript range checking can be selected (if not turned on by default) or turned off (if it is on by default) as desired in the program or in the command that executes the compiler.

5. From a textbook on FORTRAN, determine how exception handling is done in FORTRAN programs.
For example, a Fortran “Read” statement can intercept inputerrors and end-of-file conditions, both of which are detected by the input device hardware. In both cases, the Read statement can specify the label of some statement in the user program that deals with the condition. In the case of the end-of-file, it is clear that the condition is not always considered an error. In most cases, it is nothing more than a signal that one kind of processing is completed and another kind must begin. In spite of the obvious difference between end-of-file and events that are always errors, such as a failed input process, Fortran handles both situations with the same mechanism.

6. In languages without exception-handling facilities, it is common to have most subprograms include an “error” parameter, which can be set to some value representing “OK” or some other value representing “error in procedure”. What advantage does a linguistic exception-handling facility like that of Ada have over this method?
There are several advantages of a linguistic mechanism for handling exceptions, such as that found in Ada, over simply using a flag error parameter in all subprograms. One advantage is that the code to test the flag after every call is eliminated. Such testing makes programs longer and harder to read. Another advantage is that exceptions can be propagated farther than one level of control in a uniform and implicit way. Finally, there is the advantage that all programs use a uniform method for dealing with unusual circumstances, leading to enhanced readability.

7. In a language without exception handling facilities, we could send an error-handling procedure as a parameter to each procedure that can detect errors that must be handled. What disadvantages are there to this method?
There are several disadvantages of sending error handling subprograms to other subprograms. One is that it may be necessary to send several error handlers to some subprograms, greatly complicating both the writing and execution of calls. Another is that there is no method of propagating exceptions, meaning that they must all be handled locally. This complicates exception handling, because it requires more attention to handling in more places.

Chapter 13 Answers

Review Questions

1. What are the three possible levels of concurrency in programs?

Concurrency in software execution can occur at four different levels: instruction level (executing two or more machine instructions simultaneously), statement level (executing two or more high-level language statements simultaneously), unit level (executing two or more subprogram units simultaneously), and program level (executing two or more programs simultaneously).

2. Describe the logical architecture of an SIMD computer.

In an SIMD computer, each processor has its own local memory. One processor controls the operation of the other processors. Because all of the processors, except the controller, execute the same instruction at the same time, no synchronization is required in the software. Perhaps the most widely used

SIMD machines are a category of machines called vector processors. They have groups of registers that store the operands of a vector operation in which the same instruction is executed on the whole group of operands simultaneously. Originally, the kinds of programs that could most benefit from this architecture were in scientific computation, an area of computing that is often the target of multiprocessor machines. However, SIMD processors are now used for a variety of application areas, among them graphics and video processing. Until recently, most supercomputers were vector processors.

3. Describe the logical architecture of an MIMD computer.

Computers that have multiple processors that operate independently but whose operations can be synchronized are called Multiple-Instruction Multiple- Data (MIMD) computers. Each processor in an MIMD computer executes its own instruction stream. MIMD computers can appear in two distinct configurations: distributed and shared memory systems. The distributed MIMD machines, in which each processor has its own memory, can be either built in a single chassis or distributed, perhaps over a large area. The shared-memory MIMD machines obviously must provide some means of synchronization to prevent memory access clashes. Even distributed MIMD machines require synchronization to operate together on single programs. MIMD computers, which are more general than SIMD computers, support unit-level concurrency. The primary focus of this chapter is on language design for shared memory MIMD computers, which are often called multiprocessors.

4. What level of program concurrency is best supported by SIMD computers?

Statement-level concurrency

5. What level of program concurrency is best supported by SIMD computers?

Unit-level concurrency

6. Describe the logical architecture of a vector processor.

Vector processor have groups of registers that store the operands of a vector operation in which the same instruction is executed on the whole group of operands simultaneously. Originally, the kinds of programs that could most benefit from this architecture were in scientific computation, an area of computing that is often the target of multiprocessor machines.

7. What is the difference between physical and logical concurrency?

There are two distinct categories of concurrent unit control. The most natural category of concurrency is that in which, assuming that more than one processor is available, several program units from the same program literally execute simultaneously. This is physical concurrency. A slight relaxation of this concept of concurrency allows the programmer and the application software to assume that there are multiple processors providing actual concurrency, when in fact the actual execution of programs is taking place in interleaved fashion on a single processor. This is logical concurrency.

8. what is the work of a scheduler?

A run-time system program called a scheduler manages the sharing of processors among the tasks.

34. What does the Java sleep method do?

The sleep method has a single parameter, which is the integer number of milliseconds that the caller of sleep wants the thread to be blocked. After the specified number of milliseconds has passed, the thread will be put in the task-ready queue. Because there is no way to know how long a thread will be in the task-ready queue before it runs, the parameter to sleep is the minimum amount of time the thread will not be in execution. The sleep method can throw an InterruptedException, which must be handled in the method that calls sleep.

35. what does the Java yield method do?

The yield method, which takes no parameters, is a request from the running thread to surrender the processor voluntarily. The thread is put immediately in the task-ready queue, making it ready to run. The scheduler then chooses the highest-priority thread from the task-ready queue. If there are no other ready threads with priority higher than the one that just yielded the processor, it may also be the next thread to get the processor.

36. what does the Java join method do?

The join method is used to force a method to delay its execution until the run method of another thread has completed its execution. join is used when the processing of a method cannot continue until the work of the other thread is complete.

37. What does the Java interrupt method do?

The interrupt method is one way to communicate to a thread that it should stop. This method does not stop the thread; rather, it sends the thread a message that actually just sets a bit in the thread object, which can be checked by the thread. The bit is checked with the predicate method, isInterrupted. This is not a complete solution, because the thread one is attempting to interrupt may be sleeping or waiting at the time the interrupt method is called, which means that it will not be checking to see if it has been interrupted. For these situations, the interrupt method also throws an exception, InterruptedException, which also causes the thread to awaken (from sleeping or waiting). So, a thread can periodically check to see whether it has been interrupted and if so, whether it can terminate. The thread cannot miss the interrupt, because if it was asleep or waiting when the interrupt occurred, it

will be awakened by the interrupt.

42. What kind of Java object is a monitor?

In Java, a monitor can be implemented in a class designed as an abstract data type, with the shared data being the type. Accesses to objects of the class are controlled by adding the synchronized modifier to the access methods.

47. How are explicit locks supported in Java?

Java 5.0 introduced explicit locks as an alternative to synchronized method and blocks, which provide implicit locks. The Lock interface declares the lock, unlock, and tryLock methods. The predefined ReentrantLock class implements the Lock interface. To lock a block of code, the following idiom can be used:

Lock lock = new ReentrantLock();

. . .


try {

// The code that accesses the shared data

} finally {



48. What kinds of methods can run in a C# thread?

Rather than just methods named run, as in Java, any C# method can run in its own thread.

55. What is Concurrent ML?

Concurrent ML (CML) is an extension to ML that includes a form of threads and a form of synchronous message passing to support concurrency. The language is completely described in Reppy (1999).

59. Who developed the monitor concept?

The monitor concept is developed and its implementation in Concurrent Pascal is described by Brinch Hansen (1977)

Problem Set

1 . Explain why a race condition can create problems for  a system.

a race condition creates problem because when a race condition happens two or more tasks are racing to use the shared resource and the behavior of the program depends on which task arrives first (and wins the race).

2. What are the different ways to handle deadlock?

When deadlock occurs, assuming that only two program units are causing the deadlock, one of the involved program units should be gracefully terminated, thereby allowed the other to continue.

3. Busy waiting is a method whereby a task waits for a given event by continuously checking for that event to occur. What is the main problem with this approach?

The main problem with busy waiting is that machine cycles are wasted in the process.

4. In the producer-consumer example of Section 13.3, suppose that we incorrectly replaced the release(access) in the consumer process with wait(access). What woud be the result of this error on execution of the system?

Deadlock would occur if the release(access) were replaced by a wait(access) in the consumer process, because instead of relinquishing access control, the consumer would wait for control that it already had.

Chapter 12 Answers

Review Questions
4 . What is message protocol?
The entire collection of methods of an object is called the message protocol, or message interface, of the object.

5. What is an overriding method?
An overriding method is a method that provide an operation in the subclass that is similar to one in the parent class, but is customized for objects of the subclass. For example, a parent class, Bird, might have a draw method that draws a generic bird. A subclass of Bird named Waterfowl could override the draw method inherited from Bird to draw a generic waterfowl, perhaps a duck.

6. Describe a situation where dynamic binding is a great advantage over its absence.
Consider the following situation: There is a base class, A, that defines a method draw that draws some figure associated with the base class. A second class, B, is defined as a subclass of A. Objects of this new class also need a draw method that is like that provided by A but a bit different because the subclass objects are slightly different. So, the subclass overrides the inherited draw method. If a client of A and B has a variable that is a reference to class A’s objects, that reference also could point at class B’s objects, making it a polymorphic reference. If the method draw, which is defined in both classes, is called through the polymorphic reference, the run-time system must determine, during execution, which method should be called, A’s or B’s.

7. What is dynamic dispatch?
dynamic dispatch is a kind of polymorphism provided by the dynamic binding of messages to method definitions. This is sometimes called

8. What is an abstract method? What is an abstract class?
For example, suppose a program defined a Building class and a collection of subclasses for specific types of buildings, for instance, French_Gothic. It probably would not make sense to have an implemented draw method in Building. But because all of its descendant classes should have such an implemented method, the protocol (but not the body) of that method is included in Building. Such a method is often called an abstract method ( pure virtual method in C++). A class that includes at least one abstract method is called an abstract class (abstract base class in C++).

10. What is an inner class?
Inner classes are non-static classes that are nested directly in another class.

11. What is the message protocol of an object?
The message protocol of an objects are all the methods.

12. From where are Smalltalk objects allocated?
All Smalltalk objects are allocated from the heap and are referenced through reference variables, which are implicitly dereferenced.

18. From where can C++ objects be allocated?
The objects of C++ can be static, stack dynamic, or heap dynamic. Explicit deallocation using the delete operator is required for heap-dynamic objects, because C++ does not include implicit storage reclamation.

25. What is mixins in objective-C?
Mixins are sometimes used to add certain functionalities to different classes. And, of course, the class still has a normal superclass from which it inherits members. So, mixins provide some of the benefits of multiple inheritance, without the naming collisions that could occur if modules did not require module names on their functions.

29. Does objective-C support multiple inheritance?
No, In fact, C++ is the only language discussed in this chapter that supports multiple inheritance. On the
other hand, languages that provide alternatives to multiple inheritance, such as Objective-C, Java, and C#, clearly have an advantage over Smalltalk in that area.

31. What is the root class in Objective-C?
The predefined root class named NSObject

33. What is the purpose of an Objective-C category?
A category is a secondary interface of a class that contains declarations of methods.

Problem Set

1 . What important part of support for inheritance is missing in Java?
Java does not support the private and protected derivations of C++. One can surmise that the Java designers believed that subclasses should be subtypes, which they are not when private and protected derivations are supported. Thus, they did not include them.

5. Compare abstract class and interface in Java.
An interface can be used to simulate multiple inheritance. A class can be derived from a class and implement an interface, with the interface taking the place of a second parent class. This is sometimes called mixin inheritance, because the constants and methods of the interface are mixed in with the methods and data inherited from the superclass, as well as any new data and/or methods defined in the subclass.
In addition to interfaces, Java also supports abstract classes, similar to those of C++. The abstract methods of a Java abstract class are represented as just the method’s header, which includes the abstract reserved word. The abstract class is also marked abstract. Of course, abstract classes cannot be instantiated.

10. Explain one advantage of inheritance.
Inheritance offers a solution to both the modification problem posed by abstract data type reuse and the program organization problem. If a new abstract data type can inherit the data and functionality of some existing type, and is also allowed to modify some of those entities and add new entities, reuse is greatly facilitated without requiring changes to the reused abstract data type. Programmers can begin with an existing abstract data type and design a modified descendant of it to fit a new problem requirement. Furthermore, inheritance provides a framework for the definition of hierarchies of related classes that can reflect the descendant relationships in the problem space.

13. Descripbe the mechanism of dynamic dispatch with an example in Java. Is it possible to dynamically dispatch the data members?
In C++, a method must be defined as virtual to allow dynamic binding. In Java, all method calls are dynamically bound unless the called method has been defined as final, in which case it cannot be overridden and all bindings are static. Static binding is also used if the method is static or private, both of which disallow overriding.

16. State why java is said to be more pure object-oriented than C++.
Java’s design for supporting object-oriented programming is similar to that of C++, but it employs more consistent adherence to object-oriented principles. Java does not allow parentless classes and uses dynamic binding as the “normal” way to bind method calls to method definitions. This, of course, increases execution time slightly over languages in which many method bindings are static. At the time this design decision was made, however, most Java programs were interpreted, so interpretation time made the extra binding time insignificant. Access control for the contents of a class definition are rather simple when compared with the jungle of access controls of C++, ranging from derivation controls to friend functions. Finally, Java uses interfaces to provide a form of support for multiple inheritance, which does not have all of the drawbacks of actual multiple inheritance.

17. What are the different options for object destruction in Java?
Finalize is related to C++ destructor. A finalize method is implicitly called when the garbage collector is about to reclaim the storage occupied by the object. The problem with finalize is that the time it will run cannot be forced or even predicted. The alternative to using finalize to reclaim resources held by an object about to be garbage collected is to include a method that does the reclamation. The only problem with this is that all clients of the objects must be aware of this method and remember to call it.

20. Compare the way Smalltalk provides dynamic binding with that of C++.
In C++, the programmer can specify whether static binding or dynamic binding is to be used. Because static binding is faster, this is an advantage for those situations where dynamic binding is not necessary. Furthermore, even the dynamic binding in C++ is fast when compared with that of Smalltalk. Binding a virtual member function call in C++ to a function definition has a fixed cost, regardless of how distant in the inheritance hierarchy the definition appears. Calls to virtual functions require only five more memory references than statically bound calls (Stroustrup, 1988). In Smalltalk, however, messages are always dynamically bound to methods, and the farther away in the inheritance hierarchy the correct method is, the longer it takes. The disadvantage of allowing the user to decide which bindings are static and which are dynamic is that the original design must include these decisions, which may have to be changed later.

21. Compare the support for polymorphism in C# with that of in Objective-C.
In Objective-C, polymorphism is implemented in a way that differs from the way it is done in most other common programming languages. A polymorphic variable is created by declaring it to be of type id. Such a variable can reference any object. The run-time system keeps track of the class of the object to which
an id type variable refers. If a call to a method is made through such a variable, the call is dynamically bound to the correct method, assuming one exists.
To allow dynamic binding of method calls to methods in C#, both the base method and its corresponding methods in derived classes must be specially marked. The base class method must be marked with virtual, as in C++. To make clear the intent of a method in a subclass that has the same name and protocol as a virtual method in an ancestor class, C# requires that such methods be marked override if they are to override the parent class virtual method.

25. Study and explain private and public modifiers in C++. How do those modifiers differ in C#?
C++ includes both classes and structs, which are nearly identical constructs. The only difference is that the default access modifier for class is private, whereas for structs it is public. C# also has structs, but they are very different from those of C++. In C#, structs are, in a sense, lightweight classes. They can have constructors, properties, methods, and data fields and can implement interfaces but do not support inheritance.

Chapter 11 Answers

Review Questions

1. What are the two kinds of abstraction in programming languages?
The two fundamental kinds of abstraction in contemporary programming languages are process abstraction and data abstraction.

2. Define abstract data type.
An abstract data type is a data structure, in the form of a record, but which includes subprograms that manipulate its data.

6 . Explain how information hiding is provided in Ada package.
Data type representations can appear in the package specification but be hidden from clients by putting them in the private clause of the package. The abstract type itself is defined to be private in the public part of the package specification. Private types have built-in operations for assignment and comparison for equality and inequality.

10 . What is the use of the Ada with clause?
The with clause makes the names defined in external packages Visible.

11. What is the use of Ada use clause?
The use clause eliminates the need for explicit qualification of the references to entities from the named package.

15. What is the purpose of a C++ destructor?
Destructors are often used as a debugging aid, in which case they simply display or print the values of some or all of the object’s data members before those members are deallocated. The name of a destructor is the class’s name, preceded by a tilde (~).

16. What are the legal return types of a destructor?
Neither constructors nor destructors have return types, and neither use return statements. Both constructors and destructors can be explicitly called.

20. What is the use of limited private types?
An alternative to private types is a more restricted form: limited private types. Nonpointer limited private types are described in the private section of a package specification, as are nonpointer private types. The only syntactic difference is that limited private types are declared to be limited private in the visible part of the package specification. The semantic difference is that objects of a type that is declared limited private have no built-in operations. Such a type is useful when the usual predefined operations of assignment and comparison are not meaningful or useful. For example, assignment and comparison are rarely used for stacks.

21. What are initializers in Objective-C?
Initializers are constructors.

27. Where are all java methods defined?
Methods in Java must be defined completely in a class.

30. What is a friend function? What is a friend class?
Friend functions have access to the private entities of the class where they are declared to be friends.Friend class is a class that can access the private entities of the class which has friend function in it.

37. What is the name of all Ruby constructors?
Constructors in Ruby are named initialize.

Problem Set

8. What are the drawbacks of user-defined generic classes in Java 5.0?
There are some drawbacks to these user-defined generic classes. For one thing, they cannot store primitives. Second, the elements cannot be indexed. Elements must be added to user-defined generic collections with the add method. Next, we implement the generic stack example using an Array List. Note that the last element of an ArrayList is found using the size method, which returns the number of elements in the structure. Elements are deleted from the structure with the remove method. 

10. Which two conditions make data type “abstract”?
• The representation of objects of the type is hidden from the program units that use the type, so the only direct operations possible on those objects are those provided in the type’s definition.
• The declarations of the type and the protocols of the operations on objects of the type, which provide the type’s interface, are contained in a single syntactic unit. The type’s interface does not depend on the representation of the objects or the implementation of the operations. Also, other program units are allowed to create variables of the defined type.

11. Why is the destructor of C# rarely used?
Although C# allows destructors to be defined, because it uses garbage collection for most of its heap objects, destructors are rarely used.

12. How are classes in Ruby made dynamic?
Classes in Ruby are dynamic in the sense that members can be added at any time. This is done by simply including additional class definitions that specify the new members. Moreover, even predefined classes of the language, such as String, can be extended.

13. Compare and contrast the data abstraction of Java and C++.
Java support for abstract data types is similar to that of C++. There are, however, a few important differences. All objects are allocated from the heap and accessed through reference variables. Methods in Java must be defined completely in a class. A method body must appear with its corresponding method
header. Therefore, a Java abstract data type is both declared and defined in a single syntactic unit. A Java compiler can inline any method that is not overridden. Definitions are hidden from clients by declaring them to be private. Rather than having private and public clauses in its class definitions, in Java access modifiers can be attached to method and variable definitions. If an instance variable or method does not have an access modifier, it has package access.

15. Give one capability that Java 5.0 provides which C# 2005 does not.
One capability that Java 5.0 provides that C# 2005 does not is wildcard classes.

Chapter 10 Answers

Review Questions

1. What is the definition used in this chapter for “simple” subprograms?
By “simple” they mean that subprograms cannot be nested and all local variables are static.

2. Which of the caller or callee saves execution status information?
The last three actions of a call clearly must be done by the caller. Saving the execution status of the caller could be done by either.

4 . What is a task of a linker?
When the linker is called for a main program, its first task is to find the files that contain the translated subprograms referenced in that program and load them into memory. Then, the linker must set the target addresses of all calls to those subprograms in the main program to the entry addresses of those subprograms. The same must be done for all calls to subprograms in the loaded subprograms and all calls to library subprograms.

11 . What is an EP, and what is it’s purpose?
EP is required to control the execution of a subprogram. Initially, the EP points at the base, or first address of the activation record instance of the main program. Therefore, the run-time system must
ensure that it always points at the base of the activation record instance of the currently executing program unit. When a subprogram is called, the current EP is saved in the new activation record instance as the dynamic link. The EP is then set to point at the base of the new activation record instance. Upon return from the subprogram, the stack top is set to the value of the current EP minus one and the EP is set to the dynamic link from the activation record instance of the subprogram that has completed its execution. Resetting the stack top effectively removes the top activation record instance.

16 . Describe the deep-access method of implementing dynamic scoping.
If local variables are stack dynamic and are part of the activation records in a
dynamic-scoped language, references to nonlocal variables can be resolved by searching through the activation record instances of the other subprograms that are currently active, beginning with the one most recently activated. This concept is similar to that of accessing nonlocal variables in a static-scoped language with nested subprograms, except that the dynamic—rather than the static—chain is followed. The dynamic chain links together all subprogram activation record instances in the reverse of the order in which they were activated. Therefore, the dynamic chain is exactly what is needed to reference nonlocal variables in a dynamic-scoped language. This method is called deep access, because access may require searches deep into the stack.

17. Describe the shallow-access method of implementing dynamic scoping.
In the shallow-access method, variables declared in subprograms are not stored in the activation records of those subprograms. Because with dynamic scoping there is at most one visible version of a variable of any specific name at a given time, a very different approach can be taken. One variation of shallow access is to have a separate stack for each variable name in a complete program. Every time a new variable with a particular name is created by a declaration at the beginning of a subprogram that has been called, the variable is given a cell at the top of the stack for its name. Every reference to the name is to the variable on top of the stack associated with that name, because the top one is the most recently created. When a subprogram terminates, the lifetimes of its local variables end, and the stacks for those variable names are popped. This method allows fast references to variables, but maintaining the stacks at the entrances and exits of subprograms is costly.

Problem Set

7. It is stated in this chapter that when nonlocal variables are accessed in a dynamic-scoped language using the dynamic chain, variable names must be stored in the activation records with the values. If this were actually done, every nonlocal access would require a sequence of costly string comparisons on names. Design an alternative to these string comparisons that would be faster.

One very simple alternative is to assign integer values to all variable names used in the program. Then the integer values could be used in the activation records, and the comparisons would be between integer values, which are much faster than string comparisons.

8. Pascal allows gotos with nonlocal targets. How could such statements be handled if static chains were used for nonlocal variable access? Hint: Consider the way the correct activation record instance of the static parent of a newly enacted procedure is found (see Section 10.4.2).

Following the hint stated with the question, the target of every goto in a program could be represented as an address and a nesting_depth, where the nesting_depth is the difference between the nesting level of the procedure that contains the goto and that of the procedure containing the target. Then, when a goto is executed, the static chain is followed by the number of links indicated in the nesting_depth of the goto target. The stack top pointer is reset to the top of the activation record at the end of the chain.

9. The static-chain method could be expanded slightly by using two static links in each activation record instance where the second points to the static grandparent activation record instance. How would this approach affect the time required for subprogram linkage and nonlocal references?
Including two static links would reduce the access time to nonlocals that are defined in scopes two steps away to be equal to that for nonlocals that are one step away. Overall, because most nonlocal references are relatively close, this could significantly increase the execution efficiency of many programs.

11. If a compiler uses the static chain approach to implementing blocks, which of the entries in the activation records for subprograms are needed in the activation records for blocks?

A static chain is a chain of static links that connect certain activation record instances in the stack. During the execution of a subprogram P, the static link of its activation record instance points to an activation record instance of P’s static parent program unit. That instance’s static link points in turn to P’s static grandparent program unit’s activation record instance, if there is one. So, the static chain connects all the static ancestors of an executing subprogram, in order of static parent first. This chain can obviously be used to implement the accesses to nonlocal variables in static-scoped languages.

Chapter 9 Answers

Review Questions

1. What are the three general characteristics of subprograms?
• Each subprogram has a single entry point.
• The calling program unit is suspended during the execution of the called
subprogram, which implies that there is only one subprogram in execution
at any given time.
• Control always returns to the caller when the subprogram execution

2. What does it mean for a subprogram to be active?
A subprogram is said to be active if, after having been called, it has begun execution but has not yet completed that execution.

3. What is given in a header of a subprogram?
A subprogram header, which is the first part of the definition, serves several purposes. First, it specifies that the following syntactic unit is a subprogram definition of some particular kind.1 In languages that have more than one kind of subprogram, the kind of the subprogram is usually specified with a special word. Second, if the subprogram is not anonymous, the header provides a name for the subprogram. Third, it may optionally specify a list of parameters.

4. What characteristic of Python subprograms sets them apart from those of other languages?
One characteristic of Python functions that sets them apart from the functions of other common programming languages is that function def statements are executable. When a def statement is executed, it assigns the given name to the given function body. Until a function’s def has been executed, the function cannot be called. Consider the following skeletal example:
if . . .
def fun(. . .):
. . .
def fun(. . .):
. . .

5. What languages allow a variable number of parameters?
C# allows methods to accept a variable number of parameters, as long as they are of the same type.

6. What is a Ruby array formal parameter?
Ruby supports a complicated but highly flexible actual parameter configuration. The initial parameters are expressions, whose value objects are passed to the corresponding formal parameters. The initial parameters can be following by a list of key => value pairs, which are placed in an anonymous hash and a reference to that hash is passed to the next formal parameter. These are used as a substitute for keyword parameters, which Ruby does not support. The hash item can be followed by a single parameter preceded by an asterisk. This parameter is called the array formal parameter.

23. What is Automatic Generalization?
The type inferencing system of F# is not always able to determine the type of parameters or the return type of a function. When this is the case, for some functions, F# infers a generic type for the parameters and the return value. This is called automatic generalization.

24. What is an overloaded subprogram?
An overloaded subprogram is a subprogram that has the same name as another subprogram in the same referencing environment.

25. What is ad hoc binding?
Ad hoc binding is when the environment of the call statement that passed the subprogram as an actual parameter.

26. What is multicast delegate?
All of the methods stored in a delegate instance are called in the order in which they were placed in the instance. This is called a multicast delegate.

30. What are the design issues for functions?
The following design issues are specific to functions:
• Are side effects allowed?
• What types of values can be returned?
• How many values can be returned?

31. What two languages allow multiple values to be returned from a function?
Ruby allows the return of more than one value from a method. Lua also allows functions to return multiple values.

Problem Set

3. Argue in support of the template functions of C++. How is it different from the template functions in other languages?
C++ templated classes are instantiated to become typed classes at compile time. For example, an instance of the templated Stack class, as well as an instance of the typed class, can be created with the following declaration:
Stack<int> myIntStack;
However, if an instance of the templated Stack class has already been created for the int type, the typed class need not be created.

6 . Compare and contrast PHP’s parameter passing with that of C#.
PHP’s parameter passing is similar to that of C#, except that either the actual parameter or the formal parameter can specify pass-by-reference. Passby- reference is specified by preceding one or both of the parameters with an ampersand.

8 . Argue against the Java design of not providing operator overloading
Arithmetic operators are often used for more than one purpose. For example, + usually is used to specify integer addition and floating-point addition. Some languages—Java, for example—also use it for string catenation. This multiple use of an operator is called operator overloading and is generally thought to be acceptable, as long as neither readability nor reliability suffers.

12 . Research Jensen’s Device, which was a widely known use of pass-by-name parameters, and write a short description of what it is and how it can be used.

Implementing a pass-by-name parameter requires a subprogram to be passed to the called subprogram to evaluate the address or value of the formal parameter. The referencing environment of the passed subprogram must also be passed. This subprogram/referencing environment is a closure. Pass-by-name parameters are both complex to implement and inefficient. They also add significant complexity to the program, thereby lowering its readability and reliability. Because pass-by-name is not part of any widely used language, it is not discussed further here. However, it is used at compile time by the macros in assembly languages and for the generic parameters of the generic subprograms in C++, Java 5.0, and C# 2005.

15. How is the problem of passing multidimensional arrays handles by Ada?
Ada compilers are able to determine the defined size of the dimensions of all arrays that are used as parameters at the time subprograms are compiled. In Ada, unconstrained array types can be formal parameters. An unconstrained array type is one in which the index ranges are not given in the array type definition. Definitions of variables of unconstrained array types must include index ranges. The code in a subprogram that is passed an unconstrained array can obtain the index range information of the actual parameter associated with such parameters

Chapter 8 Answers


Review Questions

1. What is definition of control structure
A control structure is a control statement and the collection of statements whose execution it controls.

2. What did Bohm and Jocopini prove about flowcharts?
A selection statement provides the means of choosing between two or more execution paths in a program. Such statements are fundamental and essential parts of all programming languages, as was proven by Böhm and Jacopini.

3. What is the definition of block?
In Ruby, a block is a sequence of code, delimited by either braces or the do and end reserved words. Blocks can be used with specially written methods to create many useful constructs, including iterators for data structures. This construct consists of a method call followed by a block. A block is actually an anonymous method that is sent to the method (whose call precedes it) as a parameter

9. What are the design issues for multiple-selection statement?
The following is a summary of these design issues:
• What is the form and type of the expression that controls the selection?
• How are the selectable segments specified?
• Is execution flow through the structure restricted to include just a single
selectable segment?
• How are the case values specified?
• How should unrepresented selector expression values be handled, if at all?

12. On what previous language was C’s switch statement based?
Studies have shown, however, that the
ability to have control flow from one selectable segment to another is rarely
used. C’s switch is modeled on the multiple-selection statement in ALGOL
68, which also does not have implicit branches from selectable segments

19. What does the range function in phyton do?
range takes one, two, or three parameters. The following examples demonstrate
the actions of range:
range(5) returns [0, 1, 2, 3, 4]
range(2, 7) returns [2, 3, 4, 5, 6]
range(0, 8, 2) returns [0, 2, 4, 6]

22. What is the main reason user-located loop control were invented?
In some situations, it is convenient for a programmer to choose a location for loop control other than the top or bottom of the loop body. As a result, some languages provide this capability. A syntactic mechanism for user-located loop control can be relatively simple, so its design is not difficult. Such loops have the structure of infinite loops but include user-located loop exits.

23. What are the design issues for user-located loop control mechanisms?
The design issues for such a mechanism are the following:
• Should the conditional mechanism be an integral part of the exit?
• Should only one loop body be exited, or can enclosing loops also be exited?

26. what is a user defined iteration control?
A user-defined iteration statement for the tree would successively set the
loop variable to point to the nodes in the tree, one for each iteration. The initial
execution of the user-defined iteration statement needs to issue a special call to
the iterator to get the first tree element. The iterator must always remember
which node it presented last so that it visits all nodes without visiting any node
more than once. So an iterator must be history sensitive. A user-defined iteration
statement terminates when the iterator fails to find more elements.

29. How are iterator implemented in Ruby?
Ruby predefines several iterator methods, such as times and upto for
counter-controlled loops, and each for simple iterations of arrays and hashes.

Problem Set

1. What design issues should be considered for two-way selection statements?
The design issues for two-way selectors can be summarized as follows:
• What is the form and type of the expression that controls the selection?
• How are the then and else clauses specified?
• How should the meaning of nested selectors be specified?

2. Python uses indentation to specify compound statements. Give an example in support of this statement.
Python uses indentation to specify compound statements. For example,
if x > y :
x = y
print “case 1”

3. How can a straightforward grammar for a two-way selector statement lead to the problem of syntactic ambiguity? Give an example.
That ambiguous grammar was as follows:
<if_stmt> →if <logic_expr> then <stmt>
| if <logic_expr> then <stmt> else <stmt>
The issue was that when a selection statement is nested in the then clause of a selection statement, it is not clear to which if an else clause should be associated.

11. Explain the advantages and dis advantages of the Java switch statemen, compared to C++’s switch statement.

The C switch statement has virtually no restrictions on the placement of
the case expressions, which are treated as if they were normal statement labels.
This laxness can result in highly complex structure within the switch body. The
following example is taken from Harbison and Steele (2002).
switch (x)
if (prime(x))
case 2: case 3: case 5: case 7:
case 4: case 6: case 8: case 9: case 10:
This code may appear to have diabolically complex form, but it was designed
for a real problem and works correctly and efficiently to solve that problem.3
The Java switch prevents this sort of complexity by disallowing case
expressions from appearing anywhere except the top level of the body of the switch.

14. State one of the main legitimate needs for gotos.
One of the main legitimate needs for gotos—premature exits from loops—can
be met with highly restricted branch statements, such as break.

Chapter 7 Answers

Review Questions

2.      What is a ternary operator?

ternary operator is  conditional expressions that can be used anywhere in a program (in a C-based language) where any other expression can be used. In addition to the C-based languages, conditional expressions are provided in Perl, JavaScript, and Ruby.

3.      What is a prefix operator?

prefix operators is the operators that precede the operands.

5.      What is a nonassociative operator?

Operator with illegal expression.

9.      What is a coercion?

coercion is an automatic conversion. For example, if an int variable and a float variable are added in Java, the value of the int variable is coerced to float and a floating-point add is done.

18.  What is short circuit evaluation?

A short-circuit evaluation of an expression is one in which the result is determined without evaluating all of the operands and/or operators. For example, the value of the arithmetic expression.

25.  What mixed mode assignments are allowed in Ada?

Ada does not allow mixed-mode assignment.

26.  What mixed mode assignments are allowed in Java?

C++, Java and C# allow mixed-mode assignment only if the required coercion is widening. So, an int value can be assigned to a float variable, but not vice versa. Disallowing half of the possible mixedmode assignments is a simple but effective way to increase the reliability of Java and C#, relative to C and C++.

28.  What is a cast?

Cast is explicit type conversions. To specify a cast, the desired type is placed in parentheses just before the expression to be converted.

Problem Set

 1.      When might you want the compiler to ignore type differences in an expression?

Suppose Type1 is a subrange of Integer. It may be useful for the difference between Type1 and Integer to be ignored by the compiler in an expression.

7.      Describe a situation in which the add operator in a programming language would not be commutative.

 An expression such as a + fun(b)

8.      Describe a situation in which the add operator in a programming language would not be associative.

Consider the integer expression A + B + C. Suppose the values of A, B, and C are 20,000, 25,000, and -20,000, respectively. Further suppose that the machine has a maximum integer value of 32,767. If the first addition is computed first, it will result in overflow. If the second addition is done first, the whole expression can be correctly computed.

9.      Assume the following rules of associativity and precedence for expressions:

Precedence Highest *, /, not

+, , &, mod


=, /=, < , <=, >=, >


Lowest or, xor

Associativity Left to right


Show the order of evaluation of the following expressions by parenthesizing

all subexpressions and placing a superscript on the right parenthesis

to indicate order. For example, for the expression

a + b * c + d

the order of evaluation would be represented as

((a + (b * c)1)2 + d)3

a. a * b – 1 + c

b. a * (b – 1) / c mod d

c. (a – b) / c & (d * e / a – 3)

d. -a or c = d and e

e. a > b xor c or d <= 17

f. -a + b

(a) ( ( ( a * b )1 – 1 )2 + c )3

(b) ( ( ( a * ( b – 1 )1 )2 / c )3 mod d )4

(c) ( ( ( a – b )1 / c )2 & ( ( ( d * e )3 / a )4 – 3 )5 )6

(d) ( ( ( – a )1 or ( c = d )2 )3 and e )4

(e) ( ( a > b )1 xor ( c or ( d <= 17 )2 )3 )4

(f) ( – (a + b)1 )2


 10.  Show the order evaluation of the expression of problem 9, assuming that there are no precedence rules and all operators associate right to left.

(a) ( a * ( b – ( 1 + c )1 )2 )3

(b) ( a * ( ( b – 1 )2 / ( c mod d )1 )3 )4

(c) ( ( a – b )5 / ( c & ( d * ( e / ( a – 3 )1 )2 )3 )4 )6

(d) ( – ( a or ( c = ( d and e )1 )2 )3 )4

(e) ( a > ( xor ( c or ( d <= 17 )1 )2 )3 )4

(f) ( – ( a + b )1 )2

11.  Write a BNF description of the precedence and associativity rules defined for the expressions in Problem 9. Assume the only operands are the names a,b,c,d, and e.

<expr> → <expr> or <e1> | <expr> xor <e1> | <e1>

<e1> → <e1> and <e2> | <e2>

<e2> → <e2> = <e3> | <e2> /= <e3> | <e2> < <e3>

| <e2> <= <e3> | <e2> > <e3> | <e2> >= <e3> | <e3>

<e3> → <e4>

<e4> → <e4> + <e5> | <e4> – <e5> | <e4> & <e5> | <e4> mod <e5> | <e5>

<e5> → <e5> * <e6> | <e5> / <e6> | not <e5> | <e6>

<e6> → a | b | c | d | e | const | ( <expr> )

Chapter 6 Answers

Review Questions

1.      What is a descriptor?

A descriptor is the collection of the attributes of a variable. In an implementation, a descriptor is an area of memory that stores the attributes of a variable. If the attributes are all static, descriptors are required only at compile time. These descriptors are built by the compiler, usually as a part of the symbol table, and are used during compilation.

2.      What are the advantages and disadvantages of decimal data types?

Decimal types have the advantage of being able to precisely store decimal values, at least those within a restricted range, which cannot be done with floating-point. The disadvantages of decimal types are that the range of values is restricted because no exponents are allowed, and their representation in memory is mildly wasteful.

3.      What are the design issues for character string types?

The two most important design issues that are specific to character string types are the following:

  • • Should strings be simply a special kind of character array or a primitive type?
  • • Should strings have static or dynamic length?

4.      Describe the three string length options.

There are several design choices regarding the length of string values. First, the length can be static and set when the string is created. Such a string is called a static length string. This is the choice for the strings of Python, the immutable objects of Java’s String class, as well as similar classes in the C++ standard class library, Ruby’s built-in String class, and the .NET class library available to C# and F#.

The second option is to allow strings to have varying length up to a declared and fixed maximum set by the variable’s definition, as exemplified by the strings in C and the C-style strings of C++. These are called limited dynamic length strings. Such string variables can store any number of characters between zero and the maximum. Recall that strings in C use a special character to indicate the end of the string’s characters, rather than maintaining the string length.

The third option is to allow strings to have varying length with no maximum, as in JavaScript, Perl, and the standard C++ library. These are called dynamic length strings. This option requires the overhead of dynamic storage allocation and deallocation but provides maximum flexibility.

6.      What are the advantages of user-defined enumeration types?

Enumeration types can provide advantages in both readability and reliability. Readability is enhanced very directly: Named values are easily recognized, whereas coded values are not.

8.      What are the design issues for arrays?

The primary design issues specific to arrays are the following:

  • • What types are legal for subscripts?
  • • Are subscripting expressions in element references range checked?
  • • When are subscript ranges bound?
  • • When does array allocation take place?
  • • Are ragged or rectangular multidimensioned arrays allowed, or both?
  • • Can arrays be initialized when they have their storage allocated?
  • • What kinds of slices are allowed, if any?

18.  What is an access function for an array?

Arrays are part of most programming languages. The relationship between a reference to an array element and the address of that element is given in an access function, which is an implementation of a mapping.

20.  What is the structure of an associative array?

In Perl, associative arrays are called hashes, because in the implementation their elements are stored and retrieved with hash functions. The namespace for Perl hashes is distinct: Every hash variable name must begin with a percent sign (%). Each hash element consists of two parts: a key, which is a string, and a value, which is a scalar (number, string, or reference). Hashes can be set to literal values with the assignment statement, as in

%salaries = (“Gary” => 75000, “Perry” => 57000,

“Mary” => 55750, “Cedric” => 47850);

21.  What are the purpose of level numbers in COBOL?

level numbers in COBOL indicate by their relative values the hierarchical structure of the record.          Any line that is followed by a line with a higher-level number is itself a record.

 24.  Are the tuples of Python mutable?

No, tuples are immutable because otherwise there wouldn’t be an immutable sequence type.

43.  What is a compatible type?

A compatible type is one that either is legal for the operator or is allowed under language rules to be implicitly converted by compiler-generated code (or the interpreter) to a legal type.

50.  What is name type equivalence?

Name type equivalence means that two variables have equivalent types if they are defined either in the same declaration or in declarations that use the same type name.


Problem Set

 2.      How are negative integers stored in memory?

A negative integer could be stored in sign-magnitude notation, in which the sign bit is set to indicate negative and the remainder of the bit string represents the absolute value of the number. Sign-magnitude notation, however, does not lend itself to computer arithmetic. Most computers now use a notation called twos complement to store negative integers, which is convenient for addition and subtraction. In twos-complement notation, the representation of a negative integer is formed by taking the logical complement of the positive version of the number and adding one. Ones-complement notation is still used by some computers. In ones-complement notation, the negative of an integer is stored as the logical complement of its absolute value. Ones-complement notation has the disadvantage that it has two representations of zero.

 3.      The collection of values that can be represented by a floating-point type is defined in terms of precision and range. What are precision and range ? Show the IEEE Floating-Point Standard 754 format for single- and double-precision representation.

The collection of values that can be represented by a floating-point type is defined in terms of precision and range. Precision is the accuracy of the fractional part of a value, measured as the number of bits. Range is a combination of the range of fractions and, more important, the range of exponents.

chapter 6 problem set 3



5.      What disadvantages are there in implicit deferencing of pointers, but only in certain contexts? For example , consider the implicit deference of a pointer to a record in Ada when it is used to reference a record field.

When implicit dereferencing of pointers occurs only in certain contexts, it makes the language slightly less orthogonal. The context of the reference to the pointer determines its meaning. This detracts from the readability of the language and makes it slightly more difficult to learn.

7.      Compare the pointer and reference type variable in C++.

fundamental difference: A pointer refers to an address in memory, while a reference refers to an object or a value in memory. As a result, although it is natural to perform arithmetic on addresses, it is not sensible to do arithmetic on references. C++ includes a special kind of reference type that is used primarily for the formal parameters in function definitions. A C++ reference type variable is a constant pointer that is always implicitly dereferenced. Because a C++ reference type variable is a constant, it must be initialized with the address of some variable in its definition, and after initialization a reference type variable can never be set to reference any other variable. The implicit dereference prevents assignment to the address value of a reference variable. Reference type variables are specified in definitions by preceding their names with ampersands (&). For example,

int result = 0;

int &ref_result = result;

. . .

ref_result = 100;

In this code segment, result and ref_result are aliases.

8.      What are the differences between the reference type variable of C++ and those of Java?

In their quest for increased safety over C++, the designers of Java removed C++-style pointers altogether. Unlike C++ reference variables, Java reference variables can be assigned to refer to different class instances; they are not constants. All Java class instances are referenced by reference variables. That is, in fact, the only use of reference variables in Java.

17.  What kind of conversion is called a nonconverting cast? Explain with example in Ada language.

Ada is nearly strongly typed. It is only nearly strongly typed because it allows programmers to breach the type-checking rules by specifically requesting that type checking be suspended for a particular type conversion. This temporary suspension of type checking can be done only when an instantiation of the generic function Unchecked_Conversion is called. Such functions can be instantiated for any pair of subtypes. One takes a value of its parameter type and returns the bit string that is the parameter’s current value. No actual conversion takes place; it is merely a means of extracting the value of a variable of one type and using it as if it were of a different type. This kind of conversion is sometimes called a nonconverting cast.