Nearly Macro-free microKanren

Abstract

We describe changes to the microKanren implementation that make it more practical to use in a host language without macros. With some modest runtime features common to most languages, we show how an implementer lacking macros can come closer to the expressive power that macros usually provide—with varying degrees of success. The result is a still functional microKanren that invites slightly shorter programs, and is relevant even to implementers that enjoy macro support. For those without it, we address some pragmatic concerns that necessarily occur without macros so they can better weigh their options.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

Request permissions from permissions@acm.org.

TFP ’23, January 13–15, 2023, Boston, Massachusetts

© 2023 Association for Computing Machinery. ACM ISBN 978-1-4503-XXXX-X/18/06…$15.00 https://doi.org/XXXXXXX.XXXXXXX

Appendices

A conj Derivation

Starting with the variadic function based on the macro in Listing 2, we first $\upeta$-expand and split the definition.

We next substitute for the definitions of and .

This definition of sequences the invocations of goal and state in the order they appear. acts like a non-deterministic operator. In each recursive call, we accumulate by mapping, using special delaying implementation of Kanren-language streams, the next goal in the list.

The state does not change in the recursion: only needs to build the stream. Therefore we can assemble the stream on the way in—instead of passing in and separately, we pass in their combination as a stream. The function is tail recursive; we can change the signature in the one and only external call and the recursive call. Adding the trivial base case to , yields the version shown in Listing 3.

B conda Derivation

At this point and in are begging to be passed as a stream ; we oblige them. We lift that local function to a global definition, passing all the parameters it needs. Since the only call to is in , we know that third parameter will always be a non-empty list.

If we also add a line in to dispatch with the trivial case, we arrive at the definition in Listing 6. Most of Listing 6 is a functional implementation of that cascade behavior. knows it has at least one goal; it’s job is to determine if there is precisely one goal, precisely two goals, or more than two goals.