Loading...
Please wait, while we are loading the content...
Similar Documents
Computing Rectangular Dissections - A Case Study in Deriving Functional Programs from Logical Specifications (1996)
| Content Provider | CiteSeerX |
|---|---|
| Author | Padawitz, Peter |
| Abstract | Logical specifications provide an abstract level of programming where programs are given as axioms defining functions and predicates on constructor-based data types. Axiomatic function definitions are transformed into functional programs, predicate definitions are compiled into logic programs. If functions are to be implemented as logic programs, they must be flattened into predicates. In this paper, we exemplify the inverse translation: predicates used as multi-valued, nondeterministic, functions are compiled into streamgenerating functions, which enumerate multiple values. Generate-and-test algorithms, usually implemented as logic programs, can be realized in this way as functional programs. Our case study deals with a configuration problem. Two nondeterministic algorithms that compute rectangular dissections are specified in the functional-logic language of Expander, flattened into Prolog programs, and, alternatively, translated into ML programs, which produce streams of dissections. Besides the compilation of predicates into stream functions the case study illustrates the use of polymorphic types and higher-order functions for accomplishing well-structured and reusable software. |
| File Format | |
| Publisher Date | 1996-01-01 |
| Access Restriction | Open |
| Subject Keyword | Logical Specification Rectangular Dissection Deriving Functional Program Logic Program Functional Program Generate-and-test Algorithm Multiple Value Inverse Translation Predicate Definition Case Study Deal Functional-logic Language Prolog Program Polymorphic Type Constructor-based Data Type Ml Program Reusable Software Nondeterministic Algorithm Higher-order Function Configuration Problem Stream Function Abstract Level Axiomatic Function Definition |
| Content Type | Text |
