Concept of Programming Languages – Chapter 16 (Logic Programming Languages)

Review Question
1. What are the three primary uses of symbolic logic in formal logic ?
– 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 ?
– functor and and ordered list of of parameters

3. What are the two modes in which a proposition can be stated ?
– 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 ?
-B1 U B2 U . . . U Bn C A1 n A2 n . . . n Am

5. What are antecedents ? Consequents ?
– 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
– 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 ?
– a. Have a single atomic proposition on the left side
b. empty left side.

9. What does it mean for a language to be nonprocedural ?
– Language in which the programs do not exactly state how a result is to be computed but rather describe the form of the result.

Problem Set
1. “All predicate calculus propositions can be algorithmically converted to clausal form”. Is this statement true or false ? Explain.
– True.

8. Critically comment on the following statement : “ Logic programs are nonprocedural”
– It is true, because logical programs use lots of different processes based on its conditions. If a certain logical requirement is true, then a program will execute the corresponding process, instead of procedurally executing the statements.

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 ?
– 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.

Concept of Programming Languages – Chapter 15 (Functional Programming Languages)

REVIEW QUESTION:

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)
(expression)
)

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
4. Refer to a book on Haskell programming and discuss the feature of Haskell.
– Haskell features lazy evaluation, pattern matching, list comprehension, type classes, and type polymorphism. It is a purely functional language, which means that in general, functions in Haskell do not have side effects. There is a distinct construct for representing side effects, orthogonal to the type of functions. A pure function may return a side effect which is subsequently executed, modeling the impure functions of other languages.
Haskell has a strong, static type system based on Hindley–Milner type inference. Haskell’s principal innovation in this area is to add type classes, which were originally conceived as a principled way to add overloading to the language, but have since found many more uses.
The construct which represents side effects is an example of a monad. Monads are a general framework which can model different kinds of computation, including error handling, nondeterminism, parsing, and software transactional memory. Monads are defined as ordinary datatypes, but Haskell provides some syntactic sugar for their use.

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

