Difference between revisions of "Publications/newton.16.rte.report"
From LRDE
(Created page with "{{Publication | published = true | date = 2016-02-22 | lrdeinc = Publications/newton.16.els.inc | lrdekeywords = Rational languages, typechecking, finite automata | lrdenewsda...") |
|||
| Line 11: | Line 11: | ||
| address = Paris, France |
| address = Paris, France |
||
| annote = This technical report corresponds to the publication newton.16.edtchs |
| 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 textitrational type expression |
||
| type = techreport |
| type = techreport |
||
| id = newton.16.rte.report |
| id = newton.16.rte.report |
||
| Line 27: | Line 27: | ||
newton.16.edtchs<nowiki>}</nowiki>, |
newton.16.edtchs<nowiki>}</nowiki>, |
||
abstract = <nowiki>{</nowiki> This report provides detailed background of our |
abstract = <nowiki>{</nowiki> This report provides detailed background of our |
||
| − | development of the |
+ | 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. <nowiki>}</nowiki> |
|
<nowiki>}</nowiki> |
<nowiki>}</nowiki> |
||
Revision as of 15:29, 23 February 2016
- 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 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.
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
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. }
}