如何印清單

2005 年我問過 Thinker 這樣的問題:想程式常碰到要印出清單的情況,對人類而言習慣的格式是:

1, 2, 3, 4

但這個格式對於 C 語言來說卻不太好處理。一般可以寫成這樣:

<<一般作法>>=
void normal(const char *list[], const int len)
{
    int i = 0;
    printf("%s", list[i++]);
    for (; i < len; i++) {
        printf(", %s", list[i]);
    }
    puts("");
}
@

但是 printf 這行會重複,似乎不是最好的寫法。如果不要重複,那就得在迴圈中加個判斷式,但每次都要多個判斷又好像有點浪費:

<<判斷作法>>=
void condition(const char *list[], const int len)
{
    int i;
    for (i = 0; i < len; i++) {
        if (i != 0)
            printf(", ");
        printf("%s", list[i]);
    }
    puts("");
}
@

當時 Thinker 想了想,給了我一個用 function pointer 的答案

void dummy() {
}

void line() {
   printf("  ------\n");
}

inter = &dummy;
for(i = 0; i < n; i++) {
   inter();
   printf("%s\n", record[i]);
   inter = &line;
}

話說,事隔多年,今天在看其他東西的時候,突然想到這個問題可以用 Clifford’s Device 的方法做。

<<Clifford>>=
void clifford(const char *list[], const int len)
{
    int i = 0;
    while (1) {
        if (0) {
          clifford:
            printf(", ");
        }
        printf("%s", list[i++]);
        if (i >= len)
            break;
        goto clifford;
    }
    puts("");
}
@

各位看官,可有什麼新想法嗎?

<<list.c>>=
#include <stdio.h>

<<一般作法>>

<<判斷作法>>

<<Clifford>>

int main(int argc, char *argv[])
{
    const char *list[] = {
        "one",
        "two",
        "three",
    };
    const int l = sizeof(list) / sizeof(char *);

    normal(list, l);
    condition(list, l);
    clifford(list, l);
    return 0;
}
@

當然啦,如果是 python,這問題可簡單了:

>>> l = ['one', 'two', 'three']
>>> print ', '.join(l)
one, two, three

另,本文採用 Noweb 格式,用工具跑一遍就可以產生 list.c 。

Advertisements

Curious case of closure in Go and Python

At http://tour.golang.org/#39, I found the following sample code:

package main

import "fmt"

func adder() func(int) int {
	sum := 0
	return func(x int) int {
		sum += x
		return sum
	}
}

func main() {
	pos, neg := adder(), adder()
	for i := 0; i < 10; i++ {
		fmt.Println(
			pos(i),
			neg(-2*i),
		)
	}
}

Its document reads:

… functions are full closures. The adder function returns a closure. Each closure is bound to its own sum variable.

Take that into consideration, it might be easier to understand the execution result:

0 0
1 -2
3 -6
6 -12
10 -20
15 -30
21 -42
28 -56
36 -72
45 -90

To me, variable sum is similiar to ‘instance variable’, in Object-oriented’s terminology. However, in Python, things can be quite different.

def adder():
    sum = 0

    def f(x):
        sum += x
        return sum
    return f


def main():
    pos, neg = adder(), adder()
    for i in xrange(0, 10):
        print pos(i), neg(-2 * i)

The code looks roughly the same, but it will raise the following exception:

Traceback (most recent call last):
  File "closure.py", line 17, in 
    main()
  File "closure.py", line 13, in main
    print pos(i), neg(-2 * i)
  File "closure.py", line 5, in f
    sum += x
UnboundLocalError: local variable 'sum' referenced before assignment

This is because if sum is to be modified, Python must decide which variable to change. sum += x is the same as sum = sum + x, and sum = suggests it’s a local variable, since all variable is by default local in Python. Given that, expression sum + x can not be evaluated because sum, as a local variable, is still undefined here.

If the sum += x line is removed, and sum + x is returned directly, the result will be:

0 0
1 -2
2 -4
3 -6
4 -8
5 -10
6 -12
7 -14
8 -16
9 -18

It runs okay, but the result is wrong. Where does function f get the value of sum? If Python cannot find a variable in locals(), it will try to find it from the scope above it, i.e. function adder, and sum is indeed defined in it. The real Python equivelent of the Go program above will be:

class adder:
    def __init__(self):
        self.sum = 0
    def __call__(self, x):
        self.sum += x
        return self.sum


def main():
    pos, neg = adder(), adder()
    for i in xrange(0, 10):
        print pos(i), neg(-2 * i)


if __name__ == '__main__':
    main()

Functions are already first class objects in Python. Here we create a class that its instance behaves like a function, so it is a function because of duck typing.

Multi-thread testing in Pyramid

If you want to do multi-thread testing in Pyramid, it probably won’t work the first time because request and registry are thread local, and things like get_renderer will call get_current_registry. When it happens in a thread, it won’t get the same value as it would have in the main thread.

So, here is a hack to address this:

import pyramid.threadlocal
from threading import Thread, Lock

candidates = [
    (self._test1, ()),
    (self._test2, ()),
    (self._test3, ()),
    ]

def random_func(pyramid_thread_locals):
    pyramid.threadlocal.manager.push(pyramid_thread_locals)
    time.sleep(random.random())  # 0 ~ 1 sec
    func, args = random.choice(candidates)
    func(*args)

