Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T21:18:08.638Z Has data issue: false hasContentIssue false

A combinatory account of internal structure

Published online by Cambridge University Press:  12 March 2014

Barry Jay
Affiliation:
University of Technology Sydney, School of Software, P.O. Box 123, Broadway, 2007, Australia, E-mail: Barry.Jay@uts.edu.au, E-mail: Thomas.Given-Wilson@uts.edu.au
Thomas Given-Wilson
Affiliation:
University of Technology Sydney, School of Software, P.O. Box 123, Broadway, 2007, Australia, E-mail: Barry.Jay@uts.edu.au, E-mail: Thomas.Given-Wilson@uts.edu.au

Abstract

Traditional combinatory logic uses combinators S and K to represent all Turing-computable functions on natural numbers, but there are Turing-computable functions on the combinators themselves that cannot be so represented, because they access internal structure in ways that S and K cannot. Much of this expressive power is captured by adding a factorisation combinator F. The resulting SF-calculus is structure complete, in that it supports all pattern-matching functions whose patterns are in normal form, including a function that decides structural equality of arbitrary normal forms. A general characterisation of the structure complete, confluent combinatory calculi is given along with some examples. These are able to represent all their Turing-computable functions whose domain is limited to normal forms. The combinator F can be typed using an existential type to represent internal type information.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable