Better lambdas if argument types infer from argument usage

Topics: General
Feb 28, 2014 at 6:55 PM
Edited Feb 28, 2014 at 6:55 PM
You can read the brief description and discussion here: https://typescript.codeplex.com/workitem/2208

At stake is the brevity of lambdas in TypeScript. As Ryan demonstrates, a general solution for type inference is prohibitively time expensive to include in the compiler due to overloading and subtyping. However, I posit a weaker algorithm that is low cost and still applicable to a majority of practical cases.

Ryan requested that the discussion continue on the forum so that others could weigh in. If you have insight on this problem please provide what additional information you can to progress resolution of this issue.

I will start with an addition to the original algorithm I posited that addresses an inconsistency. The following code sample demonstrates the problem.
function overload(x:number, y:number) {};
function overload(x:string, y:string) {};

function f(x, y) {
  overload(x, y);
  var z: number = y;
}
The original algorithm visits the implicitly typed parameters in some pre-determined order. For sake of this example, let us assume that order is from left to right. If this order is taken, x is not inferred, because the candidate overloads for overload is [[number, number], [string, string]] and therefore the independent candidate type set (I will abbreciate to ICTS) for x is {number, string}.

However, if we choose a right-to-left order, the type of x is inferred as number. This is because the ICTS for y is determined as {number}, and therefore the candidate overloads for overload is reduced to [[number, number]], and thus the ICTS for x is reduced to {number}.

Therefore, to solve the accident of ordering which parameter is inferred first, the inference algorithm can be changed slightly.
inferParams(scope, params):
  return Foreach param (x) in params:
    Let us = [u | u <- foreach usage of x in scope:
                         the independent set of candidate types for x]
    Let ts = intersect us
    return Case ts:
      {t}: (x, TypeIs t)
      {} : (x, NoType)
      otherwise: (x, AmbigType)

inferParamsFixpoint(scope, params):
  Let r = inferParams(scope, params)
  Let (typeIs, noType, ambigType) = (extractTypeIs(r), extractNoType(r),
                                                      extractAmbigType(r))
  Let scope' = applyToScope(typeIs, scope)
  return Case typeIs:
    []: (scope', r)
    otherwise: typeIs ++ noType ++ inferParamsFixPoint(scope', ambigType)
The new addition is inferParamsFixpoint which repeatedly retries to infer parameters thought to be ambiguous (non-empty, non-singleton ICTS) as long as some parameters are being inferred. Applied to the example scenario, x is first ambiguous and so ends up in the ambigType list, whereas y is inferred as ends up in the typeIs list. Because typeIs is non-empty, inferParamsFixPoint recurses on the ambigType list with the new scope information resulting from the inference of y. Therefore on the second call to inferParams, x is successfully inferred. inferParamsFixpoint will recurse once more on the empty ambigType list, find that no new parameters were inferred (typeIs is empty), and terminate.

The pseudo-code that I have used is a made-up syntax but assumes a functional style. If this code is unclear I can instead mock an implementation in some real language like TypeScript or Haskell.

Thanks for your time and help.