More Web Proxy on the site http://driver.im/

Article

Type-Checking of Heterogeneous Sequences in Common Lisp

Authors:

Didier VernaAuthors Info & Claims

ELS2016: Proceedings of the 9th European Lisp Symposium on European Lisp Symposium

Article No.: 2, Pages 13 - 20

Published: 09 May 2016 Publication History

Abstract

We introduce the abstract concept of rational type expression and show its relationship to rational language theory. We further present a concrete syntax, regular type expression, and a Common Lisp implementation thereof which allows the programmer to declaratively express the types of heterogeneous sequences in a way which is natural in the Common Lisp language. The implementation uses techniques well known and well founded in rational theory, in particular the use of the Brzozowski derivative and deterministic automata to reach 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.

References

[1]

Declaring the elements of a list, discussion on comp.lang.lisp, 2015.

[2]

H. G. Baker. A decision procedure for Common Lisp's SUBTYPEP predicate. Lisp and Symbolic Computation, 5(3):157-190, 1992.

Digital Library

[3]

J. A. Brzozowski. Derivatives of regular expressions. J. ACM, 11(4):481-494, 1964.

Digital Library

[4]

R. D. Cameron. Perl style regular expressions in Prolog, CMPT 384 lecture notes, 1999.

[5]

J. Chroboczek. CL-Yacc, a LALR(1) parser generator for Common Lisp, 2009.

[6]

P. Domain. Alexandria implementation of destructuring-case.

[7]

N. Funato. Public domain implementation of destructuring-bind, 2013.

[8]

H. Hosoya, J. Vouillon, and B. C. Pierce. Regular expression types for XML. ACM Trans. Program. Lang. Syst., 27(1):46-90, Jan. 2005.

Digital Library

[9]

J. D. U. Johh E. Hopcroft, Rajeev Motwani. Introduction to Automata Theory, Languages, and Computation. Addison Wesley, 2001.

Digital Library

[10]

W. H. Newman. Steel Bank Common Lisp user manual, 2015.

[11]

J. Newton. Report: Efficient dynamic type checking of heterogeneous sequences. Technical report, EPITA/LRDE, 2016.

[12]

S. Owens, J. Reppy, and A. Turon. Regular-expression derivatives re-examined. J. Funct. Program., 19(2):173-190, Mar. 2009.

Digital Library

[13]

C. Rhodes. User-extensible sequences in Common Lisp. In Proceedings of the 2007 International Lisp Conference, ILC '07, pages 13:1-13:14, New York, NY, USA, 2009. ACM.

Digital Library

[14]

A. Shinn, J. Cowan, and A. A. Gleckler. Revised 7 report on the algorithmic language scheme. Technical report, 2013.

[15]

ANSI. American National Standard: Programming Language - Common Lisp. ANSI X3.226:1994 (R1999), 1994.

[16]

E. Weitz. Common Lisp Recipes: A Problem-solution Approach. Apress, 2015.

Digital Library

[17]

G. Xing. Minimized Thompson NFA. Int. J. Comput. Math., 81(9):1097-1106, 2004.

[18]

F. Yvon and A. Demaille. Théorie des Langages Rationnels. 2014.

Cited By

Newton JVerna DVerna DCooper D(2018)Strategies for Typecase OptimizationProceedings of the 11th European Lisp Symposium on European Lisp Symposium10.5555/3323215.3323219(23-31)Online publication date: 18-Apr-2018
https://dl.acm.org/doi/10.5555/3323215.3323219
Newton JVerna DChari GBoix EMarr S(2018)Recognizing heterogeneous sequences by rational type expressionProceedings of the 3rd ACM SIGPLAN International Workshop on Meta-Programming Techniques and Reflection10.1145/3281074.3281077(5-14)Online publication date: 5-Nov-2018
https://dl.acm.org/doi/10.1145/3281074.3281077

Index Terms

Type-Checking of Heterogeneous Sequences in Common Lisp
1. Software and its engineering
  1. Software creation and management
    1. Software development techniques
  2. Software notations and tools
    1. Formal language definitions
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Recognizing heterogeneous sequences by rational type expression
META 2018: Proceedings of the 3rd ACM SIGPLAN International Workshop on Meta-Programming Techniques and Reflection

We summarize a technique for writing functions which recognize types of heterogeneous sequences in Common Lisp. The technique employs sequence recognition functions, generated at compile time, and evaluated at run-time. The technique we demonstrate ...
Limited Automata and Context-Free Languages
Non-Classical Models of Automata and Applications V

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence ...
On the power of quantum finite state automata
FOCS '97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science

In this paper, we introduce 1-way and 2-way quantum finite state automata (1qfa's and 2qfa's), which are the quantum analogues of deterministic, nondeterministic and probabilistic 1-way and 2-way finite state automata. We prove the following facts ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ELS2016: Proceedings of the 9th European Lisp Symposium on European Lisp Symposium

May 2016

117 pages

ISBN:9782955747407

Conference Chair:
Irène Anne Durand
LaBRI, University of Bordeaux, France
,
General Chair:
Michał Psota
Emergent Network Defense, Kraków, Poland

In-Cooperation

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

European Lisp Scientific Activities Association

Publication History

Published: 09 May 2016

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
10
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Newton JVerna DVerna DCooper D(2018)Strategies for Typecase OptimizationProceedings of the 11th European Lisp Symposium on European Lisp Symposium10.5555/3323215.3323219(23-31)Online publication date: 18-Apr-2018
https://dl.acm.org/doi/10.5555/3323215.3323219
Newton JVerna DChari GBoix EMarr S(2018)Recognizing heterogeneous sequences by rational type expressionProceedings of the 3rd ACM SIGPLAN International Workshop on Meta-Programming Techniques and Reflection10.1145/3281074.3281077(5-14)Online publication date: 5-Nov-2018
https://dl.acm.org/doi/10.1145/3281074.3281077

View Options

View options

Media

Figures

Other

Tables

View Table of Contents