next up previous
Next: 6.8 SETL Implementations Up: 6. Conclusions Previous: 6.6 Miscellaneous Desiderata

Subsections


6.7 Beyond the Fringe

There are a number of ``features'' which might appear at first glance to be desirable in SETL, but which really are not.

  
6.7.1 Pointers

Perhaps the most obvious example is pointers, explicit as in Pascal or Ada (C pointers are so tied to a machine memory model that they permit arithmetic, which is an abomination), or implicit as in Java or SNOBOL. The LISP family would be lost without them. Pointers are so useful in the construction of data structures in various languages that programmers who are used to them may wonder how on earth one is to get along without them. The obvious answer is to use maps. Aliases are, after all, sometimes useful, but as remarked in Sections 1.1 [Why SETL?] and 5.3.5 [On Aliases], they should be avoided except where there is some compelling reason to use them. For situations where aliases are genuinely appropriate, maps are the ideal general reference structure, because they allow keys to be selected on the basis of their semantic content rather than being forced to be opaque nodes or thinly veiled integers, and maps also have the virtue of clearly identifying a context within which each reference (map lookup) occurs--every map is like a separate address space.

Most languages that have pointers include pointers to variables. Scheme does not, but the ease with which data can be converted to code at run-time produces a similar effect. Nor does Java--its pointers are all to objects--and this at least eliminates one class of alias.

To add pointers to variables in SETL would completely destroy its value semantics. Even to add pointers to objects would be unwise, because maps already best serve the required purpose in a high-level language; there is more to be lost than gained in burdening the SETL programmer with the need to keep track of the distinction between an object and a reference to that object. Neither is it feasible to insist that all user-defined objects have the kind of status they have in Jave, where all accesses begin with a reference. This would make them unacceptably different from SETL's fundamental aggregate objects (sets and tuples), which are strictly values.

6.7.2 Closures and Continuations

Another unwelcome addition to SETL would be closures and more generally continuations in the Scheme sense. I consider even the creation of ``procedure values'' by the routine pseudo-operator to be a provisional measure that is to be deprecated, despite the fact that it was indispensable in ``escaping the event loop'' [89] in Section 5.3.8.3 [The Event Loop] via callbacks. It is of interest that a cautionary note regarding the manipulation of a global variable had to be given with that example.

A closure can preserve local variables from destruction beyond their normal span, so that the state of those variables can be inspected and updated when the closure is later invoked. Closures have some similarity to pointers in that the holder of a closure is effectively in possession of a set of references to variables. Worse, whereas the number of variables to which ordinary procedure values can refer is bounded by the number of global identifiers in a program, there is no such limit for closures. The same pair of lambda expressions, for example, can be used any number of times to produce new pairs of closures, each pair referring to a variable in a different activation record.

Closures are in any case a poor substitute for a more forthright way of bundling data with the means to access and manipulate it, namely objects. Callbacks, too, are better treated in Java/C++ style than being implemented using procedure values or closures. The lightweight multiple inheritance available to any Java object through the repeated use of implements allows it to register for callbacks by any other object that recognizes the appropriate interface simply by defining methods with the names and signatures required by that interface, and identifying itself to that other object by calling the appropriate registration method.

  
6.7.3 Threads and Fine-Grained Concurrency

This dissertation has argued for the liberal use of processes, and I hope the case study of Chapter 4 [WEBeye: A Case Study] has begun to demonstrate their value. These processes enjoy the ``high walls of protection'' alluded to in Section 5.3.7 [On Program Size] around them: they share very few resources, and those which they do share are usually mediated by third parties such as server processes.

By contrast, languages that encourage the use of ``threads'' (processes sharing variables in the ``local'' address space) create synchronization concerns for which the programmer must remain constantly vigilant.

I have found Java ideal as a language for introducing concurrency and its attendant problems in three courses so far: a graduate course in Advanced Operating Systems, a senior undergraduate course in Network Programming, and in a junior undergraduate course in Programming Languages, because the elements (thread creation, synchronization, and signalling) are very accessibly packaged in Java, and this allows my students to proceed rapidly to the stage of learning for themselves how difficult concurrent programming is to do correctly. It was rare indeed to find a student program that used the synchronized keyword completely appropriately, had no race conditions, and was entirely safe from deadlock.

