This book provides foundations for software specification and formal software development from the perspective of work on algebraic specification, concentrating on developing basic concepts and studying their fundamental properties. These foundations are built on a solid mathematical basis, using elements of universal algebra, category theory and logic, and this mathematical toolbox provides a convenient language for precisely formulating the concepts involved in software specification and development. Once formally defined, these notions become subject to mathematical investigation, and this interplay between mathematics and software engineering yields results that are mathematically interesting, conceptually revealing, and practically useful. The theory presented by the authors has its origins in work on algebraic specifications that started in the early 1970s, and their treatment is comprehensive. This book contains five kinds of material: the requisite mathematicalfoundations; traditional algebraic specifications; elements of the theory of institutions; formal specification and development; and proof methods. While the book is self-contained, mathematical maturity and familiarity with the problems of software engineering is required; and in the examples that directly relate to programming, the authors assume acquaintance with the concepts of functional programming. The book will be of value to researchers and advanced graduate students in the areas of programming and theoretical computer science.
GATlab: Modeling and Programming with Generalized Algebraic Theories
Categories and categorical structures are increasingly recognized as useful abstractions for modeling in science and engineering. To uniformly implement category-theoretic mathematical models in software, we introduce GATlab, a domain-specific language for algebraic specification embedded in a technical programming language. GATlab is based on generalized algebraic theories (GATs), a logical system extending algebraic theories with dependent types so as to encompass category theory. Using GATlab, the programmer can specify generalized algebraic theories and their models, including both free models, based on symbolic expressions, and computational models, defined by arbitrary code in the host language. Moreover, the programmer can define maps between theories and use them to declaratively migrate models of one theory to models of another. In short, GATlab aims to provide a unified environment for both computer algebra and software interface design with generalized algebraic theories. In this paper, we describe the design, implementation, and applications of GATlab.
Programming Language Foundations in Agda – Table of Contents
This book is an introduction to programming language theory using the proof assistant Agda.
Practical Foundations for Programming Languages
Functional programming with bananas, lenses, envelopes and barbed wire
We develop a calculus for lazy functional programming based on recursion operators associated with data type definitions. For these operators we derive various algebraic laws that are useful in deriving and manipulating programs. We shall show that all example functions in Bird and Wadler's “Introduction to Functional Programming” can be expressed using these operators.
Types and Programming Languages
A type system is a syntactic method for automatically checking the absence of certain erroneous behaviors by classifying program phrases according to the kinds of values they compute. The study of type systems--and of programming languages from a type-theoretic perspective -- -has important applications in software engineering, language design, high-performance compilers, and security. This text provides a comprehensive introduction both to type systems in computer science and to the basic theory of programming languages. The approach is pragmatic and operational; each new concept is motivated by programming examples and the more theoretical sections are driven by the needs of implementations. Each chapter is accompanied by numerous exercises and solutions, as well as a running implementation, available via the Web. Dependencies between chapters are explicitly identified, allowing readers to choose a variety of paths through the material. The core topics include the untyped lambda-calculus, simple type systems, type reconstruction, universal and existential polymorphism, subtyping, bounded quantification, recursive types, kinds, and type operators. Extended case studies develop a variety of approaches to modeling the features of object-oriented languages.
Algebra of programming
Algebra of programming by Bird, Richard, 1997, Prentice Hall edition, in English
The semantics of clear, a specification language
This paper gives a semantics for the Clear language for specifying problems and programs, described by Burstall and Goguen in 1977. A blend of denotational semantics with categorical ideas is used.
Principal type-schemes for functional programs | Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages
As part of the Digital Library's transition to Open Access, new features for researchers are available in the Premium Edition. Click here to learn more.
Category Theory for Programmers: The Preface
Table of Contents Part One Category: The Essence of Composition Types and Functions Categories Great and Small Kleisli Categories Products and Coproducts Simple Algebraic Data Types Functors Functo…
Algebraic data integration
In this paper, we develop an algebraic approach to data integration by combining techniques from functional programming, category theory, and database theory. In our formalism, database schemas and instances are algebraic (multi-sorted equational) theories of a certain form. Schemas denote categories, and instances denote their initial (term) algebras. The instances on a schema S form a category, S–Inst, and a morphism of schemas F : S → T induces three adjoint data migration functors: ΣF : S–Inst → T–Inst, defined by substitution along F, which has a right adjoint ΔF : T–Inst → S–Inst, which in turn has a right adjoint ΠF : S–Inst → T–Inst. We present a query language based on for/where/return syntax where each query denotes a sequence of data migration functors; a pushout-based design pattern for performing data integration using our formalism; and describe the implementation of our formalism in a tool we call AQL (Algebraic Query Language).
When Does a Specification Become a Program? · The Phoenix Architecture
A spec can contain prose, tests, schemas, formal models, even executable code. The useful boundary is not the syntax but, rather, what survives: if you throw the implementation away, what has to remain so you can build the next one?
Integrating functional and imperative programming | Proceedings of the 1986 ACM conference on LISP and functional programming
We present a new model, based on monads, for performing input/output in a non-strict, purely functional language. It is composable, extensible, efficient, requires no extensions to the type system, and extends smoothly to incorporate mixed-language ...
When Does a Specification Become a Program? - The Phoenix Architecture
A spec can contain prose, tests, schemas, formal models, even executable code. The useful boundary is not the syntax but, rather, what survives: if you throw the implementation away, what has to remain so you can build the next one?
When Does a Specification Become a Program? - The Phoenix Architecture
A spec can contain prose, tests, schemas, formal models, even executable code. The useful boundary is not the syntax but, rather, what survives: if you throw the implementation away, what has to remain so you can build the next one?
OCaml Programming: Correct + Efficient + Beautiful — OCaml Programming: Correct + Efficient + Beautiful
A textbook on functional programming and data structures in OCaml, with an emphasis on semantics and software engineering. This book is the textbook for CS 3110 Data Structures and Functional Programming at Cornell University. A past title of this book was “Functional Programming in OCaml”.