10. What does the following Scheme functions do ?
(define (x lis)
(cond
((null ? lis) 0)
((not (list? (car lis)))
(cond
((eq? (car lis) #) (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.

Concept of Programming Languages – Chapter 14 (Exception Handling and Event Handling)

REVIEW QUESTION:
1. Define exception, exception handler, raising an exception, disabling an exception, continuation, finalization, and built-in exception.

– Exception : any unusual event, erroneous or not, that is detectable by either hardware or software and that may require special processing.

Exception handler : a code unit which processes an exception.

Raising an exception : When a event associated with an exception occurs

Disabling an exception : Ignoring a certain hardware-detectable exceptions.

Continuation : Control transfer to somewhere in the program outside of the handler code or program might terminate .

Finalization : ability to complete some computation regardless of how subprogram execution terminates.

Built-in exception : Exception that is not made by the user, but rather comes as default.

2. When is an exception thrown or raised ?
– When an event associated with an exception occurs

3. What are the advantages of having support for exception handling built in to a language ?

– Without built-in exception handling, the code to detect error condition can be a clutter to the program. Existence of built-in exception handling would simplify a source program.

4. Give an example of hardware-detectable execution.

– Division by zero

5. What does it mean for an exception to be bound to an exception handler ?

– A specific exception is to be handled by a specific exception handler also, because different exceptions are to be treated differently.

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 ?

– Constraint_Error,Program_Error,Storage_Error, and Tasking_Error.

11. Are there any predefined exceptions in Ada ?

– Yes, there are, for example Ada.Text_IO defines the End_Error exception.

12. What is the use of Suppress pragma in Ada ?
– Run-time checks that are parts of built-in exceptions can be disabled in Ada programs

13. Describe three problems with Ada’s exception handling.

– The propagation model, which allows exceptions to be propagated to an outer scope in which the exception is not visible, inadequacy of exception handling for tasks, and exception handling was not extended to deal with new constructs in Ada 95.

Problem Set
1. What mechanism did early programming languages provide to detect to attempt to deal with errors ?

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

– 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 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, for example in Ada, using an error flag parameter in all subprograms. One advantage is that the code to test the error is eliminated after every call. Such test code makes program longer and harder to read. Second advantage is that exceptions can be propagated farther in a uniform and implicit way. Also, there is an advantage that all program use a similar method to deal with exceptions, which enhances 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.

Concept of Programming Languages – Chapter 13 (Concurrency)

REVIEW QUESTION:

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

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

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?

Scheduler manages the sharing of processors among the tasks.

12. What is a heavyweight task? What is a lightweight task?

Heavyweight task executes in its own address space. Lightweight task all run in the same address space.

16. What is a task descriptor?

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?

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?

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?

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?

Sleep method blocks the the thread.

35. What does the Java yield method do?

Yield method surrenders the processor voluntarily as a request from the running thread.

36. What does the Java join method do?

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?

Interrupt becomes one way to communicate to a thread that it should stop.

55. What is Concurrent ML?

Concurrent ML is an extension to ML that includes a fform of threads and a form of synchronous message passing to support concurrency.

56. What is the use of the spawn primitive of CML?

The use of Spawn primitive of CML is to create a thread.

57. What is the use of subprograms BeginInvoke and EndInvoke in F#?

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?

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.

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?

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

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.

Concept of Programming Languages – Chapter 12 (Support for Object-Oriented Programming)

REVIEW QUESTION:

2. What are the problems associated with programming using abstract data types?

-In nearly all cases, the features and capabilities of the existing type are not quite right for the new use.

-The type definitions are all independent and are at the same level.

4. What is message protocol?

Message protocol is the entire collection of methods of an object.

5. What is an overriding method?

Overriding method is method that overrides the inherited method.

7. What is dynamic dispatch?

Dynamic dispatch is the third characteristic (after abstract data types and inheritance) of object-oriented programming language which is a kind of polymorhphism provided by the dynamic binding of messages to method definitions.

12. From where are Smalltalk objects allocated?

Smalltalk objects are allocated from the heap and are referenced through reference variables, which are implicitly dereferenced.

15. What kind of inheritance, single or multiple, does Smalltalk support?

Smalltalk supports single inheritance; it does not allow multiple inheritance.

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

33. What is the purpose of an Objective-C category?

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?

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?

By implicitly calling a finaliz emethod 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 ?
– in ways of its formal definition, the parameters and return types.

3. Compare the inheritance of C++ and Java.
– 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

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

9. Given an example of inheritance in C++, where a subclass overrides the superclass methods.
– class human{
public :
void eat(){std::cout<<”Eating”;}
}
class man : public human{
public :
void eat(){std::cout<<”Eat like a boss”;}
}

10. Explain one advantage of inheritance
– Allows programmer to reuse a class with modifications that doesn’t apply to the initial class, so both class can still be used. This also improves readability and writability.

14. Explain type checking in Java
-Type checking happens before execution. Type checking can only uses type information that have declared in your program, and not the possible type that an object has at runtime. Java checks all line of code to make sure that it uses values correctly according to the declared types.

16. State why Java is said to be more pure object oriented than C++.
-Because Java implements pure class. Every function / statements in Java is run by a class. While in C++ not all functions are run by a class.

17. What are the different options for object destruction in Java ?
– Using Close method or Finalize method.

Concept of Programming Languages – Chapter 11 (Abstract Data Types and Encapsulation Constructs)

Review Questions

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

– Process Abstraction and Data Abstraction

2. Define abstract data type .

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

3. What are the advantages of the two parts of the definition of abstract data type ?

– Increased reliability, Reduces range of code and number of variables which a programmer must be aware when writing / reading part of program. Make name conflict less likely to happen

5. What are the language design issues for abstract data types ?

– ADTs must have a function that allows a user to modify a value inside that data type. Although the method is public, the value itself must be private.

10. What is the use of the Ada with clause ?

– To make the names defined in external packages visible

11. What is the use of the Ada use clause ?

– To eliminate 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 ?

– Class must be accessed from an instance of itself while package can be accessed directly.

13. From where are C++ objects allocated ?

– From heap

15. What is the purpose of a C++ destructor ?

– To deallocate heap space the object used.

16. What are the legal return types of a destructor ?

– destructor has no return type

21. What are initializers in Objective-C?

– Constructors that must be explicitly called.

26. Why does Java not have destructors ?

– Because Java has its own implicit garbage collection.

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.

– 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 nonpointer concept in Java ?

– 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++ ?
– The compiler will automatically make a default one

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

Concepts of Programming Languages – Chapter 10 (Implementing Subprograms)

REVIEW QUESTION:

1. What are the two reasons why implementing subprograms with stack-dynamic local variables is more difficult than implementing simple sub-programs?

A stack-dynamic local variable is more complex activation records. The compiler must generate code to cause implicit allocation and de-allocation of local variables
Recursion must be supported (adds the possibility of multiple simultaneous activations of a subprogram).

2. What is the difference between an activation record and activation record instance?

The Format, or layout, of the non-code part of a subprogram is called an activation record.

An activation record stores all the information about subprogram calls, activation records stores the following data (in the following order)

Return address
Static link – to the static parent (where the subprogram is declared).
Dynamic link – to the caller of this subprogram.
Parameters
Local variables.

4. What are the two steps in locating a nonlocal variable in a static-scoped language with stack-dynamic local variables and nested subprograms?

Find the correct activation record instance
Determine the correct offset within that activation record instance

5. Define static chain, static depth, nesting_depth, and chain offset.

A static chain is a chain of static links that connects certain activation record instances

Static_depth is an integer associated with a static scope representing the scope’s nesting depth

The chain_offset or nesting_depth of a non-local reference is the difference between the static_depth of the reference and that of the scope where it is declared

6. What are the two potential problems with the static chain methods?

A nonlocal reference is slow if the number of scopes between the reference and the declaration of the referenced variable is large
Time-critical code is difficult, because the costs of nonlocal references are not equal, and can change with code upgrades and fixes

7. What is display?

One alternative to static chain is to use a display, for this approach, the static links are collected in a single array called a display. Display uses a pointer array to store the activation records along the static chain.

10. Explain the two methods of implementing block?

Blocks are treated as parameter less subprograms that are always called from the same place in the program.

Block can also be implemented in a different and somewhat simpler and more efficient way. The maximum amount of storage required for block variables at any time during the exaction of program can be statically determined, because block are entered and exited in strictly textual order.

11. Describe the deep access method of implementing dynamic scoping?

Deep Access – nonlocal references are found by searching the activation record instances on the dynamic chain. Length of chain cannot be statically determined every activation record instance must have variable names

12. Describe the shallow access method of implementing dynamic scoping?

In case of shallow access names and values are stored in a global table. Using this method, space is allocated for every variable name that is in the program (one space for variable temp though there might be several declarations of temp in the different methods). When a sub-routine is called it saves the current value of the variable and replaces it with the value in its current scope and restores the value of the variable while exiting.

14. Compare the efficiency of the deep access method to that of the shallow access method, in term of both call and nonlocal access?

The deep access methods provides fast subprogram linkage, but references to nonlocal, especially references to distant nonlocals (in term of the call chain), are costly. The shallow access methods provide much faster references to nonlocals, especially distant nonlocals, but are more costly in term of subprogram linkage.

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 ?

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

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.

– Using approach that uses an auxiliary data structure called a display. Or, to write variable names as integers. These integers act like an array. So when the activation happens, the comparisons will be faster.

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?

There are two options for implementing blocks as parameterless subprograms: One way is to use the same activation record as a subprogram that has no parameters. This is the most simple way, because accesses to block variables will be exactly like accesses to local variables. Of course, the space for the static and dynamic links and the return address will be wasted. The alternative is to leave out the static and dynamic links and the return address, which saves space but makes accesses to block variables different from subprogram locals.