<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
We give a formal treatment of simple type theories, such as the simply-typed $λ$-calculus, using the framework of abstract clones. Abstract clones traditionally describe first-order structures, but by equipping them with additional algebraic structure, one can further axiomatize second-order, variable-binding operators. This provides a syntax-independent representation of simple type theories. We describe multisorted second-order presentations, such as the presentation of the simply-typed $λ$-calculus, and their clone-theoretic algebras; free algebras on clones abstractly describe the syntax of simple type theories quotiented by equations such as $β$- and $η$-equality. We give a construction of free algebras and derive a corresponding induction principle, which facilitates syntax-independent proofs of properties such as adequacy and normalization for simple type theories. Working only with clones avoids some of the complexities inherent in presheaf-based frameworks for abstract syntax.
To appear in the proceedings of FSCD 2021; 16 pages
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Computer Science - Programming Languages, presentations, F.3.2; F.4.1, variable binding, 004, 510, Logic in Computer Science (cs.LO), logical relations, free algebras, second-order abstract syntax, abstract clones, substitution, F.3.2, F.4.1, induction, simple type theories, Programming Languages (cs.PL), ddc: ddc:004
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, Computer Science - Programming Languages, presentations, F.3.2; F.4.1, variable binding, 004, 510, Logic in Computer Science (cs.LO), logical relations, free algebras, second-order abstract syntax, abstract clones, substitution, F.3.2, F.4.1, induction, simple type theories, Programming Languages (cs.PL), ddc: ddc:004
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |