Questions and Answers of Programming Language Pragmatics

Design a maze in which there are starting positions that return Trapped when the starting position is Open.
True or False? All recursive algorithms need a base case, even if it is “Do nothing.”
True or False? The general case is what allows recursion to terminate.
True or False? The base case is what allows recursion to terminate.
True or False? A recursive function must always contain both a base case and a general case, although the base case may be empty.
True or False? Both void and value-returning functions can be recursive.
True or False? The body of a recursive function can include many calls to itself.
True or False? If a program halts and an error message similar to“RUN-TIME STACK OVERFLOW” appears, the cause may be infinite recursion.
True or False? In general, a nonrecursive solution to a problem is more memory efficient than a recursive solution.
True or False? Tail recursion often indicates that the problem could be solved more efficiently using iteration.
True or False? There usually are more local variables in a recursive routine than in the equivalent iterative routine.
Repeat the previous exercise using Java Lock variables.Data from Repeat the previous exercise Give amore efficient solution to the previous exercise that avoids the use of notify All. (Warning:
Drawing inspiration from Examples 13.29 and 13.30, design a nonblocking linked-list implementation of a stack using compare_and_swap. (When CAS was first introduced, on the IBM 370 architecture, this
Rewrite Example 13.51 in Java.
Repeat the previous exercise in C#. Add information about parameter names and generic instances.
Fill in the missing lines in Figure C 4.19.
Is &(&i) ever valid in C? Explain.
Does a program run faster when the programmer leaves optional parameters out of a subroutine call? Why or why not?
Following the code in Figure 6.5, and assuming a single-stack implementation of iterators, trace the contents of the stack during the execution of a for loop that iterates over all nodes of a
Give an example of a “benign” race condition—one whose outcome affects program behavior, but not correctness.
We have defined the ready list of a thread package to contain all threads that are runnable but not running, with a separate variable to identify the currently running thread. Could we just as easily
Imagine you are writing the code to manage a hash table that will be shared among several concurrent threads. Assume that operations on the table need to be atomic. You could use a single mutual
The typical spin lock holds only one bit of data, but requires a full word of storage, because only full words can be read, modified, and written atomically in hardware. Consider, however, the hash
Building on the previous exercise, suppose that stack nodes are dynamically allocated. If we read a pointer and then are delayed (e.g., due to preemption), the node to which the pointer refers may be
We noted in Section 13.3.2 that several processors, including the ARM, MIPS, and Power, provide an alternative to compare_and_swap (CAS) known as load_linked/store_conditional (LL/SC). A load_linked
Starting with the test-and-test_and_set lock of Figure 13.8, implement busy-wait code that will allow readers to access a data structure concurrently. Writers will still need to lock out both readers
Assuming the Java memory model,(a) Explain why it is not sufficient in Figure 13.11 to label X and Y as volatile.(b) Explain why it is sufficient, in that same figure, to enclose C’s reads (and
Implement the nonblocking queue of Example 13.30 on an x86. Do you need fence instructions to ensure consistency? If you have access to appropriate hardware, port your code to a machine with a more
Consider the implementation of software transactional memory in Figure 13.19.(a) How would you implement the read set, write map, and lock map data structures? You will want to minimize the cost not
The code of Example 13.35 could fairly be accused of displaying poor abstraction. If we make desired condition a delegate (a subroutine or object closure), can we pass it as an extra parameter, and
The mechanism used in Figure 13.13 to make scheduler code reentrant employs a single OS-provided lock for all the scheduling data structures of the application. Among other things, this mechanism
Show how to implement a lock-based concurrent set as a singly linked sorted list. Your implementation should support insert, find, and remove operations, and should permit operations on separate
Implement a nonblocking version of the set of the previous exercise.Previous Exercise:Show how to implement a lock-based concurrent set as a singly linked sorted list. Your implementation should
To make spin locks useful on a multi programmed multiprocessor, one might want to ensure that no process is ever preempted in the middle of a critical section. That way it would always be safe to
Show how to use semaphores to construct a scheduler-based n-thread barrier.
Prove that monitors and semaphores are equally powerful. That is, use each to implement the other. In the monitor-based implementation of semaphores, what is your monitor invariant?
Show how to use binary semaphores to implement general semaphores.
In Example 13.38 (Figure 13.15), suppose we replaced the middle four lines of procedure P withand the middle four lines of procedure V withWhat is the problem with this new version? Explain how it
Suppose that every monitor has a separate mutual exclusion lock, so that different threads can run in different monitors concurrently, and that we want to release exclusion on both inner and outer
Show how general semaphores can be implemented with conditional critical regions in which all threads wait for the same condition, thereby avoiding the overhead of unproductive wake-ups.
Write code for a bounded buffer using the protected object mechanism of Ada 95.
Repeat the previous exercise in Java using synchronized statements or methods. Try to make your solution as simple and conceptually clear as possible. You will probably want to use notify All.
Give amore efficient solution to the previous exercise that avoids the use of notify All. (It is tempting to observe that the buffer can never be both full and empty at the same time, and to assume
Explain how escape analysis, mentioned briefly in Sidebar 10.3, could be used to reduce the cost of certain synchronized statements and methods in Java.
The dining philosophers problem is a classic exercise in synchronization (Figure 13.20). Five philosophers sit around a circular table. In the center is a large communal plate of spaghetti. Each
In the previous exercise you may have noticed that the dining philosophers are prone to deadlock. One has to worry about the possibility that all five of them will pick up their right-hand forks
In some concurrent programming systems, global variables are shared by all threads. In others, each newly created thread has a separate copy of the global variables, commonly initialized to the
AND parallelism in logic languages is analogous to the parallel evaluation of arguments in a functional language (e.g., Multilisp). Does OR parallelism have a similar analog?
In Section 13.4.5 we claimed that both AND parallelism and OR parallelism were problematic in Prolog, because they failed to adhere to the deterministic search order required by language semantics.
In Section 13.4.1 we cast monitors as a mechanism for synchronizing access to shared memory, and we described their implementation in terms of semaphores. It is also possible to think of a monitor as
Show how shared memory can be used to implement message passing. Specifically, choose a set of message-passing operations (e.g., no-wait send and explicit message receipt) and show how to implement
When implementing reliable messages on top of unreliable messages, a sender can wait for an acknowledgment message, and retransmit if it doesn’t receive it within a bounded period of time. But how
While Go allows both input (receive) and output (send) guards on its select statements, Occam and CSP allow only input guards. The difference has to do with the fact that Go is designed for
In Section C 13.5.3 we described the semantics of a terminate arm on an Ada select statement: this arm may be selected if and only if all potential communication partners have terminated, or are
Does filename “globbing” provide the expressive power of standard regular expressions? Explain.
Write shell scripts to(a) Replace blanks with underscores in the names of all files in the current directory.(b) Rename every file in the current directory by prepending to its namea textual
In Example 14.16 we used "$@" to refer to the parameters passed to ll. What would happen if we removed the quote marks? (Try this for files whose names contain spaces!) Read the man page for bash and
(a) Extend the code in Figure 14.5, 14.6, or 14.7 to try to kill processes more gently. You’ll want to read the man page for the standard kill command. Use a TERM signal first. If that doesn’t
Write a Perl, Python, or Ruby script that creates a simple concordance: a sorted list of significant words appearing in an input document, with a sublist for each that indicates the lines on which
Write Emacs Lisp scripts to(a) Insert today’s date into the current buffer at the insertion point (current cursor location).(b) Place quote marks (" ") around the word surrounding the insertion
Explain the circumstances under which it makes sense to realize an interactive task on the Web as a CGI script, an embedded server-side script, or a client-side script. For each of these
Write a web page with embedded PHP to print the first 10 rows of Pascal’s triangle (see Example C 17.10 if you don’t know what this is). When rendered, your output should look like Figure
Create a fill-in web form that uses a JavaScript implementation of the Luhn formula to check for typos in credit card numbers.Figure 14.15: Adder Adder 12 First addend function doAdd () { 34
(a) Modify the code of Figure 14.15 (Example 14.35) so that it replaces the form with its output, as the CGI and PHP versions of Figures 14.11 and 14.14 do.(b) Modify the CGI and PHP scripts of
Run the following program in Perl:You may be surprised by the output. Perl 5 allows named subroutines to nest, but does not create closures for them properly. Rewrite the code above to create a
Write a program that will map the web pages stored in the file hierarchy below the current directory. Your output should itself be a web page, containing the names of all directories and .html files,
In Section 14.4.1 we claimed that nested blocks in Ruby were part of the named scope in which they appear. Verify this claim by running the following Ruby script and explaining its output:Now comment
Write a Perl script to translate English measurements (in, ft, yd, mi) into metric equivalents (cm, m, km). You may want to learn about the e modifier on regular expressions, which allows the
Write a Perl script to find, for each input line, the longest substring that appears at least twice within the line, without overlapping.
Perl provides an alternative (?:. . . ) form of parentheses that supports grouping in regular expressions without performing capture. Using this syntax, Example 14.57 could have been written as
Consider again the sed code of Figure 14.1. It is tempting to write the first of the compound statements as follows (note the differences in the three substitution commands):Explain why this
Consider the following regular expression in Perl: /^(?:((?:ab)+) |a((?:ba)*))$/. Describe, in English, the set of strings it will match. Show a natural NFA for this set, together with the minimal
Modify the XSLT of Figure C 14.24 to do one or more of the following:(a) Alter the titles of conference papers so that only first words, words that follow a dash or colon (and thus begin a subtitle),
Suppose bibliographic entries in Figure C 14.23 contain a mandatory key element, and that other documents can contain matching cite elements. Create an XSLT script that imitates the work of BibTEX.
If you were writing a two-pass compiler, why might you choose a high level IF as the link between the front end and the back end? Why might you choose a medium-level IF?
Consider a language like Ada or Modula-2, in which a module M can be divided into a specification (header) file and an implementation (body) file for the purpose of separate compilation. Should M’s
Many research compilers (e.g., for SR, Cedar, Lynx, and Modula-3) have used C as their IF. C is well documented and mostly machine independent, and C compilers are much more widely available than
List as many ways as you can think of in which the back end of a just-in- time compiler might differ from that of a more conventional compiler. What design goals dictate the differences?
Suppose that k (the number of temporary registers) in Figure 15.6 is 4 (this is an artificially small number for modern machines). Give an example of an expression that will lead to register spilling
Modify the attribute grammar of Figure 15.6 in such a way that it will generate the control flow graph of Figure 15.3 instead of the linear assembly code of Figure 15.7.Figure 15.3:Figure 15.6:Figure
Add productions and attribute rules to the grammar of Figure 15.6 to handle Ada-style for loops. Using your modified grammar, hand-translate the syntax tree of Figure 15.10 into pseudo assembly
One problem (of many) with the code we generated in Section 15.3 is that it computes at run time the value of expressions that could have been computed at compile time. Modify the grammar of Figure
Modify the grammar of Figure 15.6 to generate jump code for Boolean expressions, as described in Section 6.4.1. You should assume short circuit evaluation.Figure 15.6:type = int then "readint" else
Our GCD program did not employ subroutines. Extend the grammar of Figure 15.6 to handle procedures without parameters (feel free to adopt any reasonable conventions on the structure of the syntax
The grammar of Figure 15.6 assumes that all variables are global. In the presence of subroutines, we should need to generate different code (with fp-relative displacement mode addressing) to access
Compare and contrast GIMPLE with the notation we have been using for syntax tree attribute grammars.
PC-relative branches on many processors are limited in range—they can only target locations within 2k bytes of the current PC, for some k less than the word size of the machine. Explain how to
We have noted that Linux creates a single data segment containing all the static data of libraries that might be called (directly or indirectly) by a given program. The space required for this
In Example C 9.61 we described how the GNU Ada Translator (gnat) for the x86 uses dynamically generated code to represent a subroutine closure. Explain how a similar technique could be used to
Write the formula of Example 15.4 as an expression tree (a syntax tree in which each operator is represented by an internal node whose children are its operands). Convert your tree to an expression
We assumed in Example 15.4 and Figure 15.4 that a, b, c, and s were all among the first few local variables of the current method, and could be pushed onto or popped from the operand stack with a
The speculative optimization of Example 16.5 could in principle be statically performed. Explain why a dynamic compiler might be able to do it more effectively.
Perhaps the most common form of run-time instrumentation counts the number of times that each basic block is executed. Since basic blocks are short, adding a load-increment-store instruction sequence
Visit software.intel.com/en-us/articles/pintool-downloads and download a copy of Pin. Use it to create a tool to profile loops. When given a (machine code) program and its input, the output of the
Outline mechanisms that might be used by a binary rewriter, without access to source code, to catch uses of uninitialized variables, “double deletes,” and uses of deallocated memory (e.g.,
Extend the code of Figure 16.4 to print information about(a) Fields(b) Constructors(c) Nested classes(d) Implemented interfaces(e) Ancestor classes, and their methods, fields, and constructors(f)
Write an interactive tool that accepts keyboard commands to load specified class files, create instances of their classes, invoke their methods, and read and write their fields. Feel free to limit
In Java, if the concrete type of p is Foo, p.getClass() and Foo.class will return the same thing. Explain why a similar equivalence could not be guaranteed to hold in Ruby, Python, or JavaScript.
Design a “test harness” system based on Java annotations. The user should be able to attach to a method an annotation that specifies parameters to be passed to a test run of the method, and
C++ provides a typeid operator that can be used to query the concrete type of a pointer or reference variable:if (typeid(*p) == typeid(my_derived_type)) ...Values returned by typeid can be compared

Showing 400 - 500 of 818