enhancements compiledducktyping
- Using a (partially) strongly typed language naturally lends itself to wanting overloaded methods for speedups etc. One wants to be able to call "max" for finding the maximum both of two ints and two floats, without having to convert the ints and floats to slow Python objects first.
- There are issues like the
__getitem__operator; which depending on the parameters will either return a slice (new array/list) or a specific item (preferably of a native type). Strongly typing it is still wanted for speed...- An equivalent to C macros would be nice. Inline functions doesn't work the same way because parameters must either have a specific type or go through
objectconversion. The C++ solution is a "templated inline function", this requires sophisticated template support though.
I have a very definite proposal for syntax that I'm going to be persistent about, but that is a seperate discussion which should be dealt with seperately. For the sake of the discussion I'll therefore introduce the keyword duckdef.
duckdef operates the same way as cdef, except for when a type is not specified (for a parameter or the return value). While the default type in cdef and def signatures is object, leaving the type unspecified for duckdef basically means "fill inn whatever is needed"; i.e. the caller of the function decides the types.
This is implemented by creating a duplicate of the method (and mangle the names) for each combination of parameter types and return values. It would be possible to inline the contents of the function instead, however I strongly believe this is a seperate issue that should be treated orthogonally to this one (ask for a full explanation; I did think this through.)
Example:
#!python
duckdef max(a, b): return a if a > b else b
cdef clientcode():
cdef float x = ..., y = ..., z
cdef int i = ..., j = ..., k
z = max(x, y) # float, float, float
k = max(i, j) # int, int, int
max(x, j) # void, float, int
print max(x, i) # object, float, intThis will have almost exactly the behaviour of the code below (ie with the exception of variable namespaces):
#!python
cdef float max_1(float a, float b): return a if a > b else b
cdef int max_2(int a, int b): return a if a > b else b
cdef void max_3(int a, int b):
# Discarded return type is a bit special; we will make modifications
# to the function then (ie not raising error, but changing behaviour).
# Any expressions in return statements will be evaluated but discarded.
a if a > b else b
return
cdef object max_4(float a, int b): return a if a > b else b
...
cdef clientcode()
cdef float x = ..., y = ..., z
cdef int i = ..., j = ..., k
z = max_1(x, y)
k = max_2(i, j)
max_3(i, j)
print max_4(x, i)Let's do this:
#!python
duckdef max(a, b): return a if a > b else b
cdef clientcode():
cdef int i = 1, j = 2
cdef object o = 1, p = 2
cdef char* r1 = max(i, j) # char*, int, int
cdef char* r2 = max(o, p) # char*, object, objectNow, the first call will obviously result in a compile-time error; specifically the return statement in max will complain because the expression can not be coerced to char*. However, the actual problem is in the calling function (the writer of "max" didn't intend for "char*" to be a possible return type).
One crucial part of a nice implementation of this scheme is therefore to give this error message in a nice way, indicating that the problem could both be in the callsite and function definition site.
The appropriate analogy at this time is how this would happen with Python code -- a run-time error would have happened somewhere, and if that was deep in a chain and happened because an object of wrong type was passed in a long way up, one has the call stack to look at. So, compile-time errors in duckdef's should return the entire "instantiation stack" that led to the error. (There might be several such stacks in a program in principle, but one of them will be compiled first and stop the compiler.)
The second line use of max will not raise a compile-time error of course, but a run-time error will result because the object max tried to return cannot be converted to char*.
As noted above, the combinatorial effect in the parameters will work recursively for duckdefs calling duckdefs. Still I believe it should be manageable because C++ compilation works, and C++ has had this kind of combinatoric effects with templates for ages (which has slowed down compiling times, but it's still very far from an unmanageable problem -- people do compile C++ code; and time is better spent on creating compiler caches than worry about this I think).
In C++ one might write code such as:
boolean file_exists(int handle) {
return check_handle_exists(handle)...
}
boolean file_exists(char* filename) {
return file_exists(get_file_handle(filename));
}for convenience. This kind of overloading can be had simply by some kind of isinstance:
#!python
duckdef file_exists(x):
if isinstance(x, char*): # yes, this is psuedo-code, such type issues are orthogonal to this suggestion
x = get_file_handle(x)
return check_handle_exists(handle)Of course, when this is instantiated into "cdef boolean file_exists(char* x)" the instanceof check can with some optimizations be stripped away (not particularily clever optimization either), giving the exact same effect as in C++ (and same syntax as in Python).
Finally, it might be required to create typed variables. A typeof or similar should be provided for this. It would be "keyword", not a function, as it is used in compilation-time type-context. I.e:
#!python
duckdef some_func(x, y):
cdef typeof(x) tmp
tmp = x + y
return tmptypeof(x) is exactly what it says in the signature on the instantiated function (and might very well be object).
In addition to creating new function instances on different types, new function instances should be created for different [:enhancements/assumptions: assumptions] as well. I.e:
#!python
duckdef sum(arr):
if arr.len == 1:
return arr[0]
elif arr.len == 2:
return arr[0] + arr[1]
else:
# Hmm, len is big, ok with function dispatch
return real_sum(arr)
def clientcode():
cdef Array[len=1] arr1 = ...
cdef Array[len=2] arr2 = ...
cdef Array[len=5] arr3 = ...
cdef Array[len=10] arr4 = ...
cdef Array arr5 = ...
print sum(arr1), sum(arr2), sum(arr3), sum(arr4), sum(arr5)Here, if one instance of sum is created per assumption combination as well as type combination, then the optimizations applicable to assumptions (optimizing away that if-test) can carry over across duckdef call boundaries. In principle, five instances of the sum function above will hit C : One for each case where len is known (only carrying the instruction) and one where it is not known (carrying the whole if-test).
Of course, the third and fourth instantiations will be identical. I propose that this fact should not alter the design of this mechanism, but be noted as a possible compiler optimization (ie detecting that the cases overlap and treat them together; if nothing else then by comparing the resulting function parse-trees to create less C code...).
First solution is of course "pxd inlineable duckdefs", that's trivial.
One step up in modularity would be predeclaring a list of possible overloads (ie types and assumptions) in an associated pxd file. Something like this:
#!python
# utils.pxd
duckdef int max(int, int)
duckdef float max(float, float)
duckdef float64 sum(Array[dtype=float64])
duckdef int32 sum(Array[dtype=int8])
duckdef int32 sum(Array[dtype=int32])
duckdef int64 sum(Array[dtype=int64])
# utils.pyx
duckdef max(a, b): return a if a >= b else bThen, the overloads listed can be instantiated by using some standard name mangling scheme like C++ does (failing that, add syntax to manually mangle the names).
However, there's a final, and much more important, solution. It requires that one drops assumptions though, so let's focus on types. If so, one can simply use object across modules (but not inside modules)! However, one would not cast "unsigned char" to Python int, but to a Python object emulating the correct overflow semantics. (ctypes comes very close, and does overflow wrapping, but unfortunately does not implement the required operator overloads.)
With that last suggestion in mind, you can perhaps see where I'm heading -- "duckdef" is of course the good old "def" in disguise! The approach above would make a "compiled duck-typed def" walk and talk exactly like Python "def".
Unfortunately, in Cython, the behaviour of "def" is to fill in "object" as a default, and "unsigned char" converts to Python, non-wrappable int. With the above approach, we want:
def f(x):
return x * 4
cdef char n = 100
print f(n) # should print -112- There is a backwards-compatible solution here:
-
- Make "def" behave exactly like the "duckdef" described above (except that an "object-for-all-parameters"-version is always created and exported as a "def" of today; instantiations are created as "cdef")
- The old C types, when used as parameters to a "def/duckdef", are coerced to object for backwards compatability.
- Introduce a new set of type identifiers that coerces to Python objects emulating the native behaviour. These are treated like described above with respect to "duckdef".
I.e:
#!python
def f(x):
return x * 4
cdef char n = 100
print f(n) # same as print <object>f(<object>n)
cdef ctypes.c_char n = 100
print f(n) # creates new overload of f function, "cdef object f(ctypes.c_char)"I stress again the reason this is wanted: If f is instantiated and efficiently compiled as cdef object f(char x) then the x variable will overflow. The point is then that if char (or ctypes.c_char) coerces not to a Python int, but to an object that wraps, the code will have the exact same effect whether or not f is compile-time-typed!
By even the most trivial mechanisms, one can allow one assumption to be based on another one. Like this:
#!python
duckdef some_matrix_func(x, y):
cdef ndarray[shape=x.shape + y.shape, dtype=x.dtype] resultThere are real reasons for wanting to do something like the above. Calling the function without assumptions placed on x.shape and y.shape will simply result in errors, so there's no complex inference here.
This step doesn't have to be taken at once; but I think it is a natural step after the above is sorted out. When this is added though (and probably not before) you get Turing-completeness in this scheme. I hope this is not looked upon as a problem in itself. It does mean that people can quite simply write code that halts the compiler:
#!python
duckdef infinite_recursion_in_compiler(arr):
cdef Array[len=arr.len+1] tmp = ...
infinite_recursion_in_compiler(tmp)but maximum recursion limits and so on takes care of this.
Most importantly: People don't have to misuse the feature, even if it is there :-)