core.typed

add HSequential type

Details

  • Type: Enhancement Enhancement
  • Status: Resolved Resolved
  • Priority: Minor Minor
  • Resolution: Completed
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None

Description

Hi, Ambrose

I've implemented part of HSequential as we discussed in CTYP-126.

But currently

(t/cf (fn [& y] (if (empty? y) nil (first y))))

will got Type error, saying

(I (HSequential [Any *]) clojure.core.typed/NonEmptyCount)

can't be applied to

(HSequential [x Any *])

it's easy to fix via adding special case in `upcast-to-HSequential` in patch, but this maybe not very general, I also think even `upcast-to-HSequential` isn't general at all.

How should I solve this error?

  1. ambrose-hsequential-v3-1.patch
    08/Apr/14 10:39 AM
    82 kB
    Ambrose Bonnaire-Sergeant
  2. ambrose-various-fixes.patch
    03/Apr/14 1:18 PM
    35 kB
    Ambrose Bonnaire-Sergeant
  3. hsequential.diff
    31/Mar/14 4:48 AM
    18 kB
    Di Xu
  4. hsequential-demo.diff
    03/Apr/14 9:59 AM
    20 kB
    Di Xu
  5. hsequential-v2.diff
    07/Apr/14 3:02 AM
    49 kB
    Di Xu
  6. hsequential-v3.diff
    08/Apr/14 9:06 AM
    70 kB
    Di Xu

Activity

Hide
Ambrose Bonnaire-Sergeant added a comment -

You should call subtype directly with those two types and add printlns until the culprit is obvious.

There's a nice sub? macro in c.c.t.test.core

There's a bug in your second subtype? case; the test should be (HSequential? s), not (HSequential? t).

Show
Ambrose Bonnaire-Sergeant added a comment - You should call subtype directly with those two types and add printlns until the culprit is obvious. There's a nice sub? macro in c.c.t.test.core There's a bug in your second subtype? case; the test should be (HSequential? s), not (HSequential? t).
Hide
Ambrose Bonnaire-Sergeant added a comment -

I believe if you fix the subtype case, the left hand side will have a CountRange that satisfies the right.

Show
Ambrose Bonnaire-Sergeant added a comment - I believe if you fix the subtype case, the left hand side will have a CountRange that satisfies the right.
Hide
Ambrose Bonnaire-Sergeant added a comment -

Hmm I see what you were trying to do. I suggest following HMap's subtyping.

Make `upcast-HSequential` which is [HSequential -> Type]. It always returns a slightly less accurate type, which is still useful to continue the subtyping check.

The subtyping case should test (HSequential? s) and then (subtype (upcast-HSequential s) t).

Show
Ambrose Bonnaire-Sergeant added a comment - Hmm I see what you were trying to do. I suggest following HMap's subtyping. Make `upcast-HSequential` which is [HSequential -> Type]. It always returns a slightly less accurate type, which is still useful to continue the subtyping check. The subtyping case should test (HSequential? s) and then (subtype (upcast-HSequential s) t).
Hide
Ambrose Bonnaire-Sergeant added a comment -

I think upcast-HSequential should do something like

(HSequential [Any])
=>
(I (t/Coll Any) clojure.lang.Sequential (ExactCount 1))

Show
Ambrose Bonnaire-Sergeant added a comment - I think upcast-HSequential should do something like (HSequential [Any]) => (I (t/Coll Any) clojure.lang.Sequential (ExactCount 1))
Hide
Ambrose Bonnaire-Sergeant added a comment -

A nice thing we can do with HSequential is move most of the custom logic for (subtype HVec HVec), (subtype HList HList) and (subtype HSeq HSeq) into one place.

All we need is {HVec,Hlist,HSeq}->HSequential functions, and then we can have subtyping cases like

(and (HVec? s) (HVec? t))
(subtype (HVec->HSequential s) (HVec->HSequential t))

This also applies to cs_gen.

Show
Ambrose Bonnaire-Sergeant added a comment - A nice thing we can do with HSequential is move most of the custom logic for (subtype HVec HVec), (subtype HList HList) and (subtype HSeq HSeq) into one place. All we need is {HVec,Hlist,HSeq}->HSequential functions, and then we can have subtyping cases like
(and (HVec? s) (HVec? t))
(subtype (HVec->HSequential s) (HVec->HSequential t))
This also applies to cs_gen.
Hide
Di Xu added a comment -

Or, could we add special handler in `In` to handle the case of intersection of HSequential and CountRange, like change (In (HSequential [a b c *]) (CountRange 1 5)) -> (HSequential [a b c c c]) and (In (HSequential [a *]) (CountRange 1)) -> (HSequential [a a *])

something like that?

Show
Di Xu added a comment - Or, could we add special handler in `In` to handle the case of intersection of HSequential and CountRange, like change (In (HSequential [a b c *]) (CountRange 1 5)) -> (HSequential [a b c c c]) and (In (HSequential [a *]) (CountRange 1)) -> (HSequential [a a *]) something like that?
Hide
Ambrose Bonnaire-Sergeant added a comment -

I'm not sure. The first example would actually be (U (HSequential [a b]) (HSequential [a b c]) (HSequential [a b c c]) (HSequential [a b c c c]).

It might generate very large types.

Either way the subtype style I described is still needed.

Show
Ambrose Bonnaire-Sergeant added a comment - I'm not sure. The first example would actually be (U (HSequential [a b]) (HSequential [a b c]) (HSequential [a b c c]) (HSequential [a b c c c]). It might generate very large types. Either way the subtype style I described is still needed.
Hide
Di Xu added a comment -

Well, I think we're talking about two different problem here, the problem you're talking about is how to compare HSequential with other type, the one I'm talking about is how to use CountRange to extends HSequential type, because

(HSequential [Any *])

can never be the subtype of

(HSequential [Any Any *])

, only when we put constraint that the count of first one is at least 1. Right?

So, I'll first extends `In` as I described here, and leave your solution to future. For the efficience consideration, I think it's not a big problem, because most CountRange just specified low bound as `empty?`, so we don't need to generate a large set very often.

Show
Di Xu added a comment - Well, I think we're talking about two different problem here, the problem you're talking about is how to compare HSequential with other type, the one I'm talking about is how to use CountRange to extends HSequential type, because
(HSequential [Any *])
can never be the subtype of
(HSequential [Any Any *])
, only when we put constraint that the count of first one is at least 1. Right? So, I'll first extends `In` as I described here, and leave your solution to future. For the efficience consideration, I think it's not a big problem, because most CountRange just specified low bound as `empty?`, so we don't need to generate a large set very often.
Hide
Ambrose Bonnaire-Sergeant added a comment -

I was responding that (HSequential [a b c *]) (CountRange 1 5)) -> (HSequential [a b c c c])
is unsound, and should be (U (HSequential [a b]) (HSequential [a b c]) (HSequential [a b c c]) (HSequential [a b c c c]).

Show
Ambrose Bonnaire-Sergeant added a comment - I was responding that (HSequential [a b c *]) (CountRange 1 5)) -> (HSequential [a b c c c]) is unsound, and should be (U (HSequential [a b]) (HSequential [a b c]) (HSequential [a b c c]) (HSequential [a b c c c]).
Hide
Ambrose Bonnaire-Sergeant added a comment - - edited

Perhaps a better idea is to add an extra field in HSequential/HList etc. for a CountRange. Then (HSequential [a b c *]) (CountRange 1 5)) -> (HSequential [a b c *] :count (CountRange 1 5))

That way there's no chance of generating massive types, and we can utilise that information in subtyping to simplify the HSequential at the last minute.

Show
Ambrose Bonnaire-Sergeant added a comment - - edited Perhaps a better idea is to add an extra field in HSequential/HList etc. for a CountRange. Then (HSequential [a b c *]) (CountRange 1 5)) -> (HSequential [a b c *] :count (CountRange 1 5)) That way there's no chance of generating massive types, and we can utilise that information in subtyping to simplify the HSequential at the last minute.
Hide
Di Xu added a comment -

