In my current work, the main stream platform is .NET. I have not invested a lot of time to start to program in C# for .NET, but I am kind of attracted by F#, which is a functional language for .NET that I would like to know more about.

Recently, I purchased a book to know more about F# and I learn some thing that is called “Y-combinator” in functional programming. The F# code for the “Y-combinator” looks like this,

let rec y f x =
  f (y f) x;;

You can apply the “Y-combinator” to some non-recursive functional function to make it recursive. For example,

let fac f = function
  | 0 -> 1
  | n -> n * f (n-1);;

> y fac 5;;
val it : int = 120

I was curious about how to do similar thing in Python. So, I try the following code snippet:

def Y(f):
  def g(x):
    return f(Y(f))(x)
  return g

def fac(f):
  def g(x):
    return 1 if x == 0 else x * f(x-1)
  return g

With these function definitions, “Y(fac)(10)” will give you the correct result 3628800. On the other hand, it is not really easy for me to understand this code as most of my daily programming tasks are in imperative programming style with some more straight forward functional feature. Beside the mathematical way (described in the wiki page) to understand how this work, one way one can see how this work is to see how the code unroll under python interpreter:

Y(fac)(5) -> fac(Y(fac))(5) -> g(5) inside fac with f = Y(fac)

Then the “g(5)” inside fac returns 5 * Y(fac)(4) . The Y(fac)(4) will return 4 * Y(fac)(3) and so on.

It seems there is a lot interesting thing in pure functional world. Hope I will learn more about them soon.

Tags: programming

I use python and hadoop distributed file system (HDFS) to process large amount of data at work. Instead of using the regular map-reduce mechanism provided by hadoop, I have my home-made map-reduce python engine written using Pyro. It turns out it is quite efficient and sometimes it is much faster than the corresponding streaming code for some simple map-reduce work. For this kind of work, I access the file in HDFS using “hadoop fs -cat” by the unix pipe (popen) in python. It seems to me it might be useful to be able to bypass the somehow ugly unix pipe and “hadoop fs -cat” combination. There already is a SWIG wrapper of python for hdfs. However, I think it will be nice to have ctypes wrapper such that no extra compiling is necessary for installation. I spend a few nights working on such wrapper and hope it will be useful. The results is a single python module that I call “phdfs“. It provides most of the API in the libhdfs. It will be useful if one want to read, write and manipulate the hadoop filesystem with the flexible and powerful python syntax.

You can download the phdfs.py, and try it out yourself. I have not tested all the methods, so YMMV.

Tags: programming

前一陣子看到 lukhnos 在寫一個能讓 OV 用 Ruby 來寫 filter 的模組，一時心血來潮想看看如何用 python 來寫 OV 的 filter 的模組。花了點時間研究了一下如何在 C/C++ 中內藏 python。 雖說用 python 來寫程式作研究也有好一陣子，也曾經用過 SWIG 來控制用 C/C++ 寫的物理模擬程式， 在 C/C++ 中呼叫 python 倒是第一次實做。花了點時間寫了個 prototype，在 lukhnos 的協助下，搞定了一個讓 OV 可以用 python 寫 filter 的模組 (在 OV 的 svn repository: Modules/OVOFPythonBased/ 中)。

OV 的 filter 主要是呼叫一個叫 process 的 method。傳到 process 中的只是一個字串，所以實做 OV 的 filter 並不是太難。發展的過程中，大多數的時間花在看 python 的 C API 文件，熟悉如何在 C/C++ 中建立 python 的物件及將參數傳給 python 的 method。

讓 OV 的 filter 機制可以用 modern 的 python 或是 ruby 實做只是第一步。Dynamic language 的方便已經讓發展新的 filter 的工作大大的簡化。所以下一個就是看看能不能讓 OV 用 Python 或是 Ruby 來寫輸入法。在未來實驗類似酷音等比較複雜的自然語言處理的輸入法模組的時候，如果可以用 Python 或是 Ruby 來寫輸入法應該會有很大的助益。

寫 python based OV filter 時, 只需要定義好對應到 process 的 python method/function 就好了，python 的部份是完全的被動，python 的 code 並不需要管 C/C++ 的 class 與 instance，只需要實做一個叫 process 的函數就可以了。 但寫 OV 的輸入法模組的時候，有幾個 OV 的物件必須要傳到 Python 中，而且 Python 也最要能夠 subclass OV 中的 class 來保持 OV API 介面的一致。基本上要做下面幾件事：

