Research

39 views

Accumulators: A New Logic Variable Abstractions for Functional Languages

Much attention has been focused by the declarative languages community on combining the functional and logic programming paradigms. In particular, there are many efforts to incorporate logic variables into functional languages. We propose a
of 21

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Tags
Transcript
  Theoretical Computer Science 81 (1991) 201-221 Elsevier 201 Keshav Pingali** Computer Science Department, Cornell University, Ithaca, NY, USA Kattamuri Ekanadham IBM Research, T.J. Watson Research Center, Hawthorne, NY, USA Abstract Pingali, K. and K. Ekanadham, Accumulators: new logic variable languages, Theoretical Computer Science 81 (1991) 201-221. abstractions for functional Much attention has been focused by the declarative languages community on combining the functional and logic programming paradigms. In particular, there are many efforts to incorporate logic variables into functional languages. We propose a generalization of logic variables called accumulators which are eminently suited for incorporation into functional languages. We demon- strate the utility of accumulators by presenting examples which show that accumulators can be used profitably in many scientific applications to enhance storage efficiency and parallelism. zyxwvutsrqponmlkjihg 1. Introduction Declarative languages, such as functional and logic programming languages, have received much attention lately as appropriate vehicles for programming parallel machines. Conventional imperative languages such as FORT N or IV&CAL have sequential operational semantics based on commands that cause side-effects in a global store. These languages can be adapted for parallel machines by extending them with annotations, using which the programmer can request parallel execution in chosen parts of his program. Unfortunately, imperative languages with parallel annotations can exhibit unintended nondeterministic behavior because of races between updating and reading of storage locations. more satisfactory alternative is to make the compiler responsible for finding parallelism. rallelism in imperative * This paper was presented at the Eighth Cortference on Foundations of Software Technology and 7heoretical Computer Science (Pune, 1988) and selected for publication by K.V. Nori. ** Supported by NSF g rant CCR-8702668 and an I 0304-3975/91/$03.50 @ 1991-Elsevier Science Publishers B.V.  202 K. Pingali, K. Ekanadham language programs is severely limited by reuse of storage locations and parallelizing compilers enhance parallelism by eliminating such reuse of storage through transfor- mations such as renaming, scalar expansion etc. [9]. Evidently, the imperative programming model encourages the programmer 90 reuse storage only to have the compiler eliminate the reuse This seems rather pointless-why not begin with a programming model in which storage reuse cannot arise? Declarative languages provide precisely such a model to the programmer. In contrast to imperative languages, declarative languages can be give.. an operational semantics which is naturally parallel since it is based on rewrite rules rather than on updating of a global store. The entire program is considered to be an expression that is rewritten to the answer by successively simplifying subexpressions. Subex- pressions of the program can be rewritten in parallel and a variety of parallel rewriting strategies such as parallel innermost, parallel outermost, dataflow rule etc., have been studied extensively. Moreover, parallelism comes with a guarantee of determinacy-there are a variety of theorems such as the Church-Rosser theorem that guarantee that the final result of the rewriting is independent of the order in which subexpressions are rewritten. Much of the current interest in declarative languages stems from this unique combination of natural parallelism and guaranteed determinacy. One active area of research in declarative languages is combining the functional and logic paradigms [S, 61. Logic languages provide a number of computational features like logic variables and backtracking which are not present in functional languages. Of particular interest to us is the introduction of logic variables into functional languages. In a functional language, an identifier obtains its value as the result of evaluation of a single applicative expression. In contrast, a Z0gic variable in logic programming languages obtains its value incrementally by the intersection of successively applied constraints. The incorporation of logic variables into an otherwise functional language provides the programmer with a powerful tool for writing elegant and efficient programs for problems such as the construction of large arrays in scientific programming [4], owner-coupled sets in database programming [ 111, and the coding of constraint-based algorithms such as Milner’s polymorphic type deduction algorithm. The research reported in this paper arose from our efforts to use logic variables to alleviate the so-called “copying problem” of purely functional data structures [4]. In a pure functional language, a data structure is a value (just like an integer or floating point number) which is produced as the result of evaluating a single applicative expression. This is satisfactory when the data structure is built bottom-up (as lists are): first, the components of the data structure can be constructed, and then these components can be assembicd together to produce the desired data structure. However, this does not work for “flat” data structures, such as arrays and matrices. Constructing large arrays and matrices functionally is difficult because usuallY, there is no uniform rule for computing matrix elemsnts; for example, the computation of oundary elements may be quite different from the computation of  Accumulators: logic variables for functional languages 203 interior elements. In such situations, writing a single applicative expression for defining the entire matrix can be inefficient and the resulting program zyxwvutsrqponmlkjihgfedcb ay be quite obscure [4]. An alternative is to compute the desired matrix as the limit of a sequence of matrices which differ incrementally from each other. Unfortunately, the absence of an update operation in functional languages means that each matrix in this sequence is a different value, and the construction of a matrix of size n x n may involve making zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA 2 copies of the matrix Logic variables provide an elegant solution to this problem because they allow the programmer to define an array incrementally without making intermediate copies. To construct a large matrix, the programmer first allocates a matrix of the desired size, in which each element is an uninitialized logic variable. These logic variables can be bound incrementally in the program, without having fo copy the entire data structure; for example, the array can be passed to two procedures, one of which instantiates variables on the boundary while the other instantiates variables in the interior. In this way, large data structures can be constructed without the copy overhead of functional data structures. This use of logic variables is similar to the use of “difference-lists” in pure logic programming. In Section 2 we examine the notion of logic variables and observe that the means through which they acquire values is unnecessarily limited to term-unification and propose a generalization to other user defined functions. We argue that logic variables should be generalized to enable the programmer to specify any commutative and associative function (such as +, *, m/Ax, min, set insertion, etc.) in place of unification for giving values to logic variables. These generalized logic variables have the flavor of objects in object-oriented languages. As *with any new language construct, there are two questions that must be answered. First, is the extension useful? Second, can it be easily implemented? We believe that both questions can be answered affirmatively for generalized logic variables. They can be used to lower the storage requirements of declarative language programs without any loss of parallelism; in fact, many problems, their use enhances parallelism. Section 3 provides some examples to illustrate that logic variables are very useful for writing standard scientific programs. Section 4 presents a formal operational semantics for a functional language with logic variables and Section 5 briefly discusses some implementation considerations. Section 6 presents our conclusions and suggestions for future work. 2. zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA ogic variables In functional languages, the notion of a “variable” is absent-one only has identifiers that are synonyms for values. An identifier is introduced through a binding that associates it with an expression; the identifier is a synonym for the value of that expression. The programming model does not support manipulation of iden- tifiers. As an example, consider the following definition of a function. The curly braces denote a kt-WC style block whit is a set of local bindings followed by a return expression. Wlien the function pq is invoked with an argument value for N,  204 zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA . Pingali, K. Ekanadharn an applicative interpreter first evaluates the expression p(N). The identifier X is then bound to the resulting value, after which the function 4 is invoked. Thus, an identifier never participates in any operation until it is replaced by a value. zyxwvutsrqponmlkjihgfed pqW)={X=pW) Y=q N,XJz= y+x return 2). This is true even under lazy evaluation. A lazy evaluator delays the evaluation of expressions until they are needed to produce the output of the program In the program shown above, the computation of the values of X and Y would be “delayed” until an attempt was made to evaluate Y + X. At that point, the expressions for Y and X would be evaluated, and the identifiers bound to their values. Under lazy evaluation, the transformation from a name to a value involves two steps: first the name X is replaced by some sort of a descriptor that points to the computation of p(N) and rat er the descriptor is replaced by a computed value. The intermediate form is transparent to the program, because the program can never check whether the value of X has been computed at any point-the interpreter checks this internally and prevents the intermediate form to participate in any operations, except in argument passing. Logic languages extend this behavior even further by introducing variables as “first-class citizens”. A variable in a logic programming language represents a place holder; therefore, it can be introduced in the program without necessarily binding it to a value. Variables are bound to values by unification performed during pattern matching of arguments in a function call. This permits textual separation of the creation of a variable from the specification of a value for it. For example, the following logic program is intended to specify the same function pq: PdN, 2) :- P(N, X), q(N, X, Y), add(Y, X, a. Invoking a goal like pq(5, Z’), binds N to the value 5 and instantiates two new variables X and Y, which are initially undefined. By including appropriate definitions for the functions p and q, it is possible to achieve the expected sequence of events, viz. computing ~(5, X) binds X to some value and computing q( N, X, Y) binds Y to some value and so on. However, logic: programs offer a lot more flexibility than is apparent in the above definitioq of pq- For instance, we can define the functions p and q very differently to create eflects that are not possible to reproduce in a functional language. Consider the clauses P N, XL dN 090). nvoking p( 5, ) returns the unbound variable and invoking q(5, both X and Y to 0. his program illustrates the fact that the behavior  Accumulators: logic variables for functional languages 205 in logic languages is fundamentally different from anything found in functional languages: the direction of flow of information is not determined a priori and the variable can participate in unification any number of times. Note that the values bound by each unification must be consistent. For example, if a. variable is bound to 5, an attempt to unify it with 6 will cause a failure of unification. This enlsures that the program output is determinate, even under parallel evaluation. Operationally, a variable is associated with some storage which undergoes state transitions as depicted in Fig. zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA . The initial state corresponds to the variable being unbound and the final state corresponds to the variable being grounded or completely defined. Actually we should imagine several final states, one for each different constant value that the variable can assume. Figure 1 shows only a prototypical part of the state diagram. A transition is caused by unification. As long as the variable is unified with other unbound variables, the state remains the same. Once it is unified with a constant value, it reaches the final state and its value cannot be changed any more. Further unifications can only reinforce that its value is what was defined. An attempt to unify it with some other value results in failure (that is, an error state) which is denoted by the symbol F. unifi with another undefined variable unify with c unib with d#C * jail Fig. 1. Prototypical state diagram of a scalar variable. How can we introduce logic variables into a functional language? In logic languages, unification is done during pattern matching of arguments in a function instantiation. Since unification may cause a “side-effect” on the state of the variable, we prefer that the side-effect take place through an explicit command rather than implicitly during function calling. Therefore, we use the syntax A = variable( ) to introduce a logic variable and name it zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGF , while the command indicates that the value x is to be unifie ith the variable . These commands can occur wherever a binding can QCC e base functional language. this also fixes the directionality of information flow, by requiring that unification
Advertisement
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks