Macro expansion: evaluating a pattern variable that could be a number or a function

Questions & Answers
1

This is related to my struggles with getting a new #lang to work. I've discovered a bug in my code, but I am not sure how to modify my macro to make it work as expected.

The key parts of my macro and supporting code are:

(define-syntax wires-operator
                 ;; literals:
  (syntax-rules (AND OR LSHIFT RSHIFT NOT -> // SHOW)
    [(wires-operator lhs OR rhs -> dest)
     (define (dest) (wires-or (lhs) (rhs)))]
    [(wires-operator input -> dest)
     (define (dest) input)]
    [(wires-operator SHOW wire)
     (printf "wire ~s = ~s\n" (object-name wire)
             (if (number? wire)
                 wire
                 (wire)))]
))

(define (wires-or x y) (bitwise-ior x y))

and it's expanding something like this:

(wires-operator 5 -> a)
(wires-operator a -> b)
(wires-operator 15 OR a -> c)
(wires-operator SHOW a)
(wires-operator SHOW b)
(wires-operator SHOW c)

the SHOW a works fine. But the SHOW b results in wire b = #<procedure:a>.

Okay, so I need to detect whether I have a number or a function that I need to evaluate. That's what the printf is trying to do.

I know that the problem here is related to pattern variables or macro hygiene or compile-time versus run-time, but I don't know what I don't know. :slight_smile:

The OR also fails, but more dramatically: the 15 OR a -> c results in:

application: not a procedure;
 expected a procedure that can be applied to arguments
  given: 15

And I understand what's going wrong: it's trying to evaluate something like (15).

This is confusing. It seems like:

  • the printf thinks that (number? wire) is true, but it's a function and prints that way!
  • the OR expansion tries to expand something equivalent to (15) and of course fails.

So my macro needs to either (1) figure out at compile-time whether the actual text of the pattern variable is a numerical constant or some sequence of letters, or (2) expand into something that will do the same at run-time.

How can I do that?

2

I poked at this some more, and I can get close with syntax-parse.

(As an aside: the zoo of "syntax-*" things is confusing. syntax-parse, syntax-rule, syntax-parse, define-syntax, define-syntax-rule, syntax-rules, syntax-case...and they all seem to be just a little different. Some are wrappers around other, more general ones. They overlap...mostly? But overall it's hard to figure out which one to use, and why, and when.)

At any rate: syntax/parse can do the kind of number / id branching that I want:

(define-syntax (test% stx)
  (syntax-parser
    [(_ lhs:id rhs:number)
         #'(define (lhs) rhs)] ;; treat rhs as an expression to just evaluate
    [(_ lhs:id rhs:id)
         #'(define (lhs) (rhs))] ;; treat rhs as a function to be called
    )
  )

(define (a) 123)

(test% b OR a)
(test% c OR 456)

works and defines (b) and (c) as expected. But now I don't know how to handle the literals from my code: I need things like OR and -> to be treated as literals in the patterns. syntax-rules lets me list those, but I can't figure out how to do the same with syntax-parse. I tried a #:literals line, but that didn't work.

If I can get the literals working, that would give me one way to make this work. But then I'd have to write four cases for each binary operator, since each operand can be one of two syntax classes.

So, once I can handle the literals: is there a way to do the number/id handling in the template, or elsewhere where I can have one pattern that does the appropriate branching?

3

Your wires have the potential to create several suspended computations, like "futures" (parallelism) or "suspensions" ("thunks"; laziness). To fix this your code must force
wires all the way down to numbers not just one level deep:

#lang racket

#; {type Wire = Number u (-> Wire)}

(define-syntax wires-operator
                 ;; literals:
  (syntax-rules (AND OR LSHIFT RSHIFT NOT -> // SHOW)
    [(wires-operator lhs OR rhs -> dest)
     (define (dest) (wires-or (touch lhs) (touch rhs)))]
    [(wires-operator input -> dest)
     (define (dest) input)]
    [(wires-operator SHOW wire)
     (printf "wire ~s = ~s\n" (object-name wire) (touch wire))]))

#; {Wirse -> Number}
;; an alternative name would be `force` (see "lazy")
;; `touch` because it reminds me of Halstead style futures 
(define (touch wire)
  (if (number? wire)
      wire
      (touch (wire))))

(define (wires-or x y) (bitwise-ior x y))


(wires-operator 5 -> a)

(wires-operator a -> b)

(wires-operator 15 OR a -> c)

(wires-operator SHOW a)

(wires-operator SHOW b)

(wires-operator SHOW c)

When you design such code, you may wish to add a comment on your choice of data representation and then imagine "signatures" for your auxiliaries in terms of those
representations. See above.

1 Like
4

Hi, @ddrake.

Regarding "literals", there are a couple of options here, but if you're already using syntax-parse, you might get some mileage out of #:datum-literals, depending on the use-case.

As far as I understand, #:literals are treated as literal identifiers. In other words, they check whether whatever needs to match is free-identifier=? to the literal you specify.

On the other hand, #:datum-literals treats whatever you provide as completely literal, that is, literal symbols instead of identifiers.

This second case is often useful when the accompanying syntax has no purpose other than as keywords, so to speak.

Regarding the multiple cases you have to deal with, there are also multiple ways of approaching this, but a simple way to initially aggregate some of these patterns, would be to use syntax-classes:

;; wires-syntax.rkt

#lang racket/base

(require
  (for-syntax
   racket/base
   syntax/parse))

(provide
  wires-operator)

(begin-for-syntax
  ;; here you can combine multiple patterns into one,
  ;; if they share certain properties or should be treated similarly
  (define-syntax-class wires-atom
    #:attributes (expand)
    
    (pattern id:id      #:with expand #'(id))
    (pattern num:number #:with expand #'num)))

(define-syntax (wires-operator stx)
  (syntax-parse stx
    #:datum-literals (AND OR LSHIFT RSHIFT NOT -> // SHOW)
    
    [(wires-operator lhs:wires-atom AND rhs:wires-atom -> dest:id)
     #'(define (dest)
         (wires-and lhs.expand rhs.expand))]
    
    [(wires-operator lhs:wires-atom OR rhs:wires-atom -> dest:id)
     #'(define (dest)
         (wires-or lhs.expand rhs.expand))]
    
    [(wires-operator lhs:wires-atom LSHIFT n:number -> dest:id)
     #'(define (dest)
         (wires-lshift lhs.expand n))]
    
    [(wires-operator lhs:wires-atom RSHIFT n:number -> dest:id)
     #'(define (dest)
         (wires-rshift lhs.expand n))]
    
    [(wires-operator NOT lhs:wires-atom -> dest:id)
     #'(define (dest)
         (wires-not lhs.expand))]
    
    [(wires-operator input:expr -> dest:id)
     #'(define (dest) input)]
    
    [(wires-operator SHOW wire)
     #'(printf "wire ~s = ~s\n" (object-name wire) (wire))]
    
    [(wires-operator // comments ...)
     #'(void)]
    
    [(wires-operator)
     #'(void)]))

(define (wires-and x y)
  (bitwise-and x y))

(define (wires-or x y)
  (bitwise-ior x y))

(define (wires-not x)
  (bitwise-bit-field (bitwise-not x) 0 16))

(define (wires-lshift x n)
  (arithmetic-shift x n))

(define (wires-rshift x n)
  (arithmetic-shift x (- n)))

(wires-operator 5 -> a)
(wires-operator a -> b)
(wires-operator 15 OR a -> c)
(wires-operator SHOW a)
(wires-operator SHOW b)
(wires-operator SHOW c)

wire a = 5
wire b = #<procedure:a>
wire c = 15

I hope that helps a bit.

That being said, @EmEf has a pretty good suggestion also, in terms of abstracting over the terms of the DSL in terms of thunks, because as he alludes, this can be a very powerful way of structuring your language.

If you ever work up the appetite, The Reasoned Schemer was my favourite installment of the X Schemer books, and takes a similar approach to doing constraint logic programming (related to but distinct from logic programming, in the vein of Prolog) with suspended computations.

5

Thanks -- your syntax class suggestion works for me. And I'm using @EmEf's idea to recursively evaluated things. Overall things seem pretty good.

But when I try to show the values for some of the wires from the original Advent of Code puzzle, something is getting stuck in an infinite loop. I'm pretty sure it's my recursive evaluation that is getting stuck. There is, of course, a DAG describing the dependencies for the values of the wires, and I'm not sure if there's a bug in my code, in the puzzle, or if somehow you can get a cycle in the quote-unquote DAG but nevertheless evaluate the value.

I'm tempted to write some code that interprets this wires DSL but doesn't evaluate the signals -- it builds and shows that DAG. And then I could look for loops; my experience with graph traversal algorithms is pretty thin, so it would be good practice...

6

If your DSL code defines mutually-referential wires, touch as defined will diverge:

(wires-operator b -> a)
(wires-operator a -> b)
(wires-operator SHOW a)

Add an eprintf to touch to see how the wires refer to each other:

#; {Wirse -> Number}
;; an alternative name would be `force` (see "lazy")
;; `touch` because it reminds me of Halstead style futures 
(define (touch wire)
  (cond
    [(number? wire) wire]
    [else
     (eprintf "touching ~a\n" (object-name wire))
     (touch (wire))]))

Consider scoping wires via a let* like scope if you want a dag.

(Also consider the syntax-spec package, which allows you to specify complete DSL grammars together with binding specifications.)

1 Like
7

What do you mean here? How would I "scope wires via a let"?

It turns out that I do have a mostly-working implementation. The problem is, the DAG representing the dependencies is very large, and with the naive way that touch does recursion, you get a combinatorial explosion in the number of recursive calls and Racket runs out of memory.

So. I need to memoize. I've been struggling with that; the way touch works and does its recursion somehow doesn't cooperate with hash sets. I have code that gets the values, and seemingly updates the hash-set, but somehow the inserted key and value are never seen, and so when it looks at the hash set to see if it already computed the value, it never thinks it did.

What is strange is that I also added in some code that builds the directed graph of dependencies. That was surprisingly easy! It turns out that the parsing macro, in addition to calling one of the bitwise functions, just needed to also call a function to add the appropriate edges.

I wrote a function that calculates the dependencies of a given node/wire; that uses the same kind of recursion that touch does and updates a set as it goes along, and that works perfectly.

I suspect there may be some kind of race condition that makes the hash set update not work as expected, though I'm not sure why that fails and regular sets work.

So I either need (1) a way to actually memoize touch, or perhaps (2) to do breadth-first search starting from the root of the dependency graph, and to build up a hash set as it does the search. This would effectively be memoization for touch in reverse.

I've poked at the graph modules do-bfs but haven't been able to get it to work. Any suggestions with either the regular memoization, or a graph search that can build up the values and avoid combinatorial explosion in naive recursion?

8

I can't really guess at the race-condition you might have without looking at the code, but one way to "memoize" the solution, would be to use a parameter.

I quickly mocked up a solution this way, without macros, though, as a proof of concept.

spoilers 
#lang racket/base

(require
  racket/list
  racket/match)

(define (binary op s₀ s₁)
  (case op
    [(OR)     (bitwise-ior s₀ s₁)]
    [(AND)    (bitwise-and s₀ s₁)]
    [(LSHIFT) (arithmetic-shift s₀ (+ s₁))]
    [(RSHIFT) (arithmetic-shift s₀ (- s₁))]))

(define (operation . ex)
  (match ex
    [(list op s₀ s₁) (binary op s₀ s₁)]

    [(list _ s)
     (bitwise-not s)]))

(define px-binary   #px"^(.*?) (.*?) (.*?) -> (.*?)$")
(define px-unary    #px"^(.*?) (.*?) -> (.*?)$")
(define px-identity #px"^(.*?) -> (.*?)$")

(define value
  (match-lambda
    [(pregexp #px"^(\\d+)$" (list _ num)) (string->number num)]
    [name
     (string->symbol name)]))

(define destinations (make-parameter #false))

(define (record-wires)
  (with-input-from-file "booklet.txt"
    (lambda ()
      (for ([line (in-lines)])
        (match line
          [(pregexp px-binary (list _ signal₀ operator signal₁ (app value destination)))
           {destinations
            (hash-set
             {destinations} destination
             (map value `(,operator ,signal₀ ,signal₁)))}]
        
          [(pregexp px-unary (list _ operator signal (app value destination)))
           {destinations
            (hash-set
             {destinations} destination
             (map value `(,operator ,signal)))}]
        
          [(pregexp px-identity (list _ signal (app value destination)))
           {destinations
            (hash-set
             {destinations} destination
             (value signal))}]

          [unexpected
           (error 'parser (format "encountered unexpected input: ~a" unexpected))])))))

(define (lookup destination)
  (define signal (hash-ref {destinations} destination))
  (define result
    (cond
      [(symbol? signal) (lookup signal)]

      [(pair? signal)
       (apply operation (car signal)
              (for/list ([value (in-list (cdr signal))])
                (if (number? value) value (lookup value))))]

      [else signal]))
  
  {destinations
   (hash-set {destinations} destination result)}
  result)

(define (solve-wires)
  (parameterize ([destinations (hash)])
    (record-wires) (lookup 'a)))

(solve-wires)
;=> 46065

The crux of the solution comes down to the parameter destinations. TL;DR, parameters are thread local variables, which can be "scoped" using a parameterize expression, whereby any references under that scope to the parameter, refer to a particular parameterization of it, i.e. like a distinct fork of the variable.

Parameter procedures are what we use to set and get values from the parameter, like so:

{parameter}       ;; get value
{parameter value} ;; set value

I use curly braces to distinguish these operations, although this is unimportant to the syntax of the thing.

So, with this in mind, we use the hash as we normally would but are free to update the hash (which is immutable, for what it's worth) as we go along, setting values to destinations for constants, and computing those that are due to operators.

I might have fudged it, but the result is the same as from the Beautiful Racket tutorial, so I'll assume it's correct.

I hope this helps to give you some intuition for this particular strategy. I am kind of a nut about parameters, so take with a grain of salt.

9

On Jul 22, 2025, at 5:26 PM, Dan Drake via Racket Discourse notifications@racket.discoursemail.com asked "What do you mean here? How would I scope wiresvia alet*` '"

Say you have a "wire program" like this one:

(wires-operator b -> a)
(wires-operator a -> b)
(wires-operator SHOW a)

The expansion binds b and a as mutually recursive functions at the module level. So the body of a sees b and the body of b sees a.
Hence it is too easy to create cyclic graphs, when you state you want DAGs.

One way to prevent cycles is to compute dependencies.

Another one is to take over #%module-begin and to set up the definitions via a let* so that the body of b can't see any wires, the body of a can see b, and so on. Then the lexical scope alone guarantees a DAG. Most typed FPLs use a scope arrangement like this one; Racket uses mutual recursion instead by default.

If you decided to have cycles after all, you'd add a construct for creating cycles, making it explicit where you want touch to work hard.

10

Yep! And I've done that.

I mentioned above that one amazing lovely thing about making your own DSL this way is that it was almost trivial to modify my parsing code to build a dependency graph. I haven't added anything that actually checks it, but it would be trivial: given

#lang wires
b -> a
a -> b

My code currently builds up a directed graph called dependencies and provides it. So you can run that in DrRacket, and in the REPL:

> (get-edges dependencies)
'((a b) (b a))
> (dag? dependencies)
#f
11

I tried something that almost works.

The idea is: the bfs returns a hash table mapping nodes to their distance from the root. So, use that to do this:

  1. Make an empty hash table. Modify eval-rec to look to that to return memoized values in that table.
  2. For distance 1, 2, 3... from the "numerical signal" root:
  3. Get all the nodes of that distance.
  4. For each node, run touch (in my code I call it eval-rec), and put the value into the hash table.

In principle, as the distance increases, touch can use the memoized values "one value below" and it will be very fast.

But for the huge Advent of Code puzzle, there's a problem: the breadth-first-search returns the shortest distance to the root. But you can have multiple paths to the root that are of very different distances.

The combinatorial explosion I mentioned above happens when you have multiple cycles along a path to the root.

So you can have a wire that along one path is, say, distance 2 to the root. But if it depends on two values, and other branch is distance 10 to the root with many cycles, touch tries to evaluate that "early" but will take forever to evaluate that other, long branch, and it only has the distance-1 nodes in the hash table to help it.

The algorithm I have is valid, but it's easy in practice to defeat it with something like the above, and the provided Advent of Code puzzle does just that.

You can see my otherwise-very-nice code in this branch of my github repo.

12

I have looked a bit at parameters and they are still very mysterious to me. I didn't see a motivation or use-case for them and went on looking at other stuff. But now I'm motivated to learn why they are cool. I will take a look!

(I am also likely to just go to the Beautiful Racket solution and mimic that; I cheated very briefly and looked at it, and it seems like it avoids whatever problem that my approaches here keep getting tripped up on.)

13

They are mysterious! But in a good way :wink:

You'll obviously find your own way there, but the idea is that you can create arbitrary scopes for a variable. It's almost like having a global variable, in say, Python, but with the ability to restrict what value the variable takes in a particular parameterization (i.e., scope).

We use parameters all the time in Racket, but as a certain disembodied gaseous lifeform once quipped, "When you do things right, people won’t be sure you’ve done anything at all."

A very common occurrence is when you use, with-input-from-* and friends.

Essentially, when you say

(with-input-from-file "some-file.txt"
  (lambda () ... do-something ...))

the procedure with-input-from-file, is wrapping the thunk--i.e. the (lambda () ...)--in a parameterization of current-input-port, such that, you guessed it, the current input port visible inside of the thunk, is a port into the file you specified:

(parameterize ([current-input-port (open-input-file "some-file.txt"])
  (lambda () ... do-something ...))

Anything referring to current-input-port in this scope, sees this port into the file, regardless of "where" they are (except for other, more deeply nested parameterizations of the variable, of course).

It removes the "locality" requirement from variable scopes, which obviates a lot of threading of state through forms that would be necessary without it.

It also makes it really nice to work with immutable data, because you're assigning to and reading from the parameter's state, not a mutable data structure itself.

P.S. the PDF graph of the wires booklet in your repo is :ok_hand:

14

That's just the graph module's graphviz output. All I did was build the graph and write it out to a .dot file and make it into a PDF. :slight_smile:

15

VICTORY!

I now have this working. I've pushed my changed to my puzzle-test branch.

The key realization I needed to make was related to eager evaluation, and why trying to do the caching / memoization at runtime wasn't working: all the various functions evaluate their arguments first, and if the evaluation of those arguments calls other functions, they evaluate their arguments...and so on. This means that you really never have access to the name of the thing whose value you're trying to memoize; eager evaluation has always drilled that down to a numerical constant.

So we either need to do some runtime hacking...or to control when and how things get evaluated.

Well, that's exactly what macros do!

I introduced a helper macro that takes a wire and the expression representing its value. The macro can use the wire's name to expand out some code that checks the cache / hash table; the helper macro outputs some code that evaluates the wire's value, and populates the cache.

So this was a good exercise, even if it took far, far too long for my weak little pea brain to really, truly understand the runtime evaluation model, and how you need to work with/around that with macros.

I started down this (now extremely deep...) rabbit hole by wanting to understand more about macros. And the great news is, I do! I got to the point where i can say "yes, I see what the problem is, and a macro is exactly the solution." And it only took me a few moments to whip up the macro I needed!

So @bakgatviooldoos : in the end, it's not a race condition, and I didn't investigate parameters. (Yet!.

Thank you all for your continued help. You really stuck with this and helped me keep going until my dumb self figured it out.

1 Like