Efficient dynamic type checking of heterogeneous sequences

Authors

Jim Newton

Place

Paris, France

Type

techreport

Keywords

Rational languages, typechecking, finite automata

Date

2016-02-22

Abstract

This report provides detailed background of our development of the textitrational type expression

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 \textit{rational type expression},
		  concrete syntax, \textit{regular type expression}, and a
		  \cl implementation which allows the programmer to
		  declarative express the types of heterogeneous sequences in
		  a way which is natural in the \cl 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. }
}