Sixteenth Chapter : Logic Programming Languages

Review

1. What are the three primary uses of symbolic logic in formal logic ?
Answer: to express propositions, to express the relationships between propositions, and to
describe how new propositions can be inferred from other propositions that
are assumed to be true.

2. What are the two parts of a compound term ?
Answer: function and and ordered list of of parameters

3. What are the two modes in which a proposition can be stated ?
Answer: one in which a proposition is defined to be true and one in which that the proposition is something to be determined.

4. What is general form of a proposition in clausal form ?
Answer: B1 U B2 U . . . U Bn C A1 n A2 n . . . n Am

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

6. Give general definitions of resolution and unification
Answer:

Resolution : inference rule that allows inferred propositions to be computed from given propositions, thus providing a method with potential application to automatic theorem proving.
Unification : Process of determining useful values for variables.

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

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

Problem Set

1. Compare the concept of data typing in Ada with that of Prolog.
Answer: 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?

Answer: 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.

9. From a book on Prolog, learn and write a description of a monkey-banana prolem. Why does Prolog allow this problem to exist in its implementation ?
Answer: The problem is defined as this : a monkey is in a room. Suspended from the ceiling is a bunch of bananas, beyond the monkey’s reach. However, in the room there are also a chair and a stick. The ceiling is just the right height so that a monkey standing on a chair could knock the bananas down with the stick. The monkey knows how to move around, carry other things around, reach for the bananas, and wave a stick in the air. What is the best sequence of actions for the monkey?
It exists to create a variation in output of Prolog. As Prolog is an AI programming language, a variation might be needed in AI output to make them respond relevant to the situation.

Fifteenth Chapter : Functional Programming Languages

Review

2. What does a lambda expression specify?
Answer: 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.
Answer: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?
Answer: 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?
Answer: REPL stand for read-evaluate-print loop.

11. What are the two forms of DEFINE?
Answer: 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) (expression)

27. What is the use of the fn reserved word in ML?

Answer: 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.

29. What is a curried function?

Answer: Curried functions are interesting and useful because new functions can be constructed from them by partial evaluation.

30. What does partial evaluation mean?

Answer: Partial evaluation means that the function is evaluated with actual parameters for one or more of the leftmost formal parameters.

31. Define reader macros.

Answer: Reader macros or read macros, that are expanded during the reader phase of a LISP languageprocessor. A reader macro expands a specific character into a string of LISP code. For example, the apostrophe in LISP is a read macro that expands to a call to QUOTE. Users can define their own reader macros to create other shorthand constructs.

32.What is the use of evaluation environment table?

Answer: 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. When an identifier is declared, either implicitly or explicitly, it is placed in the evaluation environment.

Problem Set

8.How is the functional operator pipeline(|>)used in F#?

Answer: 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. Consider the following example code, which uses the high-order functions filter and map:

let myNums = [1; 2; 3; 4; 5]

let evensTimesFive = myNums

|> List.filter (fun n −> n % 2 = 0)

|> List.map (fun n −> 5 * n)

 

9. What does the following Scheme function do?
Answer:

