Concept Of Programming Language Chapter 16

28 Jun

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

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.

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 Language Chapter 15

28 Jun

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 ?
– parameters and the mapping of a function.

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

4. In what common data structure are LISP lists normally stored ?
– As linked list structure in which each node has two pointers.

5. Explain why QUOTE is needed for a parameter that is a data list.
– To return lists or atoms without changing them.

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

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

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?

Curried functions are interesting and useful because 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.

31. Define reader macros.

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?

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

 

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

Concept Of Programming Language Chapter 14

28 Jun

Review Question

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

An exception is an unusual event that is detectable by either hardware or software and that may require special processing. The special processing that may be required when an exception is detected is called exception handling. The processing is done by a code unit or segment called an exception handler. An exception is raised when its associated event occurs. In some situations, it may be desirable to ignore certain hardware-detectable exceptions—for example, division by zero—for a time. This action would be done by disabling the exception. After an exception handler executes, either control can transfer to somewhere in the program outside of the handler code or

Program execution can simply terminate. We term this the question of control continuation after handler execution, or simply continuation. In some situations, it is necessary to complete some computation regardless of how subprogram execution terminates. The ability to specify such a computation is called finalization. Built-in exceptions have a built-in meaning, it is generally inadvisable to use these to signal program-specific error conditions.  Instead we introduce a new exception using an exception declaration, and signal it using a raise expression when a run-time violation occurs.  That way we can associate specific exceptions with specific pieces of code, easing the process of tracking down the source of the error.

 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 ?

– A powerful tool for constructing more reliable software systems.

7. Where are unhandled exceptions propagated in Ada if raised in a subprogram?A block? A package body? A task?

When an exception is raised in a block, in either its declarations or executable statements, and the block has no handler for it, the exception is propagated to the next larger enclosing static scope, which is the code that “called” it. The point to which the exception is propagated is just after the end of the block in which it occurred, which is its “return” point. When an exception is raised in a package body and the package body has no handler for the exception, the exception is propagated to the declaration section of the unit containing the package declaration. If the package happens to be a library unit (which is separately compiled), the program is terminated.

If an exception occurs at the outermost level in a task body (not in a nested block) and the task contains a handler for the exception, that handler is executed and the task is marked as being completed. If the task does not have a handler for the exception, the task is simply marked as being completed; the exception is not propagated. The control mechanism of a task is too complex to lend itself to a reasonable and simple answer to the question of where its unhandled exceptions should be propagated.

8. Where does execution continue after an exception is handled in Ada ?

– Control simply continues after the exception clause.

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

 

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

 

Concept Of Programming Language Chapter 13

28 Jun

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

3. Describe the logical architecture of an MIMD computer.
-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.

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

7. What is the difference between physical and logical concurrency ?
– Physical concurrency is when it is assumed that if more than one processor is available, several program units from the same program literally execute simultaneously. Logical concurrency is assuming multiple processors can execute simultaneously while the actual execution is taking place in a single processor.

8. What is the work of a scheduler ?
– Managing the share of processors among tasks.

9. Give some examples of languages which can be used for synchronization.
– Ada 95, Java, C#, F#, Python and Ruby

10. When is a task in a blocked state ?
– When its execution is interrupted by one of several different events

Problem Set

2. What are the different ways to handle deadlock ?
– One of the ways is to design algorithm where tasks that can cause deadlock to not to run together. Or, to allow them to execute at the same time but with an exception if a deadlock happens, the program will either reset its status to the time when deadlock has not occurred or to break forcefully from the loop and continues execution.

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 ?
– A continuous check might mean a deadlock for a task, where it does something that does not has a direct impact on the program unless the specified event happens. It does consume extra processor capability. A better way to do this might be executing the same task when an event occurs, instead of running it first and make it waiting and continuously wasting CPU capability.

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.

 

Concept Of Programming Language Chapter 12

28 Jun

Review Questions

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

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 old type requires at least some minor modifications.

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

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

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

6. Describe a situation where dynamic binding is a great advantage over its absence.
– 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. With overriding, we can directly modify B’s draw function. But without it, we either make a specific function in A for B and inherit it.

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

9. Describe briefly the eight design issues used in this chapter for objectoriented languages.
The Exclusivity of Objects
Are Subclasses Subtypes?
Type Checking and Polymorphism
Single and Multiple Inheritance
Object Allocation and Deallocation
Dynamic and Static Binding
Nested Classes
Initialization of Objects

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

12. From where are small talk objects allocated?

 virtually everything, from items as simple as the integer constant 2 to a complex file-handling system. All smalltalk objects are allocated form the heap and are referenced through reference variables

13. Explain how smalltalk messages are bound to methods. When does this take place?

 all computation is through message. Replies to messages have the form of objects and are used to return requested or computed information or only to confirm that the requested service has been computed

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

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.

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)

 

Concept Of Programming Language Chapter 11

28 Jun

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.

 6. Explain how information hiding is provided in an Ada package.
– The spec package has two parts, public and private
– The name of the abstract type appears in the public part of the specification package. This part may also include representations of unhidden types
– The representation of the abstract type appears in a part of the specification called the private part

7. To what is the private part of an Ada package specification visible?
Public part

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.

13. From where are C++ objects allocated?

 from the class

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

 use as a debugging aid, in which case they simply display or print the values of some or all of the object’s data member before those members are deallocated.

17. Where are all Java variables defined?

 in a single syntactic unit

21. What is the use of @private @public directives?

 to specify the access levels of the instance variables in a class definition

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

 

Concept Of Programming Language Chapter 10

28 Jun

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

10. Define static chain, static_depth, nesting_depth,and chain_offset.
– static chain : a chain of static links that connect certain activation record instances in the stack.
– static depth : integer associated with a static scope that indicates how deeply it is nested in the outermost scope.
– nesting_depth : difference between static_depth of a subprogram containing reference to x and the static_depth of a subprogram containing the declaration of x.
– chain_offset : number of links to the correct activation record instance

12. How are references to variables represented in the static-chain method?
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 ?

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