As with pointers and closures, the issue again is resource sharing by multiple parties. In this case, however, the parties are threads, and instead of only one party at a time making access to common resources, all the parties at once can do so, in an interleaved if not literally concurrent manner.

Apart from disciplined programming, the best defense against the enormous challenges raised by the need to deal with all the possible interactions of simultaneously executing threads is to minimize those interactions. A model that offers the ``convenience'' of shared access to all the data that is naturally visible to all threads works powerfully against this minimization.

For this reason, even without considering the problems of defining and implementing a SETL system that is correct and yet does a reasonable job of timeslicing and of code optimization, I am very much opposed to the introduction of any kind of threads in SETL that would allow the sharing of global (but process-local) data. Currently, the only objects to which SETL processes share access are external, and in good designs are themselves processes. This is as it should be.

Conversely, threads are not likely to be particularly useful in SETL. Message-passing between processes is at worst a heavier mechanism than strictly necessary in any given situation, and certainly is a sufficient base upon which to implement semaphores, monitors, and so on. In the following example, suggested by Doug Lea's ``bounded counter'' study [136, pp. 84-102], a monitor for a counter (the counter could as easily be a bounded buffer) is implemented as a process which accepts increment requests from ``producers'' and decrement requests from ``consumers'' through server sockets. Requests are serviced immediately if possible, and the requester is blocked otherwise: *

-- To run me in Unix:  setl -DMIN=0 -DMAX=2 {me} &
 
var counter := MIN;      -- MIN effectively #defined on command line
var producers := {};     -- clients awaiting increment
var consumers := {};     -- clients awaiting decrement
 
inc_sock := open (`0', `server-socket');     -- listen for producers
dec_sock := open (`0', `server-socket');     -- listen for consumers
 
putfile (`inc-port', str port inc_sock);     -- advertise producer port
putfile (`dec-port', str port dec_sock);     -- advertise consumer port
 
loop                                            -- cycle indefinitely
 
  [ready] := select ([{inc_sockdec_sock}]);
 
  if inc_sock in ready then     -- producer (increment) request
    fd := accept (inc_sock);
    if fd /= om then
      if counter < MAX then     -- satisfy request immediately
        counter +:= 1;
        send_counter_value_to_client (fd);
        notify_any_waiting_consumer;
      else                      -- counter at MAX, defer request
        producers with:= fd;
      end if;
    end if;
  end if;
 
  if dec_sock in ready then     -- consumer (decrement) request
    fd := accept (dec_sock);
    if fd /= om then
      if counter > MIN then     -- satisfy request immediately
        counter -:= 1;
        send_counter_value_to_client (fd);
        notify_any_waiting_producer;
      else                      -- counter at MIN, defer request
        consumers with:= fd;
      end if;
    end if;
  end if;
 
end loop;
 
-- Refinements
 
notify_any_waiting_consumer::
  fd from consumers;        -- pull arbitrary fd from consumers
  if fd /= om then
    counter -:= 1;
    send_counter_value_to_client (fd);
  end if;
 
notify_any_waiting_producer::
  fd from producers;        -- pull arbitrary fd from producers
  if fd /= om then
    counter +:= 1;
    send_counter_value_to_client (fd);
  end if;
 
-- Subprogram
 
proc send_counter_value_to_client (fd);
  printa (fdcounter);     -- tell client the new counter value
  close (fd);
end proc;
This program can be exercised conveniently by running as many instances of the following programs as desired. For simplicity, they assume they are being run on the local machine in the same directory as the monitor, but because the communication uses full-fledged TCP sockets, they can easily be run anywhere if the monitor's actual host name and port numbers are first substituted in the open calls: *
-- Producer program (requests one increment)
fd := open (`localhost:' + getfile `inc-port', `socket');
print (getline fd);
 
-- Consumer program (requests one decrement)
fd := open (`localhost:' + getfile `dec-port', `socket');
print (getline fd);


next up previous
Next: 6.8 SETL Implementations Up: 6. Conclusions Previous: 6.6 Miscellaneous Desiderata
David Bacon
1999-12-10