Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Programming with Enumerable Sets of Structures
 
Loading...
Thumbnail Image
conference paper

Programming with Enumerable Sets of Structures

Kuraj, Ivan  
•
Kuncak, Viktor  
•
Jackson, Daniel
2015
Acm Sigplan Notices
ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA)

We present an efficient, modular, and feature-rich framework for automated generation and validation of complex structures, suitable for tasks that explore a large space of structured values. Our framework is capable of exhaustive, incremental, parallel, and memoized enumeration from not only finite but also infinite domains, while providing fine-grained control over the process. Furthermore, the framework efficiently supports the inverse of enumeration (checking whether a structure can be generated and fast-forwarding to this structure to continue the enumeration) and lazy enumeration (achieving exhaustive testing without generating all structures). The foundation of efficient enumeration lies in both direct access to encoded structures, achieved with well-known and new pairing functions, and dependent enumeration, which embeds constraints into the enumeration to avoid backtracking. Our framework defines an algebra of enumerators, with combinators for their composition that preserve exhaustiveness and efficiency. We have implemented our framework as a domain-specific language in Scala. Our experiments demonstrate better performance and shorter specifications by up to a few orders of magnitude compared to existing approaches.

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/2814270.2814323
Web of Science ID

WOS:000367256500003

Author(s)
Kuraj, Ivan  
•
Kuncak, Viktor  
•
Jackson, Daniel
Date Issued

2015

Publisher

Assoc Computing Machinery

Publisher place

New York

Published in
Acm Sigplan Notices
Total of pages

20

Volume

50

Issue

10

Start page

37

End page

56

Subjects

Algorithms

•

Languages

•

Verification

•

Dependent enumeration

•

data generation

•

invariant

•

pairing function

•

algebra

•

exhaustive testing

•

random testing

•

lazy evaluation

•

program inversion

•

DSL

•

SciFe

Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LARA  
Event nameEvent placeEvent date
ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA)

Pittsburgh, PA

OCT 25-30, 2015

Available on Infoscience
February 16, 2016
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/124191
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés