This volume describes recent research in graph reduction and related areas of functional and logic programming, as reported at a workshop in 1986. The papers are based on the presentations, and because the final versions were prepared after the workshop, they reflect some of the discussions as well. Some benefits of graph reduction can be found in these papers: - A mathematically elegant denotational semantics - Lazy evaluation, which avoids recomputation and makes programming with infinite data structures (such as streams) possible - A natural tasking model for fine-to-medium grain parallelism. The major topics covered are computational models for graph reduction, implementation of graph reduction on conventional architectures, specialized graph reduction architectures, resource control issues such as control of reduction order and garbage collection, performance modelling and simulation, treatment of arrays, and the relationship of graph reduction to logic programming.
An Architecture for Combinator Graph Reduction examines existing methods of evaluating lazy functional programs using combinator reduction techniques, implementation, and characterization of a means for accomplishing graph reduction on uniprocessors, and analysis of the potential for special-purpose hardware implementations. Comprised of eight chapters, the book begins by providing a background on functional programming languages and existing implementation technology. Subsequent chapters discuss the TIGRE (Threaded Interpretive Graph Reduction Engine) methodology for implementing combinator graph reduction; the TIGRE abstract machine, which is used to implement the graph reduction methodology; the results of performance measurements of TIGRE on a variety of platforms; architectural metrics for TIGRE executing on the MIPS R2000 processor; and the potential for special-purpose hardware to yield further speed improvements. The final chapter summarizes the results of the research, and suggests areas for further investigation. Computer engineers, programmers, and computer scientists will find the book interesting.
In light of research over the last decade on new ways of representing and performing computations, this book provides a timely reexamination of computer organization and computer architecture. It systematically investigates the basic organizational concepts of reduction, data flow, and control flow (or state transition) and their relationship to the underlying programming paradigms. For each of these concepts, Kluge looks at how princip1es of language organization translate into architectures and how architectural features translate into concrete system implementations, comparing them in order to identify their similarities and differences. The focus is primarily on a functional programming paradigm based on a full-fledged operational &-calculus and on its realization by various reduction systems. Kluge first presents a brief outline of the overall configuration of a computing system and of an operating system kernel, introduce elements of the theory of Petrinets as modeling tools for nonsequential systems and processes, and use a simple form of higher-order Petri nets to identify by means of examples the operational and control disciplines that govern the organization of reduction, data flow, and control flow computations. He then introduces the notions of abstract algorithms and of reductions and includes an overview of the theory of the &-calculus. The next five chapters describe the various computing engines that realize the reduction semantics of a full-fledged &-calculus. The remaining chapters provide self-contained investigations of the G-machine, SKI combinator reduction, and the data flow approach for implementing the functional programming paradigm. This is followed by a detailed description of a typical control flow (or von Neumann) machine architecture (a VAX11 system). Properties of these machines are summarized in the concluding chapter, which classifies them according to the semantic models they support.
Available in Paperback Available in eBook editions (PDF format) Institution: Syracuse University (Syracuse, NY, USA) Advisor(s): Prof. Klaus J. Berkling Degree: Ph.D. in Computer and Information Science Year: 1993 Book Information: 248 pages Publisher: Dissertation.com ISBN-10: 1612337570 ISBN-13: 9781612337579 View First 25 pages: (free download) Abstract The operational aspects of Lambda Calculus are studied as a fundamental basis for high-order functional computation. We consider systems having full reduction semantics, i.e., equivalence-preserving transformations of functions. The historic lineage from Eval-Apply to SECD to RTNF/RTLF culminates in the techniques of normal-order graph Head Order Reduction (HOR). By using a scalar mechanism to artificially bind relatively free variables, HOR makes it relatively effortless to reduce expressions beyond weak normal form and to allow expression-level results while exhibiting a well-behaved linear self-modifying code structure. Several variations of HOR are presented and compared to other efficient reducers, with and without sharing, including a conservative breadth-first one which mechanically takes advantage of the inherent, fine-grained parallelism of the head normal form. We include abstract machine and concrete implementations of all the reducers in pure functional code. Benchmarking comparisons are made through a combined time-space efficiency metric. The original results indicate that circa 2010 reduction rates of 10-100 million reductions per second can be achieved in software interpreters and a billion reductions per second can be achieved by a state-of-the art custom VLSI implementation.
This book constitutes the refereed proceedings of the Third International Workshop on Algorithms in Bioinformatics, WABI 2003, held in Budapest, Hungary, in September 2003. The 36 revised full papers presented were carefully reviewed and selected from 78 submissions. The papers are organized in topical sections on comparative genomics, database searching, gene finding and expression, genome mapping, pattern and motif discovery, phylogenetic analysis, polymorphism, protein structure, sequence alignment, and string algorithms.
This book takes a foundational approach to the semantics of probabilistic programming. It elaborates a rigorous Markov chain semantics for the probabilistic typed lambda calculus, which is the typed lambda calculus with recursion plus probabilistic choice. The book starts with a recapitulation of the basic mathematical tools needed throughout the book, in particular Markov chains, graph theory and domain theory, and also explores the topic of inductive definitions. It then defines the syntax and establishes the Markov chain semantics of the probabilistic lambda calculus and, furthermore, both a graph and a tree semantics. Based on that, it investigates the termination behavior of probabilistic programs. It introduces the notions of termination degree, bounded termination and path stoppability and investigates their mutual relationships. Lastly, it defines a denotational semantics of the probabilistic lambda calculus, based on continuous functions over probability distributions as domains. The work mostly appeals to researchers in theoretical computer science focusing on probabilistic programming, randomized algorithms, or programming language theory.
This book defines a logical system called the Protocol-theoretic Logic of Epistemic Norms (PLEN), it develops PLEN into a formal framework for representing and reasoning about epistemic norms, and it shows that PLEN is theoretically interesting and useful with regard to the aims of such a framework. In order to motivate the project, the author defends an account of epistemic norms called epistemic proceduralism. The core of this view is the idea that, in virtue of their indispensable, regulative role in cognitive life, epistemic norms are closely intertwined with procedural rules that restrict epistemic actions, procedures, and processes. The resulting organizing principle of the book is that epistemic norms are protocols for epistemic planning and control. The core of the book is developing PLEN, which is essentially a novel variant of propositional dynamic logic (PDL) distinguished by more or less elaborate revisions of PDL’s syntax and semantics. The syntax encodes the procedural content of epistemic norms by means of the well-known protocol or program constructions of dynamic and epistemic logics. It then provides a novel language of operators on protocols, including a range of unique protocol equivalence relations, syntactic operations on protocols, and various procedural relations among protocols in addition to the standard dynamic (modal) operators of PDL. The semantics of the system then interprets protocol expressions and expressions embedding protocols over a class of directed multigraph-like structures rather than the standard labeled transition systems or modal frames. The intent of the system is to better represent epistemic dynamics, build a logic of protocols atop it, and then show that the resulting logic of protocols is useful as a logical framework for epistemic norms. The resulting theory of epistemic norms centers on notions of norm equivalence derived from theories of process equivalence familiar from the study of dynamic and modal logics. The canonical account of protocol equivalence in PLEN turns out to possess a number of interesting formal features, including satisfaction of important conditions on hyperintensional equivalence, a matter of recently recognized importance in the logic of norms, generally. To show that the system is interesting and useful as a framework for representing and reasoning about epistemic norms, the author applies the logical system to the analysis of epistemic deontic operators, and, partly on the basis of this, establishes representation theorems linking protocols to the action-guiding content of epistemic norms. The protocol-theoretic logic of epistemic norms is then shown to almost immediately validate the main principles of epistemic proceduralism.
