Concept of Programming Language Chapter 15

Review question

1. Define functional form, simple list, bound variable, and referential transparency.

Answer : A higher-order function, or functional form, is one that either takes one or more functions as parameters or yields a function as its result, or both. A simple list is the problem of membership of a given atom in a given list that does not include sublists. A bound variable is a variable that never changes in the expression after being bound to an actual parameter value at the time evaluation of the lambda expression begins. A referential transparency is the execution of a function always produces the same result when given the same parameters

2. What does a lambda expression specify?

Answer : In Scheme, a nameless function actually includes the word LAMBDA, and is called a lambda expression. For example, (LAMBDA (x) (* x x)) is a nameless function that returns the square of its given numeric parameter. This function can be applied in the same way that named functions are: by placing it in the beginning of a list that contains the actual parameters.

7. What does the abbreviation REPL stand for?

8. What are the three parameters to IF?

Answer : The Scheme two-way selector function, named IF, has three parameters: a predicate expression, a then expression, and an else expression. A call to IF has the form (IF predicate then_expression else_expression)

11. What are the two forms of DEFINE?

Answer : DEFINE takes two lists as parameters. The first parameter is the prototype of a function call, with the function name followed by the formal parameters, together in a list. The second list contains an expression to which the name is to be bound.

12. Describe the syntax and semantics of COND.

Answer : The syntax of COND is

(COND

(predicate1 expression1)

(predicate2 expression2)

. . .

(predicaten expressionn)

[(ELSE expressionn+1)]

)

The semantics of COND is as follows: The predicates of the parameters are evaluated one at a time, in order from the first, until one evaluates to #T. The expression that follows the first predicate that is found to be #T is then evaluated and its value is returned as the value of COND. If none of the predicates is true and there is an ELSE, its expression is evaluated and the value is returned. If none of the predicates is true and there is no ELSE, the value of COND is unspecified. Therefore, all CONDs should include an ELSE.

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.

Answer : Reader macros or read macros, that are expanded during the reader phase of aLISP language processor. 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.

33. Explain the process of currying.

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

43. What is the syntax of lambda expression in F#?

Answer : The syntax in F# is (fun a b −> a / b)

Problem set

6. Refer to a book on Haskell programming and discuss the features of Haskell

Haskell features lazy evaluation, pattern matching, list comprehension, type classes, and type polymorphism.

Lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until its value is needed (non-strict evaluation) and which also avoids repeated evaluations (sharing). The sharing can reduce the running time of certain functions by an exponential factor over other non-strict evaluation strategies, such as call-by-name.

Pattern matching is the act of checking a perceived sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact. The patterns generally have the form of either sequences or tree structures. Uses of pattern matching include outputting the locations (if any) of a pattern within a token sequence, to output some component of the matched pattern, and to substitute the matching pattern with some other token sequence.

List comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It follows the form of the mathematical set-builder notation (set comprehension) as distinct from the use of map and filter functions.

Type class is a type system construct that supports ad-hoc polymorphism. This is achieved by adding constraints to type variables in parametrically polymorphic types. Such a constraint typically involves a type class T and a type variable a, and means that a can only be instantiated to a type whose members support the overloaded operations associated with T.

Polymorphism is a programming language feature that allows values of different data types to be handled using a uniform interface.

7. What features make F# unique when compared to other languages?

F# has a full-featured IDE, an extensive library of utilities that supports imperative, object-oriented, and functional programming, and has interoperability with a collection of nonfunctional languages. F# includes a variety of data types. Among these are tuples, like those of Python and the functional languages ML and Haskell, lists, discriminated unions, an expansion of ML’s unions, and records, like those of ML, which are like tuples except the components are named. F# has both mutable and immutable arrays.

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)

Concept of Programming Language Chapter 14

REVIEW QUESTIONS

2. When is an exception thrown or raised?

Answer : An exception is raised when its associated event occurs.

11. Are there any predefined exceptions in Ada?

12. What is the use of Suppress pragma in Ada?

Answer : Disabling certain run-time checks that are parts of the built-in exceptions.

15. Which standard libraries define and throw the exception out_of_range in C++?

16. Which standard libraries define and throw the exception overflow_error in C++?

25. What is the difference between checked and unchecked exceptions in Java?

Answer : Exceptions of class Error and RuntimeException and their descendants are called unchecked exceptions. All other exceptions are called checked exceptions. Unchecked exceptions are never a concern of the compiler.

