{'fraction_non_alphanumeric': 0.023097112860892388, 'fraction_numerical': 0.0010498687664041995, 'mean_word_length': 5.108974358974359, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Implementing Substructural Logical Frameworks

A key component in proof assistant software is the meta-language used to encode the objects that are being reasoned about. Such a meta-language is called a logical framework. Several different logical frameworks exist; some only provide the most basic encoding of abstract syntax data, while others support powerful representation methodologies and concepts such as judgments-as-types and higher-order abstract syntax, e.g. the logical framework LF. The direct support for high-level concepts in the logical framework allows for rapid prototyping of new logics, type systems, and semantics. It also eases the development of theorems when the key concepts are directly supported. A concept, which is becoming increasingly important, is resources, but so far resources have not been supported very well by existing logical frameworks. In this thesis I develop the theoretical infrastructure required to implement — and give an implementation of — a new logical framework that extends LF with the concepts of both linear resources, which must be used exactly once, and affine resources, which can be used at most once. I take a slightly revised version of CLF [CPWW02a] as the starting point for my logical framework. I develop an explicit substitution calculus with linear and affine types, which I use as the foundation in my implementation of CLF called Celf. In this setting I prove strong normalization, type preservation, and confluence for a context-split-oblivious reduction semantics. I define the pattern fragment for the higher-order unification problem in linear and affine type theory and give a deterministic algorithm that computes most general unifiers on this fragment. I also extend this algorithm to the linear-changing pattern fragment and use this to implement the unification algorithm in Celf. Finally, I describe the Celf implementation.