Efficient dynamic type checking of heterogeneous sequences

Authors

Jim Newton

Place

Paris, France

Type

techreport

Projects

Climb

Keywords

Rational languages, typechecking, finite automata

Date

2016-02-22

Abstract

This report provides detailed background of our development of the rational type expression, concrete syntax, regular type expression, and a Common Lisp implementation which allows the programmer to declarative express the types of heterogeneous sequences in a way which is natural in the Common Lisp language. We present a brief theoretical background in rational language theory, which facilitates the development of rational type expressionsin particular the use of the Brzozowski derivative and deterministic automata to arrive at a solution which can match a sequence in linear time. We illustrate the concept with several motivating examples, and finally explain many details of its implementation.

Documents

• Paper

Efficient Dynamic Type-checking of Heterogeneous Sequences

Authors

Jim Newton, Akim Demaille, Didier Verna

Article submitted to ELS 9 2016

ELS 2016 Article Presentation Slides

Project Report

Report

Source code

You may download the source code from LRDE gitlab mirror

Bibtex (lrde.bib)

@TechReport{	  newton.16.rte.report,
  author	= {Jim Newton},
  title		= {Efficient dynamic type checking of heterogeneous
		  sequences},
  institution	= {LRDE},
  year		= 2016,
  number	= {2005D002},
  address	= {Paris, France},
  month		= feb,
  annote	= {This technical report corresponds to the publication
		  newton.16.edtchs},
  abstract	= { This report provides detailed background of our
		  development of the rational type expression, concrete
		  syntax, regular type expression, and a Common Lisp
		  implementation which allows the programmer to declarative
		  express the types of heterogeneous sequences in a way which
		  is natural in the Common Lisp language. We present a brief
		  theoretical background in rational language theory, which
		  facilitates the development of rational type expressions,
		  in particular the use of the Brzozowski derivative and
		  deterministic automata to arrive at a solution which can
		  match a sequence in linear time. We illustrate the concept
		  with several motivating examples, and finally explain many
		  details of its implementation. }
}