Liuw's Thinkpad

There are two predefined decorators in Python: @staticmethod and @classmethod.

I’m somewhat confused. For someone who has a shallow Java background, static method and class method are just the same.

See this for short.

And see Python PEP and manuals for details.

During the search about Python singleton pattern, I discovered [ActiveState recipe 66531].

In this Borg Pattern, instances’ internal dictionary points to the same place, so all instances share the same state. Also, [Alex Martelli], the author of this recipe, has a interesting comment: Borg Pattern != Singleton Pattern. I admit that I confuse Borg Pattern with Singleton Pattern at first.

It’s NOT a singleton object… it doesn’t NEED to be! This is a completely and deeply different pattern from Singleton, and thus I find the latest comment totally off-base. Singleton focuses (wrongly) on object IDENTITY: that’s what the Gof4 focuses on, that’s what “EffC++” focuses on, etc, etc. But we don’t really care about identity most of the time, but about state and behavior.

The “Borg” design pattern IS quite possible in C++ (just a bit more laborious, but not much) and was indeed once written up in C++ Report (but I forget the name it was given then and can’t find my old issue): you get as many objects as you want, with separate identities but all sharing state and behavior. That’s the POINT! Just about all the practical USEFULNESS of Singleton without the troublesome identity-issue that Singleton tends to give.

Here’s the code, quite simple, cool.

class Borg:
    __shared_state = {}
    def __init__(self):
        self.__dict__ = self.__shared_state

There are three ways to get this job done.

1 Module Implementation

The easiest implementation is to use a module scope variable. Module is persistent and shared by all references through its life time, no matter how it is renamed or modified.

See this [stackoverflow post on Python singleton]. Xen Xend makes use of this Python feature, which exposes a moudule function as interface to singleton class.

2 Class Implementation

The second implemention is class implementation, it’s not so convenient because Python does not support static variable itself. It certainly requires some tricks to get this job done.

According to this [ActiveState recipe 52558], it’s all about create exactly one instance of some class. But this is not so convient cause it uses automatic delegation.

3 Function Argument Default Value Implementation

Also another trick. The default value of a function argument is initialized only once and persistent. See the following example.

def f(x, l=[]):
    l.append(x)
    return l

This is least recommended.

It feels easy to copy/paste within Emacs, but sometimes we need to transfer data between Emacs and other programs. Many window systems have some sort of “clipboard” to do simple transfers.

Emacs can also make use of system clipboard. See following commands.

clipboard-kill-region
clipboard-kill-ring-save
clipboard-yank

I’ve been looking for them for years, gee.

中文实在不清楚Process和Procedure如何进行区别，所以题目写了英文。

SICP习题1.11

A function f is defined by the rule that f(n) = n if n = 3 and f(n) = f(n-1) + 2f(n-2) + 3f(n-3) if n >= 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an interative process

SICP中已经给了一个例子，把linear recursive转化为iterative。后面一个要求其实是要把tree recursive进行转化。

好吧，递归的很简单。

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

我比较笨点，迭代的想了好久，写出来个挺锉的。

(define (f n)
  (if (< n 3)
      n
      (f-aux  4 2 1 0 3 n)))

(define (f-aux product a b c count n)
  (if (> count n)
      product
      (f-aux (+ a (* 2 b) (* 3 c))
             (+ a (* 2 b) (* 3 c))
             a
             b
             (+ count 1)
             n)))

这个代码是有冗余的。并不需要专门用一个product去记录结果。写出这样的代码，其实是对“迭代”理解得还不够深刻。改进后的代码是这样的。

(define (f n)
  (if (< n 3)
      n
      (f-aux  4 2 1 2 n)))

(define (f-aux a b c count n)
  (if (> count n)
      c
      (f-aux (+ a (* 2 b) (* 3 c))
             a
             b
             (+ count 1)
             n)))

count并不是必要的，可以直接用n自减到0即可。

ChinaUnix的win_hate也给出了一个版本。我改写了一下，好看点。

(define (g n)
  (g-aux 0 1 2 n))

(define (g-aux x y z n)
  (if (= 0 n)
      x
      (g-aux y z (+ (* 3 x) (* 2 y) z) (- n 1))))

但是这个版本的定义域默认是非负整数，我觉得这是不合适的，因为题目中没有明确指出这一点。

总结一下，有几点比较有意思的：

1. 线性递归和树形递归的尾递归情况，可以转化为迭代，其他情况未考究；
2. 转化时，关键是总结出各个参数的关系，没有必要使用专门的参数去记录结果；
3. 理解迭代的关键点是，每一时刻参数都保持有函数进一步运算的必要信息，而递归把这些信息放在了栈上，由系统隐式操作。

Quoted from SICP 1.2

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process.

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose “looping constructs” such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.

Apparently, RECURSIVE PROCESS is not identical to RECURSIVE PROCEDURE. I’m fooled by my previous knowledge gained from C and Java.

