1st Edition

Combinatory Logic Pure, Applied and Typed

By Katalin Bimbó Copyright 2012
    358 Pages 10 B/W Illustrations
    by Chapman & Hall

    Combinatory logic is one of the most versatile areas within logic that is tied to parts of philosophical, mathematical, and computational logic. Functioning as a comprehensive source for current developments of combinatory logic, this book is the only one of its kind to cover results of the last four decades. Using a reader-friendly style, the author presents the most up-to-date research studies. She includes an introduction to combinatory logic before progressing to its central theorems and proofs. The text makes intelligent and well-researched connections between combinatory logic and lambda calculi and presents models and applications to illustrate these connections.

    Elements of combinatory logic
    Objects, combinators and terms
    Various kinds of combinators
    Reductions and combinatory bases
    Main theorems
    Church–Rosser property
    Normal forms and consistency
    Fixed points
    Second fixed point theorem and undecidability
    Recursive functions and arithmetic
    Primitive and partial recursive functions
    First modeling of partial recursive functions in CL
    Second modeling of partial recursive functions in CL
    Undecidability of weak equality
    Connections to l-calculi
    l-calculi: L
    Combinators in L
    Back and forth between CL and L
    (In)equational combinatory logic
    Inequational calculi
    Equational calculi
    Term models
    Operational models
    Encoding functions by numbers
    Models for typed CL
    Relational models
    Dual and symmetric combinatory logics
    Dual combinators
    Symmetric combinators
    Structurally free logics
    Applied combinatory logic
    Illative combinatory logic
    Elimination of bound variables
    Typed combinatory logic
    Simply typed combinatory logic
    Intersection types for combinators
    Elements of combinatory logic
    Main theorems
    Recursive functions and arithmetic
    Connections to l-calculi
    (In)equational combinatory logic
    Dual and symmetric combinatory logic
    Applied combinatory logic
    Typed combinatory logic
    List of Symbols


    Katalin Bimbo is an assistant professor in the Department of Philosophy at the University of Alberta in Edmonton, Canada.

    For beginners, it is a compact introduction, including exercises, to the classical syntactic theory of combinators with some pointers to their models and their relation with λ-calculus. More advanced readers may find in the book much information on the connections between combinators and non-classical and substructural logics that are now a prominent topic in several areas, from philosophical logic to theoretical computer science, information that is mostly scattered through the research literature.

    One of the commendable aspects of the book is its extensive and up-to-date bibliography, which deals with CL and other relevant topics in logic; it will surely aid many readers who may need to brush up on background information in the course of their study.
    —Computing Reviews, 2012