[racket] non-terminating type check for typed racket

30 minutes ago, Danny Yoo wrote:
> 
> diff --git a/collects/typed-scheme/types/filter-ops.rkt
> b/collects/typed-scheme/types/filter-ops.rkt
> index 2d24753..3786840 100644
> --- a/collects/typed-scheme/types/filter-ops.rkt
> +++ b/collects/typed-scheme/types/filter-ops.rkt
> @@ -132,7 +132,11 @@
>      (case-lambda [() -top]
>                   [(f) f]
>                   [fs (make-AndFilter fs)]))
> -  (let loop ([fs (remove-duplicates args filter-equal?)] [result null])
> +  (let loop ([fs (time (begin (displayln (length args))
> +                             ;; Subtle: remove-duplicates appears not to use
> +                             ;; a fast hashtable unless #:key is defined and
> +                             ;; the comparator is either eq? or equal?.
> +                             (remove-duplicates args equal? #:key
> Rep-seq)))] [result null])
>      (if (null? fs)
>          (match result
>            [(list) -top]

The comment is wrong -- the key argument isn't even mentioned in the
code that decides whether to construct a hash table or not.  Also, the
restriction on the comparator should be obvious -- a generic hash
table would be more complicated to do and the costs would be different
(therefore deciding when to use one).

But in the TR case the transformation seems fine because
`filter-equal?' is defined as a simple

  (define (filter-equal? a b) (= (Rep-seq a) (Rep-seq b)))

Sam/Vincent: that's probably a good thing to do, and even better --
get rid of `filter-equal?' so it's easier to use the seq directly.
(IIUC, it's the thing that has efficiency as its whole point.)  A
quick grep finds this loop:

  (for/or ([f (in-list result)]) (or (filter-equal? f t) (implied-atomic? t f)))

which could also be improved if the -seq of `t' is taken only once.

And one more point -- I see this:

  (define-struct Rep (seq free-vars free-idxs stx) #:transparent)
  [...]
  (p/c (struct Rep ([seq exact-nonnegative-integer?] 
                    [free-vars (hash/c symbol? variance?)]                   
                    [free-idxs (hash/c symbol? variance?)]
                    [stx (or/c #f syntax?)]))
       [replace-syntax (Rep? syntax? . -> . Rep?)])

Assuming that `p/c' is (a bad name for) `provide/contract', then why
is this used by internal TR code??  Sounds lik a very bad idea for
something as primitive as that.

Danny: if my guess is correct, you'll get another speedup if you use
`Type-seq' which is the unconracted version.

(That also seems like a bad name -- if I knew that both were
available, I'd expect `Rep-seq' to be the one that knows about the
representation and therefore the faster one...  But since this is all
TR internals, I think that it shouldn't use contracts at that level.)

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                    http://barzilay.org/                   Maze is Life!