TXR: writing recursive pattern matching directives

Question

I'm having trouble understanding how to write recursive pattern matching functions in TXR. Below I try to define a recursive directive for recognizing file paths. I know in this case I can represent this grammar with a regular expression ([a-z]+\/)+[a-z]+, but I have a more complex rule set in mind for my real code that would benefit from it. What is causing this directive to fail when there is a forward slash?

@(define location)@\
@  (cases)@\
@/[a-z]+/@\
@  (or)@\
@/[a-z]+//@(location)@\
@  (end)@\
@(end)
@(repeat)
@(cases)
@{location (location)}
@  (output)
@location is a valid location.
@  (end)
@(or)
@location
@  (output)
@location is not a valid location.
@  (end)
@(end)
@(end)

Example valid inputs:

this/is/valid
this/is/also/valid
this
a/b/c

Answer 1

(Of course, you're almost certainly aware that location is matching a regular language which we can just munge with a regex: /[a-z]+(\/[a-z]+)*/. I'm assuming this is just a "recursion hello world" warm-up for something more complicated.)

The thing about cases is that it uses top to bottom, short-circuited evaluation. The second case cannot match since the first case matches its prefix. It's not like a regex branch operator where the order of the subexpressions doesn't matter.

If I simply swap the two cases, the sample works for me.

What also works (in this particular case) is changing cases to some. The some directive doesn't stop at the first match.

Using some is not a cure-all for this sort of cases ordering problem because sometimes you need to short circuit around a case to terminate recursion (for instance, avoid left-recursing when some condition is hit) or to avoid degenerate performance (exponential time). I'm reminded of a university professor's joke: "you've heard of divide and conquer; this is multiply and surrender".

some also has the property that the later clauses "see" bindings from earlier successfully matching clauses. That might interfere with it being a solution for a cases-ordering problem. That is to say, the later clause might fail to match due to a variable clash. The :resolve feature of some might be helpful in that situation or might not.