ClojureScript

Improved inference for loop / recur

Details

  • Type: Enhancement Enhancement
  • Status: Closed Closed
  • Priority: Major Major
  • Resolution: Completed
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None
  • Patch:
    Code and Test

Description

Currently, type inference in loop / recur is done as if a let construct were being used. Critically, the inferred types of the bound locals is assumed to be that implied by their inits, with the types of the recur expressions not being considered.

CLJS-1561 attempts to address this situation by warning if the code recurs with a different type. But, it is common and legal practice to have code that results in the type varying. (For example, initial bindings might be nil, with things breaking out of the loop / recur when a non-nil value is found.)

Perhaps the right thing to do is to infer that the types of each local are the sum of the types derived from their inits and the types of the recur expressions.

As a concrete example, consider this code:

(loop [x nil]
  (let [y (and x 3)]
    (if y
      y
      (recur "a"))))

Currently x is inferred to be of type clj-nil. A consequence is that (with CLJS-2869) y will initially be inferred to be of type clj-nil, and, since it is the return value, the entire loop / recur is inferred to be of type clj-nil.

Instead, perhaps x should be inferred to be of type #{clj-nil string} by taking the sum of the types inferred by the init and the recur expression. Then (with CLJS-2869), y would be inferred to be of type number and the entire loop / recur would be correctly inferred to be of type number.

In order to infer the types of the recur expressions, you need to start with the types initially inferred by the initial bindings. I'd propose that this produce an initial set of types, and then the entire thing can be analyzed again (using the sum types), to deduce the correct types. Then, after this second analysis, a second sum can be done, and if it differs you could either do additional analysis cycles until things converge, or (in the name of compiler perf), just throw in the towel for non-converging situations and conclude that the type is any.

The same arguments above would apply to function arguments when recur is used, but unhinted arguments start off as type any and therefore cannot grow to encompass more types, and hinted arguments have their types specified.

  1. CLJS-2873-0.patch
    05/Sep/18 5:34 PM
    5 kB
    Mike Fikes
  2. CLJS-2873-1.patch
    23/Nov/18 2:29 PM
    7 kB
    Mike Fikes
  3. CLJS-2873-2.patch
    23/Nov/18 5:05 PM
    7 kB
    Mike Fikes
  4. CLJS-2873-3.patch
    23/Nov/18 8:09 PM
    7 kB
    Mike Fikes

Activity

Hide
David Nolen added a comment -

Makes sense but can we get some tests?

Show
David Nolen added a comment - Makes sense but can we get some tests?
Hide
Mike Fikes added a comment -

CLJS-2873-1.patch adds tests.

Show
Mike Fikes added a comment - CLJS-2873-1.patch adds tests.
Hide
Mike Fikes added a comment -

CLJS-2873-2.patch is the same CLJS-2873-1.patch except the it removes a commented binding that was inadvertently left in the code during dev.

Show
Mike Fikes added a comment - CLJS-2873-2.patch is the same CLJS-2873-1.patch except the it removes a commented binding that was inadvertently left in the code during dev.
Hide
Mike Fikes added a comment -

CLJS-2873-3.patch cleans up the code a little and addresses perf: While CLJS-2873-2.patch yields a speedup of 0.94 when compiling the Coal Mine corpus, CLJS-2873-3.patch improves this to a speedup of 0.97.

Show
Mike Fikes added a comment - CLJS-2873-3.patch cleans up the code a little and addresses perf: While CLJS-2873-2.patch yields a speedup of 0.94 when compiling the Coal Mine corpus, CLJS-2873-3.patch improves this to a speedup of 0.97.

People

Vote (0)
Watch (0)

Dates

  • Created:
    Updated:
    Resolved: