New module (written in C) for using the high-precision QD library
Hi, I wrote a module for wrapping the well-known high-precision QD library written by D.H. Bailey. You can find it here: https://github.com/baruchel/qd It is written in pure C with the CPython C-API in order to get the highest possible speed. The QD library provides floating number types for ~32 and ~64 decimals digits of precision and should be quicker for such precisions than other arbitrary-precision libraries. My ultimate goal is to implement these two types as new dtype for Numpy arrays, but I release here a first version which already gives a complete interface to the QD library. Regards, -- Thomas Baruchel -- https://mail.python.org/mailman/listinfo/python-list
Re: New module (written in C) for using the high-precision QD library
Hi, Thank you for your answer. Actually this is the third version I am writing for using the QD library; the first onPython using ctypes; the second one was in Cython; this one is in C. I don't claim being a Cython expert and maybe my Cython code was not optimal but I can say the C version is significantly quicker (and the binary is about half the size of the Cython binary). I admit Cython is a great idea but for this very specific project I like rather using C: behind the scene thre is no need to interact with Python; data only relies on elementary C types, etc. I decided to migrate from Cython to C when I realized that I was merely embedding C in Cython almost all the time. Furthermore, the QD library is old, stable and simple. Once my module will be ready it won't evolve much; thus maintaining the project shouldn't be an issue. I am using Python 2 with the people I am working with and I release my work as it; maybe I will rewrite it for Python 3 one day but it is not my immediate purpose. Last day I started implementing the new type as dtype for Numpy; for the moment, I disabled this part in the code (because it is far to be really usable) but it can already be tried for having a short glance by uncommenting one line in the code. Best regards. tb. -- https://mail.python.org/mailman/listinfo/python-list
My attempts in playing with tail-recursion in python
Hi,
I would like to share some of my recent attempts concerning recursivity in
python, more precisely recursivity with lambda functions.
I know that the title of my thread with the "tail-recursion" words may wake up
some long and old war; please don't take it as such. I am not claiming anything
about what programming languages should be or not; I enjoy using python for
many purposes and I perfectly know how to handle loops for achieving some tasks,
but sometimes I like rather think with recursivity because I have been using
various dialects of Lisp for a long time. I had a very great time studying the
Y-combinator; then I wrote various pieces of code for remapping recursive calls
to loop iterations.
The following functions are fully usable; I hope someone will enjoy using them.
If you are not interested by the explanations, just jump to the end of the
message and take my functions for using them.
Here is a recursive function:
fac = lambda f: lambda n: 1 if n==0 else n*f(n-1)
The Y-combinator is well known:
Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))
Now, you can use the recursive function:
rf = Y(fac)
rf(5)
Now we write fac as a tail-recursive function:
fac = lambda f: lambda a,b: b if a==0 else f(a-1,a*b)
rf = Y(fac)
rf(5,1)
but of course, the recursivity is handled like previously.
In fact, it is very easy to build some effcient wrapper; for instance:
(lambda f: f(lambda *args: ("callback",args)))
will act in the following way:
(lambda f: f(lambda *args: ("callback",args)))(fac)(5,1)
--> ('callback', (4, 5))
(lambda f: f(lambda *args: ("callback",args)))(fac)(4,5)
--> ('callback', (3, 20))
(lambda f: f(lambda *args: ("callback",args)))(fac)(3,20))
--> ('callback', (2, 60))
(lambda f: f(lambda *args: ("callback",args)))(fac)(2,60)
--> ('callback', (1, 120))
(lambda f: f(lambda *args: ("callback",args)))(fac)(1,120)
--> ('callback', (0, 120))
(lambda f: f(lambda *args: ("callback",args)))(fac)(0,120)
--> 120
Here, the "callback" string is arbitrary chosen in order to make the loop know
that a next call is needed.
Now, the recursivity is handled as successive calls, which is what I was looking
for. A first proposal could be:
def with_tail_recursion(func):
x = (lambda f: f(lambda *args: ("callback",args)))(func)
def wrapper(*args):
out = ("callback",args)
while type(out)==tuple and out[0]=="callback":
out = x(*out[1])
return out
return wrapper
Now, the very same function can be used as recursive or inside a loop:
fac = lambda f: lambda a,b: b if a==0 else f(a-1,a*b)
rf = Y(fac)
tr = with_tail_recursion(fac)
rf(5,1)
--> 120
tr(5,1)
--> 120
Of course, if most of your job relies on writing functions returning tuples
with the string "callback" being the first argument, you should use another
keyword in the previous code ;-)
You can inspect the stack by raising an exception:
f2 = lambda f: lambda n: 1/n if n==0 else f(n-1)
and see the differences between Y(f2)(5) and with_tail_recursion(f2)(5)
But I was not fully happy with the use of a tuple, efficient but a little too
tricky to my eyes. For that reason, I took the Y combinator again and slightly
modified it:
lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))
Now, the function doesn't call itself, but returns a function calling itself
with the relevant arguments.
I like this new function better than the previous one, but it is now more
difficult for the wrapper to detect when it is time to leave the loop.
Right now, I use the following test: checking for the __call__ string in
the dir() list. This means ONE IMPORTANT THING: this second wrapper can't
handle tail-recursive functions returning functions, (which is actually more
likely to happen than tail-recursive functions returning tuples with the
string "callback" being the first argument ;-) ). But I like it that way:
def B(func):
x = (lambda f: (lambda x: x(x))(lambda y:
f(lambda *args: lambda: y(y)(*args(func)
def wrapper(*args):
out = x(*args)
while '__call__' in dir(out):
out = out()
return out
return wrapper
tr2 = B(fac)
tr2(5,1)
--> 120
Now, you can write functions with a huge depth of recusivity with no
problem :
B(lambda f: lambda n: "ok" if n==0 else f(n-1))(5000)
(don't try with the Y combinator instead...)
Best regards,
--
Thomas Baruchel
--
http://mail.python.org/mailman/listinfo/python-list
Re: My attempts in playing with tail-recursion in python
Le 28-08-2013, Thomas Baruchel a écrit : > The following functions are fully usable; I hope someone will enjoy using > them. > > If you are not interested by the explanations, just jump to the end of the > message and take my functions for using them. Despite the very short size of my function, I made a module of it as a convenience for my own use. I share here my "recursion.py" file in which I also added some docstrings. - module "recursion.py" --- """ The recursion module provides convenient functions for handling recursion with lambda functions. The famous Y-combinator is provided as a convenience, but the most distinctive function of the module is the B function for handling tail-recursion. Written by Thomas Baruchel """ Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args))) def B(func): """ B(lambda) -> lambda Return a usable function from a lambda expression written with a tail-recursion style. The new function will be evaluated inside a loop with no recursive calls, allowing high depths of recursion. Since the internal loop evaluates the return of the function as long as it is callable, the function does not work with functions returning functions (at the end of the recursive calls); there is no restriction otherwise. E.g.: fac = lambda f: lambda a,b: b if a==0 else f(a-1,a*b) func = B(fac) func(5,1) --> 120 or more shortly: B(lambda f: lambda a,b: b if a==0 else f(a-1,a*b))(5,1) --> 120 """ x = (lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args(func) def wrapper(*args): out = x(*args) while callable(out): out = out() return out return wrapper -- http://mail.python.org/mailman/listinfo/python-list
A new module for performing tail-call elimination
Hi, after having spent much time thinking about tail-call elimination in Python (see for instance http://baruchel.github.io/blog/ ), I finally decided to write a module for that. You may find it at: https://github.com/baruchel/tco Tail-call elimination is done for tail-recursion as well as for continuation-passing style (cps) in a consistent syntax for both usages. Any tail-recursive function having the suitable format for being embeddable in the Y combinator can be used here with no change at all (with the main difference that tail-calls will be eliminated), but other continuations can also be added The module is available under two forms: traditional python code and cython compilable code (pre-compiled binaries are also released for the cython version). Of course the Cython version is quicker and should be preferred for serious work. I must admit I haven't browsed much in order to know if similar projects already exist; I was happy to do it for myself, but I want to share it now in case other people are interested by it also. Best regards, -- Thomas Baruchel -- https://mail.python.org/mailman/listinfo/python-list
Version 1.1 of the tco module (tail-calls, recursion, call/cc)
The version 1.1 of the tco module is released. It is much more owerful since it now allows nested systems of continuations. The most important is probably rather that I took the time to write a very detailed presentation of the module on my blog: http://baruchel.github.io/ Regards, tb. -- https://mail.python.org/mailman/listinfo/python-list
