A pattern matcher for miniKanren or How to get into trouble with CPS macros

Andrew W. Keep, Michael D. Adams, Lindsey Kuper, William E. Byrd, and Daniel P. Friedman

Status: Published


CPS macros written using Scheme’s syntax-rules macro system allow for guaranteed composition of macros and control over the order of macro expansion. We identify a limitation of CPS macros when used to generate bindings from a non-unique list of user-specified identifiers. Implementing a pattern matcher for the miniKanren relational programming language revealed this limitation. Identifiers come from the pattern, and repetition indicates that the same variable binding should be used. Using a CPS macro, binding is delayed until after the comparisons are performed. This may cause free identifiers that are symbolically equal to be conflated, even when they are introduced by different parts of the source program. After expansion, this leaves some identifiers unbound that should be bound. In our first solution, we use syntax-case with bound-identifier=? to correctly compare the delayed bindings. Our second solution uses eager binding with syntax-rules. This requires abandoning the CPS approach when discovering new identifiers.


Andrew W. Keep, Michael D. Adams, Lindsey Kuper, William E. Byrd, and Daniel P. Friedman. A pattern matcher for miniKanren or how to get into trouble with CPS macros. In Scheme ’09: Proceedings of the 2009 Scheme and Functional Programming Workshop, number CPSLO-CSC-09-03 in California Polytechnic State University Technical Report, pages 37–45. 2009. URL http://digitalcommons.calpoly.edu/csse_fac/83/.

BibTeX Entry

  author = {Keep, Andrew W. and Adams, Michael D. and Kuper, Lindsey and Byrd, William E. and Friedman, Daniel P.},
  title = {A pattern matcher for {miniKanren} or How to get into trouble with {CPS} macros},
  booktitle = {Scheme '09: Proceedings of the 2009 Scheme and Functional Programming Workshop},
  pages = {37--45},
  year = {2009},
  number = {CPSLO-CSC-09-03},
  series = {California Polytechnic State University Technical Report},
  url = {http://digitalcommons.calpoly.edu/csse_fac/83/},