[Solved]: Algorithm for type conversion / signature matching

Problem Detail: 

I'm working on an expression typing system and looking for insights on what algorithms may be available which solve my problem -- or a proof that its complexity is too high to be reasonable to implement. The problem is defined below.

I have a set of types which form a directed graph $T = (V,E)$ (assume no cycles). This graph represents the allowed type conversions in a language. For example an edge $e_i = v_1 \rightarrow v_2$ indicates that $v_1$ can be implicitly converted to type $v_2$.

I have a set of parameter types for a function expressed as a set $P = { p_1 ... p_n : p_i ∈ V }$. I also have a list of functions $F$ that might be applicable at this point. Each function has a signature (the types it accepts) $F_j = { f_1 ... f_n : t_i ∈ V }$.

The goal is to use a series of type conversions allowed by $T$ to convert $P$ into a signature compatible with any function in $F$. Conversion means moving along an edge in the graph to another type. Compatible means the converted parameter types match the function types.

If each conversion has a cost of 1, which function, if selected, has the minimum total conversion cost for all parameters?

---

A very simple example: Assume we have a graph of types integer -> real -> complex. Our parameters have the types { integer, real }. We have a function with types { complex, complex }. The first integer takes two conversion to match complex, and the real takes one conversion, for a total cost of three. We have another function with types { real, real }. This has a cost of one and is thus the better match.

---

My initial idea is to treat the search as a path through a graph and use a modified A* algorithm. Each of the possible functions is a goal in that graph, and each path between nodes represents the conversion of a single parameter type. With even a modest number of allowed type conversions however this becomes very inefficient.

Asked By : edA-qa mort-ora-y

Answered By : sxu

I would suggest first solving the all-pairs shortest distance problem on the graph $T$ (or at least the single source version for each $p_i$ as the source) using standard approaches. Then, for each function signature $F_j=f_1,\dots,f_n$, compute $\sum_{i=1}^nd(p_i,f_i)$, where $d(p,f)$ is the distance between $p$ and $f$ (which can be infinite if $f$ is not reachable from $p$), then take the function that achieves the minimum. You should be able to do this in $O(|V|^3+nm)$ if you have $n$ parameters and $m$ functions.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2677