5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This seems good. Though it looks expensive I believe the $O(|V|^3)$ part only has to be done once (I can reuse that result for all matching). Plus in practice the type graph will be highly disconnected, making it even faster. $\endgroup$ – edA-qa mort-ora-y Jul 11 '12 at 3:51
  • $\begingroup$ @edA-qamort-ora-y You are right, corrected my answer. $\endgroup$ – sxu Jul 11 '12 at 17:58
  • $\begingroup$ I think the reuse can even be extended further. Since T is static for an entire program (any number of P/F combinations), this high cost only has to be paid once, regardless of how much matching we need to do. $\endgroup$ – edA-qa mort-ora-y Jul 12 '12 at 1:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.