(1) 用 SWIG 來把 OV 的 class 轉成 Python 的 class。
(2) 定義對應到 Python class 的 OV C/C++ class。
(3) 在 (2) 中最重要的一件事就是要把將 OV C/C++ 中 instance pointer 轉成 Python 可以認得的物件。

在這三項工作裡，最容易的部份是 (1)。基本上只要把 Framework/Headers/OpenVanilla.h 剪貼到 SWIG 的 interface 檔中就好，唯一要注意的地方是要讓 SWIG 知道要將 C++ 的 class 轉成 python 的 class。這要用到 SWIG 中的 directors 。請見 SWIG 的相關文件 與 Modules/OVIMPython/ 中的 OVIMPython.i。

接下來要就是要讓 OV C/C++ 知道 Python 的存在，主要要去 subclass 兩個 OV C/C++ 的 class, OVInputMethodContext 和 OVInputMethod, 讓 OV 的 loader 可以呼叫對應的 python 物件。請見 Modules/OVIMPython/OVIMPythonBased.cpp 中的 OVIMPythonBasedContext 與 OVIMPythonBased class。 這兩個 wrap classes 作的事情很簡單，就是實做 C++ method 來呼叫對應的 Python instance method。但是之前的一個障礙就是 OVInputMethodContext 及 OVInputMethod 中的 method 的參數裡大多是指向 C++ 的 instance 的 pointers。要怎麼把這些對應的 instance 變成 python 物件在傳給 python 倒是一個比較不容易的問題。也牽涉到 SWIG 怎麼把 C++ 物件映射到 python 物件的細節。

也許在 SWIG 有對應的解法，但我並沒有從 SWIG 的文件中看到顯而易見的方法來解決這個問題。後來是在研究 SWIG 產生的 python module 的檔案中找到 hint。對每一個要 wrap 的 C++ class，SWIG 會產生兩個對應的 python class。例如如果在 C++ 中有如下的宣告:

class OVKeyCode : public OVBase  {
public:
virtual int code()=0;
};

SWIG 會建立下面兩個 python class:

class OVKeyCode(OVBase):
...

和

class OVKeyCodePtr(OVKeyCode):
...

其中 OVKeyCodePtr 的 constructer ( __init__() in python ) 可以用 SWIG 中的表示 C/C++ pointer 的 python pointer object 建立對應的 python object。所以接下來要作的就是要把 C/C++ 的 pointer 轉成 python 中 pointer object。而 SWIG 的作法只是把 C/C++ 中的 pointer 的 address 和 type 換成特殊格式的字串，在 SWIG 所產生的 C/C++ 的 wrap 檔中有一個特別的函式 (char *SWIG_PackData(char *c, void *ptr, int sz) ) 就是把 C/C++ 的 pointer 換成字串，所以我們就可以用這個函式將 C/C++ 的 pointer 轉成對應的 python 字串然後透過 SWIG 產生的 aClassPtr 來產生 python 中的 aClass 的 instance，而這個 python instance 的 implementation 就是對應的 C/C++ implementation。

這樣的 mapping 實在有點太複雜而不直覺。還沒有真的詳讀 SWIG 的文件，不知道有沒有比較優雅的方式來作同樣的事。雖說如此，對要用 python 寫輸入法的人可以完全不去理 wrapper 本身及兩個語言的物件對應的複雜性，專注在用 python 來寫輸入法。 在lukhnos 稍早寫的用Python + OpenVanilla寫輸入法中有用 python 的 OV 輸入法的 minimum example。

我想這只是第一步，我自己來試著了解 embedding python 的小小練習。如果有空的話，再看看如何真的用 python 在 OV 裡作些有趣的事。

Tags: programming

The following code create circular references in python:

>>> aRef = []
>>> aRef.append(aRef)
>>> print aRef
[[...]]

This creates a list object referred by a variable named “aRef”. the first element in the list object is a reference to itself. In this case, the “del aRef” dereference aRef to the list object. However, the reference count of the list object does not decrease to zero and the list object is not garbage collected, since the list object still refers to itself. In this case, the garbage collector in Python will periodically check if such circular references exist and the interpreter will collect them. The following is an example to manually collect the space used by circular referenced objects.

>>> import gc
>>> gc.collect()
0
>>> del aRef
>>> gc.collect()
1
>>> gc.collect()
0

Tags: programming