Back to search

University of British Columbia

Redex-plus : a metanotation for programming languages

Abstract

dc:description

When defining the syntax and semantics of programming languages, computer scientists often use some kind of computer science metanotations. These metanotations are often informal or under-defined: human readers can understand them intuitively, but they are unsuitable for use in rigorous formal proofs. The aim of this project is to develop a tool that bridges the gap between the intuitive metanotations for defining programming languages, and proof assistant languages in which properties of the languages defined can be formally proven. In this thesis, I present Redex-Plus, an implementation of a computer science metanotation based on the Racket language Redex, which is used to define programming language models. Redex-Plus is a compiler that translates language models defined in the Redex language to corresponding definitions in various proof assistant languages. Redex-Plus also generates boilerplate such as binding operations, saving the users from the tedious job of writing boilerplate by hand. Redex-Plus supports Coq, Agda, SMT-LIB, and Beluga as translation targets; it can faithfully translate language models with multiple types of bound variables; and it gives users the choice between multiple ways to represent variable binding when using the Coq or Agda targets. I evaluate Redex-Plus by formalizing a variant of Simply Typed Lambda Calculus and proving some important properties of the language model in both Coq and Agda, and by formalizing a variant of System F and attempting to prove the same properties in Coq. The source code repository of Redex-Plus is publicly available at https://gitlab.com/xujunfeng/redex-plus , and on Zenodo.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Xu, Junfeng
Contributors dc:contributor
  • Bowman, William J. (Professor of computer science)

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/85550

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Xu, Junfeng. Redex-plus : a metanotation for programming languages. master's thesis, University of British Columbia, 2023. http://hdl.handle.net/2429/85550