Support `(a ,@b c) quasiquote pattern

[zacque0]

Hi,

Right now, only splice pattern at the end is supported:

CL-USER> (trivia:match (list 1 2 3 4 5)
	   (`(,a ,b ,@c) (list a b c)))
(1 2 (3 4 5))

And doing this gives an error:

CL-USER> (trivia:match (list 1 2 3 4 5)
	   (`(,a ,@b ,c) (list a b c)))
; Evaluation aborted on #<TRIVIA.LEVEL2.IMPL::UNBOUND-PATTERN APPEND {1001A34DB3}>.

I'm interested in extending the quasiquote pattern to do something like:

CL-USER> (trivia:match (list 1 2 3 4 5)
	   (`(,a ,@b ,c) (list a b c)))
; => (1 (2 3 4) 5)
CL-USER> (trivia:match (list 1 2 3 4 5)
	   (`(,@a ,b ,c) (list a b c)))
; => ((1 2 3) 4 5)

Is there any idea to achieve that? I tried looking into trivia-quasiquote.impl but it's not obvious how it works with the quasiquote-expand. I don't mind sending in a patch if I can implement it by myself.

[guicho271828]

Trivia-quasiquote uses fare-quasiquote which replaces readmacros.
But fare-quasiquote readtable must be activated. Like this in the test. https://github.com/guicho271828/trivia/blob/master/test/quasiquote.lisp

[guicho271828]

Oh I misunderstood your question.

Ok I see. It is probably necessary to see how fare-quasiquote expands `(,a ,@b ,c).

It seems like it uses append, so the straightforward way will be to implement a pattern for append, as suggested in the error message.

[guicho271828]

So one approach would be to check the patterns inside, analyse, and signals a compile error if a deterministic interpretation is impossible.

To check the pattern inside, use defpattern-inline which are expanded before any other pattern expansion happens. Inline patterns are to normal patterns, just like macros are to functions. See https://github.com/guicho271828/trivia/wiki/Inline-Patterns NVM this is unrelated. forget about inline patterns

[zacque0]

Not reading the source code or anything, but I guess (,a ,@b ,c). expands to (append (list a) b (list c)).
For this case you can extract each element by (car obj), (butlast (cdr obj)), and (last obj) respectively, if you implement a heuristic rule.

I see.

This is incomplete in terms of logic programming, as it does not work when there are more than two ,@s, e.g., (,a ,@b ,@c ,d). Now there are no way to know the size of b and c in compile time, so compiling it into a pattern is impossible.

Oh, I didn't think about that. Right now, I think I'll use only a list pattern having at most one ,@, but at different position in a list.

A logic programming language like Prolog, which has backtracking and enumeration, would unify and iterate over every possible assignments of b and c for (,a ,@b ,@c ,d). For example, if the input is (1 2 3 4 5), then a=1, d=5, and b is any of (2 3 4) (2 3) (2) (), with c being (), (4), (3 4), (2 3 4) respectively.

As for two ,@ and above, maybe being able to specify a heuristic/policy might be helpful?

E.g. if we match (1 2 3 4 5) against the pattern (,a ,@b ,@c ,d) and evaluate (list a b c d):

1. for "first-greedy" approach, we get (1 (2 3 4) () 5)
2. for "last-greedy" approach, we get (1 () (2 3 4) 5)
3. for "distributed" approach, we get (1 (2) (3 4) 5).

Just an idea though.

So one approach would be to check the patterns inside, analyse, and signals a compile error if a deterministic interpretation is impossible.

Thanks. So if (,a ,@b ,c) expands to (append (list a) b (list c)), then checking for at most one atom in the append arguments might work. Then, I'm not sure where to go from here. I'll need to read deeper into the doc/code.

[guicho271828]

As for two ,@ and above, maybe being able to specify a heuristic/policy might be helpful?

I do not think a pattern matching library should implement unification and backtracking. Pattern matching should finish in constant time. Otherwise I would make a unification library or logic programming library independently or as an extension of Trivia.

[guicho271828]

For two ,@ s, it should emit a compile-time error.

[zacque0]

I do not think a pattern matching library should implement unification and backtracking. Pattern matching should finish in constant time. Otherwise I would make a unification library or logic programming library independently or as an extension of Trivia.

I see. My knowledge in this area is very lacking. Thanks for letting me know!

For two ,@ s, it should emit a compile-time error.

Ok.