[Cython] CF based type inference
Hi! Recently I've started work on new type inference engine. Now it's almost ready and I want to discuss it. It works like this: first infer type for each assignment then for whole entry. It has some advantages over previous algorithm: - it handles assignment cycles, see test_swap() for example - it can infer type using info about assignments on the whole entry: a = 1 b = a a = "str" a is python object and b is integer. Here are testcases that show some new cases it can solve: https://github.com/vitek/cython /blob/_type_inference_new/tests/run/type_inference_new.pyx Here is branch for it https://github.com/vitek/cython /tree/_type_inference_new -- vitja. ___ cython-devel mailing list cython-devel@python.org http://mail.python.org/mailman/listinfo/cython-devel
Re: [Cython] CF based type inference
On 21 May 2013 11:26, Vitja Makarov wrote: > Hi! > > Recently I've started work on new type inference engine. Now it's almost > ready and I want to discuss it. > > It works like this: first infer type for each assignment then for whole > entry. It has some advantages over previous algorithm: > - it handles assignment cycles, see test_swap() for example > - it can infer type using info about assignments on the whole entry: > > a = 1 > b = a > a = "str" > > a is python object and b is integer. > > Here are testcases that show some new cases it can solve: > https://github.com/vitek/cython/blob/_type_inference_new/tests/run/type_inference_new.pyx > > Here is branch for it > https://github.com/vitek/cython/tree/_type_inference_new > > -- > vitja. > > ___ > cython-devel mailing list > cython-devel@python.org > http://mail.python.org/mailman/listinfo/cython-devel > Hey Vitja, Cool! How do you want to handle variable merge at control flow joins? Would you promote (backwards incompatible), use a union type, or object? E.g. what does this result in: x = 0 for i in range(N): x += 0.2 * i print typeof(x) ___ cython-devel mailing list cython-devel@python.org http://mail.python.org/mailman/listinfo/cython-devel
Re: [Cython] CF based type inference
2013/5/21 mark florisson > On 21 May 2013 11:26, Vitja Makarov wrote: > > Hi! > > > > Recently I've started work on new type inference engine. Now it's almost > > ready and I want to discuss it. > > > > It works like this: first infer type for each assignment then for whole > > entry. It has some advantages over previous algorithm: > > - it handles assignment cycles, see test_swap() for example > > - it can infer type using info about assignments on the whole entry: > > > > a = 1 > > b = a > > a = "str" > > > > a is python object and b is integer. > > > > Here are testcases that show some new cases it can solve: > > > https://github.com/vitek/cython/blob/_type_inference_new/tests/run/type_inference_new.pyx > > > > Here is branch for it > > https://github.com/vitek/cython/tree/_type_inference_new > > > > -- > > vitja. > > > > ___ > > cython-devel mailing list > > cython-devel@python.org > > http://mail.python.org/mailman/listinfo/cython-devel > > > > Hey Vitja, > > Cool! How do you want to handle variable merge at control flow joins? > Would you promote (backwards incompatible), use a union type, or > object? E.g. what does this result in: > > x = 0 > for i in range(N): > x += 0.2 * i > print typeof(x) Hi Mark, Nothing changed in your example old algorithm was able to handle this "simple" kind of cycles as well as new one: def foo(int N): x = 0 for i in range(N): x += 0.2 * i print typeof(x) So this function (not that N is an integer here) will print 'dobule'. With new algorithm we can go further: def foo(int N): x = 1 y = 0 for i in range(N): x = x * 0.1 + y * 0.2 y = x * 0.3 + y * 0.4 print typeof(x), typeof(y) Here both x and y will be inferred as double -- vitja. ___ cython-devel mailing list cython-devel@python.org http://mail.python.org/mailman/listinfo/cython-devel
Re: [Cython] CF based type inference
On 21 May 2013 14:14, Vitja Makarov wrote: > > > > 2013/5/21 mark florisson >> >> On 21 May 2013 11:26, Vitja Makarov wrote: >> > Hi! >> > >> > Recently I've started work on new type inference engine. Now it's almost >> > ready and I want to discuss it. >> > >> > It works like this: first infer type for each assignment then for whole >> > entry. It has some advantages over previous algorithm: >> > - it handles assignment cycles, see test_swap() for example >> > - it can infer type using info about assignments on the whole entry: >> > >> > a = 1 >> > b = a >> > a = "str" >> > >> > a is python object and b is integer. >> > >> > Here are testcases that show some new cases it can solve: >> > >> > https://github.com/vitek/cython/blob/_type_inference_new/tests/run/type_inference_new.pyx >> > >> > Here is branch for it >> > https://github.com/vitek/cython/tree/_type_inference_new >> > >> > -- >> > vitja. >> > >> > ___ >> > cython-devel mailing list >> > cython-devel@python.org >> > http://mail.python.org/mailman/listinfo/cython-devel >> > >> >> Hey Vitja, >> >> Cool! How do you want to handle variable merge at control flow joins? >> Would you promote (backwards incompatible), use a union type, or >> object? E.g. what does this result in: >> >> x = 0 >> for i in range(N): >> x += 0.2 * i >> print typeof(x) > > > Hi Mark, > > Nothing changed in your example old algorithm was able to handle this > "simple" kind of cycles as well as new one: > > def foo(int N): > x = 0 > for i in range(N): > x += 0.2 * i > print typeof(x) > > So this function (not that N is an integer here) will print 'dobule'. > > With new algorithm we can go further: > > def foo(int N): > x = 1 > y = 0 > for i in range(N): > x = x * 0.1 + y * 0.2 > y = x * 0.3 + y * 0.4 > print typeof(x), typeof(y) > > Here both x and y will be inferred as double > Ok, so I assume it promotes the incoming types (all reaching definitions)? If N == 0, then when using objects you get an int, otherwise a double. What happens when the reaching types cannot be promoted together? Do you fall back to object? > -- > vitja. > > ___ > cython-devel mailing list > cython-devel@python.org > http://mail.python.org/mailman/listinfo/cython-devel > ___ cython-devel mailing list cython-devel@python.org http://mail.python.org/mailman/listinfo/cython-devel
Re: [Cython] CF based type inference
2013/5/21 mark florisson > On 21 May 2013 14:14, Vitja Makarov wrote: > > > > > > > > 2013/5/21 mark florisson > >> > >> On 21 May 2013 11:26, Vitja Makarov wrote: > >> > Hi! > >> > > >> > Recently I've started work on new type inference engine. Now it's > almost > >> > ready and I want to discuss it. > >> > > >> > It works like this: first infer type for each assignment then for > whole > >> > entry. It has some advantages over previous algorithm: > >> > - it handles assignment cycles, see test_swap() for example > >> > - it can infer type using info about assignments on the whole entry: > >> > > >> > a = 1 > >> > b = a > >> > a = "str" > >> > > >> > a is python object and b is integer. > >> > > >> > Here are testcases that show some new cases it can solve: > >> > > >> > > https://github.com/vitek/cython/blob/_type_inference_new/tests/run/type_inference_new.pyx > >> > > >> > Here is branch for it > >> > https://github.com/vitek/cython/tree/_type_inference_new > >> > > >> > -- > >> > vitja. > >> > > >> > ___ > >> > cython-devel mailing list > >> > cython-devel@python.org > >> > http://mail.python.org/mailman/listinfo/cython-devel > >> > > >> > >> Hey Vitja, > >> > >> Cool! How do you want to handle variable merge at control flow joins? > >> Would you promote (backwards incompatible), use a union type, or > >> object? E.g. what does this result in: > >> > >> x = 0 > >> for i in range(N): > >> x += 0.2 * i > >> print typeof(x) > > > > > > Hi Mark, > > > > Nothing changed in your example old algorithm was able to handle this > > "simple" kind of cycles as well as new one: > > > > def foo(int N): > > x = 0 > > for i in range(N): > > x += 0.2 * i > > print typeof(x) > > > > So this function (not that N is an integer here) will print 'dobule'. > > > > With new algorithm we can go further: > > > > def foo(int N): > > x = 1 > > y = 0 > > for i in range(N): > > x = x * 0.1 + y * 0.2 > > y = x * 0.3 + y * 0.4 > > print typeof(x), typeof(y) > > > > Here both x and y will be inferred as double > > > > Ok, so I assume it promotes the incoming types (all reaching > definitions)? If N == 0, then when using objects you get an int, > otherwise a double. What happens when the reaching types cannot be > promoted together? Do you fall back to object? Can you provide example please? And yes if type cannot be inferred it fallback to object. -- vitja. ___ cython-devel mailing list cython-devel@python.org http://mail.python.org/mailman/listinfo/cython-devel
Re: [Cython] CF based type inference
On 21 May 2013 14:41, Vitja Makarov wrote: > > > > 2013/5/21 mark florisson >> >> On 21 May 2013 14:14, Vitja Makarov wrote: >> > >> > >> > >> > 2013/5/21 mark florisson >> >> >> >> On 21 May 2013 11:26, Vitja Makarov wrote: >> >> > Hi! >> >> > >> >> > Recently I've started work on new type inference engine. Now it's >> >> > almost >> >> > ready and I want to discuss it. >> >> > >> >> > It works like this: first infer type for each assignment then for >> >> > whole >> >> > entry. It has some advantages over previous algorithm: >> >> > - it handles assignment cycles, see test_swap() for example >> >> > - it can infer type using info about assignments on the whole entry: >> >> > >> >> > a = 1 >> >> > b = a >> >> > a = "str" >> >> > >> >> > a is python object and b is integer. >> >> > >> >> > Here are testcases that show some new cases it can solve: >> >> > >> >> > >> >> > https://github.com/vitek/cython/blob/_type_inference_new/tests/run/type_inference_new.pyx >> >> > >> >> > Here is branch for it >> >> > https://github.com/vitek/cython/tree/_type_inference_new >> >> > >> >> > -- >> >> > vitja. >> >> > >> >> > ___ >> >> > cython-devel mailing list >> >> > cython-devel@python.org >> >> > http://mail.python.org/mailman/listinfo/cython-devel >> >> > >> >> >> >> Hey Vitja, >> >> >> >> Cool! How do you want to handle variable merge at control flow joins? >> >> Would you promote (backwards incompatible), use a union type, or >> >> object? E.g. what does this result in: >> >> >> >> x = 0 >> >> for i in range(N): >> >> x += 0.2 * i >> >> print typeof(x) >> > >> > >> > Hi Mark, >> > >> > Nothing changed in your example old algorithm was able to handle this >> > "simple" kind of cycles as well as new one: >> > >> > def foo(int N): >> > x = 0 >> > for i in range(N): >> > x += 0.2 * i >> > print typeof(x) >> > >> > So this function (not that N is an integer here) will print 'dobule'. >> > >> > With new algorithm we can go further: >> > >> > def foo(int N): >> > x = 1 >> > y = 0 >> > for i in range(N): >> > x = x * 0.1 + y * 0.2 >> > y = x * 0.3 + y * 0.4 >> > print typeof(x), typeof(y) >> > >> > Here both x and y will be inferred as double >> > >> >> Ok, so I assume it promotes the incoming types (all reaching >> definitions)? If N == 0, then when using objects you get an int, >> otherwise a double. What happens when the reaching types cannot be >> promoted together? Do you fall back to object? > > > Can you provide example please? And yes if type cannot be inferred it > fallback to object. > Sure, e.g. if cond: x = 2 else: x = "hello" use(x) A tricky one is this: try: x = f() # let's say 'double' x = g() # let's say 'string' finally: print typeof(x) # what does this print if 'f' can raise an exception? > > -- > vitja. > > ___ > cython-devel mailing list > cython-devel@python.org > http://mail.python.org/mailman/listinfo/cython-devel > ___ cython-devel mailing list cython-devel@python.org http://mail.python.org/mailman/listinfo/cython-devel
Re: [Cython] CF based type inference
2013/5/21 mark florisson > On 21 May 2013 14:41, Vitja Makarov wrote: > > > > > > > > 2013/5/21 mark florisson > >> > >> On 21 May 2013 14:14, Vitja Makarov wrote: > >> > > >> > > >> > > >> > 2013/5/21 mark florisson > >> >> > >> >> On 21 May 2013 11:26, Vitja Makarov wrote: > >> >> > Hi! > >> >> > > >> >> > Recently I've started work on new type inference engine. Now it's > >> >> > almost > >> >> > ready and I want to discuss it. > >> >> > > >> >> > It works like this: first infer type for each assignment then for > >> >> > whole > >> >> > entry. It has some advantages over previous algorithm: > >> >> > - it handles assignment cycles, see test_swap() for example > >> >> > - it can infer type using info about assignments on the whole > entry: > >> >> > > >> >> > a = 1 > >> >> > b = a > >> >> > a = "str" > >> >> > > >> >> > a is python object and b is integer. > >> >> > > >> >> > Here are testcases that show some new cases it can solve: > >> >> > > >> >> > > >> >> > > https://github.com/vitek/cython/blob/_type_inference_new/tests/run/type_inference_new.pyx > >> >> > > >> >> > Here is branch for it > >> >> > https://github.com/vitek/cython/tree/_type_inference_new > >> >> > > >> >> > -- > >> >> > vitja. > >> >> > > >> >> > ___ > >> >> > cython-devel mailing list > >> >> > cython-devel@python.org > >> >> > http://mail.python.org/mailman/listinfo/cython-devel > >> >> > > >> >> > >> >> Hey Vitja, > >> >> > >> >> Cool! How do you want to handle variable merge at control flow joins? > >> >> Would you promote (backwards incompatible), use a union type, or > >> >> object? E.g. what does this result in: > >> >> > >> >> x = 0 > >> >> for i in range(N): > >> >> x += 0.2 * i > >> >> print typeof(x) > >> > > >> > > >> > Hi Mark, > >> > > >> > Nothing changed in your example old algorithm was able to handle this > >> > "simple" kind of cycles as well as new one: > >> > > >> > def foo(int N): > >> > x = 0 > >> > for i in range(N): > >> > x += 0.2 * i > >> > print typeof(x) > >> > > >> > So this function (not that N is an integer here) will print 'dobule'. > >> > > >> > With new algorithm we can go further: > >> > > >> > def foo(int N): > >> > x = 1 > >> > y = 0 > >> > for i in range(N): > >> > x = x * 0.1 + y * 0.2 > >> > y = x * 0.3 + y * 0.4 > >> > print typeof(x), typeof(y) > >> > > >> > Here both x and y will be inferred as double > >> > > >> > >> Ok, so I assume it promotes the incoming types (all reaching > >> definitions)? If N == 0, then when using objects you get an int, > >> otherwise a double. What happens when the reaching types cannot be > >> promoted together? Do you fall back to object? > > > > > > Can you provide example please? And yes if type cannot be inferred it > > fallback to object. > > > > Sure, e.g. > > if cond: > x = 2 > else: > x = "hello" > use(x) > > x will be of object type here. > A tricky one is this: > > try: > x = f() # let's say 'double' > x = g() # let's say 'string' > finally: > print typeof(x) # what does this print if 'f' can raise an > exception? > > As well as here. Can it raise exception or not doesn't matter here since typeof() returns type of entry and it's calculated at compile time. -- vitja. ___ cython-devel mailing list cython-devel@python.org http://mail.python.org/mailman/listinfo/cython-devel
