Relational Synthesis for Pattern Matching

Dmitry Kosarev, Petr Lozov, Dmitry Boulytchev

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review


We present a completely declarative approach to synthesizing pattern matching construct implementations based on application of relational programming, a specific form of constraint logic programming. Our approach is based on relational representations of both the high-level semantics of pattern matching and the semantics of an intermediate-level implementation language. This choice makes our approach, in principle, very scalable as we only need to modify the high-level semantics in order to synthesize the implementation of a pattern matching new feature. Our evaluation on a set of small samples, partially taken from existing literature shows, that our framework is capable of synthesizing optimal implementations quickly. Our in-depth stress evaluation on a number of artificial benchmarks, however, has shown the need for future improvements.

Original languageEnglish
Title of host publicationProgramming Languages and Systems - 18th Asian Symposium, APLAS 2020, Proceedings
EditorsBruno C. Oliveira
PublisherSpringer Nature
Number of pages18
ISBN (Print)9783030644369
StatePublished - 2020
Event18th Asian Symposium on Programming Languages and Systems, APLAS 2020 - Fukuoka, Japan
Duration: 30 Nov 20202 Dec 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12470 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference18th Asian Symposium on Programming Languages and Systems, APLAS 2020

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


  • Pattern matching
  • Relational interpreters
  • Relational programming


Dive into the research topics of 'Relational Synthesis for Pattern Matching'. Together they form a unique fingerprint.

Cite this