Wow, that's a good idea. So when (> (:lower c) (count (:types t))) we should extends the types with (repeat (:rest t)), but I don't know what to do with drest. I will mark it unsupport.

There're a problem makes me complete lost. With hsequential-demo.diff patch, after changing the r/-hsequential into r/-hvec there'll be no problem testing

lein test :only clojure.core.typed.test.core/annotate-user-defined-ploydot

but after changing back to r/-hsequential, there'll be a type error. I don't know what I'm missing, I've debugged it for a whole day and still feel lost. I've greped the code that support HVec in fold_default.clj, frees.clj, promote_demote.clj and subst.clj. And copy the code to implement HSequential, but still got type error. I don't know what's going on here.

ps. the bug you mentioned in the first comment is not a bug, I was going to test if t is HSequential or not, and upcast s to HSequential if so, just like the {HVec,Hlist,HSeq}->HSequential you menntioned.

Show
Di Xu added a comment - Wow, that's a good idea. So when (> (:lower c) (count (:types t))) we should extends the types with (repeat (:rest t)), but I don't know what to do with drest. I will mark it unsupport. There're a problem makes me complete lost. With hsequential-demo.diff patch, after changing the r/-hsequential into r/-hvec there'll be no problem testing
lein test :only clojure.core.typed.test.core/annotate-user-defined-ploydot
but after changing back to r/-hsequential, there'll be a type error. I don't know what I'm missing, I've debugged it for a whole day and still feel lost. I've greped the code that support HVec in fold_default.clj, frees.clj, promote_demote.clj and subst.clj. And copy the code to implement HSequential, but still got type error. I don't know what's going on here. ps. the bug you mentioned in the first comment is not a bug, I was going to test if t is HSequential or not, and upcast s to HSequential if so, just like the {HVec,Hlist,HSeq}->HSequential you menntioned.
Hide
Ambrose Bonnaire-Sergeant added a comment - - edited

I found a bunch of (pre-existing) bugs and added a few cases you were missing. I started getting the same type error for HVec/HSequential; hopefully the attached patch will help you continue.

Show
Ambrose Bonnaire-Sergeant added a comment - - edited I found a bunch of (pre-existing) bugs and added a few cases you were missing. I started getting the same type error for HVec/HSequential; hopefully the attached patch will help you continue.
Hide
Di Xu added a comment -

Well, turns out we don't need CountRange to pass the test case, but we also can't pass it with `first`, because both function and arguments have free variable, so change the test case to concrete type.

Show
Di Xu added a comment - Well, turns out we don't need CountRange to pass the test case, but we also can't pass it with `first`, because both function and arguments have free variable, so change the test case to concrete type.
Hide
Ambrose Bonnaire-Sergeant added a comment -

The rest arguments of a function are actually ISeq's, not just Sequentials. We should be calling -hseq instead of -hsequential in the :fn check method.

If you `mvn test` you'll see what this breaks.