(define (y s lis)
(cond
((null? lis) ‘() )
((equal? s (car lis)) lis)

10.What does  the following Scheme function do?
Answer:
(define ( x lis)
(cond
(( null? lis) 0 )
(( not(list? (car lis)))
(cond
((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-#f atoms in the given list
(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.

Fourteenth Chapter : Exception Handling and Event Handling

Review

6. What is exception propagation in Ada?
Answer: 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?
Answer: 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?
Answer: There are four exceptions that are defined in the default package, Standard:
– Constraint_Error
– Program_Error
– Storage_Error
– Tasking_Error

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

12. What is the use of Suppress pragma in Ada?
Answer: 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?
Answer: Try clause.

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

31. What is the use of the assert statement?
Answer: 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?
Answer: 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?
Answer: 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?
Answer: 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 to attempt to deal with errors ?

Answer: There were no possibility for the user program to detect or attempt to deal with errors. In case if error happens, the program will be terminated and control will be transferred to the operating system.

2. Describe the approach for the detection of subscript range errors used in C and Java.

Answer: C does not check subscript ranges. While in Java, compilers usually generate a code to check the correctness of every subscript expression. If any exception generates, 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 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?
Answer: 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?

Answer: 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.

Thirteenth Chapter : Concurrency

Review

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

– 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)

7. What is the difference between physical and logical concurrency?
Answer: Physical concurrency is several program units from the same program that literally execute simultaneously. Logical concurrency is multiple processors providing actual concurrency, when in fact the actual execution of programs is taking place in interleaved fashion on a single processor.

8. What is the work of a scheduler?
Answer: Scheduler manages the sharing of processors among the tasks.

12. What is a heavyweight task? What is a lightweight task?
Answer: Heavyweight task executes in its own address space. Lightweight task all run in the same address space.

16. What is a task descriptor?
Answer: Task descriptor is a data structure that stores all of the relevant information about the execution state of a task.

18. What is the purpose of a task-ready queue?
Answer: The purpose of a task-ready queue is to be storage of tasks that are ready to run.

21. What is a binary semaphore? What is a counting semaphore?
Answer: Binary semaphore is a semaphore that requires only a binary-valued counter, like the one used to provide competition synchronization. A counting semaphore is a synchronization object that can have an arbitrarily large number of states.

30. What is purpose of an Ada terminate clause?
Answer: The purpose of an Ada terminate clause is to mark that the task is finished with its job but is not yet terminated.

34. What does the Java sleep method do?
Answer: Sleep method blocks the the thread.

35. What does the Java yield method do?
Answer: Yield method surrenders the processor voluntarily as a request from the running thread.

36. What does the Java join method do?
Answer: Java forces a method to delay its execution until the run method of another thread has completed its execution.

37. What does the Java interrupt method do?
Answer: Interrupt becomes one way to communicate to a thread that it should stop.

55. What is Concurrent ML?
Answer: Concurrent ML is an extension to ML that includes a form of threads and a form of synchronous message passing to support concurrency.

56. What is the use of the spawn primitive of CML?
Answer: The use of Spawn primitive of CML is to create a thread.

57. What is the use of subprograms BeginInvoke and EndInvoke in F#?
Answer: The use of subprograms BeginInvoke and Endinvoke in F# is to call threads asynchronously.

58. What is the use of the DISTRIBUTE and ALIGN specification of HPC?
Answer: The use of DISTRIBUTE and ALIGN specification of HPC is to provide information to the compiler on machines that do not share memory, that is, each processor has its own memory.

Problem Set

1. Explain clearly why a race condition can create problems for a system.
Answer: Because 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). The importance of competition synchronization should now be clear.

2. What are the different ways to handle deadlock?
Answer:

– Ignoring deadlock
– Detection
– Prevention
– Avoidance

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?
Answer: Busy-waiting or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input or a lock is available. Spinning can also be used to generate an arbitrary time delay, a technique that was necessary on systems that lacked a method of waiting a specific length of time. Processor speeds vary greatly from computer to computer, especially as some processors are designed to dynamically adjust speed based on external factors, such as the load on the operating system. Busy waiting may loop forever and it may cause a computer freezing.

Tweltfth Chapter : Support for Object-Oriented Programming

Review

1. Name two functional languages that support object-oriented programming.
Answer: C++ and Objective-c

2. What are the problems associated with programming using abstract data types ?
Answer: in nearly all cases, the features and capabilities of the existing type are not quite right for the new
use. The old type requires at least some minor modifications.

3. What is the advantage of inheritance ?
Answer: Allows to reuse ADT and modificate it without actually modifying the original ADT and program organization problem.

4. What is message protocol ?
Answer: Entire collection of methods of an object.

5. What is an overriding method ?
Answer: A new method that overrides inherited method(i.e. Changes how the method behaviors compared to the inherited one)

15. What kind of inheritance, single or multiple, does Smalltalk support?
Answer: Smalltalk supports single inheritance; it does not allow multiple inheritance.

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

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

33. What is the purpose of an Objective-C category?
Answer: The purpose of an Objective-C category is to add certain functionalities to different classes and also to 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.

38. What is boxing?
Answer: Boxing is primitive values in Java 5.0+ which is implicitly coerced when they are put in object context. This coercion converts the primitive value to an object of the wrapper class of the primitive value’s type.

39. How are Java objects deallocated?
Answer: By implicitly calling a finalize method when the garbage collector is about to reclaim the storage occupied by the object.

Problem Set

2. In what ways can “compatible “ be defined for the relationship between an overridden method and the overriding method ?
Answer: In ways of its formal definition, the parameters and return types.

3. Compare the inheritance of C++ and Java.
Answer:

-In Java, all objects are Inherited, either directly or indirectly. While in C++ a class can be defined to stand on its own without an ancestor.

– In Java, there’s no access level specifier of inheritance, while C++ has private public and protected.

– In Java, the functions are virtual by default. While in C++ the functions CAN BE MADE virtual with the keyword virtual

5. Compare the class entity access controls of C++ and Ada 95.
Answer: 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.

7. What is one programming situation where multiple inheritance has a significant disadvantage over interfaces ?
Answer: When two or more parent classes are derived from one grandparent class and has one child. (diamond problem)

Eleventh Chapter : Abstract Data Types and Encapsulation Constructs

Review

1. What are three primary uses of symbolic logic in formal logic?
Answer:

– to express propositions
– to express the relationships between propositions, and
– to describe how new propositions can be inferred from other propositions that are assumed to be true.

2. Define abstract data type .

Answer: A data structure in the form of a record, but which includes subprograms that manipulate its data.

3. What are the two modes in which a proposition can be stated?
Answer: Propositions can be stated in two modes: one in which the proposition is defined to be true, and one in which the truth of the proposition is something that is to be determined. In other words, propositions can be stated to be facts or queries.

5. What are antecedents? Consequent?
Answer: Antecedents are the right side of clausal form propositions, whereas Consequents are the left side of clausal form propositions, because it is the consequence of the truth of the antecedent.

7. What are the forms of Horn clauses?
Answer: Horn clauses can be in only two forms: They have either a single atomic proposition on the left side or an empty left side. The left side of a clausal form proposition is sometimes called the head, and Horn clauses with left sides are called headed Horn clauses. Headed Horn clauses are used to state relationships, such as likes( bob, trout ) likes( bob, fish ) x fish( trout )

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

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

Problem Set

2. Suppose someone designed a stack abstract data type in which the function top returned an access path (or pointer ) rather than returning a copy of the top element. This is not a true data abstraction. Why ? Give an example that illustrates the problem.

Answer: The problem with this is that the user is given access to the stack through the returned value of the “top” function. For example, if p is a pointer to objects of the type stored in the stack, we could have:

p = top(stack1);

*p = 42;

These statements access the stack directly, which violates the principle of a data abstraction.

4. What are the advantages of the non-pointer concept in Java ?

Answer:

Variable Access are absolutely defined by the programmer

– No memory leak (i.e. dangling pointers, nameless variables etc)

9. What happens if the constructor is absent in Java and C++ ?
Answer: The compiler will automatically make a default one

11. Why is the destructor of C# rarely used ?
Answer: Because C# has its own garbage collection method , just like Java

Tenth Chapter : Implementing Subprograms

Review

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

2. Which of the caller or callee saves execution status information?
Answer: Called.

4. What is the task of a linker?
Answer: The task of a linker is to find the files that contain the translated subprograms referenced in that program and load them into memory.

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

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

Problem Set

6. Although local variables in Java methods are dynamically allocated at the beginning of each activation, under what circumstances could the value of a local variable in a particular activation retain the value of previous activation ?

Answer: If the variable is declared as static. Static modifier is a modifier that makes a variable history – sensitive.

8. Pascal allows gotos with non-local targets. How could such statements be handled if static chains were used for non-local 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).
Answer: 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 non-local references ?

Answer: Including two static links would reduce the access time to non-locals that are defined in scopes two steps away to be equal to that for non-locals that are one step away. Overall, because most non-local references are relatively close, this could significantly increase the execution efficiency of many programs.