[Cython] Type Inference: Inter Procedural Analysis

[Stefan Behnel]

Hi!

Thanks for working on this!

usama hameed schrieb am 29.12.2017 um 19:31:
> I recently suggested implementing Inter-Procedural Analysis to infer
> function types and made the following Github issue
> <https://github.com/cython/cython/issues/1893>, and I was advised to
> communicate on this channel.
> 
> I went through the code base, and have implemented a rudimentary type
> inference system with inter procedural analysis of function types and
> arguments, and have handled recursive cases. However, the code base needs
> to be cleaned up a lot and is quite buggy right now. Furthermore, I am
> pretty sure a lot of edge cases need to be handled, i.e. closures etc.

I guess you are referring to this repository:

https://github.com/usama54321/Cython/commits/master


> The reason I am sending out this email is to get some suggestions. Right
> now, the code I have written is pretty hacky, since the current code base
> of the project does not accommodate much flexibility to perform inter
> procedural analysis.

Interesting. Could you elaborate on what you found missing or badly
designed? Would be interesting to know for us.

Here are a couple of comments on your changes:

1) The functionality looks really nice. Since you weren't accustomed with
the code base before, it's understandable that things aren't perfectly
integrated with the existing architecture. That can be cleaned up.

2) I was surprised to see that you didn't git-clone the existing repository
but created a new one from a source copy instead. But that's probably ok
for getting started because (I think) you wrote the code experimentally and
didn't focus that much on ready-to-merge commits anyway. Also, you
accidentally added .pyc and .so files. Those shouldn't be under version
control. It would probably be best to start over from a fresh clone and
apply your changes as patch.

3) The commits are a bit difficult to follow because the commit comments
are essentially free of information. It would help if you had used them to
explain the steps you took and what your intentions were.

4) Is there a reason why you didn't merge the Graph building with the
control flow analysis in FlowControl.py?

5) I can't see any test code, but since you implemented this in multiple
iterations, I'm sure that you had test code on your side that you tried to
compile. Could you add some examples that show how this change improves
things? There are hints on writing tests in the hacker guide:

https://github.com/cython/cython/wiki/HackerGuide#getting-started

Specifically, look at the "*infer*.pyx" file tests in tests/run/. I think
it would be best to add a new one.


> I found an enhancement suggestion
> <https://github.com/cython/cython/wiki/enhancements-typeinference> on the
> GitHub project, and was wondering whether this should be done first in
> order to make a more flexible type inference system before trying to
> properly implement inter procedural analysis into the project.

Type inference was implemented long ago and has been improved a couple of
times since then. It's not perfect, but it's actually quite good and can
further be improved in gradual steps. Inter-procedural analysis seems like
one such improvement.


> I just started on this as part of a university course project, but I want
> to continue working on this. I am not really familiar with the project's
> development ecosystem, and it would be really helpful if I'm given some
> guidance.

It would certainly be great to have this feature added. Could you explain
some of your design decisions? That would help me understand what you did
and why, so that I can start giving advice on where to go from here.

Generally speaking, I think it would be good if we could make it reuse more
of the existing infrastructure for type inference and control flow
analysis. I would only want to diverge from those if you could convince me
that this feature is fundamentally independent from what's there, but that
would surprise me. Correct me if I'm wrong, but what I would expect is
basically an incremental type inference that (partially) re-infers
functions when their dependencies (i.e. the functions that they call)
change their return type. Was the incremental part here something that you
found difficult?

Stefan