今天下午研究了一下Continuation，在Wikipedia上看到了Continuation Passing Style的相关介绍，带有例程（不过是用Scheme写的）。既然自己在用Emacs，那么试试把例子都用Elisp实现一下吧。

其中有一个函数，用来制作支持CPS的函数，原型是这样的：

(define (cps-prim f)
  (lambda args
    (let ((r (reverse args)))
      ((car r) (apply f
                (reverse (cdr r)))))))

这样用，比如说要制作一个支持CPS的减法运算：

(define cps- (cps-prim -))

假如不使用cps-prim，那么每个函数都要这样写：

(define cps- (a b k)
  (k (- a b)))

很显然，使用cps-prim更加方便点。于是我打算用Elisp也做一个同样的函数，谁让我这么懒呢。

Elisp比较乱，所以写了挺久的，但是总算是写出来了：

(defun cps-prim (f)
  #'(lambda (args)
      (let ((r (reverse args)))
        (funcall (car r) (apply f
                                (reverse (cdr r)))))))
(fset 'cps- (cps-prim '-))

但是使用cps-的时候，会提示f无值。好吧，查一个info，心彻底凉了。11.9.2中明确写到，Elisp是不支持闭包的，所以f在cps-中是unbound的。想偷懒偷不成咯。

再进一步想想，Elisp不支持闭包，是否就不支持高阶函数呢？个人程序设计语言方面没什么了解，只能google了。显然我不是第一个想到这个问题的，还真是发现了一些有趣的东西。

http://lambda-the-ultimate.org/node/1936

有人说：

Closure = Function x Environment

不得不说，这个等式，比一个冗长的定义更清楚。

A bash(1) script, from Advanced Bash-Scripting Guide.

#!/bin/bash

echo
if [ 0 ]; then
    echo "0 is true"
else
    echo "0 is false"
fi

echo
if [ 1 ]; then
    echo "1 is true"
else
    echo "1 is false"
fi

echo
if [ -1 ]; then
    echo "-1 is true"
else
    echo "-1 is false"
fi

echo
if [  ]; then
    echo "NULL is true"
else
    echo "NULL is false"
fi

echo
if [ xyz ]; then
    echo "random string is true"
else
    echo "random string is false"
fi

echo
if [ $uninit_var ]; then
    echo "Uninitialized variable is true"
else
    echo "Uninitialized variable is false"
fi

echo
if [ -n "$xyz" ]; then
    echo "Uninitialized variable is true"
else
    echo "Uninitialized variable is false"
fi

xyz=
echo
if [ -n "$xyz" ]; then
    echo "Null variable is true"
else
    echo "Null variable is false"
fi

echo
if [ "false" ]; then
    echo "\"false\" is true"
else
    echo "\"false\" is false"
fi

echo
exit 0

“likely()” and “unlikely()” are macros defined in Linux kernel. But the true story is about optimization.

#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

These macros can be used in user space, though. Because they are in fact some built-in features of gcc(1). gcc(1) should optimize assembly generation according to program’s need.

Try this simple sample.

int main()
{
    int a;
    if (likely(a == 100))
        printf("Branch 1\n");
    else
        printf("Branch 2\n");
    return 0;
}

I use an uninitialized variable, that’s a bug, but this does not affect my demostration. Feel free to ignore that uninitialized “a”, we just need something to compare to a constant, don’t we? If I use two constants for comparison, gcc(1) will optimize in compile time and we can not see the outcoming of “likely()” and “unlikely()”.

Use gcc(1) to generate assembly.

$ gcc -S -O2 likely.c

Here is what we get. Ignore less important part, focus on most valuable snippet.

    cmpl $100, %eax
    jne  .L2
    movl $.LC0, (%esp)
    call puts
.L4:
    addl $4, %esp
    xorl %eax, %eax
    popl %ecx
    popl %ebp
    leal -4(%ecx), %esp
    ret
.L2:
    movl $LC1, (%esp)
    call puts
    jmp  .L4

Pay attention to that “jne” directive. We compare variable (which stores in eax) with 100 to see if they are equal. The outcoming result is “likely” to be true, so that “jne” is not executed, the code just falls through. The benifit we get is that no jumping means no pipe line flush, we can make full use of directive cache.

If I change “likely” to “unlikely” in my C code, assembly code generation will be different. However, it should follow the same rule as above – make full use of pipe line.

I often use GDB to debug my C program. I have no idea that it can also work with assembly program until I read Professional Assembly Language.

General, we need to assemble our source with AS option ‘-gstabs’ so that AS can generate debugging information for us.

$ as -gstabs -o ex.o ex.s
$ ld -o ex ex.o

Launch GDB as we always do. We can set break point with the following syntax.

(gdb) break *label+offset

Unfortunately, there is a well-known GDB bug. When the program is run, GDB just ignores the breakpoint, and runs through the entire program.

To work around this problem, we have to include a dummy instruction as the first instruction code element after our breakpoint. In assembly, the dummy instruction is NOP.

For instance, we want to break at label ‘_start’.

_start:
    nop
    ...

(gdb) break *_start+1

That should just work fine.