28. What is the purpose of the Java finally clause?

Answer : There are some situation in which a process must be executed regardless of whether a tryclause throws an exception and regardless of whether a thrown exception is caught in a method. One example of such a situation is a file that must be closed. Another is if the method has some external resource that must be freed in the method regardless of how the execution of the method terminates. This is the purpose of Java finally clause made.

30. In which version were assertions added to Java?

31. What is the use of the assert statement?

Answer : Assert statement use is for defensive programming.

32. What is event-driven programming?

Answer : Programming whose 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 : Defining the data and methods that are needed for frames.

PROBLEM SET

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

Most of computer hardware system are capable of detecting certain run-time error conditions, such as floating-point overflow. Early programming languages were designed and implemented in such a way that the user program could neither detect nor attempt to deal with such errors. In these languages, the occurrence of such an error simply causes the program to be terminated and control to be transferred to the operating system. The typical operating system reaction to a run-time error is to display a diagnostic message, which may be meaningful and therefore useful, or highly cryptic. After displaying the message, the program is terminated.

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

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

9. Write a comparative analysis of the throw clause and throws clause of Java.

1) You can declare multiple exception thrown by method in throws keyword by separating them in common e.g. throws IOException, ArrayIndexBoundException etc, while you can only throw one instance of exception using throw keyword e.g. throw new IOException(“not able to open connection”).
2) throws keyword gives a method flexibility of throwing an Exception rather than handling it. with throws keyword in method
signature a method suggesting its caller to prepare for Exception declared in throws clause, specially in case of checked Exception and provide sufficient handling of them. On the other hand throw keyword transfer control of execution to caller by throwing an instance of Exception. throw keyword can also be used in place of return as shown in below example:
private static boolean shutdown() {
throw new UnsupportedOperationException(“Not yet implemented”);
}
as in below method shutdown should return boolean but having throw in place compiler understand that this method will always throw exception .
3) throws keyword cannot be used anywhere exception method signature while throw keyword can be used inside method or static initializer block provided sufficient exception handling as shown in example.
static{
try {
throw new Exception(“Not able to initialized”);
} catch (Exception ex) {
Logger.getLogger(ExceptionTest.class.getName()).log(Level.SEVERE, null, ex);
}
}
worth remembering is that static initalizer block should complete normally.
4) throw keyword can also be used to break a switch statement without using break keyword as shown in below example:
int number = 5;
switch(number){
case 1:
throw new RuntimeException(“Exception number 1″);
case 2:
throw new RuntimeException(“Exception number 2″);
}

Concept of Programming Language Chapter 13

Review question

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)

2. Describe the logical architecture of an SIMD computer.

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

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

3. Describe the logical architecture of an MIMD computer.

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

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

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.

16. What is a task descriptor?

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?

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

59. Who developed the monitor concept?

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

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?

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?

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

Review question

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 type definitions are all independent and are at the same level.

5. What is an overriding method?

Answer : Overriding method is method that overrides the inherited method.

6. Describe a situation where dynamic binding is a great advantage over its absence.

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

7. What is dynamic dispatch?

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

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

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.

25. What is mixins in objective-C?

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

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 finalizemethod when the garbage collector is about to reclaim the storage occupied by the object.

Problem set

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

– In Java, all classes inherit from the Object class directly or indirectly. Therefore, there is always a single inheritance tree of classes in Java, and Object class is root of the tree. In Java, if we create a class that doesn’t inherit from any class then it automatically inherits from Object Class. In C++, there is forest of classes; when we create a class that doesn’t inherit from anything, we create a new tree in forest.

– In Java, members of the grandparent class are not directly accessible.

– The meaning of protected member access specifier is somewhat different in Java. In Java, protected members of a class “A” are accessible in other class “B” of same package, even if B doesn’t inherit from A (they both have to be in the same package)

– Java uses extends keyword for inheritence. Unlike C++, Java doesn’t provide an inheritance specifier like public, protected or private. Therefore, we cannot change the protection level of members of base class in Java, if some data member is public or protected in base class then it remains public or protected in derived class. Like C++, private members of base class are not accessible in derived class.
Unlike C++, in Java, we don’t have to remember those rules of inheritance which are combination of base class access specifier and inheritance specifier.

– In Java, methods are virtual by default. In C++, we explicitly use virtual keyword.

