|
|
|
CS 441 Programming Languages Final Exam Winter 2001 Answer any five questions from Section A. Answer ALL questions from Section B. Please do your own work. PLEASE DO NOT COLLABORATE WITH ANYONE. Any suggestion of collaboration will result in an automatic F for this class. In each answer, list ALL references used or consulted.
Section A 1 Under what circumstances is an interpreter preferable to a compiler? What circumstances make the compiler better? Interpreters work better on languages with simpler structures and for languages that have dynamic type binding for variables. This is in part because it is difficult to change the types of variables dynamically in the machine code. The overall time of interpretation includes the time to do dynamic type binding, and, therefore, is less costly. Compilers are preferred on the languages with static type bindings, because programs in these languages can be easily translated into very efficient machine code. Compilers have the advantage of very fast program execution, once the translation process is complete. (3) 3 Some languages permit the binding of type to a data object at run time. Discuss the advantages and disadvantages of this strategy. With dynamic type binding the type is not specified by a declaration statement. Instead, the binding occurs when the variable is assigned a value in an assignment statement. When the assignment statement is executed, the variable being assigned is bound to the type of the value, variable or expression on the right side of the assignment. Advantages of dynamic type binding:
Disadvantages of dynamic type binding:
4 How would the usefulness of a language be limited if it contained no control structures? A control structure is a control statement and the collection of statements whose execution it controls. Language without control structures would not have any capability for selection of alternative flow paths (selection statements) and no means of causing the repeated execution of groups of statements (iterative statements). Lack of iterative statements will force the program to have a separate statement for each necessary iteration, which will make programs huge and hard to read. For example, a program needing 1 million iterations will have a million statements to do that, instead of a counter controlled loop, which can accomplish the same task with a few lines of code. Lack of selection statements will limit the program to just a set of assignment statements which are not very useful by themselves. Research showed that sequence, selection and pretest logical loops are absolutely required to express computations. (3) 6 State some advantages of dynamic scope over static scope in defining the global environment of a procedure. Dynamic scoping is based on the calling sequence of subprograms, not on their
spatial relationship to each other and, therefore, the scope can only be
determined at run time. Most of the sources including textbook discuss the
disadvantages of dynamic scoping. Several problems come from dynamic scoping: (3,4) 9 What is the difference between inheritance and the use of include files such as in C++? Inheritance allows a new ADT to inherit the data and functionality of some existing ADT and to modify it as needed. For example in C++ classes "iostream", "fstream" and "ostream" inherit from class "ios". Include files, on the other hand, provide libraries of predefined functions to extend the functionality of the language. Libraries provide input, output, formatting, math and other functions. Although, they can be replicated by programmer, there is no need to do that and use of library functions provides for better portability. The use of the include files does not imply inheritance, just inclusion of the code into the user program. However, the user can define new classes, which will inherit from the classes provided in the library.
Section B 11 Although parameterized ADT definitions are a very interesting concept, their implementation can force other, perhaps undesirable, constraints on a compiler and run-time system. An implication of the implementation of generic packages in Ada is that binding of generic packages is dynamic-- that is, packages must be instantiated. This, in turn, makes the resolution of overloading a run-time process, not static one. Why does dynamic instantiation force dynamic overloading resolution? Why are these implementation constraints unfortunate? Can you dream up any way around these constraints? You may restrict the semantics of the language as you think about this one. According to my research (see references) each instantiation of a generic package in Ada produces completely separate code. Each separate instance has the size and layout of all the type parameters, and can be compiled just like ordinary code. This means the code runs as efficiently as ordinary code. That is why excessive use of generic packages can lead to a bloated code. Overloading combined with generic packages gives us a way to refer to different instances of a generic by the same name; the compiler figures out which instance we meant.(3,5) 12 Some languages permit nonhomogeneous arrays, that is, arrays whose components are not necessarily the same type. What properties should a language have for such a structure to be compatible with the language and how might such a structure be implemented? Many languages provide record or struct types, which are essentially nonhomogeneous arrays. These types are used when the data is heterogeneous and, therefore, different fields cannot be processed in the same way. Instead of subscripts, records use field names. Field names, which are static, provide efficient access to the fields and support type checking. Language, supporting nonhomogeneous array should provide a way to reference all fields efficiently, without jeopardizing readability. One example would be a C++ dot notation. Two possible ways of referencing the fields are the fully qualified and elliptical references. Record fields are stored in adjacent memory cells, using relative memory addressing. Records and structures are safe, because they allow type checking and efficient because of the static binding.(3)
13 PROLOG and SQL take different approaches to implementing the logic mode. Compare the two approaches and discuss their relative advantages. PROLOG is a predicate calculus language where queries describe a desired set
of tuples by specifying a predicate the tuples must satisfy. A Prolog program
can be viewed as the specification of a list of goals to be satisfied. If the
data is represented as facts, for a PROLOG system to have a substantial
vocabulary, it must have access to many such facts. To determine whether a
particular fact is asserted it is necessary for Prolog to search the database,
perhaps linearly from end to end. Execution of a program may require many
thousands of such searches. While Prolog can determine whether a goal matches
the fact, this is essentially a database lookup job, and there are systems,
which are highly optimized for carrying out such lookups. It seems possible
therefore, that integrating such a system into a Prolog program may lead to
significant performance gains. (1,2) 14 In several situations, a queue is used. For example, messages that are passed may be queued and processes waiting to synchronize may be queued. Examine the possibility of making these priority queues where the originating process assigns a priority to the activity that is queued. How might this be useful? How might this be implemented? This arrangement may be useful for scheduling, where each queued activity is executed accordingly to its priority. When the item is placed in priority queue its position depends on the priority. Depending on implementation of the queue the item with minimum or maximum priority is the only one that could be accessed. Priority assignment could be accomplished by associating a variable with an item to be queued, which will store the priority. The design should specify the numerical value of the highest and the lowest priority. Items with the same priority will be process in the first come, first served order. Priorities of the items already processed should be returned to a sorted pool of available priorities for future assignment. 15 What might be some of the advantages and disadvantages of using syntax diagrams as opposed to EBNF or BNF? Syntax diagrams are mapped directly from BNF/EBNF, and represent exactly the same information in more human-friendly way. While better readability is the syntax graphs' main advantage, it becomes a disadvantage when the syntax needs to be read into computer. The other disadvantage is the space requirement. (3) Reference:
http://www.kevinboone.com/pgche/plsql.html
|
| e-mail Mikhail Viron |