MODCAP(ID:2761/mod005)A language evolved from MADCAP, also by Wells and by Rollo Silver. a simple, moderately extensible, lexically-scoped expression language with functions as first-class objects, retention, unenforced abstract data types, pointer semantics and rendezvous-based concurrency Functions can return multiple values Language based on functions, with assignment and sequencing providing the imperative features, encapsulation and genericity providing the object-oriented features, and the possibility of parallel evaluation catering for the logic non-determinism. Structures: Related languages
References: purpose yet regular with a reasonably small compiler capable of producing efficient target code. It resembles many languages--Lisp, Algol 68, Ada, Smalltalk, Poly (to name a few~--in various particular ways, but is unified by a unique typing system that we believe allows conciliation of the sometimes conflicting design goals of flexibility and efficiency. This report is a working version of one part of the defining document for Modcap. It is intended to be analogous to the Ada Reference Manual or the Pascal Report. An additional part entitled Rationale and Users" Manual for Modcap is in preparation. That part, which will be analogus to Rationale for the Desiqn of Ada or the Pascal Users" Manual, will contain much more in the way of explanatory text and examples. Comments, corrections, and suggested modifications of all kinds are solicited. Of special concern is the level of formality. It is currently felt that there will be no more precise definition short of the compiler written in Modcap and an analogous two-level description of the computational model and interpreter. DOI in SIGPLAN Notices 19(12) December 1984 view details in TOPLAS 7(4) October 1985 view details in ACM Transactions on Programming Languages and Systems 7(3) July 1985 view details in SIGPLAN Notices 20(07) July 1985 (Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments) view details A concurrent algorithm for finding the fewest number of queens needed to "cover" the nxn chessboard, 1<=n<=8, is given here in the Modcap programming language. This algorithm is a straightforward generalization of a good serial algorithm and uses concurrency at two levels: SIMD and MIMD. The Modcap language is well suited for coding this algorithm since it contains primitive operations on sets of natural numbers to express the SIMD parallelism and concurrently evaluable functions (i.e. tasks) to express the MIMD parallelism. The idea of the algorithm ls first to find a good cover that uses few queens and then prove by exhaustive search that this cover, or a better one discovered during the search, is best possible. SIMD parallelism is involved in the set-theoretic operations that are used to calculate coverage of the chessboard during both phases of the algorithm. MIMD parallelism is involved primarily during the exhaustive search phase of the algorithm, wherein various disjoint parts of the search are assigned to independent functions that may be evaluated concurrently. MIMD parallelism is also used during the precalculation of covering sets for queens on each of the nxn squres of the board and of certain transformation indices of squares used to prune redundant branches of the search tree. Extract: Appendix: a Brief Introduction to Modcap Appendix: a Brief Introduction to Modcap Madcap is a block-structured, (multivalued) function-based, expression language. It uses pointer semantics and has an assignment operation that, much like Smelltalk [Go]83] assigns names (i.e. identifiers) to data items of all types. Assignment comes in several forms, using underscored identifiers (.x), e-symbol prefixed identifiers (@y), and the prefix hat symbol (^) to the left (end in some cease to the right) of s multiple-value-returning expression, but uses no infix assignment operator per so. The most important assignment form is the declarative assignment that has one or more underlined identifiers to the left of the expression: x, ~ (a+l, n!); The identifiers are names for newly declared variables within the current "block". They are initialized to the items returned by the expression (in parallel order) and are declared to have the corresponding "type". In the example, x is declared to have the type of a+l and (at run time) is initialized to its value. Similarly, y gets its type and initial run-time value from the expression n!. Once declared, a variable may be reassi@ned a value consistent with its declared type using the prefix @-symbol instead of the underscore: ? x a+2; In both cases the expression on the right meyreturn more items then 9ivan names. These extra items merely remain es part of an accumulating list of items that might: form an argument list for a function call, become part of a structure, or be assigned names at a higher block level. Rn unwanted item can be discarded by using the discerdin 9 assignment denoted by the hat symbol: g uo, ^ n÷m; ¢ quotient & remainder computed; remainder discarded. R conditional oseignment has the names to the right of e test expression (in an if-then-else, uhile-do, or for-do) that produced the items, just inside the consequent (or body): if a falsity of the relation. If true, then this listed value of e is named b for use in the consequent. If falsej the nil is automatically discarded before taking the 'else' branch. R block is any bracketed list of expressions, or the "body" of an alternation or iteration. Indentation is a common form of bracketing used for expression grouping, end is equivalent to the use of parentheses or square brackets. Three important kinds of brackets that moreover delimit litersls of various structured types ere (I) French quotation marks, <<...>>, for function literals; (2) curly brackets, {... }, for set literals ; and (3) angle brackets, < . . . > , for tuple literals. Every Modcap data item is associated with a set of operations celled a spa©e. The associated space is determined by the literal form that is used to originate the |term. Numerals, for instance, are associated with the space containing operations on numbers, while French quoted program segments are associated with the space of function operations. B doto type is a set of date items. Literals produce singleton types. Larger types are produced in various ways [HRR84], one of them using the infix or operation (or equJvalently, alternation) to form the union of the types of its operands (or branches). Types propagate naturally through expressions and become, as indicated above, associated with variables in declarative assignments. Types are not explicitly named in Modcap, but are referenced by literals , variables, and expressions that "have them". Type checking amounts to e test for set-theoretic containment. R type is pure if all of its data items are associated with the same specs. The meaning of every symbolic operator depends on the (pure) type of its left (or only) operand. Thus operator overloading is fundamental to Modcap, much as is message overloading in Smalltalk. Functions are first-class data items in Modcap. There are two important operations on function used in this paper: simple and concurrent function evaluation. Simple function evaluation is denoted with the (infix) juxtaposition operator as in Get'Upper" ¢ S¢o Figure I. where G~t is a library function s and the strin 9 "Upper"~ which names ~ files is its single argument. Formal parameters are indicated with a question mark (?) prefixed to an expression that denotes the expected type(s) of the actual parameters. Formal parameters may appear arbitrarily within expressions of a function literal; they may be named cuith declarative assignments as in IForm (Figure 2), or may be used directly as in the definition of ~tP (Figure 5). The reference manuel [MRM84] describes how functions such as quo or meal can be used in infix notation as in Figure 5. Modcap has unified the concepts of remotely-called "subroutines" with in-line "macros" into the one notion of function. The code specified by e function literal <<...>> may be instantiated statically or dynamically, according to context m in fact the identical function may be instantiated statically in one context and dynamically in another. Many of the functions detailed in the figures are instantiated statically (the operator codes, for example). In fact the only ones that are instantiated dynamically are those which are either evaluated concurrently (the tasks in Canonicals Covert and Former) or are recursive (form). Concurrent function evaluation is denoted by the infix @-operator: (f,g)e() The left operand is the list of functions to be evaluated concurrently and the right operand specifies the possible communication links. (No communicating rendezvous are needed for the algorithm of this paper). If the operation completes normally (i.e. without deadlock), then the concatenated list of results of the individual {unctions followed by a true are returned when all fQnctions have completed their evaluation. If the operation deadlocks, then only folse is returned. It is treated as a deadlock uhen any function "aborts", as in the case of the algorithm of this paper. in SIGPLAN Notices 21(09) September 1986 view details Introduction This author has long felt that the notational mechanisms provided by most programming languages are inadequate, mainly due to the inadequacy of program preparation devices. Language designers have historically let existing hardware dictate the range of notation allowed in languages. Unfortunately, such restricted (and restrictive) notation seems to be spreading, with even less rationale, into pseudolanguages and textbook algorithm descriptions. This paper discusses some of the author's pet peeves regarding common language notations and describes how the Modcap language avoids them. It is worth mentioning that today, unlike twenty gears ago, special hardware is not required. Host standard input and output devices can be programmed to allow the advocated notation. This paper's content is essentially trivial. Modcap - an advanced language with important semantic features such as first-class functions and lattice-theoretic properties of types, but here only its lexical and syntactic features are broached. This paper has four sections -- character sets, identifiers, page formatting, and expressions -- followed by a brief conclusion. This material, while trivial, is not unimportant. Syntax must not get in the way of semantics -- it must allow concise and suggestive expression of the semantics so that programs can be read and understood "smoothly." in SIGPLAN Notices 21(03) March 1986 view details in SIGPLAN Notices 21(03) March 1986 view details in SIGPLAN Notices 21(03) March 1986 view details Resources
|