– Java uses a separate keyword interface for interfaces, and abstract keyword for abstract classes and abstract functions.

– Unlike C++, Java doesn’t support multiple inheritance. A class cannot inherit from more than one class. A class can implement multiple interfaces though.

– In C++, default constructor of parent class is automatically called, but if we want to call parametrized constructor of a parent class, we must use Initalizer list. Like C++, default constructor of the parent class is automatically called in Java, but if we want to call parametrized constructor then we must use super to call the parent constructor

5. Compare abstract class and interface in Java.

– First and major difference between abstract class and interface is that, abstract class is a class while interface is a interface, means by extending abstract class you can not extend another class becauseJava does not support multiple inheritance but you can implement multiple inheritance in Java.

– Second difference between interface and abstract class in Java is that you can not create non abstract method in interface, every method in interface is by default abstract, but you can create non abstract method in abstract class. Even a class which doesn’t contain any abstract method can be abstract by using abstract keyword.

– Third difference between abstract class and interface in Java is that abstract class are slightly faster than interface because interface involves a search before calling any overridden method in Java. This is not a significant difference in most of cases but if you are writing a time critical application than you may not want to leave any stone unturned.

– Fourth difference between abstract class vs interface in Java is that, interface are better suited for Type declaration and abstract class is more suited for code reuse and evolution perspective.

– Another notable difference between interface and abstract class is that when you add a new method in existing interface it breaks all its implementation and you need to provide an implementation in all clients which is not good. By using abstract class you can provide default implementation in super class.

7. What is one programming situation where multiple inheritance has a significant disadvantage over interfaces?

A situation when there are two classes derived from a common parent and those two derived class has one child.

10. Explain one advantage of inheritance.

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

13. Descripbe the mechanism of dynamic dispatch with an example in Java. Is it possible to dynamically dispatch the data members?

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

16. State why java is said to be more pure object-oriented than C++.

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

17. What are the different options for object destruction in Java?

There is no explicit deallocation operator. A finalize method is implicitly called when the garbage collector is about to reclaim the storage occupied by the object.

Concept of Programming Language Chapter 11

Review question

2. Define abstract data type.

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

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

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

Answer : The with clause makes the names defined in external packages Visible.

12. What is the fundamental difference between a C++ class and an Ada package?

Answer : Ada packages are more generalize encapsulations that can define any number of types.

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

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

Answer : Destructor has no return types and doesn’t use return statements.

20. What is the use of limited private types?

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

21. What are initializers in Objective-C?

Answer : The initializers in Objective-C are constructors.

22. What is the use of @private and @public directives?

Answer : The use is to specify the access levels of the instance variables in a class definition.

27. Where are all Java methods defined?

Answer : All Java methods are defined in a class.

30. What is a friend function? What is a friend class?

Answer : a “friend” of a given class is allowed access to public, private, or protected data in that class. Normally, function that is defined outside of a class cannot access such information.

Class that can access the private and protected members of the class in which it is declared as a friend. On declaration of friend class all member function of the friend class become friends of the class in which the friend class was declared.

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.

10. Which two conditions make data type “abstract”?

The representation of objects of the type is hidden from the program units that use the type, so the only direct operations possible on those objects are those provided in the type’s definition.

The declarations of the type and the protocols of the operations on objects of the type, which provide the type’s interface, are contained in a single syntactic unit. The type’s interface does not depend on the representation of the objects or the implementation of the operations. Also, other program units are allowed to create variables of the defined type.

12. How are classes in Ruby made dynamic?

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

13. Compare and contrast the data abstraction of Java and C++.

Java support for abstract data types is similar to that of C++. There are, however, a few important differences. All objects are allocated from the heap and accessed through reference variables. Methods in Java must be defined completely in a class. A method body must appear with its corresponding method

header. Therefore, a Java abstract data type is both declared and defined in a single syntactic unit. A Java compiler can inline any method that is not overridden. Definitions are hidden from clients by declaring them to be private. Rather than having private and public clauses in its class definitions, in Java access modifiers can be attached to method and variable definitions. If an instance variable or method does not have an access modifier, it has package access.

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.

import java.sql.*;

Concept of Programming Language Chapter 10

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?

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

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

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

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

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

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

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

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

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

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

9.  The static-chain method could be expanded slightly by using two static links in each activation  record instance where the  second points to the static grandparent activation record instance. How would this approach affect the time required for subprogram linkage and nonlocal references?

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

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

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.

Concept of Programming Language Chapter 9

REVIEW QUESTIONS

1. What are the three general characteristics of subprograms?

Answer : -Each subprogram has a single entry point.

-The calling program unit is suspended during the execution of the called subprogram, which implies that there is only one subprogram in execution at any given time.

-Control always returns to the caller when the subprogram execution terminates.

2. What does it mean for a subprogram to be active?

Answer : It means that after having been called, a subprogram has begun execution but has not yet completed that execution.

7. What is a parameter profile? What is a subprogram protocol?

Answer : Parameter profile is the number, order, and types of its formal parameters.

Subprogram protocol is its parameter profile plus, if it is a function, its return type. In languages in which subprograms have types, those types are defined by the subprogram’s protocol.

8. What are formal parameters? What are actual parameters?

Actual parameters are a list of parameters to be bound to the formal parameters of the subprogram which must be included with the name of the subprogram by the subprogram call statements.

10. What are the differences between a function and a procedure?

Answer : Functions return values and procedures do not.

15. What are the three semantic models of parameter passing?

-They can receive data from the corresponding actual parameter

-They can transmit data to the actual parameter

-They can do both.

Simply: in mode, out mode, and inout mode.

17. Describe the ways that aliases can occur with pass-by-reference parameters.

Answer : Pass by reference makes access paths available to the called subprograms, thereby providing access to non-local variables. These are the ways:

First, collisions can occur between actual parameters. Consider a C++ function that has two parameters that are to be passed by reference, as in

void fun(int &first, int &second)

If the call to fun happens to pass the same variable twice, as in

fun(total, total)

the first and second in fun will be aliases

Second, collisions between array elements can also cause aliases. For example, suppose the function fun is called with two array elements that are specified with variable subscripts, as in

fun(list[i], list[j])

If these two parameters are passed by reference and i happens to be equal to j, then first and second are again aliases.

Third, if two of the formal parameters of a subprogram are an element of an array and the whole array, and both are passed by reference, then a call such as

fun1(list[i], list)

could result in aliasing in fun1, because fun1 can access all elements of list through the second parameter and access a single element through its first parameter.

Still another way to get aliasing with pass-by-reference parameters is through collisions between formal parameters and non-local variables that are visible.

24. What is an overloaded subprogram?

Answer : Overloaded subprogram is a subprogram that has the same name as another subprogram in the same referencing environment. Every version of an overloaded subprogram must have a unique protocol; that is, it must be different from the others in the number, order, or types of its parameters, and possibly in its return type if it is a function.

26. What is multicast delegate?

Answer : Multicast delegate is all of the methods stored in a delegate instance are called in the order in which they were placed in the instance.

32. What exactly is a delegate?

Answer : A delegate is the power and flexibility of method pointers in C# increased by making them objects.

PROBLEM SET

1. Consider the following program written in C syntax:

void swap(int a, int b)
{
temp = a;

a = b;

b = temp;
}

void main()
{

int value = 1, list[5] = {2, 4, 6, 8, 10};

swap(value, list[0]);

swap(list[0], list[1]);

swap(value, list[value]);
}

For each of the following parameter-passing methods, what are all of the values of the variables value and list after each of the three calls to swap?

a. Passed by value

value = 1;

list[5] = {2, 4, 6, 8, 10};

b. Passed by reference

value = 2;

list[5] = {4, 1, 2, 8, 10};

c. Passed by value-result

value = 2;

list[5] = {4, 1, 2, 8, 10};

7. Consider the following program written in C syntax:

void fun(int first, int second)
{
first +=first;

second += second;
}

void main()
{
int list[2] = {3, 5};

fun(list[0], list[1]);
}

For each of the following parameter-passing methods, what are the values of the list array after execution?

a. Passed by value

3, 5

b. Passed by reference

6, 10

c. Passed by value-result

6, 10

14. Speculate on the issue of allowing function or method overloading in some programming languages. Why are the not allowed by many contemporary languages?

Because it is concerned to lead to ambiguity and some error compilation.

15. How is the problem of passing multidimensional arrays handled by Ada?

In Ada, unconstrained array types can be formal parameters. An unconstrained array type is one in which the index ranges are not given in the array type definition. Definitions of variables of unconstrained array types must include index ranges. The code in subprogram that is passed an unconstrained array can obtain the index range information of the actual parameter associated with such parameters.