Combinatory logic in programming. Computations with objects through examples and exercises

Description

The book is intended for computer science students, programmers and professionals who have already got acquainted with the basic courses and background on discrete mathematics. It may be used as a textbook for graduate course on theoretical computer science. The book introduces a reader to the conceptual framework for thinking about computations with the objects. The several areas of theoretical computer science are covered, including the following: type free and typed λ-calculus and combinatory logic with applications, evaluation of expressions, computations in a category. The topics, covered in the book accumulated much experience in teaching these subjects in graduate computer science courses. A rich set of examples and exercises, including solutions, has been prepared to stimulate the self studying and to make easier the job of instructor. Preface of the editors of the series Special Preface The spectrum of problems Preface to the first edition Preface to the second edition Introduction Preliminaries The spectrum of ideas Layout of a chapter State-of-the-art in an area Typical task Variants of task A recommended order of solving the tasks Derivation of Object Principle of combinatory completeness Combinatory characteristic Systems of concepts Combinatory completeness Elementary combinatory logic Deriving main combinators: tasks Historical remark Fixed Point Theoretical background. Abstraction Multiabstraction Local recursion Main tasks Exercises Extensionality Theoretical background Tasks Exercises Numerals Numbers and numerals Combinatory arithmetic Tasks Exercises Typed combinators Notion of a type Combinatory terms -terms Tasks Basis I, K, S Theoretical background Tasks Exercises Basis I, B, C, S Theoretical background A property of being basic Elementary examples Exercises Applications of fixed point combinator Y Fixed point theorem Elements of recursive computations Using the combinator Y Evaluation of a function Exercises Function list1 Theoretical background Tasks Functor-as-object Exercises Isomorphism of c.c.c. and ACS Theoretical background Tasks Currying Theoretical background Operators and functions Comprehension Connection between operators and functions Tasks Exercises Karoubi's shell Theoretical background Tasks Exercises Products and projections Theoretical background Task Product and cartesian closed category Embedding Lisp into ACS Theoretical background A main task Concluding remarks Supercombinators Theoretical background Notion of supercombinator Process of compiling Transformation to supercombinators Eliminating redundant parameters Ordering of the parameters The lambda-lifting with a recursion Execution of the lambda-lifting algorithm Other ways of lambda-lifting Full lazyness Maximal free expressions Lambda-lifting with MFE Fully lazy lambda-lifting with letrec Compound example Task Answers to exercises Lazy implementation Tasks Exercises Permutation of parameters Task Exercises Test Immediate computations Task Exercises Test de Bruijn's encoding Tasks Exercises Abstract machine: CAM Theoretical background CAM structure Instructions Tasks Exercises Optimizing CAM-computations Task Exercises Test Variable objects Models Applicative structure Typed models Partial objects Data object models The main task Elementary types Typed variable objects Computational models Indexed objects Interpretation of evaluating environment Bibliography Index Glossary Practical work Dissertations About the Author