Questions and Answers of Programming Language Pragmatics

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
Consider the person_interface and system_user_interface classes described in Example C 10.62. If student is derived from person_interface and system_ user_interface, explain what happens in the
Given the inheritance tree of Example C 10.63, show a representation for objects of class student_prof. You may want to consult Figures C 10.9, C 10.10, and C 10.11.
Given the memory layout of Figure C 10.9 and the following declarations:student& sr;system_user& ur;show the code that must be generated for the assignmentur = sr;(Pitfall: Be sure to
Standard C++ provides a “pointer-to-member” mechanism for classes:Pointers to members are also permitted for subroutine members (methods), including virtual methods. How would you implement
As an alternative to using hmethod address, this correctioni pairs in the vtable entries of a language withmultiple inheritance, we could leave the entries as simple pointers, but make them point to
In Eiffel, shared inheritance is the default rather than the exception. Only renamed features are replicated. As a result, it is not possible to tell when looking at a class whether its members will
In Figure C 10.11, consider calls to virtual methods declared in A, but called through a B, C, or D object view. We could avoid one level of indirection by appending a copy of the A part of the
Consider the Smalltalk implementation of Euclid’s algorithm, presented at the end of Section C 10.7.1. Trace the messages involved in evaluating 4 gcd: 6.
Is the define primitive of Scheme an imperative language feature? Why or why not?
It is possible to write programs in a purely functional subset of an imperative language such as C, but certain limitations of the language quickly become apparent. What features would need to be
Explain the connection between short-circuit Boolean expressions and normal-order evaluation. Why is cond a special form in Scheme, rather than a function?
Write a program in your favorite imperative language that has the same input and output as the Scheme program of Figure 11.1. Can you make any general observations about the usefulness of Scheme for
Suppose we wish to remove adjacent duplicate elements from a list (e.g., after sorting). The following Scheme function accomplishes this goal:Write a similar function that uses the imperative
Write tail-recursive versions of the following:(a)(b) ;; compute integer log, base 2 ;; (number of bits in binary representation) ;; works only for positive integers (define log2 (lambda (n) (if (= n
Write purely functional Scheme functions to(a) Return all rotations of a given list. For example, (rotate ‚(a b c d e)) should return ((a b c d e) (b c d e a) (c d e a b) (d e a b c) (e a b c d))
Write a purely functional Scheme function that returns a list of all permutations of a given list. For example, given (a b c), it should return ((a b c) (b a c) (b c a) (a c b) (c a b) (c b a)) (in
Modify the Scheme program of Figure 11.1 or the OCaml program of Figure 11.3 to simulate an NFA (nondeterministic finite automaton), rather than a DFA. (The distinction between these automata is
Consider the problem of determining whether two trees have the same fringe: the same set of leaves in the same order, regardless of internal structure. An obvious way to solve this problem is to
In Example 11.59 we showed how to implement interactive I/O in terms of the lazy evaluation of streams. Unfortunately, our code would not work as written, because Scheme uses applicative-order
Write new versions of cons, car, and cdr that operate on streams. Using them, rewrite the code of the previous exercise to eliminate the calls to delay and force. Note that the stream version of cons
Write the standard quicksort algorithm in Scheme, without using any imperative language features. Be careful to avoid the trivial update problem; your code should run in expected time n log n.Rewrite
Write insert and find routines that manipulate binary search trees in Scheme (consult an algorithms text if you need more information). Explain why the trivial update problem does not impact the
Write an LL(1) parser generator in purely functional Scheme. If you consult Figure 2.24, remember that you will need to use tail recursion in place of iteration. Assume that the input CFG consists of
Write an equality operator (call it =/) that works correctly on the yearday type of Example 11.38. (You may need to look up the rules that govern the occurrence of leap years.)
Create addition and subtraction functions for the celsius and fahrenheit temperature types introduced in Sidebar 11.3. To allow the two scales to be mixed, you should also define conversion functions
We can use encapsulation within functions to delay evaluation in OCaml:Now givenlet rec next_int n = (n, Promise (fun() -> next_int (n + 1)));;let naturals = Promise (fun() -> next_int (1));;we
Write an OCaml version of Example 11.67. Alternatively (or in addition), solve Exercises 11.5, 11.7, 11.8, 11.10, 11.13, 11.14, or 11.15 in OCaml.
In Figure C 11.6 we evaluated our expression in normal order. Did we really have any choice? What would happen if we tried to use applicative order?
Prove that for any lambda expression f , if the normal-order evaluation of Y f terminates, where Y is the fixed-point combinator λh:(λx:h(x x)) (λx:h(x x)), then f (Yf ) and Yf will reduce to
Given the definition of structures (lists) in Section C 11.7.3, what happens if we apply car or cdr to nil? How might you introduce the notion of “type error” into lambda calculus?
Letzero Ξ λx:xsucc Ξ λn:(λs:(s select second) n)where select second Ξ λx:λy:y. Now letone Ξ succ zerotwo Ξ succ one
Starting with the clauses at the beginning of Example 12.17, use resolution (as illustrated in Example 12.3) to show, in two different ways, that there is a path from a to e.
Solve Exercise 6.22 in Prolog.Data From Exercise 6.22:Use iterators to construct a program that outputs (in some order) all structurally distinct binary trees of n nodes. Two trees are considered
Consider the Prolog gcd program in Figure 1.2. Does this program work “backward” as well as forward? (Given integers d and n, can you use it to generate a sequence of integers m such that gcd(n,
In the spirit of Example 11.20, write a Prolog program that exploits backtracking to simulate the execution of a nondeterministic finite automaton.
Show that resolution is commutative and associative. Specifically, if A, B, and C are Horn clauses, show that (A ⊕B) = (B ⊕ A) and that ((A ⊕ B) ⊕ C) = (A ⊕ (B ⊕ C)), where ⊕ indicates
In Example 12.8, the query ?- classmates(jane_doe, X) will succeed three times: twice with X = jane_doe and once with X = ajit_chandra. Show how to modify the classmates(X, Y) rule so that a student
Modify Example 12.17 so that the goal path(X, Y), for arbitrary already instantiated X and Y, will succeed no more than once, even if there are multiple paths from X to Y.
Using only \+ (no cuts), modify the tic-tac-toe example of Section 12.2.5 so it will generate only one candidate move from a given board position. How does your solution compare to the cut-based one
Prove the claim, made in Example 12.19, that there is no winning strategy in tic-tac-toe—that either player can force a draw.
Prove that the tic-tac-toe strategy of Example 12.19 is optimal (wins against an imperfect opponent whenever possible, draws otherwise), or give a counterexample.
Starting with the tic-tac-toe program of Figure 12.4, draw a directed acyclic graph in which every clause is a node and an arc from A to B indicates that it is important, either for correctness or
Write Prolog rules to define a version of the member predicate that will generate all members of a list during backtracking, but without generating duplicates. Note that the cut and\+ based versions
Use the clause predicate of Prolog to implement the call predicate (pretend that it isn’t built in). You needn’t implement all of the built-in predicates of Prolog; in particular, you may ignore
Use the clause predicate of Prolog to write a predicate call_bfs that attempts to satisfy goals breadth-first.
Write a (list-based) insertion sort algorithm in Prolog. Here’s what it looks like in C, using arrays: void insertion_sort(int A[], int N) int i, j, t; for (i = 1; i < N; i++) { %3D t = A[i];
Quicksort works well for large lists, but has higher overhead than insertion sort for short lists. Write a sort algorithm in Prolog that uses quicksort initially, but switches to insertion sort (as
Write a Prolog sorting routine that is guaranteed to take O(n log n) time in the worst case.
Consider the following interaction with a Prolog interpreter:?- Y = X, X = foo(X).Y =
Restate the following Prolog rule in predicate calculus, using appropriate quantifiers:sibling(X, Y) :- mother(M, X), mother(M, Y),
Consider the following statement in predicate calculus:empty_class(C) ← ¬∃X[takes(X; C)](a) Translate this statement to clausal form.(b) Can you translate the statement into Prolog? Does
Consider the seemingly contradictory statement¬foo(X) → foo(X)Convert this statement to clausal form, and then translate into Prolog. Explain what will happen if you ask?- foo(bar).Now consider
Write a simple abstract ordered_set class (an interface) whose methods include void insert(T val), void remove (T val), bool lookup (T val), and bool is_empty(), together with a language-appropriate
C++ has no direct analogue of the extends X and super X clauses of Java. Why not?
Modify the code of Figure 7.3 or your solution to Exercise 7.12 to throw an exception if an attempt is made to enqueue an item in a full queue, or to dequeue an item from an empty queue.Data From
In Section 9.3.1 we noted that Ada 83 does not permit subroutines to be passed as parameters, but that some of the same effect can be achieved with generics. Suppose we want to apply a function to
Bjarne Stroustrup, the original designer of C++, once described templates as “a clever kind of macro that obeys the scope, naming, and type rules of C++” [Str13, 2nd ed., p. 257]. How close is
Consider the following code skeleton in C++:Explain why the compiler won’t allow the second call. Give an example of bad things that could happen if it did. #include using std::1ist; class foo
Yet another solution to the problem of the previous exercise is to make the sorting routine a method of a sorter class. The comparison routine can then be passed into the class as a constructor
In Example 7.53 we mentioned three ways to make the need for comparisons more explicit when defining a generic sort routine in C++: make the comparison routine a method of the generic parameter class
Flesh out the C++ sorting routine of Example 7.53. Demonstrate that this routine does “the wrong thing” when asked to sort an array of char* strings.
Rewrite the generic sorting routine of Examples 7.50–7.52 (with constraints) using OCaml or SML functors.
Figure 7.3 passes integer max_items to the queue abstraction as a generic parameter. Write an alternative version of the code that makes max_items a parameter to the queue constructor instead. What
In your favorite language with generics, write code for simple versions of the following abstractions:(a) A stack, implemented as a linked list(b) A priority queue, implemented as a skip list or a
(a) Give a generic solution to Exercise 6.19.Data From Exercise 6.19:Write a C++ preorder iterator to supply tree nodes to the loop in Example 6.69. You will need to know (or learn) how to use
Rewrite the code of Figure 7.3 in Ada, Java, or C#.Figure 7.3: template class queue { item items [max_items]; int next_free, next_full, num_items; public: queue () : next_free (0), next_full(0),
In Section 7.2.2 we introduced the notion of a universal reference type (void * in C) that refers to an object of unknown type. Using such references, implement a “poor man’s generic queue” in
Consider the problem of performing range checks on set expressions in Pascal. Given that a set may contain many elements, some of which may be known at compile time, describe the information that a
Ada provides two “remainder” operators, rem and mod for integer types, defined as follows [Ame83, Sec. 4.5.5]:Integer division and remainder are defined by the relation A = (A/B)*B + (A rem B),
When Sun Microsystems ported Berkeley Unix from the Digital VAX to the Motorola 680x0 in the early 1980s,many C programs stopped working, and had to be repaired. In effect, the 680x0 revealed certain
Suppose you are implementing an Ada compiler, and must support arithmetic on 32-bit fixed-point binary numbers with a programmer-specified number of fractional bits. Describe the code you would need
Consider the following declarations:1. type cell –– a forward declaration2. type cell_ptr = pointer to cell3. x : cell4. type cell = record5.
In the following code, which of the variables will a compiler consider to have compatible types under structural equivalence? Under strict name equivalence? Under loose name equivalence?type T =
Most statically typed languages developed since the 1970s (including Java, C#, and the descendants of Pascal) use some form of name equivalence for types. Is structural equivalence a bad idea? Why or
Write, in SR or pseudocode, a function that returns(a) An arbitrary nonzero element of a given array(b) An arbitrary permutation of a given arrayIn each case, write your code in such a way that if
The astute reader may have noticed that the final line of the code in Example C 6.95 embodies an arbitrary choice. It could just as easily have said gcd := b. Show how to use a guarded command to
Explain why the following guarded commands in SR are not equivalent: if a < b -> c := a [] b < c ->c := b if a < b -> c := a [] b < c -> c := b %3D [] else ->c := d [] true -> c:= d fi fi
Write a findRE generator in Icon that mimics the behavior of find, but takes as its first parameter a regular expression. Use a string to represent your regular expression, with syntax as in Section
Write a program in Icon that will print the k most common words in its input, one per line, with each preceded by a count of the number of times it appears. If parameter k is not specified on the
(Difficult) Use call-with-current-continuation (call/cc) to implement the following structured nonlocal control transfers in Scheme. (This requires knowledge of material in Chapter 11.) You will
Use lazy evaluation (delay and force) to implement iterator objects in Scheme. More specifically, let an iterator be either the null list or a pair consisting of an element and a promise which when
Give an example in C in which an in-line subroutine may be significantly faster than a functionally equivalent macro. Give another example in which the macro is likely to be faster.
Is it possible to write a tail-recursive version of the classic quicksort algorithm? Why or why not?
Write a tail-recursive function in Scheme or ML to compute n factorial (n! = П1≤i≤n i = 1 × 2 × · · · × n).
Show how to calculate the number of iterations of a general Fortran 90- style do loop. Your code should be written in an assembler-like notation, and should be guaranteed to work for all valid bounds
If you have taken a course in automata theory or recursive function theory, explain why while loops are strictly more powerful than for loops. (If you haven’t had such a course, skip this
A loop invariant is a condition that is guaranteed to be true at a given point within the body of a loop on every iteration. Loop invariants play a major role in axiomatic semantics, a formal
Bentley [Ben00, Chap. 4] provides the following informal description of binary search:We are to determine whether the sorted array X[1..N] contains the element T. . . . Binary search solves the
Rubin [Rub87] used the following example (rewritten here in C) to argue in favor of a goto statement:The intent of the code is to find the first all-zero row, if any, of an n × n matrix. Do you find
Consider a mid-test loop, here written in C, that looks for blank lines in its input:Show how you might accomplish the same task using a while or do (repeat) loop, if mid-test loops were not
In an expression-oriented language such as Algol 68 or Lisp, a while loop (a do loop in Lisp) has a value as an expression. How do you think this value should be determined? (How is it determined in
Build true iterators in Java using threads. Make your solution as clean and as general as possible. In particular, you should provide the standard Iterator or IE numerable interface, for use with
Use iterators to construct a program that outputs (in some order) all structurally distinct binary trees of n nodes. Two trees are considered structurally distinct if they have different numbers of
Write, in C#, Python, or Ruby, an iterator that yields (a) all permutations of the integers 1 . . n, (b) all combinations of k integers from the range 1 . . n (0 ≤ k ≤ n).You may represent your
Write code for the tree_iter type (struct) andthe ti_create, ti_done, ti_next, ti_val, and ti_delete functions employed in Example 6.73.
Write a C++ preorder iterator to supply tree nodes to the loop in Example 6.69. You will need to know (or learn) how to use pointers, references, inner classes, and operator overloading in C++. For
Revise the algorithm of Figure 6.6 so that it performs an in-order enumeration, rather than preorder.Figure 6.6: class BinTree implements Iterable { BinTree left; BinTree right; T val; // other
The equivalence of for and while loops, is not precise. Give an example in which it breaks down.
As noted in Section 6.4.2, languages vary in how they handle the situation in which the controlling expression in a case statement does not appear among the labels on the arms. C and Fortran 90 say

Showing 600 - 700 of 818