Improve treatment of ellipsis in `define-judgment-form`

[leafac]

Original text by @rfindler.

In general, this aspect of the handling of ellipses is implemented by the racket/datum library (the same library that syntax-case uses). It can cope with writing things like this:

((a b) ...)

where a is bound in some pattern like this (a ...) but b is just b with no ellipsis around it. It handles this by duplicating b, once for each a. That's what we'd like to happen here too. But the ellipses that are "between" premises in a define-judgment-form are not handled by just giving them to the racket/datum library. Instead, Redex is doing some of its own work before it can hand them off. And that work is what is raising the syntax error in this case.

So: best case, we figure out a more relaxed well-formedness check to implement in define-judgment-form and this example just starts working. Worse case, we need to change how the "inter premise" ellipses handling is implemented. I'm not sure which case we are in.

Test case

#lang racket
(require redex/reduction-semantics)

(define-language L
  (τ ::= n b)
  (e ::= (amb τ e ...) natural #t #f))

(define-judgment-form L
  #:mode (type I O)
  [----------------
   (type natural n)]

  [-----------
   (type #t b)]

  [-----------
   (type #f b)]

  [(type e τ) ...
   ----------------------
   (type (amb τ e ...) τ)])

(test-judgment-holds (type (amb b #f #t) b))
(test-judgment-holds (type (amb n 0 1) n))
(test-equal (judgment-holds (type (amb n 0 #f) any)) #f)
(test-equal (judgment-holds (type (amb n #t #t 11 #f) any)) #f)

Error

unsaved editor:21:14: define-judgment-form: found the same binder, τ, at different depths, 1 and 0 at: τ

References

• Initial discussion.

[leafac]

I disabled check-clauses in judgement-form.rkt by comment out its body and making it return rest. The error stays the same.

I went even further and redefined raise-syntax-error to a no-op in the scope of judgement-form.rkt. The error stays the same.

I think this rules out the "best case", i.e., a more relaxed well-formedness check isn't going to solve the problem. Do you agree?

In order to explore the "worst case", I believe I should start in compile-clause. There are many things in it that go over my head, so any directions from you are going to help a lot.

Thanks so much for the feedback, @rfindler 😄

[rfindler]

I think that the call that raises the error is this one:

https://github.com/racket/redex/blob/master/redex-lib/redex/private/judgment-form.rkt#L141

[leafac]

Of course, you are right. Disabling the check—i.e., returning cs instead of raising an error with raise-ellipsis-depth-error—changes the error message in the test to "syntax: missing ellipsis with pattern variable in template in: τ", referring to the τ that occurs outside amb in the conclusion of the rule. With that, the easy route has been definitely ruled, I think.

Now would be the time to understand the system a bit better to come up with a solution. I believe I'll need to change how the binding constraint is generated in the case at hand. When you said Redex uses racket/datum, did you mean syntax/datum? I'm studying now how it works.

Side question: When you are working on this, how do you debug? The Debugger in DrRacket fails right away, because the code fails in macro expansion at compile time. The Macro Stepper helps, by allowing me to see the macro expansions, but it is limited in that I can't, for example, set breakpoints.

Thank you!

[rfindler]

Yes, I meant syntax/datum! Thanks, duh.

When I'm working on this, I use the stacktrace information from syntax errors (that's how I pointed you to the line above) and I use printf debugging, and I combine that with some experience in knowing when things run in this code and just in Racket macros in general. Also I tried to work carefully with small input programs and test individual functions. But generally I don't think using the macro stepper or the debugger is probably what I would do for this particular problem. I think using the macro stepper might be helpful to you to figure out how some of the pieces of Redex fit together, tho. I mostly just try to use my memory for that job -- but the macro stepper is better than my memory and I should be using it more than I do.

[polux]

I was following the tutorial and found this discussion after hitting this issue. Is the following still the best way to answer question 6 for now?

[(types-exercise-6 Γ e t_2) ...
 (side-condition ,(andmap (curry equal? (term t_1)) (term (t_2 ...))))
 -------------------------
 (types-exercise-6 Γ (amb t_1 e ...) t_1)]

[rfindler]

I would probably define a judgment-form instead of using ,.

[polux]

Ack. I was merely copy-pasting this solution from the other thread but I guess my question was: is a side-condition the best solution for now? Sounds like the answer is yes. Thanks!

[rfindler]

I think a helper judgment form is superior to dipping back into Racket for this problem.

Robby

On Thu, May 28, 2020 at 8:56 AM Paul Brauner notifications@github.com wrote:

Ack. I was merely copy-pasting this solution from the other thread but I guess my question was: is a side-condition the best solution for now? Sounds like the answer is yes. Thanks!

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/racket/redex/issues/61#issuecomment-635365697, or unsubscribe https://github.com/notifications/unsubscribe-auth/AADBNMCUKY7Z2YHSPDB7W5TRTZUPPANCNFSM4CEBMU2A .

[polux]

Got it. Thanks.