I learned macros yay
Last Edited: Mon Aug 14 07:51:57 UTC 2023
I learned macros!
After a little under a year of learning, I feel like I'm finally able to call myself a lisp programmer. I started off by learning clojure and getting functional programming under my belt. Then, I went through the little schemer and began to understand the essence of lisp. Now, I feel comfortable saying that clojure isn't a lisp, but in some ways a superset of lisp.
I could use lisp, and always knew that macros existed, but never really understood them or where I would use them. That was until I started learning core.logic. So, the "proof" that I understand lisp and macros is a little example of a relational program.
LeetCode 216: Combination Sum III
Description
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
- Only numbers 1 through 9 are used.
- Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
To me, this felt like a no-brainer to use core.logic. The problem is basically just a complete search over a finite domain.
The approach
This problem is easily solved using the clojure.core.logic.fd library. It allows you to do relational programming over a finite domain of integers. I'm going to assume some background in relational programming and just get to the code.
Why macros?
Well, to be honest, macros might not even be necessary. But, I thought that because there could be a list of any number k, we would need to be able to dynamically instantiate logic variables, so I can use a macro to make that many logic variables easily.
To start, let's do a minimal example. Suppose k = 3 and n = 9. We would want a program like this:
(l/run* [?q]
(l/fresh [?v0 ?v1 ?v2]
;In the domain
(fd/in ?v0 ?v1 ?v2 (fd/domain 1 2 3 4 5 6 7 8 9))
;Each number is unique
(fd/distinct [?v0 ?v1 ?v2])
;The numbers sum to n
(fd/eq
(= 9 (+ ?v0 ?v1 ?v2)))
;Output
(l/== ?q [?v0 ?v1 ?v2])))
We have constraints to ensure each variable is in the range 1-9, to ensure that they're each distinct, and that they sum to the specified n.
Now, we can easily modify this code to support an arbitrary n by changing the 9 in the fd/eq constraint, but what if we wanted a different k? Well, we would have to add the variable to each clause and it would be quite annoying. I would certainly buy that there is a way to do this using functions (data > fns > macros), but I think using a macro makes sense here.
The approach I'm using is probably not super idiomatic when it comes to macros, but it does work!, We'll build it up clause by clause.
(defmacro makerel-lists [k n])
To start, we need a macro that accepts a k and an n.
Now, for the output, we'll be building up a list of the needed symbols by consing to a list, so we need a list to start with, and also to reverse the output because consing adds to the beginning (doing it this way makes it easier to read imo)
(defmacro makerel-lists [k n]
(let []
(reverse (->> '()))))
We'll start with what we know is in the constraint, the fresh.
(defmacro makerel-lists [k n]
(let []
(reverse
(->> '()
(cons 'l/fresh)))))
Then, we need a vector of our variables which we'll construct in the let block.
(defmacro makerel-lists [k n]
(let [vars (map #(symbol (str "?v" %)) (range k))
varsvec (vec vars)]
(reverse
(->> '()
(cons 'l/fresh)
(cons varsvec)))))
;----- macroexpanded
(l/fresh [?v0 ?v1 ?v2 ?v3])
Alright, we have our logic variables, now we need our constraints. To start, let's make the domain constraints.
(defmacro makerel-lists [k n]
(let [vars (map #(symbol (str "?v" %)) (range k))
varsvec (vec vars)
domcons (->> vars
(cons 'fd/in)
reverse
(cons '(fd/domain 1 2 3 4 5 6 7 8 9))
reverse)]
(reverse
(->> '()
(cons 'l/fresh)
(cons varsvec)
(cons domcons)))))
;----- macroexpanded for k=4 n=25
(l/fresh
[?v0 ?v1 ?v2 ?v3]
(fd/in ?v0 ?v1 ?v2 ?v3 (fd/domain 1 2 3 4 5 6 7 8 9)))
Next, we need a distinct constraint. Here, instead of building up the list like domcons, we'll just be using some quotes to make it a bit easier.
(defmacro makerel-lists [k n]
(let [vars (map #(symbol (str "?v" %)) (range k))
varsvec (vec vars)
domcons (->> vars
(cons 'fd/in)
reverse
(cons '(fd/domain 1 2 3 4 5 6 7 8 9))
reverse)
discons `(~'fd/distinct ~varsvec)]
(reverse
(->> '()
(cons 'l/fresh)
(cons varsvec)
(cons domcons)
(cons discons)))))
;----- macroexpanded for k=4 n=25
(l/fresh
[?v0 ?v1 ?v2 ?v3]
(fd/in ?v0 ?v1 ?v2 ?v3 (fd/domain 1 2 3 4 5 6 7 8 9))
(fd/distinct [?v0 ?v1 ?v2 ?v3]))
For the sum constraint, we'll be building it up in several steps. The sum statement itself (+ ?v0 ?v1 ?vn...), and then the constraint.
(defmacro makerel-lists [k n]
(let [vars (map #(symbol (str "?v" %)) (range k))
varsvec (vec vars)
domcons (->> vars
(cons 'fd/in)
reverse
(cons '(fd/domain 1 2 3 4 5 6 7 8 9))
reverse)
discons `(~'fd/distinct ~varsvec)
sumstat (cons '+ vars)
sumcons `(~'fd/eq
(~'= ~n ~sumstat))]
(reverse
(->> '()
(cons 'l/fresh)
(cons varsvec)
(cons domcons)
(cons discons)
(cons sumcons)))))
;----- macroexpanded for k=4 n=25
(l/fresh
[?v0 ?v1 ?v2 ?v3]
(fd/in ?v0 ?v1 ?v2 ?v3 (fd/domain 1 2 3 4 5 6 7 8 9))
(fd/distinct [?v0 ?v1 ?v2 ?v3])
(fd/eq (= 25 (+ ?v0 ?v1 ?v2 ?v3))))
Last but not least, we need to add our "output" constraint. This will require accepting the output logic variable as an input to the macro.
(defmacro makerel-lists [k n lvar]
(let [vars (map #(symbol (str "?v" %)) (range k))
varsvec (vec vars)
domcons (->> vars
(cons 'fd/in)
reverse
(cons '(fd/domain 1 2 3 4 5 6 7 8 9))
reverse)
discons `(~'fd/distinct ~varsvec)
sumstat (cons '+ vars)
sumcons `(~'fd/eq
(~'= ~n ~sumstat))
outcons `(~'l/== ~lvar ~varsvec)]
(reverse
(->> '()
(cons 'l/fresh)
(cons varsvec)
(cons domcons)
(cons discons)
(cons sumcons)
(cons outcons)))))
;----- macroexpanded for k=4 n=25
(l/fresh
[?v0 ?v1 ?v2 ?v3]
(fd/in ?v0 ?v1 ?v2 ?v3 (fd/domain 1 2 3 4 5 6 7 8 9))
(fd/distinct [?v0 ?v1 ?v2 ?v3])
(fd/eq (= 25 (+ ?v0 ?v1 ?v2 ?v3)))
(l/== ?q [?v0 ?v1 ?v2 ?v3]))
And Bam! We can slap this in a run* and that's a wrap.
Now, in order to solve the problem fully, we need to ensure that the outputs are unique, but it's really straightforward. (hint: just make each list a set, and then put the outputs into a set).
Overall, I'm quite proud of what I have learned. I have added a ton of stuff to my toolbox and I'm excited to keep going!