Difference between revisions of "Publications/newton.16.rte.report"

Latest revision as of 12:22, 3 December 2022

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. }
}

@@ Line 8: / Line 8: @@
 | lrdeprojects = Climb
 | authors = Jim Newton
-| title = Efficient dynamic type checking of heterogeneous sequences
+| title = Efficient Dynamic Type Checking of Heterogeneous Sequences
 | institution = LRDE
 | number = 2005D002
 | address = Paris, France
 | 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 examplesand finally explain many details of its implementation.
+| 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.
 | type = techreport
 | id = newton.16.rte.report
@@ Line 19: / Line 19: @@
 @TechReport<nowiki>{</nowiki>	  newton.16.rte.report,
   author	= <nowiki>{</nowiki>Jim Newton<nowiki>}</nowiki>,
-  title		= <nowiki>{</nowiki>Efficient dynamic type checking of heterogeneous
+  title		= <nowiki>{</nowiki>Efficient Dynamic Type Checking of Heterogeneous
-		  sequences<nowiki>}</nowiki>,
+		  Sequences<nowiki>}</nowiki>,
   institution	= <nowiki>{</nowiki>LRDE<nowiki>}</nowiki>,
   year		= 2016,