Improved inference for loop / recur

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.

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:

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.

Environment

None

Activity

Show:
David Nolen
November 22, 2018, 10:07 AM

Makes sense but can we get some tests?

Mike Fikes
November 23, 2018, 8:29 PM

CLJS-2873-1.patch adds tests.

Mike Fikes
November 23, 2018, 11:05 PM

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.

Mike Fikes
November 24, 2018, 2:09 AM

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.

David Nolen
November 24, 2018, 5:30 PM
Completed

Assignee

Mike Fikes

Reporter

Mike Fikes

Labels

None

Approval

None

Patch

Code and Test

Priority

Major
Configure