Practical Aspects of Declarative Languages: First International Workshop, PADL'99, San Antonio, Texas, USA, January 18-19, 1999, Proceedings (Lecture Notes in Computer Science (1551))

Declarative languages have traditionally been regarded by the mainstream c- puting community as too impractical to be put to practical use. At the same time, traditionalconferencesdevotedto declarativelanguagesdo not haveissues related to practice as their central focus. Thus, there are few forums devoted to discussion of practical aspects and implications of newly discovered results and techniques related to declarative languages. The goal of the First International Workshop on Practical Aspects of Declarative Languages (PADL) is to bring together researchers,practitioners and implementors of declarative languages to discuss practical issues and practical implications of their research results. The workshop was held in San Antonio, Texas, during January 18-19, 1999. This volume contains its proceedings. Fifty three papers were submitted in response to the call for papers. These papers were written by authors belonging to twenty one countries from six c- tinents. Each paper was assigned to at least two referees for reviewing. Twenty four papers were nally selected for presentation at the workshop. Many good papers could not be included due to the limited duration of the workshop. The workshop included invited talks by Mark Hayden of DEC/Compaq Systems - search Center, speaking on \Experiences Building Distributed Systems in ML," and Mark Wallace of Imperial College Center for Planning And Resource C- trol (IC-PARC), speaking on \ECLiPSe: Declarative Specic ation and Scalable Implementation. Practical Aspects of Declarative Languages Preface Table of Contents Automated Benchmarking of Functional Data Structures Motivation Modelling Datatype Usage Benchmark Generation DUG Generation DUG Evaluation An Example of a Benchmarking Experiment Aim Method Results Comparing Auburn with Manual Related Work Conclusions and Future Work References NP-SPEC: An Executable Specification Language for Solving All Problems in NP Introduction Syntax and Semantics of {sc datalog}$^{CIRC}${} Syntax of {sc datalog}$^{CIRC}$ Semantics of {sc datalog}$^{CIRC}$ Computational Properties of {sc datalog}$^{CIRC}$ The Specification Language {sc np-spec}{} Syntax of {sc np-spec}: Basics Extensions of {sc np-spec}: Tailoring Predicates The {sc np-spec}{} Prototype Specification Examples Integer Knapsack Traveling Salesman Considerations on Performance Related Work Conclusions and Future Work References Prototyping a Requirements Specification through an Automatically Generated Concurrent Logic Program Introduction OASIS OASIS Expressed in Dynamic Logic An Execution Model for OASIS Concurrent Logic Programming and OASIS Objects and Classes in Concurrent Logic Programming Object Behavior Inter-object Communication A Graphical Animation Environment Conclusions References Multi-agent Systems Development as a Software Engineering Enterprise Introduction A Framework for MAS Development Prototype Realization The textsf {PRS} Architecture Executable Specifications in ${cal E}_{hhf}$ LLP Specification of a textsf {PRS} Agent LP Prototyping of a textsf {PRS} Agent Comparison and Future Work References From Functional Animation to Sprite-Based Display Introduction Animation Data Types A Temporal Sprite Engine Sprites and Sprite Trees Interpretation of Sprite Trees From Abstract Animations to Sprite Trees Solid Images Rendered Images Overlays Space Transformation Conditional Animation State and Concurrent Updating Conclusions References Beyond Pretty-Printing: Galley Concepts in Document Formatting Combinators Introduction and RelatedWork Overview of Document Formatting Combinators A Simple Document Format Implementation Extensions Concluding Remarks References Lambda in Motion: Controlling Robots with Haskell Introduction The Problem Domain Frob and Functional Reactive Programming A Wall Follower More Abstractions A Task Monad Fusion Implementing Frob Experience Related Work Conclusions Acknowledgements References CHAT: The Copy-Hybrid Approach to Tabling Introduction Notation and Terminology The Anatomy of CHAT Freezing the Heap without a Heap Freeze Register Freezing the Local Stack without EF The Choice Point Stack and the Trail More Consumers and Change of Leader: A More Incremental CHAT Reinstalling Consumers Releasing Frozen Space and the CHAT Areas upon Completion Handling of Negation in CHAT Best and Worst Cases The Worst Case for CHAT A Best Case for CHAT A Plethora of Implementations More Insight Tests A Benchmark Set Dominated by Tabled Execution A More Realistic Mix of Tabled and Prolog Execution Conclusion Acknowledgements References The Influence of Architectural Parameters on the Performance of Parallel Logic Programming Systems Introduction Methodology Andorra-I Multiprocessor Simulation Applications Read Misses Categorisation Results and Analysis Varying Cache Block Sizes Varying Cache Sizes Varying Network Bandwidth Varying Write Buffer Sizes Summary Results Conclusions Acknowledgments References Or-Parallelism within Tabling Introduction Tabling Concepts and the SLG-WAM Parallel Execution of Tabled Programs Extending YapOr to Support Tabling The Flow of Control Conclusions References Mnesia ­- A Distributed Robust DBMS for Telecommunications Applications Introduction A Brief Overview of Mnesia DBMS Feature Discussion Complex Values Data Format and Address Space Fault Tolerance Distribution and Location Transparency Transactions and ACID The Ability to Bypass the Transaction Manager Queries Schema Alteration Some Implementation Aspects Performance Discussion Conclusions References An AQUA-Based Intermediate Language for Evaluating an Active Deductive Object-Oriented Language Introduction CDOL and ADOOD Architecture Overview of AQUA Intermediate Language Summary and Future Work Acknowledgements References Implementing a Declarative String Query Language with String Restructuring Introduction Overall Architecture Language Description System Architecture Compilation of AQL Forming and Representing Automata Analyzing the Safety of Automata Execution of AQL The Depth-First Search Engine The Production of New Strings Eliminating Duplicate Answers Performance Evaluation Conclusions References Client-Side Web Scripting with HaskellScript Introduction Minuscule Introduction to Haskell Nervous Text The HTML Object Model Properties Methods Events The IWindow Object Example: Scrolling Status Bar The Document Object The HTMLElement and Style Objects ActiveX Scripting, the Enabling Technology Conclusions Acknowledgments References MCORBA: A CORBA Binding for Mercury Introduction Overview of Mercury Mercury Binding for CORBA The Forwards Interface: Mercury Calls CORBA The Backwards Interface: CORBA Calls Mercury Other Features of CORBA Implementation The Forwards Interface: Mercury Uses CORBA Components The Backwards Interface: Mercury as a CORBA Component Conclusions and Further Work References Dead Code Elimination through Dependent Types Introduction Preliminaries Constraint Domains The Language ${rm ML}_0^{Pi }(C)$ Operational Equivalence Dead Code Elimination An Example Formalization Examples The Nth Function An Evaluator for the Call-by-Value $lambda $-Calculus Other Examples Related Work and Conclusion References Multiple Specialization of WAM Code Introduction Abstract Interpretation and Abstract Compilation Unfolding WAM Code Propagation of Information for Inter-procedural Specialization Creation of Specialized Predicates Some Problems with Our Algorithm From WAM Unfolded Code Back to Prolog WAM Instructions Implementation Generating C Code Specializing the Execution Model Performance Evaluation Conclusions References A Flexible Framework for Dynamic and Static Slicing of Logic Programs Introduction Program Slicing Criteria for Program Slicing Logic Program Slicing Why Slicing of Logic Programs Is Difficult A Framework for Slicing Logic Programs Criteria for Logic Program Slicing Mode-Annotated Logic Programs Concrete and Abstract Mode-Annotated Programs Term Dependence Graph Unique Term Identification: Term Labeling Detecting Potential Changes via Modes Data Flow between Terms Control Flow Information Side Effects, Data-, and Control Flow Relevance of Argument Positions An Algorithm for Logic Program Slicing Conclusions and Directions of Research References Applying Logic Programming to Derive Novel Functional Information of Genomes Introduction Background Genome Related Background Sequence Comparison Techniques Functional Genomics Related Concepts A Scheme to Identify Putative Orthologs and Gene-Groups Implementing Stages I, II, and III Stage 1: Extracting Genome Information from Genbank Stage II: Identifying Homologs by BLAST Comparisons Stage III: Aligning Homolog-Pairs Identification of Homologous Gene-Groups Modeling Genome Comparison as a Bipartite Graph Matching Problem Identifying Islands of Clustered Edges for Homologous Gene-Groups Implementing the Algorithm Stage 1: Extracting Genome Information from Genbank Identification of Putative Orthologs Related Works Future Works and Conclusion Acknowledgements References An Application of Action Theory to the Space Shuttle Introduction Syntax and Semantics of ${cal L}_0$ Action Description Language ${cal A}_0$ Query Description Language ${cal Q}_0$ Translation to Logic Programming Domain Independent Axioms Correctness of Domain Independent Axioms The RCS Domain The Propositions of the RCS Domain Initial Situations Soundness and Completeness Usage Results Conclusions Acknowledgments References Developing a Declarative Rule Language for Applications in Product Configuration Introduction Product Configuration Domain Configuration Rule Language Relationship to Logic Programming Semantics Complexity Issues Relation to Constraint Satisfaction Mapping Constraint Formalisms to $@mathbf {CRL}$ Expressiveness of $@mathbf {CRL}$ vs. CSP Implementation Previous Work on Product Configuration Conclusions and Future Work Acknowledgements. References University Timetabling Using Constraint Logic Programming Introduction Problem Description Constraint Logic Programming Problem Representation Search Methods Implementation and Results Conclusions and Further Work References Constraint-Based Resource Allocation and Scheduling in Steel Manufacturing Introduction The Ingots Rolling Works Outline Modeling the Problem Problem Structure Problem Parameters Problem Variables Objective Function Problem Constraints Algorithms Shop Order Assignment Furnace Assignment and Ingot Scheduling The Application Conclusions Acknowledgements References Using Constraints in Local Proofs for CLP Debugging Introduction Form of Assertions Syntax and Meaning of Assertions Conditions Allowed in Assertions Static Proof Program Verification Checking Conditions Abstractions (In)completenessof the Solver Full Example Run-Time Checking Conclusion References A Return to Elegance: The Reapplication of Declarative Notation to Software Design An Evolution of Programming The State of Declarative Programming What Can Be Learned from Object-Orientation? A Possible Future for Declarative Programming Conclusion References ECLiPSe: Declarative Specification and Scaleable Implementation Author Index This Book Constitutes The Refereed Proceedings Of The First International Workshop On Practical Aspects Of Declarative Languages, Padl'99, Held In San Antonio, Texas, Usa In January 1999. The 24 Revised Full Papers Presented Were Carefully Reviewed And Selected From A Total Of 53 Submissions; Also Included Are Abstracts Of Two Invited Talks. The Papers Are Organized In Topical Sections On Software Engineering, Innovative Applications, Implementation, Declarative Query Processing, Systems Applications, Analysis, Constraint Programming, And Declarative Languages And Software Engineering. Software Engineering -- Automated Benchmarking Of Functional Data Structures -- Np-spec: An Executable Specification Language For Solving All Problems In Np -- Prototyping A Requirements Specification Through An Automatically Generated Concurrent Logic Program -- Multi-agent Systems Development As A Software Engineering Enterprise -- Innovative Applications I -- From Functional Animation To Sprite-based Display -- Beyond Pretty-printing: Galley Concepts In Document Formatting Combinators -- Lambda In Motion: Controlling Robots With Haskell -- Implementation -- Chat: The Copy-hybrid Approach To Tabling -- The Influence Of Architectural Parameters On The Performance Of Parallel Logic Programming Systems -- Or-parallelism Within Tabling -- Declarative Query Processing -- Mnesia — A Distributed Robust Dbms For Telecommunications Applications -- An Aqua-based Intermediate Language For Evaluating An Active Deductive Object-oriented Language -- Implementing A Declarative String Query Language With String Restructuring -- Systems Applications -- Client-side Web Scripting With Haskellscript -- Mcorba: A Corba Binding For Mercury -- Analysis -- Dead Code Elimination Through Dependent Types -- Multiple Specialization Of Wam Code -- A Flexible Framework For Dynamic And Static Slicing Of Logic Programs -- Innovative Applications Ii -- Applying Logic Programming To Derive Novel Functional Information Of Genomes -- An Application Of Action Theory To The Space Shuttle -- Developing A Declarative Rule Language For Applications In Product Configuration -- Constraint Programming -- University Timetabling Using Constraint Logic Programming -- Constraint-based Resource Allocation And Scheduling In Steel Manufacturing -- Using Constraints In Local Proofs For Clp Debugging -- Declarative Languages And Software Engineering (invited) -- A Return To Elegance: The Reapplication Of Declarative Notation To Software Design -- Eclipse: Declarative Specification And Scaleable Implementation. Gopal Gupta (ed.). Includes Bibliographical References And Index. Declarative languages have traditionally been regarded by the mainstream c- puting community as too impractical to be put to practical use. At the same time, traditionalconferencesdevotedto declarativelanguagesdo not haveissues related to practice as their central focus. Thus, there are few forums devoted to discussion of practical aspects and implications of newly discovered results and techniques related to declarative languages. The goal of the First International Workshop on Practical Aspects of Declarative Languages (PADL) is to bring together researchers, practitioners and implementors of declarative languages to discuss practical issues and practical implications of their research results. The workshop was held in San Antonio, Texas, during January 18-19, 1999. This volume contains its proceedings. Fifty three papers were submitted in response to the call for papers. These papers were written by authors belonging to twenty one countries from six c- tinents. Each paper was assigned to at least two referees for reviewing. Twenty four papers were nally selected for presentation at the workshop. Many good papers could not be included due to the limited duration of the workshop. The workshop included invited talks by Mark Hayden of DEC/Compaq Systems - search Center, speaking on \Experiences Building Distributed Systems in ML," and Mark Wallace of Imperial College Center for Planning And Resource C- trol (IC-PARC), speaking on \ECLiPSe: Declarative Specic ation and Scalable Implementation