Programming Language Pragmatics 4th Edition Michael L. Scott - Solutions

Suppose we wish, as described at the end of Example 16.36, to accurately attribute sampled time to the various contexts in which a subroutine is called. Perhaps the most straightforward approach would be to log not only the current PC but also the stack back trace—the contents of the dynamic
Using your local implementations of Java and C#, compile the code of Figures 16.2 and C 16.7 all the way to machine language. Disassemble and compare the results. Can all the differences be attributed to variations in the quality of the compilers, or are any reflective of more fundamental $Code: public void insert (int v) { Stack=3, Locals=4, Args size=2 // this # 4; //Field head:LLLset $node; node n = head; 0: aload_0 1: getfield astore_2 aload_2 4: while (n.next != null // n #5; //Field LLset $node.next:LLLset $node; // conditional branch 5: &k n.next.val < v) { 6:$
Rewrite the list insertion method of Example C 16.40 in F# instead of C#. Compile to CIL and compare to the right side of Figure C 16.7. Discuss any differences you find.Figure 16.7 . method private hidebysig public void insert (int v) { instance default void insert (int32 v) cil managed { // $. method private hidebysig public void insert (int v) { instance default void insert (int32 v) cil managed { // Method begins at RVA Ox210c // Code size 108 (Ox6c) // RVA == relative // virtual address .maxstack 3 .locals init ( class LLset/node // n V_0, V_1) class LLset/node$
Building on the previous exercise, rewrite your list insertion routine (both C# and F# versions) to be generic in the type of the list elements. Compare the generic and non generic versions of the resulting CIL and discuss the differences.
Extend your F# code from Exercise C 16.16 to include list removal and search routines. After finding and reading appropriate documentation, package these routines in a library that can be called in a natural way not only from F# but also from C#.
Consider the following pseudocode:procedure P(A, B : real) X : realprocedure Q(B, C : real) Y : real . . .procedure R(A, C : real) Z : real . . .
Rewrite the attribute grammar of Figure 4.14 in the form of an ad hoc tree traversal consisting of mutually recursive subroutines in your favorite programming language. Keep the symbol table in a global variable, rather than passing it through arguments.Figure 4.14: Attributes Class of node
Write the equivalent of Figure 6.5 in C# or Ruby. Write a second version that performs an in-order enumeration, rather than preorder.Figure 6.5: class BinTree: def -_init_ (self): # constructor self.data = self.lchild self.rchild = None # other methods: insert, delete, lookup, def preorder (self):
Building on the previous exercise, implement higher-level union, intersection, and difference functions that operate on ordered sets. Note that these should not be members of the ordered_set class, but rather stand-alone functions: they should be independent of the details of list_set or any other
Continuing Example C 7.59, the callcsNames.consider(null);will generate a run-time exception, because String. compare To is not designed to take null arguments.(a) Modify Figure C 7.6 to guard against this possibility by including a predicate public Boolean valid(T a); in the Chooser interface, and
(a) Modify your solution to Exercise 7.14 so that the comparison routine is an explicit generic parameter, reminiscent of the chooser.(b) Give an alternative solution in which the comparison routine is an extra parameter to sort.Data From Exercise 7.14:Flesh out the C++ sorting routine of Example
Consider the C++ program. Explain why the final call to first_n generates a compile-time error, but the call to last_n does not. Show how to modify the final call to first_n so that the compiler will accept it.
Consider the following code in C++:Here *Lp will be a “deep copy” of L, containing a copy of each foo object. Try to write equivalent code in Java. What goes wrong? How might you get around the problem? template class cloneable_list : public list { public: cloneable_list* clone () { auto rtn = $template class cloneable_list : public list { public: cloneable_list* clone () { auto rtn = new cloneable_list(); for (auto e : *this) { rtn- style=$
Suppose we are compiling for a machine with 1-byte characters, 2-byte shorts, 4-byte integers, and 8-byte reals, and with alignment rules that require the address of every primitive data element to be an even multiple of the element’s size. Suppose further that the compiler is not permitted to
In Example 8.10 we suggested the possibility of sorting record fields by their alignment requirement, to minimize holes. In the example, we sorted smallest-alignment-first. What would happen if we sorted longest-alignment-first? Do you see any advantages to this scheme? Any disadvantages? If the
Give Ada code to map from lowercase to uppercase letters, using(a) An array(b) A functionNote the similarity of syntax: in both cases upper(‚a‚) is ‚A‚.
In Section 8.2.2 we noted that in a language with dynamic arrays and a value model of variables, records could have fields whose size is not known at compile time. To accommodate these, we suggested using a dope vector for the record, to track the offsets of the fields. Suppose instead that we want
Explain how to extend Figure 8.7 to accommodate subroutine arguments that are passed by value, but whose shape is not known until the subroutine is called at run time. sp- Ada: -- procedure foo (size : integer) is M : array (1..size, 1..size) of long float; Variable-size M part of the frame begin
Explain how to obtain the effect of Fortran 90’s allocate statement for one-dimensional arrays using pointers in C. You will probably find that your solution does not generalize to multidimensional arrays. Why not? If you are familiar with C++, show how to use its class facilities to solve the
Example 8.24, which considered the layout of a two-dimensional array of characters, counted only the space devoted to characters and pointers. This is appropriate if the space is allocated statically, as a global array of days or keywords known at compile time. Supposed instead that space is
Consider the array indexing calculation of Example 8.25. Suppose that i, j, and k are already loaded into registers, and that A’s elements are integers, allocated contiguously in memory on a 32-bit machine. Show, in the pseudo-assembly notation of Sidebar 5.1, the instruction sequence to load
Continuing the previous exercise, suppose that A has row-pointer layout, and that i, j, and k are again available in registers. Show pseudo assembler code to load A[i, j, k] into a register. Assuming that all memory loads are cache hits, how many cycles is your code likely to require on a modern
Repeat the preceding two exercises, modifying your code to include runtime checking of array subscript bounds.
In Section 8.2.3 we discussed how to differentiate between the constant and variable portions of an array reference, in order to efficiently access the subparts of array and record objects. An alternative approach is to generate naive code and count on the compiler’s code improver to find the
Consider the following C declaration, compiled on a 64-bit x86 machine:struct { int n; char c;} A[10][10];If the address of A[0][0] is 1000 (decimal), what is the address of A[3][7]?
Suppose we are generating code for an imperative language on a machine with 8-byte floating-point numbers, 4-byte integers, 1-byte characters, and 4-byte alignment for both integers and floating-point numbers. Suppose further that we plan to use contiguous row-major layout for multidimensional
Suppose A is a 10×10 array of (4-byte) integers, indexed from [0][0] through [9][9]. Suppose further that the address of A is currently in register r1, the value of integer i is currently in register r2, and the value of integer j is currently in register r3.Give pseudo-assembly language for a
Pointers and recursive type definitions complicate the algorithm for determining structural equivalence of types. Consider, for example, the following definitions:type A = record x : pointer to B y : realtype B = record x : pointer to A y :
Explain the meaning of the following C declarations:double *a[n];double (*b)[n];double (*c[n])();double (*d())[n];
In Ada 83, pointers (access variables) can point only to objects in the heap. Ada 95 allows a new kind of pointer, the access all type, to point to other objects as well, provided that those objects have been declared to be aliased:type int_ptr is access all Integer;foo : aliased Integer;ip :
As noted in Section 8.5.2, Ada 95 forbids an access all pointer from referring to any object whose lifetime is briefer than that of the pointer’s type. Can this rule be enforced completely at compile time? Why or why not?
In much of the discussion of pointers in Section 8.5, we assumed implicitly that every pointer into the heap points to the beginning of a dynamically allocated block of storage. In some languages, including Algol 68 and C, pointers may also point to data inside a block in the heap. If you were
(a) Occasionally one encounters the suggestion that a garbage-collected language should provide a delete operation as an optimization: by explicitly delete-ing objects that will never be used again, the programmer might save the garbage collector the trouble of finding and reclaiming those objects
In Example 8.52 we noted that functional languages can safely use reference counts since the lack of an assignment statement prevents them from introducing circularity. This isn’t strictly true; constructs like the Lisp letrec can also be used to make cycles, so long as uses of circularly defined $(define foo (lambda () (letrec ((a (lambda (f) (if f #\A b))) (b (lambda (f) (if f #\B c))) (c (lambda (f) (if f #\C a)))) a)))$
Here is a skeleton for the standard quicksort algorithm in Haskell:quicksort [] = []quicksort (a : l) = quicksort [...] ++ [a] ++ quicksort [...]The ++ operator denotes list concatenation (similar to @ in ML). The : operator is equivalent to ML’s :: or Lisp’s cons. Show how to express the two
In Example 6.70 we described a programming idiom in which an iterator takes a “loop body” function as argument, and applies it to every element of a given ontainer or set. Show how to use this idiom in ML to apply a function to every element of the tree in Example 11.39. Write versions of your
Show how unions can be used in C to interpret the bits of a value of one type as if they represented a value of some other type. Explain why the same technique does not work in Ada. After consulting an Ada manual, describe how an unchecked pragma can be used to get around the Ada rules.
Are variant records a form of polymorphism? Why or why not?
Learn the details of variant records in Pascal.(a) You may have noticed that the language does not allow you to pass the tag field of a variant record to a subroutine by reference. Why not?(b) Explain how you might implement dynamic semantic checks to catch references to uninitialized fields of a
We noted in Section C 8.1.3 that Ada requires the variant portions of a record to occur at the end, to save space when a particular record is constrained to have a comparatively small variant part. Could a compiler rearrange fields to achieve the same effect, without the restriction on the
In Example 8.52 we noted that reference counts can be used to reclaim tombstones, failing only when the programmer neglects to manually delete the object to which a tombstone refers. Explain how to leverage this observation to catch memory leaks at run time. Does your solution work in all cases?
In Section 8.5.3 we introduced the notion of smart pointers in C++. Learn how these are implemented, and write an explanation. Discuss the relationship to tombstones.
Rewrite Example C 8.80 using fgets, strtol, strtod, etc. (read the man pages), so that it is guaranteed not to result in buffer overflow.
The output routines of several languages (e.g., println in Swift) give special treatment to ends of lines. By contrast, C’s printf does not; it treats newlines and carriage returns the same as any other character. What are the comparative advantages of these approaches? Which do you prefer? Why?
Describe as many ways as you can in which functions in imperative programming languages differ from functions in mathematics.
Consider the following code in C++:Suppose that string_map::operator[] contains the only call to complex_ lookup anywhere in the program. Explain why it would be unwise for the programmer to expand that call textually in-line and eliminate the separate function. class string_map { string $class string_map { string cached_key; string cached_val; const string complex_lookup(const string key); // body specified elsewhere public: const string operator [] (const string key) { if (key == cached_key) return cached_val; string rtn_val = complex_lookup (key); cached_key key; cached_val = rtn_val; return rtn_val; };$
Using your favorite language and compiler, write a program that can tell the order in which certain subroutine parameters are evaluated.
Consider the following (erroneous) program in C:Local variable i in subroutine foo is never initialized. On many systems, however, the program will display repeatable behavior, printing 0 1 2 3 4 5 6 7 8 9. Suggest an explanation. Also explain why the behavior on other systems might be different,
The standard calling sequence for the c. 1980 Digital VAX instruction set employed not only a stack pointer (sp) and frame pointer (fp), but a separate arguments pointer (ap) as well. Under what circumstances might this separate pointer be useful? In other words, when might it be handy not to have
Write (in the language of your choice) a procedure or function that will have four different effects, depending on whether arguments are passed by value, by reference, by value/result, or by name.
Consider an expression like a + b that is passed to a subroutine in Fortran. Is there any semantically meaningful difference between passing this expression as a reference to an unnamed temporary (as Fortran does) or passing it by value (as one might, for example, in Pascal)? That is, can the
Consider the following subroutine in Fortran 77:subroutine shift(a, b, c)integer a, b, ca = bb = cendSuppose we want to call shift(x, y, 0) but we don’t want to change the value of y. Knowing that built-up expressions are passed as temporaries, we decide to call shift(x, y+0, 0). Our code works
In some implementations of Fortran IV, the following code would print a 3. Can you suggest an explanation? How do you suppose more recent Fortran implementations get around the problem?c main programcall foo(2)print*, 2stopendsubroutine foo(x)x = x + 1returnend
Suppose you are writing a program in which all parameters must be passed by name. Can you write a subroutine that will swap the values of its actual parameters? Explain.
Can you write a swap routine in Java, or in any other language with only call-by-sharing parameters? What exactly should swap do in such a language?
As noted in Section 9.3.1, out parameters in Ada 83 can be written by the callee but not read. In Ada 95 they can be both read and written, but they begin their life uninitialized. Why do you think the designers of Ada 95 made this change? Does it have any drawbacks?
Taking a cue from Ada, Swift provides an in out parameter mode. The language manual does not specify whether in out parameters are to be passed by reference or value-result. Write a program that determines the implementation used by your local Swift compiler.
Fields of packed records (Example 8.8) cannot be passed by reference in Pascal. Likewise, when passing a subrange variable by reference, Pascal requires that all possible values of the corresponding formal parameter be valid for the subrange:Using what you have learned about parameter-passing
Consider the following declaration in C:double(*foo(double (*)(double, double[]), double)) (double, ...);Describe in English the type of foo.
Why do you suppose that variable-length argument lists are so seldom supported by high-level programming languages?
Building on Exercise 6.35, show how to implement exceptions using call with- current-continuation in Scheme. Model your syntax after the handler-case of Common Lisp. As in Exercise 6.35, you will probably need define-syntax and dynamic-wind.Data From Exercise 6.35:Use call-with-current-continuation
Given what you have learned about the implementation of structured exceptions, describe how you might implement the nonlocal gotos of Pascal or the label parameters of Algol 60 (Section 6.2). Do you need to place any restrictions on how these features can be used?
Describe a plausible implementation of C++ destructors or Java try. . . finally blocks. What code must the compiler generate, at what points in the program, to ensure that cleanup always occurs when leaving a scope?
Use threads to build support for true iterators in Java. Try to hide as much of the implementation as possible behind a reasonable interface. In particular, hide any uses of new thread, thread.start, thread.join, wait, and notify inside implementations of routines named yield (to be called by an
In Common Lisp, multilevel returns use catch and throw; exception handling in the style of most other modern languages uses handler-case and error. Show that the distinction between these is mainly a matter of style, rather than expressive power. In other words, show that each facility can be used
Compile and run the program in Figure 9.6. Explain its behavior. Create a new version that behaves more predictably. #include #include #include char* days [7] = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}; char today [10]; void handler(int n) { printf (" %s\n",
In C#, Java, or some other language with thread-based event handling, build a simple program around the “pause button” of Examples 9.51–9.54. Your program should open a small window containing a text field and two buttons, one labeled “pause”, the other labeled “resume”. It should
Extend your answer to the previous problem by adding a “clone” button. Pushing this button should create an additional window containing another counter. This will, of course, require additional threads.
Suppose you wish to minimize the size of closures in a language implementation that uses a display to access nonlocal objects. Assuming a language like Pascal or Ada, in which subroutines have limited extent, explain how an appropriate display for a formal subroutine can be calculated when that
Elaborate on the reasons why even parameters passed in registers may sometimes need to have locations in the stack. Consider all the cases in which it may not suffice to keep a parameter in a register throughout its lifetime.
Most versions of the C library include a function, alloca, that dynamically allocates space within the current stack frame.2 It has two advantages over the usual malloc, which allocates space in the heap: it’s usually very fast, and the space it allocates is reclaimed automatically when the
Explain how to extend the conventions of Figure C 9.9 and Section C 9.2.2 to accommodate arrays whose bounds are not known until elaboration time (as discussed in Section 8.2.2). What ramifications does this have for the use of separate stack and frame pointers?
In all three of our case studies, stack-based arguments were placed into the argument build area in “reverse” order, with the lowest-numbered argument at the top. Explain why this is important.
How would you implement nested subroutines as parameters on a machine that doesn’t let you execute code in the stack? Can you pass a simple code address, or do you require that closures be interpreted at run time?
If you have read the rest of Chapter 9, you may have noticed that the term “trampoline” is also used in conjunction with the implementation of signal handlers (Section 9.6.1). What is the connection (if any) between these uses of the term?
Explain how you might implement setjmp and longjmp on a SPARC.
Build a preorder iterator for binary trees in Java, C#, or Python. Do not use a true iterator or an explicit stack of tree nodes. Rather, create nested iterator objects on demand, linking them together as a C# compiler might if it were building the iterator object equivalent of a true preorder
One source of inaccuracy in the traffic simulation of Section C 9.5.4 has to do with the timing at traffic signals. If a signal is currently green in the EW direction, but the queue of waiting cars is empty, the signal coroutine will go to sleep until current_time + EW_duration. If a car arrives
Some language designers argue that object orientation eliminates the need for nested subroutines. Do you agree? Why or why not?
Design a class hierarchy to represent syntax trees for the CFG of Figure 4.5. Provide a method in each class to return the value of a node. Provide constructors that play the role of the make_leaf, make_un_op, and make_bin_op subroutines.Figure 4.5: + E2 + T E1.ptr := make bin_op("+", E2.ptr,
Repeat the previous exercise, but using a variant record (union) type to represent syntax tree nodes. Repeat again using type extensions. Compare the three solutions in terms of clarity, abstraction, type safety, and extensibility.
Using the C# indexer mechanism, create a hash table class that can be indexed like an array. (In effect, create a simple version of the System.Collections.Hashtable container class.) Alternatively, use an overloaded version of operator[] to build a similar class in C++.
In the spirit of Example 10.8, write a double-ended queue (deque) abstraction (pronounced “deck”), derived from a doubly linked list base class.
Use templates (generics) to abstract your solutions to the previous two questions over the type of data in the container.
Repeat Exercise 10.5 in Python or Ruby. Write a simple program to demonstrate that generics are not needed to abstract over types. What happens if you mix objects of different types in the same deque?Data From Exercise 10.5:In the spirit of Example 10.8, write a double-ended queue (deque)
When using the list class of Example 10.17, the typical C++ programmer will use a pointer type for generic parameter V, so that list_nodes point to the elements of the list. An alternative implementation would include next and prev pointers for the list within the elements themselves— typically
Can you emulate the inner class of Example 10.22 in C# or C++?
Write a package body for the list abstraction of Figure 10.2.Figure 10.2 generic type item is private; default_value : item; Ada supports both type -- and value generic parameters -- package g_list is list_err : exception; type list_node is tagged private; 'tagged' means extendable; 'private' means
Rewrite the list and queue abstractions in Eiffel, Java, and/or C#.
Repeat the previous two exercises for Python and/or Ruby.
Compare Java final methods with C++ nonvirtual methods. How are they the same? How are they different?
In several object-oriented languages, including C++ and Eiffel, a derived class can hide members of the base class. In C++, for example, we can declare a base class to be public, protected, or private:In all cases, private members of A are inaccessible to methods of B, C, or D. Consider the impact
What happens to the implementation of a class if we redefine a data member? For example, suppose we haveDoes the representation of a bar object contain one b field or two? If two, are both accessible, or only one? Under what circumstances? class foo { public: int a; char *b; }; class bar : public
Discuss the relative merits of classes and type extensions. Which do you prefer? Why?
Building on the outline of Example 10.28, write a program that illustrates the difference between copy constructors and operator= in C++. Your code should include examples of each situation in which one of these may be called (don’t forget parameter passing and function returns). Instrument the
What do you think of the decision, in C++, C#, and Ada 95, to use static method binding, rather than dynamic, by default? Is the gain in implementation speed worth the loss in abstraction and reusability? Assuming that we sometimes want static binding, do you prefer the method-by-method approach of
If foo is an abstract class in a C++ program, why is it acceptable to declare variables of type foo*, but not of type foo?
Consider the Java program shown in Figure 10.8. Assume that this is to be compiled to native code on a machine with 4-byte addresses.Figure 10.8(a) Draw a picture of the layout in memory of the object created at line 15. Show all virtual function tables.(b) Give assembly-level pseudocode for the
In Ruby, as in Java 8 or Scala, an interface (mix-in) can provide method code as well as signatures. (It can’t provide data members; that would be multiple inheritance.) Explain why dynamic typing makes this feature more powerful than it is in the other languages.
Suppose that class D inherits from classes A, B, and C, none of which share any common ancestor. Show how the data members and vtable(s) of D might be laid out in memory. Also show how to convert a reference to a D object into a reference to an A, B, or C object.

Showing 500 - 600 of 817

Programming Language Pragmatics 4th Edition Michael L. Scott - Solutions

Step by Step Answers