Combinators as presheaves

Abstract

Computer scientists, logicians and other researchers have recently paid renewed attention to the model of computation based on the logic of combinators. We develop a new formalization of the syntax of combinators employing the ‘generic figures’ approach to the categories of presheaves that provides an intuitive and easily interpreted diagrammatic syntax for combinators, one that eschews the need to label proper combinators with variable names. Furthermore, we show that this formal framework provides the possibility of representing choices of operand from among given alternatives at each level of a combinatory term, allowing for a more general type of combinatory expression, which we call a multi-combinator.