pyramid_thread_locals = pyramid.threadlocal.manager.get()
threads = [Thread(target=random_func, args=(pyramid_thread_locals, ),)
           for i in range(100)]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()

There is no guarantee that pyramid.threadlocal.manager will always be there. Even if it’s there, there’s no guarantee it can be used this way. So, this should only be considered as a temporary workaround.

Words from the Wise

Quote from Interview with Donald Knuth

Still, I hate to duck your questions even though I also hate to offend other people’s sensibilities—given that software methodology has always been akin to religion. With the caveat that there’s no reason anybody should care about the opinions of a computer scientist/mathematician like me regarding software development, let me just say that almost everything I’ve ever heard associated with the term “extreme programming” sounds like exactly the wrong way to go…with one exception. The exception is the idea of working in teams and reading each other’s code. That idea is crucial, and it might even mask out all the terrible aspects of extreme programming that alarm me.

I also must confess to a strong bias against the fashion for reusable code. To me, “re-editable code” is much, much better than an untouchable black box or toolkit. I could go on and on about this. If you’re totally convinced that reusable code is wonderful, I probably won’t be able to sway you anyway, but you’ll never convince me that reusable code isn’t mostly a menace.

generate object methods at runtime

I have been working on a dialer button class since yesterday. It makes sense to use the command design pattern here, and I want to separate the commands and the buttons so I can change the functionality of every button at runtime.

So we are talking about something like this:

class DialerButtons:
    def __init__(self):
        self.command_table = [
            self.numpad_1, self.numpad_2, self.numpad_3,
            self.numpad_4, self.numpad_5, self.numpad_6,
            self.numpad_7, self.numpad_8, self.numpad_9,
            self.cancel, self.numpad_0, self.dial]

    def numpad_0(self):
        self.text.append('0')

    def execute(self, n):
        self.command_table[n]()

and you can use this class like this:

dialer = DialerButtons()
dialer.execute(0)
dialer.execute(8)

Now obviously define numpad_0 to numpad_9 is a boring task. What happens if you need to define numpad 0 to 99? So, I came out with this code piece:

    @classmethod
    def _numpad_commands_factory(cls):
        for n in xrange(0, 10):
            setattr(cls, 'numpad_%d' % n, lambda self: self.text.append(str(n)))

DialerButtons._numpad_commands_factory()

This way you initialize DialerButtons AFTER you start the program and make methods numpad_0 to 9 on the fly. At least that’s what I was trying to do. However, it didn’t come out as I expected. Every numpad method will just add ‘9’ to self.text, instead of the respective ‘0’ to ‘9’. Why?

The reason is that the context of numpad_0, for example, is actually “f(self): self.text.append(str(n)))” instead of “f(self): self.text.append(‘0’)”. so, what it does here is that it refers to the variable n inside _numpad_commands_factory, and the value of n is 9 after you executed it.

The correct code piece is:

    @classmethod
    def _numpad_commands_factory(cls):
        def f(chr):
            return lambda self: self.text.append(chr)
        for n in xrange(0, 10):
            setattr(cls, 'numpad_%d' % n, f(str(n)))

This way we can evaluate the value of str(n) first, then generate the appropriate function and assign it to numpad_n.

我果然不懂 C 啊。

from gcc-4.2.info:

5.34 An Inline Function is As Fast As a Macro

<..snipped..>

If you specify both `inline’ and `extern’ in the function definition,
then the definition is used only for inlining. In no case is the
function compiled on its own, not even if you refer to its address
explicitly. Such an address becomes an external reference, as if you
had only declared the function, and had not defined it.

This combination of `inline’ and `extern’ has almost the effect of a
macro. The way to use it is to put a function definition in a header
file with these keywords, and put another copy of the definition
(lacking `inline’ and `extern’) in a library file. The definition in
the header file will cause most calls to the function to be inlined.
If any uses of the function remain, they will refer to the single copy
in the library.

Since GCC 4.3 will implement ISO C99 semantics for inline functions,
it is simplest to use `static inline’ only to guarantee compatibility.
(The existing semantics will remain available when `-std=gnu89′ is
specified, but eventually the default will be `-std=gnu99′; that will
implement the C99 semantics, though it does not do so in versions of
GCC before 4.3. After the default changes, the existing semantics will
still be available via the `-fgnu89-inline’ option or the `gnu_inline’
function attribute.)

GCC does not inline any functions when not optimizing unless you
specify the `always_inline’ attribute for the function, like this:

/* Prototype. */
inline void foo (const char) __attribute__((always_inline));

So, consider the following program:

gcctest.c:

#include "inline.h"

int main()
{
     puts(externinline());
     return 0;
}

inline.h:

#include 

__inline__ extern char *externinline()
{
     return "inline";
}

lib.c:

char *externinline()
{
     return "extern";
}

The behavior of the executables will be different with or without the -O option of gcc. Compile it without -O, the program will print “extern”. Compile it with -O, the program will print “intern”.

GLOBAL and struct

Refer to: Gnu – Global – Help – How to find the definition effectively

To put the story even shorter, the GNU GLOBAL will not treat C struct as definition, but as `other symbol’ . This means you may only find a struct with global -s, which will give you lots of irrelevant results.

This feature is in the GLOBAL plans for the future already, which means it might be implemented sometime in the future. For now, it’s better to use GLOBAL to trace how the program runs, the relationship between functions, rather then finding the semantic details. For the semantic side, the ctags or etags is still my first choice.