Applicative Computational Systems Project Leade

V.E. Wolfengagen Combinatory Logic in Programming Library “JurInfoR” Founded in 1994 Series: Computer Science and Information Technologies Project: Applicative Computational Systems Project Leader, Dr. L.Yu. Ismailova Published on the occasion of 60th anniversary of Moscow Engineering Physics Institute Institute for Contemporary Education “JurInfoR-MSU” Department of Advanced Computer Studies and Information Technologies V.E. Wolfengagen COMBINATORY LOGIC in PROGRAMMING Computations with objects through examples and exercises 2nd edition Moscow • “Center JurInfoR” Ltd. • 2003 LBC 32.97 UDC 004 B721 Library of “JurInfoR” Founded in 1994 Series: Computer Science and Information Technologies V.E. Wolfengagen Combinatory logic in programming. Computations with ob-jects through examples and exercises. — 2-nd ed. — Moscow.: Center “JurInfoR”, 2003. — X+337 p. ISBN 5-89158-101-9 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 think-ing about computations with the objects. The several areas of the-oretical 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. ISBN 5-89158-101-9 V.E. Wolfengagen, 1987–2003 Center “JurInfoR”, 1997–2003 Center “JurInfoR” Institute for Contemporary Education “JurInfoR-MSU” Fax: +7 (095) 956-25-12. E-mail: vew@jmsuice.msk.ru Contents Preface of the editors of the series 1 Special Preface 3 The spectrum of problems 5 Preface to the first edition 7 Preface to the second edition 12 Introduction 18 1 Preliminaries 27 1.1 The spectrum of ideas . . . . . . . . . . . . . . . . . 29 1.2 Layout of a chapter . . . . . . . . . . . . . . . . . . . 30 1.3 State-of-the-art in an area . . . . . . . . . . . . . . . 32 1.4 Typical task . . . . . . . . . . . . . . . . . . . . . . . 35 1.5 Variants of task . . . . . . . . . . . . . . . . . . . . . 37 1.6 A recommended order of solving the tasks . . . . . . . 44 2 Derivation of Object 45 2.1 Principle of combinatory completeness . . . . . . . . 46 2.1.1 Combinatory characteristic . . . . . . . . . . 46 2.1.2 Systems of concepts . . . . . . . . . . . . . . 47 V ... - tailieumienphi.vn