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

Moscow: Center “JurInfoR”, 2003. — 347 p.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 a graduate course on theoretical computer science. The book introduces a reader to the conceptual framework for thinking about computations with the objects. 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 the instructor.Preface of the editors of the series.
Special Preface.
The spectrum of problems.Preliminaries.
The spectrum of ideas.
The 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.
The notion of a type.
Combinatory terms.
-terms.
Tasks.
The basis I, K, S.
Theoretical background.
Tasks.
Exercises.
The basis I, B, C, S.
Theoretical background.
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.
The 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.
The 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 laziness.
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.Practical work.
Dissertations.