Next step:

  • add rest/drest to HSeq (and HList if you're enthusiastic)
  • change -hsequential to -hseq
Show
Ambrose Bonnaire-Sergeant added a comment - The rest arguments of a function are actually ISeq's, not just Sequentials. We should be calling -hseq instead of -hsequential in the :fn check method. If you `mvn test` you'll see what this breaks. Next step:
  • add rest/drest to HSeq (and HList if you're enthusiastic)
  • change -hsequential to -hseq
Hide
Di Xu added a comment -

added, but failed in core/mapentry-first-test, core/hvec-ops and core/variable-hvec-test

I think those cases is beyond my current ability, it involve infer type variable in HSequential.

also failed in clojure.core.typed.test.fail.recur-non-seq-rest and clojure.core.typed.test.fail.recur-empty-seq

I don't know why should these cases fail. And confused by check-recur, which requires rest-arg-type has at least one element.

Show
Di Xu added a comment - added, but failed in core/mapentry-first-test, core/hvec-ops and core/variable-hvec-test I think those cases is beyond my current ability, it involve infer type variable in HSequential. also failed in clojure.core.typed.test.fail.recur-non-seq-rest and clojure.core.typed.test.fail.recur-empty-seq I don't know why should these cases fail. And confused by check-recur, which requires rest-arg-type has at least one element.
Hide
Ambrose Bonnaire-Sergeant added a comment -

Thanks, having a look.

You've added a few subtyping cases that are unsound. I'll fix them in my next patch.

It's important that (subtype? S T) only returns true if we can insert S in all places T is accepted.

(subtype? (HVec [1]) (HSequential [1]))
;=> true

(subtype? (HSequential [1]) (HVec [1]))
;=> false

(subtype? (HList [1] (HSeq [1]))
;=> true

(subtype? (HSeq [1]) (HList [1]))
;=> false

Show
Ambrose Bonnaire-Sergeant added a comment - Thanks, having a look. You've added a few subtyping cases that are unsound. I'll fix them in my next patch. It's important that (subtype? S T) only returns true if we can insert S in all places T is accepted. (subtype? (HVec [1]) (HSequential [1])) ;=> true (subtype? (HSequential [1]) (HVec [1])) ;=> false (subtype? (HList [1] (HSeq [1])) ;=> true (subtype? (HSeq [1]) (HList [1])) ;=> false
Hide
Ambrose Bonnaire-Sergeant added a comment -

Added ambrose-hsequential-v3-1.patch

Should pass all the tests. Please try it out.

Show
Ambrose Bonnaire-Sergeant added a comment - Added ambrose-hsequential-v3-1.patch Should pass all the tests. Please try it out.
Hide
Di Xu added a comment -

Oh, right.. it's unsound to do that in subtype, I was foolish that moment, sorry.

It's seems that you solved (first [1 'a]) by

(and (r/RClass? S)
     ((some-fn r/HeterogeneousVector? r/HSequential?) T))
         (if-let [[Sv] (seq
                         (filter (some-fn r/HeterogeneousVector? r/HSequential?)
                                 (map c/fully-resolve-type (c/RClass-supers* S))))]

right?

Well, I think we could close this ticket now. It spend such long time

Show
Di Xu added a comment - Oh, right.. it's unsound to do that in subtype, I was foolish that moment, sorry. It's seems that you solved (first [1 'a]) by
(and (r/RClass? S)
     ((some-fn r/HeterogeneousVector? r/HSequential?) T))
         (if-let [[Sv] (seq
                         (filter (some-fn r/HeterogeneousVector? r/HSequential?)
                                 (map c/fully-resolve-type (c/RClass-supers* S))))]
right? Well, I think we could close this ticket now. It spend such long time
Hide
Ambrose Bonnaire-Sergeant added a comment -

Actually I believe I added some extra cases for (cs-gen HVec HSeq) to fix (first [1 'a]).

That particular addition fixed (cf (-> {:a 1} first second) Number), because AMapEntry has a HVec ancestor and we used to rely on `second` having a HVec arity. Now `second` has a HSequential arity, we want to trigger this case if there's a (cs-gen RClass HSequential), instead of just (cs-gen RClass HVec).

Fantastic work, I'll merge this soon.

Show
Ambrose Bonnaire-Sergeant added a comment - Actually I believe I added some extra cases for (cs-gen HVec HSeq) to fix (first [1 'a]). That particular addition fixed (cf (-> {:a 1} first second) Number), because AMapEntry has a HVec ancestor and we used to rely on `second` having a HVec arity. Now `second` has a HSequential arity, we want to trigger this case if there's a (cs-gen RClass HSequential), instead of just (cs-gen RClass HVec). Fantastic work, I'll merge this soon.
Hide
Ambrose Bonnaire-Sergeant added a comment -

Merged.

Show
Ambrose Bonnaire-Sergeant added a comment - Merged.

People

Vote (0)
Watch (0)

Dates

  • Created:
    Updated:
    Resolved: