Chapter 16

Review Questions

1. What are the three primary uses of symbolic logic in formal logic?
– Express propositions
– Express relationships between propositions
– Describe how new propositions can be inferred from other propositions

2. What are the two parts of a compound term?
– Functor: function symbol that names the relationship
– Ordered list of parameters (tuple)

3. What are the two modes in which a proposition can be stated?
Fact and query

4. What is the general form of a proposition in clausal form?
B1 u B2 u … u Bn c A1 n A2 n … n Am
means if all the As are true, then at least one B is true

5. What are antecedents? Consequents?
Antecedents are right side of a clausal form proposition. Consequent is left side of a clausal form propositions

7. What are the forms of Horn clauses?
Headed and headless.

9. What does it mean for a language to be nonprocedural?
Programs do not state now a result is to be computed, but rather the form of the result

11. What is an uninstantiated variable?
An uninstantiated variable is a variable that has not been assigned a value

13. What is a conjunction?
Conjunctions contain multiple terms that are separated by logical AND operations

Problem Set

1. Compare the concept of data typing in Ada with that of Prolog.
Ada variables are statically bound to types. Prolog variables are bound to types only when they are bound to values. These bindings take place during execution and are tempoarary.

2. Describe how a multiple-processor machine could be used to implement resolution. Could Prolog, as currently defined, use this method?
On a single processor machine, the resolution process takes place on the rule base, one rule at a time, starting with the first rule, and progressing toward the last until a match is found. Because the process on each rule is independent of the process on the other rules, separate processors could concurrently operate on separate rules. When any of the processors finds a match, all resolution processing could terminate.

6. Explain two ways in which the list-processing capabilities of Scheme and Prolog are similar.
The list processing capabilities of Scheme and Prolog are similar in that they both treat lists as consisting of two parts, head and tail, and in that they use recursion to traverse and process lists.

7. In what way are the list-processing capabilities of Scheme and Prolog different?
The list processing capabilities of Scheme and Prolog are different in that Scheme relies on the primitive functions CAR, CDR, and CONS to build and dismantle lists, whereas with Prolog these functions are not necessary

Chapter 15

Review Questions

1. Define functional form, simple list, bound variable, and referential transparency.
– Functional form : one that either takes one or more functions as parameters or yields a function as its result.
– Simple list : A list that does not include sublist.
– Bound variable : A bound variable is a variable which never changes in the expression after being bound to an actual parameter value at the time evaluation of the lambda expressions begin.
– Referential transparency : A state where execution of function always produces the same result when given the same parameters.

2. What does a lambda expression specify?
Lambda expressions describe nameless functions

3. What data types were parts of the original LISP?
Originally only atoms and lists

4. In what common data structure are LISP lists normally stored?
LISP lists are stored internally as single-linked lists

5. Explain why QUOTE is needed for a parameter that is a data list.
QUOTE is required because the Scheme interpreter, named EVAL, always evaluates parameters to function applications before applying the function. QUOTE is used to avoid parameter evaluation when it is not appropriate

6. What is a simple list?
A list that does not include a sublist.

7. What does the abbreviation REPL stand for?
Infinite Read-Evaluate-Print Loop

8. What are the three parameters to IF?
A predicate expression, a then expression, and else expression.

11. What are the two forms of DEFINE?
– To bind a symbol to an expression
– To bind names to lambda expressions

Problem Set

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. It is used to chain together function calls while flowing the data being processed to each call.

9. What does the following Scheme function do?
(define (y s lis)
(cond
((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.

Chapter 14

Review Questions

6. What are the possible frames for exceptions in Ada?
– The frame of an exception handler in Ada is either a subprogram body, a package body, a task, or a block

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:
– Constraint_aError
– Program_Error
– Storage_Error
– Tasking_Error
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.

2.Describe the approach for the detection of subscript range errors used in C and Java.
-In C subscript ranges are not checked. Java compilers usually generate code to check the correctness of every subscript expression. If any exception generates, then an unchecked exception is thrown.

6.In languages without exception-handling facilities, it is common to have most subprograms include an “error” parameter, which can be set to some values 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 languages without exception-handling facilities, we could send an error-handling procedure as parameter to each procedure that can detect errors than must be handled. What disadvantage 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.

14. Summarize the arguments in favor of the termination and resumption models of continuation.
– The resumption model is useful when the exception is only an unusual condition, rather than an error. The termination model is useful when the exception is an error and it is highly unlikely that the error can be corrected so that execution could continue in some useful way.

Chapter 13

Review Questions

1. What are the three possible levels of concurrency in programs?
Instruction level, Statement level, and Unit level

2. Describe the logical architecture of an SIMD computer.
Computers that have multiple processors that execute the same instruction simultaneously

3. Describe the logical architecture of an MIMD computer.
Computers that have multiple processors that operate independently but whose operations can be synchronized

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

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

6. Describe the logical architecture of a vector processor.
Vector processors 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

7. What is the difference between physical and logical concurrency?
Physical concurrency – Multiple independent processors (multiple threads of control)
Logical concurrency – The appearance of physical concurrency is presented by time-sharing one processor (software can be designed as if there were multiple threads of control)

8. What is a thread of control in a program?
A thread of control in a program is the sequence of program points reached as control flows through the program

12. What is a heavyweight task? What is a lightweight task?
Heavyweight tasks execute in their own address space. Lightweight tasks all run in the same address space – more efficient

Problem Set

1. Explain clearly why competition synchronization is not a problem in a programming environment that supports coroutines but not concurrency.
Competition synchronization is not necessary when no actual concurrency takes place simply because there can be no concurrent contention for shared resources. Two nonconcurrent processes cannot arrive at a resource at the same time.

2. What is the best action a system can take when deadlock is detected?
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 would 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.

6. Suppose two tasks, A and B, must use the shared variable Buf_Size. Task A adds 2 to Buf_Size, and task B subtracts 1 from it. Assume that such arithmetic operations are done by the three-step process of fetching the current value, performing the arithmetic, and putting the new value back. In the absence of competition synchronization, what sequences of events are possible and what values result from these operations? Assume that the initial value of Buf_Size is 6.
Sequence 1: A fetches the value of BUF_SIZE (6)

A adds 2 to the value (8)

A puts 8 in BUF_SIZE

B fetches the value of BUF_SIZE (8)

B subtracts 1 (7)

B put 7 in BUF_SIZE

BUF_SIZE = 7

Sequence 2: A fetches the value of BUF_SIZE (6)

B fetches the value of BUF_SIZE (6)

A adds 2 (8)

B subtracts 1 (5)

A puts 8 in BUF_SIZE

B puts 5 in BUF_SIZE

BUF_SIZE = 5

Sequence 3: A fetches the value of BUF_SIZE (6)

B fetches the value of BUF_SIZE (6)

A adds 2 (8)

B subtracts 1 (5)

B puts 5 in BUF_SIZE

A puts 8 in BUF_SIZE

BUF_SIZE = 8

Many other sequences are possible, but all produce the values 5, 7, or 8.

Chapter 12

Review Questions

1. Describe the three characteristic features of object-oriented languages.
Abstract data types, Inheritance and Polymorphism.

2. What is the difference between a class variable and an instance variable?
The difference between instance and class variables is. Class variables only have one copy that is shared by all the different objects of a class, whereas every object has it’s own personal copy of an instance variable. So, instance variables across different objects can have different values whereas class variables across different objects can have only one value.

3. What is multiple inheritance?
An inheritance which allows a new class to inherit from two or more classes

4. What is a polymorphic variable?
A polymorphic variable can be defined in a class that is able to reference (or point to) objects of the class and objects of any of its descendants

5. What is an overriding method?
Overriding method is a method that purpose is provide an operation in the subclass that is similar to one in the parent class, but is customized for objects of the subclass.

7. What is a virtual method?
Virtual method is a function or method whose behavior can be overridden within an inheriting class by a function with the same signature.

8. What is an abstract method? What is an abstract class?
An abstract method is one that does not include a definition (it only defines a protocol). An abstract class is one that includes at least one virtual method. An abstract class cannot be instantiated

10. What is a nesting class?
Nesting class is a class whose definition appears inside the definition of another class, as if it were a member of the other class.

11. What is the message protocol of an object?
Message protocol of an object is the entire collection of methods of an object

19. How are C++ heap-allocated objects deallocated?
C++ heap-allocated objects are deallocated using destructor

29. Does Objective-C support multiple inheritance?
No Objective-C doesn’t support it. (It supports only single inheritance)

Problem Set

3. Compare the dynamic binding of C++ and Java.
In C++, a method can only be dynamically bound if all of its ancestors are marked virtual. Be default, all method binding is static. In Java, method binding is dynamic by default. Static binding only occurs if the method is marked final, which means it cannot be overriden.

5. Compare the class entity access controls of C++ and Ada 95.
C++ has extensive access controls to its class entities. Individual entities can be marked public, private, or protected, and the derivation process itself can impose further access controls by being private. Ada, on the other hand, has no way to restrict inheritance of entities (other than through child libraries, which this book does not describe), and no access controls for the derivation process.

Chapter 11

Review Questions

1. What are the two kinds of abstractions in programming language?

– Process abstraction and data abstraction.

2. Define abstract data type.
Data type that satisfies the following conditions:
-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.

8. What is the difference between private and limited private types in Ada?
– Limited private is more restricted form and objects of a type that is declared limited private have no built-in operations.

10. What is the use of the Ada with clause?
– With clause makes the names defined in external packages visible; in this case Ada. Text_IO, which provides functions for input of text.

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

12. What is the fundamental difference between a C++ class and an Ada package?
– Ada packages are more generalize encapsulations that can define any number of types.

15. What is the purpose of a C++ destructor?
– The purpose of a C++ desctructor is 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.

16. What are the legal return types of a desctructor?
-Destructor has no return types and doesn’t use return statements.

21. What are initializers in Objective-C?
– The initializers in Objective-C are constructors.

22. What is the use of @private and @public directives?
– The use is to specify the access levels of the instance variables in a class definition.

27. Where are all Java methods defined?
– All Java methods are defined in a class.

Problem Set

4. What are the advantages of the nonpointer concept in Java?
– Any task that would require arrays, structures, and pointers in C can be more easily and reliably performed by declaring objects and arrays of objects. Instead of complex pointer manipulation on array pointers, you access arrays by their arithmetic indices. The Java run-time system checks all array indexing to ensure indices are within the bounds of the array. You no longer have dangling pointers and trashing of memory because of incorrect pointers, because there are no pointers in Java.

9. What happens if the constructor is absent in Java and C++?
– It will be made automatically by the built-up in.

10. Which two conditions make data type “abstract” ?
– The representation, or definition, of the type and the operations are contained in a single syntactic unit
– The representation of objects of the type is hidden from the program units that use the type, so only direct operations possible on those objects are those provided in the type’s definition

17. The namespace of the C# standard library, System, is not implicitly available to C# programs. Do you think this is a good idea? Defend your answer.
=> I think it is not, because it reduces its efficiency.

19. Compare Java’s packages with Ruby’s modules.
– In Ruby, the require statement is used to import a package or a module. For example, the extensions package/module is imported as follows.
– require ‘extensions’
External files may be included in a Ruby application by using load or require. For example, to include the external file catalog.rb, add the following require statement.
-require “catalog.rb”
The difference between load and require is that load includes the specified Ruby file every time the method is executed and require includes the Ruby file only once.
In Java, the import statement is used to load a package. For example, a Java package java.sql is loaded as follows.

Chapter 10

Review Questions

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

2. Which of the caller of callee saves execution status information?
Either can save the execution status

3. What must be stored for the linkage to a subprogram?
Execution status information

4. What is the task of a linker?
Find files that contain the translated subprograms referenced in that program and load them into memory, set target addresses of all calls to those subprograms in the main program to the entry addresses of those subprograms.

8. What kind of machines often use registers to pass parameters?
RISC Machines

12. How are references to variables represented in the static-chain method?
It is represented by static depth.

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.