This article contains the following executables: PROXY.ZIP
Burt is a consultant and former professor of computer science specializing in software engineering and programming languages. He can be reached via CompuServe at 70262, 1074.
Scheme has long been regarded as an ideal language for prototyping because it is interactive, extensible, and contains simple, yet powerful features. Although the Scheme syntax is generally straight-forward, many programmers are nonetheless put off by it because of its heavy use of parentheses. For this reason, I've developed Proxy, an interactive language with a C-like syntax. Proxy provides all of the high-level data structures--sets, maps, sequences, and objects--useful for software design and prototyping. The Proxy interpreter is available electronically (see "Availability," page 5).
Proxy, which is written in Scheme, is implemented by translating Proxy expressions and function definitions into Scheme-language statements. These statements are then executed by a Scheme interpreter. The current implementation allows Proxy functions to call Scheme functions, which can then send results back to the Proxy program.
There are no pointers or arrays in Proxy (although a map can be thought of as a generalized array). This keeps data structures at a high level suitable for prototyping. A software system can be represented as a "state" and a collection of functions that operate on components of the state. The user may develop these operations incrementally or define them in files that are loaded prior to execution. It's also possible to manipulate objects (defined by classes) that encapsulate local states; this allows the user to define a software model as a hierarchy of submodels. The use of Proxy data structures requires some mathematical sophistication, but nothing beyond the ability of an experienced software developer.
Since Proxy uses infix notation, it avoids excessive use of parentheses. It further reduces extra parentheses by using unary operators in many cases where functional notation would be required. A comparison of the use (and disuse) of parentheses is shown in Figure 1, which provides both a Proxy and Scheme rendering of a simple recursive function that adds up the numbers in a sequence.
(a)
reduce (x) {
if (x==[]) return 0; else
return hd x + reduce (tl x);};
(b)
(define (reduce x)
(if (null? x) 0
(+ (car x) (reduce (cdr x)))))
A mathematical set is, of course, an unordered collection of elements. From a formal point of view, each element should have the same type. However, since Proxy has latent types (types not declared by the programmer), set elements are not restricted to having the same type.
The simplest set operation is to enumerate the set, delimiting its elements by curly brackets, for example, {1,2,3,4,5}. This same set can be constructed by using the range notation, {1..5} (not to be confused with the range of a map, to be defined below).
Two predicates can be applied to sets: exists and all. When the existential quantifier exists is applied to a set, the predicate returns True if at least one element of the set satisfies the predicate, and False otherwise. For example, the statement (exists x in {2,3,5,7}; even(x)); returns True. On the other hand, all returns True only if all elements of the set satisfy the predicate. For example (all x in {2,3,5,7}; even(x)); returns False.
A more general way of constructing sets is given by the form shown in Example 1. The syntax x<-expr is called a "generator" and is required. expr is evaluated to yield a set. The values of the set are successively assigned to x, and a new set is formed from elements obtained by applying the function f to the successive values of x which satisfy pred(x). pred(x), however, is optional. Example 2 should make this clearer.
{ f(x): x<- expr ; pred(x) }
{ x: x<- {1,2,3,4,5}}; returns {1,2,3,4,5}
{ x: x <- {1,2,3,4,5};x>2}; returns {3,4,5}
{ x*x: x <- {1,2,3,4,5}}; returns {1,4,9,16,25}
It is possible to have two generators, in which case an example is:
{ x+y: x <- {1,2}, y <- {3,4}} returns {4,5,6}
Only three elements returned because two additions (1+4) and (2+3) yield duplicate values.
Maps are also enumerated by delimiting their elements with curly brackets. (Formally, maps are sets of ordered pairs.) Maps are created using map construction similar to that of sets. The syntax of maps is shown in Example 3. Note that the first and second elements of each ordered pair in this example are separated by the mapping symbol ->.
m = {1->2,3->4,5->6};
The domain of a map is obtained by forming a set composed of all the first elements of the ordered pairs. Returning to Example 3, dom m returns the set {1,3,5}. Likewise, the range of a map is obtained by forming a set composed of all the second elements of the ordered pairs (rng m returns the set {2,4,6}).
A single-valued map must have all its first elements unique. Given a domain element, we can obtain the corresponding range element much like a table lookup. For example, m[1] returns the value 2 and m[5] returns 6. If a domain element is given that does not exist in the map, a false value will be returned. However, it is possible to supply your own value to be returned in this situation. This is done by supplying an additional argument called the "default error return." For example, m[7, "not found"] returns "not found" instead of False.
Domain restriction (dr) and domain subtraction (ds) produce new maps from a given map by either allowing only certain domain elements in the given map to appear in the result map, or taking away certain domain elements from the given map. The domain elements are given in a set that is the second argument of these operations, as shown in Example 4(a).
(a)
{1->2,3->2,5->6} dr {3,5}; returns {3->2,5->6}
{1->2,3->2,5->6} ds {3,5}; returns {1->2}
(b)
{1->2,3->4} overwr {3->5,4->6}; returns {1->2,3->5,4->6}
The overwrite operation m1 overwr m2 is defined as follows: Each mapping in m1 is included in the result, unless its domain element occurs in the domain of m2. In that case, it is replaced by the mapping from m2. Every mapping in m2 whose domain element does not occur in the domain of m1 is included in the result; see Example 4(b). The map update m[d] = r is an assignment and a special case of overwrite where the second operand (of overwrite) contains a single ordered pair. Assuming that m is equal to {1->2, 3->4}, m[3]=5 is equivalent to m overwr {3->5} and assigns to m the map {1->2,3->5}.
A sequence is a collection of ordered elements which may be selected by their ordinal position (index) in the sequence. The types of the elements are not necessarily the same. A sequence can be enumerated by delimiting its elements by square brackets, [1,2,3,4,5]. This same sequence can be constructed by using the range (not to be confused with the range of a map) notation, [1..5]. Another example of enumeration would be s1 = [1,2,2,3,4].
Concatenation of two sequences is performed using the concatenation operator conc. For example, the statement [1,2,3,4] conc [3,4,5] returns [1,2,3,4,3,4,5]. If s is equal to [3,4,5], then an element of the sequence can be selected using its index in the sequence. For example, s[1] returns 3, s[3] returns 5, s[4] returns False, and s[4,0] returns 0.
Other selection operators on sequences are hd, tl, last, and butlast. The first element of the sequence is returned by hd; tl returns a sequence consisting of every element but the first; last returns a sequence consisting of only the last element; and butlast returns a sequence consisting of every element but the last. Proxy also provides a general way of constructing sequences analogous to set construction. The expression expr in Example 5(a) is evaluated to yield a sequence. The values of the sequence are successively assigned to x, and a new sequence is formed from elements obtained by applying the function f to the successive values of x that satisfy pred(x); see Examples 5(b).
(a) [ f(x): x<- expr ; pred(x) ] (b) [len x: x<-["abc","defg","hijkl"];len x > 3]; returns [4,5]
Strings can be considered as sequences of characters, although a character is not a primitive type in Proxy. Since the string operators are similar to the sequence operators already discussed, we will not bother to give examples.
A struct declaration is essentially a class declaration that defines the names of the components of that class. The declaration in Example 6(a), for instance, defines item to be a struct with the field names partno, code, and quantity. Various items are instantiated by providing the struct name and values for the fields. The only restriction is that a struct component may not be a function.
(a)
struct item {partno, code, quantity;};
(b)
i1.quantity=22; assigns 22 as the new value of the quantity field
Components of structs may be selected using a dot notation similar to records in Pascal and structures in C. Component values may be updated using assignment and dot notation, as shown in Example 6(b).
A class definition is similar to a function definition except that the class name is preceded by the class keyword. Also, the body of the definition consists of a collection of function definitions (called "methods"). Contrary to C++, Proxy classes may only contain functions. Listing One (page 90) shows a FIFO queue, where the state component rep is declared as a local variable in the class header, and the initialization of this component is performed in a function with the same name as the class name. This function is called a "constructor" in C++ and is automatically invoked when the class is instantiated. If, when the class is instantiated, the user neglects to define the queue constructor, a diagnostic is triggered.
The function definitions may optionally be preceded by the public: keyword to indicate that they are exported or made visible outside the class. There are cases when one wants to define functions that are private. In this situation, the keywords private: and public: are used (in that order). Listing Two (page 90) gives an example of a priority queue.
The software-development cycle usually starts with an unambiguous, complete, and consistent requirements statement and the development of a proper interface specification and module decomposition. In this process, it's necessary to execute some representation of the formalized requirements to have some confidence that the requirements are correct. In addition, experience with the module-decomposition process tells us that it's difficult to get the decomposition right without elaborating some of the inner structure. (Conversely, it's hard to go too far with the details of inner structure without settling on the decomposition.) The conclusion is that an iterative process is called for with prototyping at a high level and implementation details suppressed.
To see how Proxy might be used in a prototyping session, consider the problem (adapted from Hekmatpour and Ince) of developing a tool to record the relationships between the modules of a software system. The requirements may be stated informally as consisting of the following routines: Add a module to the system, delete a module from the system, list what modules a given module may use, list what modules may use a given module, and list all recursive modules.
We follow the "me too" paradigm (see Alexander and Jones) for prototyping an application in three steps. The model step identifies the entities and associated operations of an application. In this case, we select an entity called "cross usage" (xu). This entity can be thought of as a set of pairs, where each pair consists of a module and the set of modules it may use. The operations are add, delete, uses, used_by, and rec_mod (recursive modules). The specification step implements the entities and operations in terms of sets, maps, sequences, and so on. We will represent xu as a map from modules to sets of modules. Each module is represented by a string. The validation step is where the operations are executed to determine if the model and implementation are appropriate. The three steps are iterated as necessary until a satisfactory design is obtained.
Figure 2 shows a module-structure diagram for a given software system. Listing Three shows the specification step of the paradigm in terms of the global state xu. The add_mod operation simply adds a module and the set of modules it uses by using map update. The effect of the del_mod operation is that all occurrences of the deleted module will be removed from the range elements of the map and the entry for the module itself will be removed from the map.
The uses and used_by operations are straightforward. Finally, rec_mod is defined in terms of an auxiliary function, reaches, which returns True if a module can reach another module through a sequence of one or more calls.
Listing Four shows the validation step of the paradigm. After initializing the database with calls to add_mod, the resulting value of xu is shown. Calls are then made to the routines uses, used_by, and rec_mod. Finally, after calling del_mod, the new value of xu is shown.
The Proxy interpreter, together with documentation and examples, is available electronically; see "Availability," page 5. I'm also developing an extension, Concurrent Proxy, that will allow modeling of concurrent and distributed software, and direct execution of data-flow modules. Contact me directly for more information on this package.
Abelson, H. and G.J. Sussman. Structure and Interpretation of Computer Programs. Cambridge, MA: MIT Press, 1985.
Alexander, H. and V. Jones. Software Design and Prototyping using me too. Englewood Cliffs, NJ: Prentice-Hall, 1990.
Hekmatpour, S. and D. Ince. Software Prototyping, Formal Methods and VDM. Reading, MA: Addison-Wesley, 1988.
_PROXY: A SCHEME-BASED PROTOTYPING LANGUAGE_ by Burt Leavenworth[LISTING ONE]
class queue(;rep) {
queue() {rep=[];}
enqueue(x) {rep=rep conc [x];}
dequeue(;x) {x=hd rep;
rep=tl rep;
return x;}
empty() {return rep==[];}};
[LISTING TWO]
class pqueue(;rep) {
pqueue() {rep=[];}
private: insrt(x,y) {if(y == []) {rep = [x]; return rep;} else
if(x < hd y) {rep = [x] conc y;return rep;} else
{rep = [hd y] conc insrt(x,tl y);
return rep;}}
public: insert(x) {rep = insrt(x,rep); return rep;}
remove(;x) { if(rep == []) return "queue empty";
x = hd rep; rep = tl rep; return x;} };
[LISTING THREE]
add_mod(m,ms) {xu[m]=ms;};
del_mod(m) {xu= {x->xu[x] diff {m}:x <- (dom xu diff {m})};};
uses(m) {return xu[m];};
used_by(m) {return {ms:ms<-dom xu;m in xu[ms]};};
rec_mod() {return {m:m<-dom xu;reaches(m,m)};};
reaches(m1,m2) {return ((m2 in xu[m1])||(exists m in xu[m1];reaches(m,m2)));};
[LISTING FOUR]
add_mod("mod2",{"mod4","mod5","mod2"});
add_mod("mod3",{"mod5"});
add_mod("mod4",{"mod1","mod2"});
add_mod("mod5",{});
add_mod("mod1",{"mod2","mod3"});
xu = {"mod2"->{"mod4","mod5","mod2"},"mod3"->{"mod5"},
"mod4"->{"mod1","mod2"},"mod5"->{},"mod1"->{"mod2","mod3"}}
uses("mod1") returns {"mod2","mod3"}
used_by("mod2") returns {"mod2","mod4","mod1"}
rec_mod() returns {"mod2","mod4","mod1"}
del_mod("mod3");
xu = {"mod2"->{"mod4","mod5","mod2"},"mod4"->{"mod1","mod2"},
"mod5"->{},"mod1"->{"mod2"}}
Example 1. A general form for constructing sets.
{ f(x): x<- expr ; pred(x) }
Example 2. General method for constructing sets.
{ x: x<- {1,2,3,4,5}}; returns {1,2,3,4,5}
{ x: x <- {1,2,3,4,5};x>2}; returns {3,4,5}
{ x*x: x <- {1,2,3,4,5}}; returns {1,4,9,16,25}
It is possible to have two generators in which case an example is:
{ x+y: x <- {1,2}, y <- {3,4}} returns {4,5,6}
Only three elements are returned because two additions (1+4) and (2+3)
yield duplicate values.
Example 3: Syntax for using maps.
m = {1->2,3->4,5->6};
Example 4: (a) Domain restriction and subtraction; (b) using the
overwrite operator
(a)
{1->2,3->2,5->6} dr {3,5}; returns {3->2,5->6}
{1->2,3->2,5->6} ds {3,5}; returns {1->2}
(b)
{1->2,3->4} overwr {3->5,4->6}; returns {1->2,3->5,4->6}
Example 5a. General form for constructing a sequence; b)
constructing the sequence [4,5].
a)
[ f(x): x<- expr ; pred(x) ]
b)
[len x: x<-["abc","defg","hijkl"];len x > 3]; returns [4,5]
Example 6: (a) Syntax for the struct declaration; (b) Assigning
values to fileds in a struct
(a)
struct item {partno, code, quantity;};
(b)
i1.quantity=22; assigns 22 as the new value of the quantity field.
Copyright © 1993, Dr. Dobb's Journal