轻描淡写

Domain name changed

2011-12-13T15:08:00.000+08:00

My current minjiezha.info domain name will be expired soon. I decided to use a new one minjiezha.com, and it will take effect in 24 hours.

Lazy CEK Machine

2011-07-28T00:00:00.000+08:00

In the CEK Machine, though the substitution for an identifier is delayed, it doesn't mean it is a lazy machine. As described in Eager and Lazy Evaluation, a lazy evaluation strategy doesn't evaluate an argument before applying it to a function. However, in the CEK machine, it always evaluates the argument to a value, so it is still a call-by-value machine. If you are careful enough, you may already notice whenever an environment is created, the expression in its closure is always a value. The real power of environment is working with lazy evaluation. So in this post, I am going to implement the call-by-name and call-by-need strategies for the CEK machine.

Call by Name
It is quite easy to implement the call-by-name strategy based on the current call-by-value one. Since the machine no longer evaluates the argument before applying it to a function, the reduction rules related to applications should be modified(For a primitive operator, the operands are needed at the moment it is evaluated, so it stays unchanged.). In the call-by-value machine, when the control string is an application, first an ArgKK continuation is handled, then a FunKK continuation is handled. Now, the two steps, 2.1 and 2.2, should be combined into one, and the FunKK continuation type is removed.

2) If the control string is a value(abstraction or constant), check the type of continuation:
2.1) If it is ArgKK, pop up the continuation, create a new environment that maps the function parameter to current closure, and set the function body and the new environment as the current expression and environment respectively;

However, the machine may need to evaluate the same argument many times now. Take expression (lambda x + x x) ((lambda y y) 1) as an example, x is mapped to ((lambda y y) 1) after reducing the outer application. Then, when evaluating + x x, ((lambda y y) 1) is evaluated twice. The reason is that a parameter may be used several times in a function body, and whenever it is needed, the original argument it maps to should be evaluated. What if remember the result of the argument for the first time it is evaluated, so it doesn't bother to re-compute it later? I will talk this in next section.

Call by Need
The idea is quite straightforward. Remember the value for a closure, so next time the closure is needed, the value is retrieved directly. Considering the same example (lambda x + x x) ((lambda y y) 1), when the first x in + x x is needed, ((lambda y y) 1) is evaluated and the result is 1. After this, the environment which maps x to ((lambda y y) 1) is updated so x is mapped to 1. When the second x is needed, 1 is retrieved from the environment and no extra evaluation is performed.

However, the implementation is not that simple. When evaluating ((lambda y y) 1), I can't simply put it as the control string of current machine, because this may destroy the machine state and the machine can't go back to previous state after it is evaluated. Instead, a separate evaluation process should be performed on it. This is kind of a sub-machine, whose evaluation logic is the same, but it relies on some states from the parent machine, such as environments because the expression itself may contain free variables. In current evaluate() function, it initializes the machine state at the beginning and clean it up at the end. It was designed like this because no sub-machine was ever needed before. I am going to refactor it so it is fed with a machine state and focuses on the reduction logic, instead of managing the lifecycle of the machine state. One advantage is an expression can be put into a particular context for evaluation. It is more flexible. The interface is changed to:

// file: eval.c
static int _evaluate(State *state);

TreeNode * evaluate(TreeNode *expr) {
    Environment *globalEnv = buildGlobalEnvironment();
    State *state = cek_newState();
    state->closure = cek_newClosure(expr,globalEnv);

    TreeNode* result = NULL;
    if(_evaluate(state)) {
        // The result control string may contain free variables, need to 
        // substitute them using the environment for it.
        TreeNode *tmp = resolveFreeVariables(state->closure->expr,state->closure->env);
        if(tmp!=NULL) {
            // actually, tmp and state->closure->expr are the same expression
            result = tmp;
            state->closure->expr = NULL;
        }
    }
    cek_cleanup(state);
    return result;
}

And the code for looking up an identifier is:

// file: eval.c
static Closure* lookupVariable(const char *name, Environment *env) {
    if(env==NULL) return NULL;
    if(strcmp(name,env->name)==0) {
        Closure *closure = env->closure;
        if(closure->env!=NULL) {
            // evaluates the expression in its environment
            State *state = cek_newState();
            state->closure = cek_newClosure(duplicateTree(closure->expr),cek_newEnvironment("",cek_newClosure(NULL,NULL),closure->env));

            if(_evaluate(state)) {
                deleteTree(closure->expr);
                cek_deleteClosure(closure);
                // save the evaluated result
                env->closure = cek_newClosure(state->closure->expr,state->closure->env);
                state->closure->expr = NULL;
            }
            cek_cleanup(state);
        }
        return env->closure;
    }
    return lookupVariable(name,env->parent);
}

More Words about Closure and Environment
Another design improvement I want to mention is the global environment. Currently, if the control string is an identifier, the machine first tries to look it up in the environments and if not found it tries to resolve it from the builtin and standard libraries. Since a library maps identifiers to expressions, it is just like an environment. So the identifier lookup can be treated universally by introducing a global environment, which contains all the identifiers and functions provided by the evaluator. It is the root environment for all environments that are created during the evaluation and it is initialized when the machine is started. Thus, to handle a control string which is an identifier, the machine only needs to look it up in the environments. If it is a builtin or standard function, the machine can finally find it in the global environment.

A closure is an expression associated with an environment. The environment is where the expression is defined rather than it is evaluated. Let's consider the reduction steps of expression (lambda x (lambda y (lambda x + x y) 2) x) 1.

(lambda x (lambda y (lambda x + x y) 2) x) 1
=> (lambda y (lambda x + x y) 2) x)                    A = {x=>(1,G), G}
=> (lambda x + x y) 2     B = {y=>(x,A), A}
=> + x y                                                               C = {x=>(2,B), B}
=> + 2 y                                                               C = {x=>(2,B), B}
=> + 2 1                                                               C = {x=>(2,B), B} *
=> 3

The result is 3 rather than 4, because at step (*), y is mapped to x, and x is looked up in environment A, where it is defined, but not the latest environment C where is evaluated.

You can get the source code in branches call-by-name and call-by-need via github.

CEK Machine

2011-07-23T00:50:00.000+08:00

In the textual machines I mentioned in previous posts, when reducing an application, without exception, everyone requires the substitution of an argument in place of all the occurences of an identifier in the abstraction body. The machine traverses the expression tree during substitution, and if the result is not a value, it needs to re-traverse it again to evaluate it. Take (lambda x + x x) 1 as an example, + x x is traversed to replace x with 1. After that, we get result + 1 1. To evaluate it, the expression + 1 1 is traversed again. It is inefficient to traverse an expression twice. We cannot get rid of this if we stick on the substitution when reducing an application. We can, however, remember the identifier and the argument at the moment and delay the substitution until it is actually needed.

To represent this delay substitution, a component that maps an identifier to an expression is needed. It is called an environment. Every expression in the machine is replaced by a pair, whose first part is an expression probably with free variables in it and the other part is an environment. It is called a closure. Of course, the environment could not map identifiers to expressions, because the machine never works on a single expression. It should map identifiers to closures. And the continuation also contains a closure. Now, the machine state changes to a control string, an environment and a continuation, so it is called a CEK machine. Here is the data structures introduced for environment and closure:

// file: cek_machine.h
struct envStruct {
    char *name;
    struct closureStruct *closure;
    struct envStruct *parent;
};

struct closureStruct {
    TreeNode *expr;
    struct envStruct *env;
};

typedef struct continuationStruct {
    ContinuationKind tag;
    Closure * closure;
    struct continuationStruct * next;
} Continuation;

Conceptually, an environment can contain several identifier-closure mappings. However, in the definition above an environment only has one such mapping. Since mappings are created when reducing applications and an abstraction only has one parameter, I keep one mapping in a standalone environment and arrange them hierarchically. When looking up for the mapped closure of an identifier, first try it in its associated environment, and if failed, try it in the parent one.

CEK Machine
There is no significant change to continuation actions. Some new actions, like creating a closure, deleting a closure, creating an environment, looking up in an environment, are very common in the reduction steps. By the way, an identifier is no long a value because it may be mapped to an expression, which can be further reduced. Here are the reduction rules:
1) If the control string is an identifier, look up the mapped closure in the environment, and set the expression and environment of the closure as current expression and environment respectively;
2) If the control string is a value(abstraction or constant), check the type of continuation:
    2.1) If it is FunKK, pop up the continuation, create a new environment that maps the function parameter to current closure, and set the function body and the new environment as the current expression and environment respectively;
    2.2) If it is ArgKK, set the continuation as FunKK, and switch the current expression and environment with these in the closure of continuation respectively;
    2.3) If it is OprKK, pop up the continuation, evaluate the primitive expression, and set the result as the current expression and set the current environment to null;
    2.4) If it is OpdKK, set next argument expression and its environment as current expression and environment respectively;
3) If the control string is an application, create and push a continuation of type ArgKK, whose closure consists of the argument expression and current environment, and set the abstractioin expression as current expression, with current environment unchanged;
4) If the control string is a primitive, create and push a continuation of type OpdKK, whose closure consists of the primitive expression and current environment, and set the first argument expression as current expression, with current environment unchanged.

Though implementation is straightforward according to the reduction rules, the code is getting complicated, so I am not duplicate it here. You can still access it on github.

A drawback of the CEK machine is no intermediate expression can be obtained after each step. What a pity! The machine always delays the substitution and expression is not actually reduced after each step. It does less work at the expense of losing immediate effects.

CK Machine

2011-06-10T16:33:00.000+08:00

In CC and SCC machines, context expands and shrinks when traversing the expression tree in postorder. The nodes in the bottom of the tree are always evaluated before the upper ones. From another perspective, treating the expression as a text string, it is evaluated from innermost to outermost. In the case that the control string is an application, a new innermost application is pushed into the context. In the case that the control string is a value, the innermost application in the context is popped up and the machine decides what to do next by inspecting its shape. I used a first-in last-out list to save the contexts, because the reduction steps only depend on the innermost application, that is the latest context, but not on the rest of the data structure. Compared to the recursive implementation, this iterative evaluator doesn't accumulate runtime stack frames, but this data structure works as an explicit stack in the single runtime stack frame. If the control string is an application, a new "stack frame" is pushed. If it is a value, the top "stack frame" is popped up. Using the control string and information in the popped up "stack frame", the machine decides subsequent actions, performing a reduction or pushing the "stack frame" back. Here is the code snippet making the decision in SCC machine:

// File: eval.c line 92-106 

// control string is the right child
    if(state->controlStr==state->context->expr->children[1]) {
        // pop an expression from the context
        state->controlStr = state->context->expr;
        ctx = state->context;
        state->context = state->context->next;
        cc_deleteContext(ctx);
        ctx = NULL;
        if(!performReduction(state)) {
            return NULL;
        }
    } else {
        state->controlStr = state->context->expr->children[1];
    }

If the control string is the left child of the innermost application, which means it is the function part, the next action is to evaluate the argument. If it is the right child, which means it is the argument, the next action is to perform reduction on the innermost application. I have to inspect such relationship between the control string and innermost application because I didn't store it in the context, although it is available when the context was created. Look at the following code snippet:

// File: eval.c line 115-119

if(!isValue(state->controlStr->children[0])) {
    state->controlStr = state->controlStr->children[0];
}else {
    state->controlStr = state->controlStr->children[1];
}

The shape of the application was clearly known when setting the control string. At this phase, the machine was able to determine the actions once control string is evaluated. If the actions are saved in the newly created context, when popped up later the saved actions can be performed directly without inspecting the shape of the application. For ease of implementation, I will tag each context indicating what to do next when it is popped up. This tagged context is called continuation. The definition is:

// File: ck_machine.h
/* Kind of each continuation. */
typedef enum {
    FunKK, ArgKK, OprKK, OpdKK
} ContinuationKind;

/* Use a LIFO list to represent the continuation. */
typedef struct continuationStruct {
    ContinuationKind tag;
    TreeNode * expr;
    struct continuationStruct * next;
} Continuation;

The innermost application is kept in a continuation as expr. Four actions are defined, with the first two for applications and the other two for primitive applications. If its is FunKK, the next action is to perform reduction on the application; If it is ArgKK, the next action is to evaluate the argument expression; If it is OprKK, the next action is to evaluate the primitive application; If it is OpdKK, the next action is to evaluate the next argument of the primitive application.

CK Machine
Now, the state of the textual machine is changed to a pair of control string and continuation, and this machine is called a CK machine. The reduction rules are similar to that of CC/SCC machine, except for manipulations on continuations:
    1) If the control string is a value(identifier, constant or abstraction), check the type of continuation:
        1.1) If it is FunKK or OprKK, pop up the continuation, set the expression in it as control string, and perform reductions;
        1.2) If it is ArgKK, set the continuation to FunKK, and set the argument expression as control string;
        1.3) If it is OpdKK, set the continuation to OprKK, and set the next argument expression as control string;
    2) If the control string is an application, create and push a continuation of type ArgKK, and set the abstraction expression as control string;
    3) If the control string is an primitive, create and push a continuation of type OpdKK, and set the first argument as control string.

The primitive application only supports two arguments till now, so the next argument just means the second argument. Here is the code implementing the reduction rules:

// File: eval.c
TreeNode * evaluate(TreeNode *expr) {
    State * state = ck_newState();
    state->controlStr = expr;

    Continuation * ctn = NULL;
    while(!ck_canTerminate(state)) {
        if(isValue(state->controlStr)) {
            switch(state->continuation->tag) {
                case FunKK: // pop up the continuation
                case OprKK:
                    state->controlStr = state->continuation->expr;
                    ctn = state->continuation;
                    state->continuation = ctn->next;
                    ck_deleteContinuation(ctn);
                    ctn = NULL;
                    if(!performReduction(state)) {
                        return NULL;
                    }
                    break;
                case ArgKK: // change continuation to FunKK
                    state->continuation->tag = FunKK;
                    state->controlStr = state->continuation->expr->children[1];
                    break;
                case OpdKK: // change to OprKK
                    state->continuation->tag = OprKK;
                    state->controlStr = state->continuation->expr->children[1];
                    break;
                default:
                    fprintf(errOut,"Error: Unknown continuation tag.\n");
                    ck_cleanup(state);
                    return NULL;
                    
            }
        }else {
            if(state->controlStr->kind==AppK) { // push an ArgKK continuation
                ctn = ck_newContinuation(ArgKK);
            }else if(state->controlStr->kind==PrimiK) { // push OpdKK continuation
                ctn = ck_newContinuation(OpdKK);
            }
            ctn->expr = state->controlStr;
            ctn->next = state->continuation;
            state->continuation = ctn;
            state->controlStr = state->controlStr->children[0];
            ctn = NULL;
        }
        #ifdef DEBUG
            // print intermediate steps
            if(!ck_canTerminate(state)) {
                fprintf(out,"-> ");
                printExpression(ck_getProgram(state),out);
                fprintf(out,"\n");
            }
        #endif
    }

    TreeNode* result = state->controlStr;
    ck_deleteState(state);
    return result;
}

The implementation is quite simple but I want to add some words about the CC/SCC and CK machine. From the code and reduction rules, the CK machine looks quite similar to that of CC/SCC machine, and there is only a tiny difference, a tag, in the data structure for context and continuation. However, the ideas behind them are really distinct. For a context, it stores the innermost application expression, which can be thought as data. While for a continuation, besides such data, it also keeps the information for actions, which can be thought as code. In the above implementation, the continuation is attached with a tag, but for other implementations, functions or programs may be attached to make it more usable and flexible. Furthermore, the programmer can even provide a program as actions to continuations explicitly. Another significant difference is: with context, the applications can only be evaluated serially from innermost to outermost, because the relationship of the innermost application and control string is necessary to decide what the next action is. With continuation, this is not required because action is saved in the continuation, and each continuation itself can decide the next action. So in some circumstances, several continuations can be skipped and another continuation can be picked to continue the evaluation. This is essential to control flow and error handling. For example, if an error happens in an application, the machine should go to the function that handles the error, instead of evaluating the next expression in current application. I will go back to this topic in later posts.

CC and SCC Machine

2011-05-28T21:28:00.000+08:00

An obvious inefficiency of our first textual machine is the repeated traversal of the expression tree to find the redex. After each reduction step, it starts over again from the root node. We really don't have to do this, because the next redex is often the reduction result of current redex, or at least, closes to the current one. Let's consider the evaluation of the following expression:
(+ ((lambda x (lambda y y) x) 1) 1)
    => (+ ((lambda y y) 1) 1)
    => (+ 1 1)
    => 2

The redex for each step is underlined. In the first two steps, the redex for next step is just the evaluation result of the current redex. And in the third step, the next redex is the parent expression of the result of previous step. Actually, we can identify the next redex by checking the result of current one or its parent for every expression. Suppose the evaluation result of a redex is an application, if either of its children is not a value, the non-value child expression will be the next redex. Otherwise, the result itself will be the next one. Suppose the result is a value, its parent or the other child will probably be the next redex. We didn't do this kind of checking in the textual machine, because we only had the complete expression as our machine state, and the machine were not aware of the result and its parent. Though this could be obtained in the implementation, from the model view, the machine does only know the complete expression. So in this post, two new machines using the strategy will be defined to improve the efficiency.

CC Machine
According to the discussion above, if the textual machine knows the redex and its parent, it can easily decide what the next redex is, rather than traversing the entire expression tree again. To keep it running until getting the final result, not just the parent of the redex, but also the parent's parent should be recorded. The redex is the machine currently interested in, and it is called control string. Except the redex, the other part of the expression is called evaluation context, from which all the parents can be obtained. The two elements are paired together to form the machine's state. So this machine is called CC machine. Combining the control string and context yields the complete expression, which is the state of the previous machine. I'd like to call the complete expression as program. Initially, the program is the control string, and the context is empty. The termination condition of this machine is when the control string is a value and context is empty. Here is the reduction rules for this machine:
    1) If the control string is a value(identifier, constant or abstraction), remove its parent from the context, and set the parent as control string;
    2) If the control string is an application or primitive, and at least one of its children is not a value, put itself into the context and set the non-value child as control string;
    3) If the control string is an application or primitive, and both of its children are values, perform reductions on it and set the result as control string.

To find the first redex, we still need to traverse the expression tree, but the traversed nodes should be remembered in the context. Since only the parent of control string is interested for each step, and from each traversed parent, we can navigate to any part of the program, I use a FILO(First-In-Last-Out) list of the traversed nodes to represent the context(Actually, we don't need such kind of data structure if a pointer to parent node is added to each node, but this requires changes to the parser, so I don't choose this option). From the implementation view, the machines perform evaluations by popping and pushing control string into or from the context to find the redex. Here is the definition for machine state and the context:

// file: cc_machine.h
/* Use a LIFO list to represent the context. */
typedef struct contextStruct {
    TreeNode * expr;
    struct contextStruct * next;
} Context;

/* Machine state is a pair of control string and the context. */
typedef struct stateStruct {
    TreeNode * controlStr;
    Context * context;
} State;

From the reductions rules, we can easily derive the actions on context:
    1) If the control string is a value, pop the head node from the list and set the node as control string;
    2) If the control string is an application or primitive, and at least one of its children is not a value, push it into the head of the list and set the non-value child as control string;
    3) If the control string is an application or primitive, and both of its children are values, perform reductions on it and set the result as control string and no action for context.

Here is the listing of code:

// file: eval.c
TreeNode * evaluate(TreeNode *expr) {
    State * state = cc_newState();
    state->controlStr = expr;

    Context * ctx = NULL;
    while(!cc_canTerminate(state)) {
        if(isValue(state->controlStr)) {
            // pop an expression from the context
            state->controlStr = state->context->expr;
            ctx = state->context;
            state->context = state->context->next;
            cc_deleteContext(ctx);
            ctx = NULL;
        }else {
            if(!isValue(state->controlStr->children[0])
                || !isValue(state->controlStr->children[1])) {
                // push the current expression into context
                ctx = cc_newContext();
                ctx->expr = state->controlStr;
                ctx->next = state->context;
                state->context = ctx;
                if(!isValue(state->controlStr->children[0])) {
                    state->controlStr = state->controlStr->children[0];
                }else {
                    state->controlStr = state->controlStr->children[1];
                }
            } else { // evaluate control string
                if(state->controlStr->kind==AppK) {
                    if(state->controlStr->children[0]->kind==ConstK) {
                        fprintf(errOut, "Error: cannot apply a constant to any argument.\n");
                        fprintf(errOut, "\t\t");
                        printExpression(state->controlStr,errOut);
                        cc_cleanup(state);
                        return NULL;
                    }else if(state->controlStr->children[0]->kind==IdK) {
                        // find function from builtin and standard library
                        TreeNode* fun = resolveFunction(state->controlStr->children[0]->name);
                        if(fun==NULL) {
                            fprintf(errOut, "Error: %s is not a predefined function.\n", state->controlStr->children[0]->name);
                            cc_cleanup(state);
                            return NULL;
                        }
                        deleteTree(state->controlStr->children[0]);
                        state->controlStr->children[0] = fun;
                    } else {
                        TreeNode *tmp = betaReduction(state->controlStr);
                        if(state->context!=NULL) {
                            if(state->context->expr->children[0]==state->controlStr) {
                                state->context->expr->children[0] = tmp;
                            }else {
                                state->context->expr->children[1] = tmp;
                            }
                        }
                        state->controlStr = tmp;
                    }
                }else if(state->controlStr->kind==PrimiK) {
                    // only perform primitive operation if operands are constants
                    if(state->controlStr->children[0]->kind==ConstK
                        && state->controlStr->children[1]->kind==ConstK) {
                        TreeNode* tmp  = evalPrimitive(state->controlStr);
                        if(state->context!=NULL) {
                            if(state->context->expr->children[0]==state->controlStr) {
                                state->context->expr->children[0] = tmp;
                            } else {
                                state->context->expr->children[1] = tmp;
                            }
                        }
                        deleteTree(state->controlStr);
                        state->controlStr = tmp;
                    } else {
                        fprintf(errOut, "Error: %s can only be applied on constants.\n", state->controlStr->name);
                        cc_cleanup(state);
                        return NULL;
                    }
                }else {
                    fprintf(errOut,"Error: Cannot evaluate unkown expression kind.\n");
                    cc_cleanup(state);
                    return NULL;

                }
            }
        }
        #ifdef DEBUG
            // print intermediate steps
            if(!cc_canTerminate(state)) {
                fprintf(out,"-> ");
                printExpression(cc_getProgram(state),out);
                fprintf(out,"\n");
            }
        #endif
    }

    TreeNode* result = state->controlStr;
    cc_deleteState(state);
    return result;
}

Let's try it:

$ ./main
Welcome to Lambda Calculus Evaluator.
Press Ctrl+C to quit.

> (lambda x x) (lambda y y) 1
-> (lambda x x) (lambda y y) 1
-> (lambda y y) 1
-> (lambda y y) 1
-> 1

SCC Machine
Examining the reduction steps at the end of the last section, step 2 and 3 are the same. That's because after step 2, the control string is (lambda y y) and the context is the parent of it. Based on the rules, the machine pops the parent and set it as control string. The machine state is changed but not actual reduction is performed on the program, so the program for both steps are the same. After that, beta-reduction is performed on the control string. Actually, we only have two possible actions after step 2: performing beta-reduction or primitive evaluation on the parent node or setting the other child as control string. We can simplify the process by checking the parent node so those two steps can be combined into one. Rule 1) of the CC machine is now revised to:
1') If the control string is a value and the other child of its parent is a value too, remove its parent from the context, perform reductions to it and set the result as control string. Otherwise, set the other child as control string.

The code needs only simple changes, so I won't duplicate it here. Here is the evaluation steps for the same expression, and the duplicated step is gone:

$ ./main
Welcome to Lambda Calculus Evaluator.
Press Ctrl+C to quit.

> (lambda x x) (lambda y y) 1
-> (lambda x x) (lambda y y) 1
-> (lambda y y) 1
-> 1

Compared to CC machine, SCC machile always has less steps. All the code is available at here.

Textual Machine

2011-05-22T00:30:00.000+08:00

For a complex expression, such as a recursive function using Y, we may go through dozens of reduction steps until getting to the final result. Currently, our evaluator only gives the final result. However, these intermediate steps are really useful for analysis and troubleshooting sometimes. Just like the manual reductions we did in last post, we can check whether the evaluator follows the reduction rules by examining the intermediate steps. So in this post, I am going to refactor the implementation of the evaluator so that it is able to print the intermediate reduction steps.

Recursive Way
An essential task of the evaluator is to find the redex to be reduced next. In our current implementation, we find it in a recursive way. That is, to find a redex in an expression, we try to find it in its child expressions first. If not found, we check if the expression itself is a redex. In this process, the evaluate function may call itself for some subexpressions. This keeps the code simple and clean. However, it also puts us in a dilemma that we cannot get the whole picture of the evaluation process. In each function invocation, we are only aware of the expression or subexpression which is under evaluation, but we don't know its role(as a function or an argument) in the original expression, what its parent expression is and so on. All the information is called evaluation context. Actually, we do have it in the sequence of C function calls. In the runtime environment of C, the function invocations are stored in a stack, and for each one, there is a stack frame for it, which keeps data for arguments, results and temporary values. So the expression we are currently evaluating is stored in the top stack frame, and its parent is stored in a previous one, and so on. The evaluation context is hidden in the list of stack frames, but we don't have an easy way to get them in C.

A potential solution is to use a global variable pointing to the root of the expression tree and print it after each evaluation step. However, this method may not work for all cases. Take (lambda x + x x) 1 as an example, after a beta-reduction, the original tree is deleted with a new tree returned as the result, so the global variable becomes a dangling pointer. Even if this could meet our requirement for printing intermediate evaluation steps, we still cannot get more evaluation context information. So I am going to implement the evaluation algorithm in a different way to make the information easy accessible.

Iterative Way
The problem for recursive way is the evaluation context is saved across many stack frames and only that in the top one is accessible. So a solution we can easily thought of is keeping all the evaluation context information in the same stack frame. We need to get rid of the recursive calls and use an iterative way. To find the redex, we need to traverse the expression tree, and all the work is done in a single evaluate function call. Since everything is in the same stack frame now, we are allowed to get anything about the evaluation context.

Based on the call-by-value evaluation strategy, we can derive the following rules to find a redex:
1) An identifier, constant or abstraction expression is not a redex;
2) If the expression is an application or primitive application, check its child expressions from left to right, if anyone is not a value, find the redex in it. Otherwise, pick the expression as a redex.

Since the leftmost expression and the argument expression is evaluated first, we need a post-order traversal of the expression tree to find the redex and evaluate it. After each step, a new expression is got and it is closer to the final result. The same post-order traversal will be performed on the expression again and again, until a value is returned. For the case that an expression can never reduce to a value, the evaluator will run forever. For another case that something is wrong in the expression, an error message will be printed and the evaluator will returns NULL. The error handling mechanism will be added in the future so values will be returned for erroneous expressions as well. Here is the code for this iterative way:

// file: eval.c
TreeNode * evaluate(TreeNode *expr) {
    TreeNode* state = expr;
    TreeNode** previous = NULL;
    TreeNode* current = NULL;
    while(state!=NULL && !isValue(state)) {
        previous = &state;
        current = state;
        while(current!=NULL) {
            if(!isValue(current->children[0])) {
                previous = ¤t->children[0];
                current = current->children[0];
            }else if(!isValue(current->children[1])) {
                previous = ¤t->children[1];
                current = current->children[1];
            }else { // reduce the current node
                if(current->kind==AppK) {   // applications
                    if(current->children[0]->kind==ConstK) {
                        fprintf(errOut, "Error: cannot apply a constant to any argument.\n");
                        fprintf(errOut, "\t\t");
                        printExpression(current,errOut);
                        deleteTree(state);
                        return NULL;
                    }else if(current->children[0]->kind==IdK) {
                        // find function from builtin and standard library
                        TreeNode* fun = resolveFunction(current->children[0]->name);
                        if(fun==NULL) {
                            fprintf(errOut, "Error: %s is not a predefined function.\n", current->children[0]->name);
                            deleteTree(state);
                            return NULL;
                        }
                        deleteTree(current->children[0]);
                        current->children[0] = fun;
                        break;
                    }
                    current=betaReduction(current);
                    *previous = current;
                    break;
                }else if(current->kind==PrimiK) {  // primitive application
                    // only perform primitive operation if operands are constants
                    if(current->children[0]->kind==ConstK
                        && current->children[1]->kind==ConstK) {
                        TreeNode* tmp  = evalPrimitive(current);
                        deleteTree(current);
                        current = tmp;
                        *previous = current;
                        break;
                    } else {
                        fprintf(errOut, "Error: %s can only be applied on constants.\n", current->name);
                        deleteTree(state);
                        return NULL;
                    }
                }else {
                    fprintf(errOut,"Error: Cannot evaluate unkown expression kind.\n");
                    deleteTree(state);
                    return NULL;
                }
            }
        }
        #ifdef DEBUG
            // print intermediate steps
            if(!isValue(state)) {
                fprintf(out,"-> ");
                printExpression(state,out);
                fprintf(out,"\n");
            }
        #endif
    }
    return state;
}

In the code, variable state keeps the intermediate expression during the evaluation, so it is used to print the intermediate steps. Variable current points to the subexpression we are currently working with, and previous is a pointer to the current pointer, so after a beta-reduction or primitive evaluation is performed on the current subexpression, we can make the parent of current point to the new expression by changing the value of previous. The state and previous variable save part of the evaluation context information, and if others are needed, such as parent expression of the redex, they can be added easily. There are two loops in the code. The outer one runs until the evaluation result is a value, and the inner one implements the post-order traversal to find and evaluate the redex. The isValue() function tests if an expression is a value, which is identifier, constant or abstraction for now. The resolveFunction() function finds a predefined function from libraries in the order of builtin library and standard library. After each step, the intermediate expression is printed if the DEBUG flag is set.

Let's try a simple example:

$ ./main
Welcome to Lambda Calculus Evaluator.
Press Ctrl+C to quit.

> (lambda x * 2 x) ((lambda x x) 3)
-> (lambda x * 2 x) 3
-> * 2 3
-> (lambda x (lambda y x `*` y)) 2 3
-> (lambda y 2 `*` y) 3
-> 2 `*` 3
-> 6

Textual Machine

In a real computer, a set of registers is used to keep the computation states, such as PC, and a list of instructions like ADD and MOV can be performed on the state to transform the machine to a new state. Our evaluator can be considered as a machine too. In contrast, the state is the expression, and the instructions are the reductions that transform expressions to expressions. We call this a textual machine, because expressions are represented as texts. This is the first textual machine we have implemented, and to improve it, a few more will be introduced in later posts.

Recursion and Y Combinator

2011-05-16T23:34:00.000+08:00

Today, I will talk about an important concept: recursion. It means a function could call itself inside its body. With recursion, many difficult problems can be solved in an easily understood way. A good case in point is the problem of Tower of Hanoi. In this post, a much simpler problem is used to demonstrate the concept of recursion and how we implement it in our evaluator.

Till now, our evaluator is capable of doing basic arithmetics, but that's not enough for a real programming language. Let's consider this problem: how to compute the factorial of n? For 3, we can compute it using (* 3 (* 2 1)); For 4, it is (* 4 (* 3 (* 2 1))). However, for n, we cannot write out the expression, because n is unknown when we are defining the function. By observing factorial 3 and 4, we can easily find out that factorial 4 is the multiplication of integer 4 and factorial 3. We can derive a recursive solution like this: to compute factorial of n, we can multiply n by factorial of n-1; to compute factorial of n-1, we can multiply n-1 by factorial of n-2; and so on. Until we meet factorial 1, whose result we know is 1. This is called the base case, where the recursion is stopped at. Start with this strategy, we can compute the factorial of n without writing out the whole expression, because the recursion will take care of it for us.

Recursion
Based on the idea described before, we can define the factorial function recursively as follows:
factorial := (lambda n (= n 1) 1 (* n (factorial (- n 1))))

We use the ":=" symbol to assign a name to a function to assist explanation and it has nothing to do with our lambda calculus evaluator. The = function checks the equality of two integers and returns a boolean value. This is not a correct expression because lambda calculus doesn't allow a function to refer to itself. Moreover, we are not able to write out such an expression, because when defining a function we need itself inside the body. Though we don't have the function when we are defining it, it will be available later. Thus, instead of referring to itself, the factorial function could have us supply a factorial function t as an argument. Using this strategy, the function we define is no longer a factorial function, but a factorial maker function: it takes some factorial function and produce a factorial function. The mkfactorial function is defined as:
    mkfactorial := (lambda t (lambda n (= n 1) 1 (* n (t (- n 1)))))

This is a legal expression in our lambda calculus evaluator, but it still sounds strange. We are defining a factorial function, but we rely on another factorial function. Obviously, we still don't have a factorial function. Think again, what if we change the definition of mkfactorial to which requires a maker function as an argument instead of a factorial functioin? We assume the mkfactorial function apply on a maker function t would produce a factorial function, and for every occurrence of a factorial function in the body we use (t t), because applying a maker function to itself produces a factorial function. We redefine the function as follows:
    mkfactorial' := (lambda t (lambda n (= n 1) 1 (* n ((t t) (- n 1)))))

And we could get factorial function by applying mkfactorial' to itself:
    factorial := mkfactorial' mkfactorial'

To examine whether the solution works, we are going to reduce factorial 3 and factorial n. To save space, I will use the names for the functions defind above during the reduction and only expand them when necessary. Remember, when evaluated in our evaluator, only the expanded expressions are kept. For factorial 3:
factorial 3
    = mkfactorial' mkfactorial' 3
    = (lambda t (lambda n (= n 1) 1 (* n ((t t) (- n 1))))) mkfactorial' 3
    => (lambda n (= n 1) 1 (* n ((mkfactorial' mkfactorial') (- n 1)))) 3
    => (= 3 1) 1 (* 3 ((mkfactorial' mkfactorial') (- 3 1)))
    => (* 3 ((mkfactorial' mkfactorial') 2))
    = (* 3 ((lambda t (lambda n (= n 1) 1 (* n ((t t) (- n 1))))) mkfactorial' 2))
    => (* 3 ((lambda n (= n 1) 1 (* n ((mkfactorial' mkfactorial') (- n 1)))) 2))
    => (* 3 ((= 2 1) 1 (* 2 ((mkfactorial' mkfactorial') (- 2 1)))))
=> (* 3 (* 2 ((mkfactorial' mkfactorial') 1)))
    = (* 3 (* 2((lambda t (lambda n (= n 1) 1 (* n ((t t) (- n 1))))) mkfactorial' 1)))
=> (* 3 (* 2 ((lambda n (= n 1) 1 (* n ((mkfactorial' mkfactorial') (- n 1)))) 1)))
=> (* 3 (* 2 ((= 1 1) 1 (* 1 ((mkfactorial' mkfactorial') (- 1 1))))))
=> (* 3 (* 2 1))
=> 6

And factorial n:
factorial n
    = mkfactorial' mkfactorial' n
    = (lambda t (lambda n (= n 1) 1 (* n ((t t) (- n 1))))) mkfactorial' n
    => (lambda n (= n 1) 1 (* n ((mkfactorial' mkfactorial') (- n 1)))) n
    => (= n 1) 1 (* n ((mkfactorial' mkfactorial') (- n 1)))
    => (* n ((mkfactorial' mkfactorial') (- n 1))

The meaning of (mkfactorial' mkfactorial') (- n 1) is factorial of n-1, and the result is what we want for factorial of n.

Y Combinator
Using the technique in the last section, we can construct the expressions for recursive functions from scratch. For each function, we always need to go through the following process: writing a function that refers to itself, changing it to a maker function, revising the maker function to make it accepts another makers function, and finally applying the maker function to itself. This is boring and clumsy. The significant part that makes each recursive function different is the maker function. Can we abstract this process into a function and the only thing we need to provide is a maker function?

The function we are eager to have is one that accepts a maker function and produces a recursive function. A maker function consists of two parts: a base case and a recursive case. The recursive stops when reaching the base case. Let's call the target function mk, and it is defined as:
    mk := (lambda t t (mk t))

Since argument t is a maker function, apply t to a recursive function, which we can make from (mk t) here, would again produce a recursive function, which is the result of mk. This is how we come up the definition of mk. Still, it is an illegal expression because mk refers to itself. Using the same technique as before, we can derive the maker function:
    mkmk' := (lambda k (lambda t t ((k k) t)))

and the mk function:
    mk := mkmk' mkmk'

We omitted the mkmk function. Now, we can define the factorial function as (mk mkfactorial). Let's check its behavior:
factorial
    = mk mkfactorial
    = (lambda k (lambda t t ((k k) t))) mkmk' mkfactorial
    => (lambda t t ((mkmk' mkmk') t)) mkfactorial
    => mkfactorial ((mkmk' mkmk') mkfactorial)
    = mkfactorial (mk mkfactorial)

According to the definition of mk, (mk mkfactorial) makes a factorial function, so the last step above is a factorial function. This is what we want.

With this mk function, we can define other recursive functions by providing a maker function. If we want to compute the sum of 1...n, we can define the function as follows:
    sum := mk (lambda t (lambda n (= n 1) 1 (+ n (t (- n 1)))))

In lambda calculus, mk is just one of such kind of functions. The more famous one is called Y:
    Y := (lambda f (lambda x f (x x)) (lambda x f (x x)))

Sometimes, when we are talking about Y combinator, it doesn't just mean the Y function, but a collection of functions like Y and mk.

Standard Library
The Y combinator is very useful for defining recursive functions. However, it is very inconvenient to write out the long expression every time we need it. So I would like to implement it as a predefined function in our evaluator, and we only need to call the Y function to use it. Unfortunately, the definition above cannot be used directly in our evaluator. Let's take a look at the reason:
Y g
    = (lambda f (lambda x f (x x)) (lambda x f (x x))) g
    => (lambda x g (x x)) (lambda x g (x x))
    => g ((lambda x g (x x)) (lambda x g (x x)))

In an eager evaluator, it won't progress in last step above, because the underlined part is an infinite loop and it can't be evaluated to a value. Since the argument is evaluated before applied to the function, g is never called in our current evaluator. This problem doesn't exist in a lazy evaluator. To solve this, we can change the underlined part to an abstraction expression. Do you still remember the η-conversion(that means λx. f x => f)? We can use the inverse-η conversion to change each application in Y into an abstraction.
Y := (lambda f

            (lambda a

                (lambda x f (lambda g (x x) g))

                (lambda x f (lambda g (x x) g)) a))

Let's try to apply this new Y on mkfactorial:
Y mkfactorial
    = (lambda f (lambda a (lambda x f (lambda g (x x) g)) (lambda x f (lambda g (x x) g)) a)) mkfactorial
    => (lambda a (lambda x mkfactorial (lambda g (x x) g)) (lambda x mkfactorial (lambda g (x x) g)) a)
    => (lambda x mkfactorial (lambda g (x x) g)) (lambda x mkfactorial (lambda g (x x) g))
    => mkfactorial (lambda g ((lambda x mkfactorial (lambda g (x x) g)) (lambda x mkfactorial (lambda g (x x) g))) g)

Look at the last step, the underlined part is a function now, so we can apply it to the mkfactorial function. To save space, let's mark the underlined part as symbol T:
    => (lambda t (lambda n (= n 1) 1 (* n (t (- n 1))))) T
    => (lambda n (= n 1) 1 (* n (T (- n 1))))

This is the recursive function we finally get. Let's apply it on integer 1:
Y mkfactorial 1
    => (= 1 1) 1 (* 1 (T (- 1 1)))
    => (lambda x (lambda y x)) 1 (* 1 (T (- 1 1)))
    => (lambda y 1) (* 1 (T (- 1 1)))

In a lazy evaluator, the result 1 is returned from last step. While in our current eager evaluator, we won't get the expected result because of our implementation of if-statement using booleans. Currently, the boolean value is encoded using a function that cosumes two arguments. The (= 1 1) expression is evaluated to (lambda x (lambda y x)). Though the underlined part is never used in the function, we still have to evaluated it, and we will go into an infinite loop when doing so. From this example, we can conclude that Y combinator doesn't work in an eager evaluator which implements the if-statement as a pure function. To solve this, one way is using a lazy evaluation strategy. Another way is treating if-statement as a special form like Scheme. We choose the first option here, so all the things we talk later are implemented in our call-by-name evaluator.(If you use the second option, the Y function defined before will work without further modifications.)

Before adding Y function into our evaluator, I'd like to say a few words about builtin library and standard library. Till now, all the predefined functions in our evaluator are builtin functions, such as +, -, > and =. All the functions require the support of primitive operators by the evaluator. We cannot implement them using pure lambda calculus expression. While for standard functions, they are implemented as lambda calculus expressions. Without the builtin library, some features of the evaluator are lost, but without the standard library, programmers can still achieve the same effect by implementing the standard functions themselves using basic expressions. So the standard library is not mandatory and usually for programmer's convenience. The Y function is for such purpose, so we define it in the standard library.

The standard library is implemented in stdlib.h and stdlib.c files. It is similar to the implementation of builtin functions, so I won't duplicate the code here. The tricky part is that the yyparse() method is used to parse the expressions for standard functions into tree structure, so it could be used by the evaluator. The simple version of Y function is used because it works in our call-by-name evaluator. The evaluate function is also updated to search functions by name in the standard library. Please refer to source code for more information.

Some other functions, such as not, or and and, are added into the standard library in the same way. As an ending, let's try the factorial, sum and a more complex fibnacci function in our evaluator:

$ ./main
Welcome to Lambda Calculus Evaluator.
Press Ctrl+C to quit. 

# factorial 3
> Y (lambda t (lambda n (= n 1) 1 (* n (t (- n 1))))) 3
-> 6

# sum 4
> Y (lambda t (lambda n (= n 1) 1 (+ n (t (- n 1))))) 4
-> 10

# fibnacci 7
> Y (lambda t (lambda n (or (= n 1) (= n 2)) 1 (+ (t (- n 1)) (t (- n 2))))) 7
-> 13

Eager and Lazy Evaluation

2011-05-14T22:13:00.000+08:00

In the post that solves the partially reduced problem, we talked about a defective evaluation and a robust one. Though they are quite different, there is one principle that is kept by both of them: evaluating the argument expression before applying it to the function. This is called eager evaluation. In our evaluator, the argument won't be applied to the function until it is evaluated to a value. Many programming languages use this eager evaluation strategy, such as C, Java and Scheme. Most programming languages have a if-statement: if condition then-clause else else-clause. When condition is true, the then-clause is executed; otherwise, the else-clause is excecuted. At any time, only one of them will be executed. In our evaluator, we use the boolean encoding, which is a function that accepts two parameters, to simulate such if-statement. However, it has a different semantic. Since we use eager evaluation, both arguments will be evaluated before applying to the function. Though only one argument is needed, still both are evaluated. This is the problem of implementing if-statement using pure functions in an eager evaluation manner(that's why Scheme provide if as a special form instead of a pure function). To solve this, we need the lazy evaluation. That is, the argument expression is not evaluated unless it is actually needed in the evaluation of the function body.

These two evaluation strategies will be discussed in detail in the following sections and we will show how to implement them by revising our current evaluator as well.

Eager Evaluation
As stated above, in eager evaluation, the argument to a function is always evaluated completely before applied to the function. Regarding to whether evaluating the body of a function, it can be further divided to applicative order and call by value.

Applicative Order
Though our defective evaluator has "partially reduced problem", we can add a tiny fix to make it work. Since the problem only happens after evaluating the application expression, we can decide whether to keep evaluating after the beta-reduction by checking its result: if it is primitive expression, or it is an application expression and its left child is an abstraction expression, which means the result is reducible, we will continue evaluating the result. Here is the code:

// file: eval.c
TreeNode * evaluate(TreeNode *expr) {
    TreeNode* result = expr;
    if(expr!=NULL) {
        switch(expr->kind) {
            case IdK:
            case ConstK:
                return expr;
            case AbsK:
                expr->children[1] = evaluate(expr->children[1]);
                return expr;
            case AppK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                if(expr->children[0]->kind==IdK) {
                    // expand tree node for builtin functions
                    BuiltinFun* fun = lookupBuiltinFun(expr->children[0]->name);
                    if(fun!=NULL) {
                        expr->children[0] = (fun->expandFun)();
                    }
                }
                result = betaReduction(expr);
                // beta-reduction may result in primitive operations
                if(result->kind==PrimiK ||
                    (result->kind==AppK && result->children[0]->kind==AbsK)) {
                    result = evaluate(result);
                }
                return result;
            case PrimiK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                // only perform primitive operation if operands are constants
                if(expr->children[0]->kind==ConstK
                    && expr->children[1]->kind==ConstK) {
                    result = evalPrimitive(expr);
                }
                return result;
            default:
                fprintf(errOut,"Unkown expression kind.\n");
        }
    }
    return expr;
}

In this fixed evaluator, the body of an abstraction expression is evaluated first, and arguments are evaluated from left to right(our syntax gurantees this). We call this applicative order(or leftmost innermost). As discussed in the post "Solving Partially Reduced Problem", this strategy can not reduce some expressions though they could be, such as (lambda x 7) (lambda x (lambda y y y) (lambda y y y)). Since the body of an abstraction is evaluated first, it will go into an infinite loop when evaluating the body of the argument, though it is never used in the function (lambda x 7).

Call by Value
The robust evaluation strategy we use is very common in modern programming languages. Unlike applicative order, it never evaluates the body of an abstraction expression. This is called call-by-value evaluation, because every argument must be reduced to a value before calling the function. Obviously, this call-by-value strategy can evaluate the expression referred at the end of last section, because it doesn't evaluate the body of an abstraction expression, but it still has the similar problem. Take (lambda x 7) ((lambda y y y) (lambda y y y)) as an example, this time we have an application expression as the argument, which cannot be reduced to a value. Apparently, call-by-value evaluation won't compute a value for such cases.

Lazy Evaluation
From the failed cases in the previous section, we learned that there are cases that argument expressions are never used in the function, so it is not necessary to evaluate them before applying to the function. Why don't we just pass them to the function and evaluate them only when we actually need them? Lazy evaluation is such a strategy that doesn't evaluate arguments until they are actually needed in the evaluation of the function body.

Normal Order
Normal order(or leftmost outermost) is the counterpart of applicative order in lazy evaluation. Though it doesn't evaluate arguments, it still evaluates the body of a function first, because its goal is to reduce the expression as much as possible. When implementing the evaluator, the right child of the application expression is not evaluated, and it is used directly to substitute the free occurences of the parameter in the body of the function. So if the argument is not used in the function, it will be ignored and never evaluated. Here is the full listing of code:

// file: eval.c
TreeNode * evaluate(TreeNode *expr) {
    TreeNode* result = expr;
    if(expr!=NULL) {
        switch(expr->kind) {
            case IdK:
            case ConstK:
                return expr;
            case AbsK:
                expr->children[1] = evaluate(expr->children[1]);
                return expr;
            case AppK:
                expr->children[0] = evaluate(expr->children[0]);
                if(expr->children[0]->kind==IdK) {
                    // expand tree node for builtin functions
                    BuiltinFun* fun = lookupBuiltinFun(expr->children[0]->name);
                    if(fun!=NULL) {
                        expr->children[0] = (fun->expandFun)();
                    }
                }
                result = betaReduction(expr);
                // beta-reduction may result in primitive operations
                if(result->kind==PrimiK ||
                    (result->kind==AppK && result->children[0]->kind==AbsK)) {
                    result = evaluate(result);
                }
                return result;
            case PrimiK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                // only perform primitive operation if operands are constants
                if(expr->children[0]->kind==ConstK
                    && expr->children[1]->kind==ConstK) {
                    result = evalPrimitive(expr);
                }
                return result;
            default:
                fprintf(errOut,"Unkown expression kind.\n");
        }
    }
    return expr;
}

This strategy can evaluates more expressions than those eager ones, including the two failed expressions referred before. You could try them out.

Call by Name
In contrast to normal order, call-by-name doesn't evaluate the body of functions. The name of parameter is bound to the argument expression. So as normal order evaluation, every occurence of the parameter in the body of a function is substituted by the argument without evaluation. We implement this evaluator based on the robust evaluation, and only a tiny modification is needed to achieve such a call-by-name evaluator:

// file: eval.c
TreeNode * evaluate(TreeNode *expr) {
    TreeNode* result = expr;
    if(expr!=NULL) {
        switch(expr->kind) {
            case IdK:
            case ConstK:
            case AbsK:
                return expr;
            case AppK:
                expr->children[0] = evaluate(expr->children[0]);
                if(expr->children[0]->kind==IdK) {
                    // expand tree node for builtin functions
                    BuiltinFun* fun = lookupBuiltinFun(expr->children[0]->name);
                    if(fun!=NULL) {
                        expr->children[0] = (fun->expandFun)();
                    } else {
                        fprintf(errOut, "Error: %s is not a builtin function.\n", expr->children[0]->name);
                        return expr;
                    }
                }
                return evaluate(betaReduction(expr));
            case PrimiK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                // only perform primitive operation if operands are constants
                if(expr->children[0]->kind==ConstK
                    && expr->children[1]->kind==ConstK) {
                    result = evalPrimitive(expr);
                } else {
                    fprintf(errOut, "Error: %s can only be applied on constants.\n", expr->name);
                }
                return result;
            default:
                fprintf(errOut,"Unkown expression kind.\n");
        }
    }
    return expr;
}

An imperfect part of call-by-name strategy is that if an argument is used several times in the function, it is re-evaluated each time. So it is often slower than call-by-value. Take (lambda x + x x) (+ 1 2) as an example, the parameter x is used twice in the function body, so we need to evaluate (+ 1 2) twice, while it is evaluated once in the call-by-value evaluation.

Call by Need
To solve the performance problem of call-by-name, we can save the result of each argument when first time evaluated, and when it is used again, we don't need to evaluate it any more. Call-by-need is a memoized version of call-by-name, when the argument is evaluated, the result is stored for subsequent uses. It produces the same result as call-by-name. To implement it, some data structure, such as symbol table, are needed to store the values. Another challenge is arguments are not evaluated in the contexts where they are define. To do this correctly when they are needed, the context in which the argument expression is defined should be attached to it. This requires another important concept called environment and I'd like to implement it in the future.

Now, we have various evalutors with different evaluation strategies in our toolbox. In the future, if I don't emphasize a particular evaluator, that means we are talking about the call-by-value evaluation. Otherwise, I will specify which evaluation strategy we are talking about.

This post only mentioned some common evaluation strategies. For a complete list, please refer to Evaluation strategy. Remember you can still reach the full list of code from here.

Solving Partially Reduced Problem

2011-04-16T11:38:00.001+08:00

We met the "partially reduced problem" when we were adding the builtin function feature. That is, the primitive expression is returned unevaluated, though it can still be reduced. Actually, it doesn't only happen on the primitive expression, but also exists for ordinary expressions. Let's try another one:

$ ./main
Welcome to Lambda Calculus Evaluator.
Press Ctrl+C to quit.

> (lambda x (lambda y y x)) 1 (lambda x x)
-> (lambda x x) 1

Obviously, the result can be further reduced to 1. Let's do a simulation of the evaluation algorithm to see why we have such problem. The expression is evaluated from left to right. First, we need to evaluate (lambda x (lambda y y x)) 1. The left hand side is an abstraction, whose body is an abstraction too. We need to evaluate its body first. The inner body y x is evaluated to y x, so it remains unchanged. The right hand side is a constant and the result is itself. After performing a beta-reduction, the expression turns to (lambda y y 1). Then, we have (lambda y y 1) (lambda x x). Both left and right hand sides are abstraction and keeps unchanged after evaluating their bodies. Finally a beta-reduction is performed and it results in (lambda x x) 1. It is not a primitive expression, so the evaluation terminates and result (lambda x x ) 1 is returned.

This kind of "partially reduced problem" exists in many expressions, so we need to fix it. However, before doing that, we will define what "totally reduced" is, as opposed to "partially reduced".

Evaluation Values
Partially reduced result is generated because the evaluator terminates at a point where it shouldn't. So essentially we are talking of the termination condition. That means our evaluator should only terminate where some conditions are met. Otherwise, it should keep evaluating the resulted expression. So if the resulted expression doesn't meet the conditions, it should never be returned. I'd like to call the expressions that can be returned as evaluation values, values for short, because they are the only results our evaluator can give out.

From our current evaluation algorithm, we can easily identify that identifiers and constants are values. For an abstraction, though we may evaluate its body first(it turns out to be a bad strategy, we will get rid of this later), we can still return it as a result. For applications and primitives, we will always perform reductions on them. So we define the evaluation values as:

    V = identifier | constant | abstraction

The evaluator terminates only if it can return the above values. It should continue to evaluate the expression if it is an application or primitive expression. However, the evaluator doesn't always guarantee to return a value for every expression. Take x y as an example, it is an application expression but it can not be further reduced because x is not a defined function. Another example is + (lambda x x) 1, with the + function can only be applied on constants. It doesn't make sense to apply + on abstractions, so it cannot be reduced to a value. Those two are invalid expressions, and we will add error handling mechanism for them in the future. Another set of expression is those that can be reduced but it never stops, such as (lambda x x x) (lambda x x x). It is an infinite loop, and the evaluator runs forever. The evaluator needs to take both of these expressions into consideration, too.

Defective Evaluation Strategy
I never inspected our current evaluation strategy in the past posts, so I am going to discuss it in detail and find the defects. Currently, the evaluator obeys the following rules:
    1) Evaluate the body of an abstraction before returning it;
    2) Evaluate both parts of the application first, then perform beta-reduction for once, and return the result.

In rule 2), I perform beta-reduction for only once because I assume after performing rule 1) to an abstraction expression, it will be simple enough so no reducible expressions could be generated by applying it to any expression. For example, for expression (lambda x (lambda y y) x) 1, before applying the abstraction to 1, it will be simplified to (lambda x x). After that, we apply it to 1 and we get the result 1. However, this is not always true. The expression mentioned at the beginning of this post is a good counterexample. And we probably have this problem when providing an abstraction as a parameter to another abstraction.

The defective assumption for rule 2) is the root cause of "partially reduced problem". Besides that, rule 1) is also a stupid choice. Consider expression (lambda x 7) (lambda x (lambda y y y) (lambda y y y)). Apparently, the result is 7, but if we evaluate the body of an abstraction first, we will go into an endless loop.

From the above analysis, we learned that performing beta-reduction only once on an application may not always give a value, and evaluating the body of an abstraction first is not a good strategy. Based on this, we are going to propose a robust evaluation strategy.

Robust Evaluation Strategy
Our robust evaluation strategy states the following rules:
    1) Return an abstraction expression directly, without evaluating its body;
    2) Keeps evaluating the expression until we get a value.

We can easily change the evaluator to use this new strategy. Here is the code:

// file: eval.c
TreeNode * evaluate(TreeNode *expr) {
    TreeNode* result = expr;
    if(expr!=NULL) {
        switch(expr->kind) {
            case IdK:
            case ConstK:
            case AbsK:
                return expr;
            case AppK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                if(expr->children[0]->kind==IdK) {
                    // expand tree node for builtin functions
                    BuiltinFun* fun = lookupBuiltinFun(expr->children[0]->name);
                    if(fun!=NULL) {
                        expr->children[0] = (fun->expandFun)();
                    }
                }
                return evaluate(betaReduction(expr));
            case PrimiK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                // only perform primitive operation if operands are constants
                if(expr->children[0]->kind==ConstK
                    && expr->children[1]->kind==ConstK) {
                    result = evalPrimitive(expr);
                }
                return result;
            default:
                fprintf(errOut,"Unkown expression kind.\n");
        }
    }
    return expr;
}

Abstractions are returned just like identifiers and constants, and we also evaluate the result of a beta-reduction. One thing I need to mention here is that we have expressions which cannot be reduced to values, as described in "Evaluation Values" section. For those invalid expressions, the evaluator could identify it. For example, for x y, we will treat x as an identifier of a builtin function and we will fail because it is not. For + (lambda x x) 1, after expanding + we will finally try to evaluate the primitive expression (lambda x x) `+` 1, and by checking its operands we will know it is invalid. We will add error handling mechanisms to keep it consistent with current computation model for these invalid expressions. For now, the evaluator just prints an error message and stop evaluating. For the expressions causing endless loops, I don't think we can find any method to determine whether an expression runs forever, because it is a halting problem. So our evaluator doesn't handle this case, and it will run forever. It is the programmer's responsibility to make sure there is no endless loop in the code. Here is the revised code:

// file: eval.c
TreeNode * evaluate(TreeNode *expr) {
    TreeNode* result = expr;
    if(expr!=NULL) {
        switch(expr->kind) {
            case IdK:
            case ConstK:
            case AbsK:
                return expr;
            case AppK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                if(expr->children[0]->kind==IdK) {
                    // expand tree node for builtin functions
                    BuiltinFun* fun = lookupBuiltinFun(expr->children[0]->name);
                    if(fun!=NULL) {
                        expr->children[0] = (fun->expandFun)();
                    } else {
                        fprintf(errOut, "Error: %s is not a builtin function.\n", expr->children[0]->name);
                        return expr;
                    }
                }
                return evaluate(betaReduction(expr));
            case PrimiK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                // only perform primitive operation if operands are constants
                if(expr->children[0]->kind==ConstK
                    && expr->children[1]->kind==ConstK) {
                    result = evalPrimitive(expr);
                } else {
                    fprintf(errOut, "Error: %s can only be applied on constants.\n", expr->name);
                }
                return result;
            default:
                fprintf(errOut,"Unkown expression kind.\n");
        }
    }
    return expr;
}

With this robust evaluation strategy, we are able to get rid of the "partially reduced problem".

Constants and Builtin Functions

2011-04-06T23:26:00.001+08:00

In last series of posts "A Simple Lambda Calculus Evaluator", we implemented a very simple evaluator for pure lambda calculus. Though it performs reductions to lambda calculus expressions, it is still far from a real programming language. In this series of posts, I would like to add some important features to make it evolve towards a real programming language, including constants and builtin functions, a new evaluation strategy, recursion and text machines. Since this series is inspired by the paper "Programming Languages and Lambda Calculi", I will follow the terms defined in it.

Natural numbers could be encoded using basic lambda calculus. However, this is not very convenient. In this post, constants and builtin functions will be added to the evaluator as in many real programming languages, though it destroys the purity.

Constants
First, we will add the most common constants, integer, to our evaluator. To make the evaluator recognize integer values, both positive and negative, the regular expression and rules are added to file scanner.l:

// file: scanner.l

lambda    "lambda"
integer   [+-]?[0-9]+
// others remain as before

%%
    /* reserved words */
{lambda}        {return LAMBDA;}

    /* constants */
{integer}       {return INT;}

// others remain as before
%%

And the token definition in parser.y:

// file: parser.y

%token  INT

%%

A new expression type named ConstK should be added for constants. The tree node structure should also be updated to hold the integer value. I will not display the code here. The parsing rule is very straightforward: create a tree node of type ConstK, and save the value in it.

// file: parser.y

expression      : ID    
                    {
                        $$ = newTreeNode(IdK);
                        $$->name = stringCopy(yytext);
                    }
                | INT
                    {
                        $$ = newTreeNode(ConstK);
                        $$->value = atoi(yytext);
                    }
                | // other rules are ignored here

Now, we need to update our two main algorithms, FV and substitute, for this new expression. For FV, since it is not a variable, the result should be an empty set. For substitute, we don't do any substitution and just return the constant:
c[x := N] = c, if c is a constant
It's time to update our implementation. The FV() function will be updated to:

// file: eval.c

static VarSet * FV(TreeNode *expr) {
    VarSet* set = NULL;
    VarSet* set1 = NULL;
    VarSet* set2 = NULL;
    switch(expr->kind) {
        case IdK:
            set = newVarSet();
            addVar(set,expr->name);
            break;
        case ConstK:
            set = newVarSet();
            break;
        // ...
    }
    return set;
}

And for substitute(), we just return the constant expression:

// file: eval.c

static TreeNode *substitute(TreeNode *expr, TreeNode *var, TreeNode *sub) {
    // ...
    switch(expr->kind) {
        case IdK:
            // ...
        case ConstK:
            return expr;
        // ...
    }
    return expr;
}

Finally, if a constant expression is evaluated, itself should be returned:

// file: eval.c

TreeNode * evaluate(TreeNode *expr) {
    if(expr!=NULL) {
        switch(expr->kind) {
            case IdK:
            case ConstK:
                return expr;
            // ...
        }
    }
    return expr;
}

We have finished adding constant to our lambda calculus evaluator, nice and easy. And don't forget to update the printExpression() function to print constants to user.

Builtin Functions
We have constants now, but it is still useless because we can't do computation on them. We are going to add two sets of operators: arithmetic operators and comparison operators. The arithmetic operator set includes six basic ones: plus(+), minus(-), times(*), over(/), modulo(%) and power(^). And the comparison operator set includes less than(<), equal(=), greater than(>), less than or equal(<=), not equal(!=) and greater than or equal(>=). Each of them is a binary operator, and we could simple add a primitive operator for each one which takes two arguments. However, this is not a good idea. In our current lambda calculus model, every function can only be applied on one argument. If we add the primitive operators directly to the evaluator, it would make our model inconsistent. Our goal is to make these operators behave as a normal function so programmers aren't required to distinguish whether this is a function or primitive operator.

As stated in the past post, any function that takes two arguments can be treated as a function that takes one argument and returns another function that takes one argument. So we can apply the same method to the operators. Our solution is: when an operator is encountered, expand it as a function that takes one argument and returns another function, which take one argument and returns the result of applying the corresponding operator to those arguments. Take + as an example:
+ => (lambda x (lambda y x `+` y))
The `+`(enclosed with backticks) stands for primitive plus. We still have primitive operators internally, but the programmer doesn't need to be aware of it. I'd like to call the operator before expanding as builtin function, and the binary operator as primitive operator. The builtin function looks the same as others functions defined by the programmer.

Now, let's implement the builtin functions.

Arithmetic Functions
First, we should make our scanner recognize the operator symbols. Since an operator symbol represents a builtin function, we will treat it as an identifier - identifier for a function :). The identifier definition in scanner.l is changed to:

// file: scanner.l

// ...
identifier  [A-Za-z_]+|[+\-*/%^<=>]
// ...

%%

Now, the arithmetic builtin functions are analyzed as IdK tokens. Nothing should be updated for the parser and we get a tree node of type IdK for each builtin function.

The evaluation logic needs to be rework for builtin functions. When evaluating an application expression, the left child tree node should be expanded if it is a builtin function. So the evaluate() function is revised to:

// file: eval.c

TreeNode * evaluate(TreeNode *expr) {
    if(expr!=NULL) {
        switch(expr->kind) {
            case IdK:
            case ConstK:
                return expr;
            case AbsK:
                expr->children[1] = evaluate(expr->children[1]);
                return expr;
            case AppK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                if(expr->children[0]->kind==IdK) {
                    BuiltinFun* fun = lookupBuiltinFun(expr->children[0]->name);
                    if(fun!=NULL) {
                        expr->children[0] = (fun->expandFun)();
                    }
                }
                return betaReduction(expr);
            default:
                fprintf(errOut,"Unkown expression kind.\n");
        }
    }
    return expr;
}

We examine the left child tree node and replace it with the expanded tree if it is of IdK type and is a builtin function. The lookupBuiltinFun() and other definitions related to builtin functions are all defined in file builtin.c. For each builtin function, we provide a corresponding expand function which returns the expanded tree for it. To save space, I won't duplicate the codes here. Take + as an example, it will be expanded as follows:

+ => (lambda x (lambda y x`+` y)):
       AbsK
        /\
       /  \
 IdK("x") AbsK
           /\
          /  \
     IdK("y") ?

We haven't add the primitive node yet! It is a tree node and we need to add a new expression type PrimiK for it.

// file: globals.h

/* expression types */
typedef enum { IdK, ConstK, AbsK, AppK, PrimiK } ExprKind;

We could reuse the current tree node structure to represent a primitive operator: set operator name as the node name and keep the left hand side operand in the first child node and right operand in the second one. So the "?" place in the above tree can be replaced with:

x `+` y:
        PrimiK("+")
           /\
          /  \
    IdK("x") IdK("y")

This PrimiK expression is hidden from the programmer, so no FV() or substitute() could be applied on it. When evaluating a PrimiK expression, we only perform primitive operation if both operands are reduced to constants, because it doesn't make sense to do arithmetic on variables or functions.

// file: eval.c
reeNode * evaluate(TreeNode *expr) {
    TreeNode* result = expr;
    if(expr!=NULL) {
        switch(expr->kind) {
            case IdK:
            case ConstK:
                return expr;
            case AbsK:
                expr->children[1] = evaluate(expr->children[1]);
                return expr;
            case AppK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                if(expr->children[0]->kind==IdK) {
                    BuiltinFun* fun = lookupBuiltinFun(expr->children[0]->name);
                    if(fun!=NULL) {
                        expr->children[0] = (fun->expandFun)();
                    }
                }
                return betaReduction(expr);
            case PrimiK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                // only perform primitive operation if operands are constants
                if(expr->children[0]->kind==ConstK
                    && expr->children[1]->kind==ConstK) {
                    result = evalPrimitive(expr);
                }
                return result;
            default:
                fprintf(errOut,"Unkown expression kind.\n");
        }
    }
    return expr;
}

The primitive evaluation is implemented in file primitive.c. For each arithmetic operator, a tree node of type PrimiK is required as input, a tree node of type ConstK is returned after applying the operator to its operands. For +, we have:

// file: primitive.c
static TreeNode* plus(TreeNode* node) {
    TreeNode* result = newTreeNode(ConstK);
    result->value = node->children[0]->value + node->children[1]->value;
    return result;
}

The printExpression() should also be updated to print PrimiK expressions. Now, let's try it.

$ ./main
Welcome to Lambda Calculus Evaluator.
Press Ctrl+C to quit.

> + 1 2
-> 1 `+` 2

Unfortunately, the final answer doesn't show up. The result is an expression of PrimiK type. That's because after applying the second argument 2 to the inner function of +, we end up with the PrimiK expression, and it is returned without further evaluation. I call this a "partially reduced problem" because the returned expression is a redex, which means it can be reduced. Actually, this is a defect of our evaluator and it doesn't just happen for the current case. However, I will postpone the detail discussion to next post, and for now I am going to add a fix for our special case. Evaluate the expression if it is a PrimiK expression.

// file: eval.c
TreeNode * evaluate(TreeNode *expr) {
    TreeNode* result = expr;
    if(expr!=NULL) {
        switch(expr->kind) {
            case IdK:
            case ConstK:
                return expr;
            case AbsK:
                expr->children[1] = evaluate(expr->children[1]);
                return expr;
            case AppK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                if(expr->children[0]->kind==IdK) {
                    BuiltinFun* fun = lookupBuiltinFun(expr->children[0]->name);
                    if(fun!=NULL) {
                        expr->children[0] = (fun->expandFun)();
                    }
                }
                result = betaReduction(expr);
                // beta-reduction may result in primitive operations
                if(result->kind==PrimiK) {
                    result = evaluate(result);
                }
                return result;
            case PrimiK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                // only perform primitive operation if operands are constants
                if(expr->children[0]->kind==ConstK
                    && expr->children[1]->kind==ConstK) {
                    result = evalPrimitive(expr);
                }
                return result;
            default:
                fprintf(errOut,"Unkown expression kind.\n");
        }
    }
    return expr;
}

Let's try it again:

$ ./main
Welcome to Lambda Calculus Evaluator.
Press Ctrl+C to quit.

> + 1 2
-> 3

Comparison Functions
Adding comparison functions is very similar to that of arithmetic functions. The only difference is the primitive evaluation method. For arithmetic functions, the return value should be a constant expression. For our current implementation, it is an integer. However, comparison functions should return a boolean value. Though we don't support builtin boolean values, we could use the method in post I to define booleans:

    TRUE   := (λx. (λy. x))

    FALSE  := (λx. (λy. y))

So the primitive evaluation for comparison functions will return an abstraction expression. And we can use it to construct an if-like expression.

$ ./main
Welcome to Lambda Calculus Evaluator.
Press Ctrl+C to quit.

> < 1 2
-> (lambda x (lambda y x))

> (< -1 0) 0 1
-> 0

Now, our evaluator can work as a simple calculator. Try more expressions and have fun. In the next post, we are going to solve the "partially reduced problem".

The full listing of code could be found here.

A Simple Lambda Calculus Evaluator - Extended

2011-02-17T23:10:00.003+08:00

In the last three posts, I implemented a very simple lambda calculus evaluator. However, it still has some syntax restrictions. In this post, I am going to show you how to extend the syntax to get rid of the restrictions. The following two restrictions will be removed:

Add syntax support for parentheses around expressions, so natural numbers and fixed points can be represented.
Variables are allowed to contain underscores and multiple letters, including both lower and upper cases.

Parentheses
Without parentheses, the expressions are evaluated from left to right without exceptions. This prevents us representing the natural numbers and fixed points, which needs to evaluate expressions on the right before left ones. So after adding parentheses, we can support the syntax for them.

Adding parentheses is really straightforward. Only one new rule for the expression needs to be added:

// file: parser.y

%%
// the expression_list rule is ignored

expression      : ID    
                    {
                        $$ = newTreeNode(IdK);
                        $$->name = stringCopy(yytext);
                    }
                | '(' LAMBDA ID 
                    {
                        $$ = newTreeNode(IdK);
                        $$->name = stringCopy(yytext);
                    } 
                    expression_list ')'
                    {
                        $$ = newTreeNode(AbsK);
                        $$->children[0] = $4;
                        $$->children[1] = $5;
                    }
                | '(' expression_list ')'
                    {
                        $$ = $2;
                    }
                   ;

That's all we need to do. Now, let's try some expressions:

$ ./main
Welcome to Lambda Calculus Evaluator.
Press Ctrl+C to quit.

> (u ((lambda x x) v))
-> u v

> (lambda f (lambda x f (f x)))
-> (lambda f (lambda x f (f x)))

> (lambda g (lambda x g (x x)) (lambda x g (x x))) g
-> g ((lambda x g (x x)) (lambda x g (x x)))

Note: to print the expression corretly, the printExpression() method should print parentheses around the right part of an application expresion if itself is an application expression.

Variables
It is common to have identifiers consist of multiple letters in many programming languages. To implement this extension is even more simple. We only need to change the definition for token identifier in file scanner.l:

// file: scanner.l

// ...
identifier    [A-Za-z_]+
// ...

%%

When performing alpha conversion on an expression, a new variable name is chosen. Though the old algorithm for picking a new name is still working for multiple-letter variables, we will use a new safer one. The algorithm is simple: appending underscores(_) to the old variable.

Here is the code snippet for alpha-conversion:

TreeNode * alphaConversion(TreeNode *expr) {

    VarSet* set = FV(expr->children[1]);
    char *name = NULL;
    int len = strlen(expr->children[0]->name);
    int attempts = 0;
    // pick a new name
    do {
        if(name!=NULL) free(name);  // free the last attempt
        attempts++;
        name = malloc(len+attempts);
        strcpy(name,expr->children[0]->name);
        int a;
        // append '_' to the original name
        for(a=0;a<attempts;a++) { 
            strcat(name,"_");
        }
    } while(strcmp(name,expr->children[0]->name)==0 || contains(set,name)==1);

    TreeNode *var = newTreeNode(IdK);
    var->name = name;
    TreeNode *result = substitute(expr->children[1], expr->children[0], var);

    expr->children[1] = result;
    expr->children[0] = var;
    return expr;
}

Let's try some expressions:

$ ./main
Welcome to Lambda Calculus Evaluator.
Press Ctrl+C to quit.

> X
-> X

> var
-> var

> a_
-> a_

> (lambda name name)
-> (lambda name name)

> say hello
-> say hello

All the source code could be checked out here.

A Simple Lambda Calculus Evaluator - III

2011-01-17T18:19:00.005+08:00

In the previous post, we translated the lambda calculus expressions into a syntax tree using some compiler generate tools. Now, we are about to evaluate it by traversing the syntax tree. First, I will introduce the evaluation algorithm in this post. Then, the implementation is presented along with some code snippet. Finally, an interactive interface which combines all the parts together is implemented. The full source code can be checkout here.

Evaluation Algorithm
For the evaluation algorithm, we have a syntax tree as the input, and as a result we are also going to output a syntax tree which is evaluated from the original one.

Let's consider the simple case first, an identifier node which doesn't have any child node, the node should evaluate to itself because no reduction can be applied to it. For the abstraction node, which has an identifier child node and another expression child node, which it is a syntax tree itself. The expression child node will be evaluated first and the resulting node will be set as the expression child node. The other part will stay the same. For an application node, which has two expression child nodes, both of them will be evaluated first and replaced by the resulting nodes. Finally according to the semantic of lambda application, a beta-reduction should be performed on the application node because the beta-reduction captures the idea of function application.

From the analysis above, we can work out a recursive algorithm which does a deep-first traversal on the syntax tree and evaluates the syntax tree in a bottom-up manner. Here is the psuedocode:

evaluate(tree):
    if tree is identifier node:
        return tree;
    else if tree is abstraction node:
        tree->right = evaluate(tree->right);
        return tree;
    else if tree is application node:
        tree->left = evaluate(tree->left);
        tree->right = evaluate(tree->right);
        tree = betaReduction(tree);
        return tree;

Now, the problem is reduced to the beta-reduction of a lambda calculus expression. In the first post, we learned that the beta-reduction can be simple defined in terms of substitution, so again our problem is reduced to implement the substitution algorithm of expressions. We can simply derive a recursive algorithm from the substitution rules defined in the first post:

substitute(tree, var, sub):
    if tree is identifier node:
        if tree.name equals var.name:
            return sub;
        else:
            return tree;
    else if tree is application node:
        tree->left = substitute(tree->left, var, sub);
        tree->right = substitute(tree->right, var, sub);
        return tree;
    else if tree is abstraction node:
        if tree.name not equals var.name:
            if tree->left is a free variable in sub:
                tree = alpahReduction(tree);
            tree->right = substitute(tree->right, var, sub);
        return tree;

Pay attention to the abstraction node case, we check the conditions in the last rule. If the condition is not met, an alpha-reduction is applied to the syntax tree before doing substitution.

There are two remaining problems: alpha-conversion and free variables. The definition of free variables in the first post is very straightforward, so I won't duplicate the algorithm here. With regard to alpha-conversion, the process consists of the following steps:

Find the set of free variables of the expression child node;
Pick a new identifier name which is different from the old one and not in the free variable set in step 1;
Substitute all free occurrences of the identifier in expression child node with the new identifier;
Replace the old identifier node with the new one.

In step 3, the substitute procedure above will be used. All the algorithms used for this evaluator has been presented, now we are going to write the codes.

Implementation
It's time to implement the evaluator. The code snippet of different algorithms will be shown in this section. To emphasize the most important part, the error handling and memory release stuff is ignored.

First and foremost, let's see the function that finds the free variable set of an expression.

static VarSet * FV(TreeNode *expr) {
    VarSet* set = NULL;
    VarSet* set1 = NULL;
    VarSet* set2 = NULL;
    switch(expr->kind) {
        case IdK:
            set = newVarSet();
            addVar(set,expr->name);
            break;
        case AbsK:
            set = FV(expr->children[1]);
            deleteVar(set,expr->children[0]->name);
            break;
        case AppK:
            set = newVarSet();
            set1 = FV(expr->children[0]);
            set2 = FV(expr->children[1]);
            unionVarSet(set,set1,set2);
            break;
        default:
            fprintf(errOut,"Unknown expression type.\n");
    }
    return set;
}

The VarSet is a data structure that represents a set of variables. It uses an inner hashtable to store the variables. The functions, newVarSet, addVar, deleteVar, unionVarSet, are very intuitive by their names. Refer to file varset.c for information about the VarSet implementation.

The code snippet for alpha-conversion is like:

TreeNode * alphaConversion(TreeNode *expr) {
    VarSet* set = FV(expr->children[1]);
    char * name = strdup(expr->children[0]->name);
    // pick a new name
    while(strcmp(name,expr->children[0]->name)==0 ||  contains(set,name)==1) {
        char lastchar = name[strlen(name)-1];
        name[strlen(name)-1] = 'a' + (lastchar+1-'a')%('z'-'a'+1);
    }
    TreeNode *var = newTreeNode(IdK);
    var->name = name;
    TreeNode *result = substitute(expr->children[1], expr->children[0], var);
    
    expr->children[1] = result;
    expr->children[0] = var;
    return expr;
}

The method for picking a new variable name is: replace the last character of the variable by a letter comes after it in the alphabet. This works for most cases though it may failed if all the attempted names are used up.

Here comes the most important function, substitute, which is used by both alpha-conversion and beta-reduction:

static TreeNode *substitute(TreeNode *expr, TreeNode *var, TreeNode *sub) {
    const char * parname = NULL;
    TreeNode * result = NULL;
    switch(expr->kind) {
        case IdK:
            if(strcmp(expr->name,var->name)==0) {
                return sub;
            }else {
                return expr;
            }
        case AbsK:
            parname = expr->children[0]->name;
            if(strcmp(parname,var->name)!=0) {
                VarSet* set = FV(sub);
                while(contains(set,parname)) {  // do alpha conversion
                    expr = alphaConversion(expr);
                    parname = expr->children[0]->name;
                }
                result = substitute(expr->children[1],var,sub);
                expr->children[1] = result;
            }
            return expr;
        case AppK:
            result = substitute(expr->children[0],var,sub);
            expr->children[0] = result;
            result = substitute(expr->children[1],var,sub);
            expr->children[1] = result;
            return expr;
        default:
            fprintf(errOut,"Unknown expression type.\n");
    }
    return expr;
}

It recursively applies itself to the child nodes of the expression.

Now, we can deal with the beta-reduction:

TreeNode * betaReduction(TreeNode *expr) {
    TreeNode* left = expr->children[0];
    if(left->kind==IdK || left->kind==AppK) {
        return expr;
    }else if(left->kind==AbsK) {
        TreeNode* result = substitute(left->children[1],left->children[0],expr->children[1]);
        return result;
    }
    return expr;
}

Finally, all the build blocks are ready. We can implement the main evaluation function:

TreeNode * evaluate(TreeNode *expr) {
    if(expr!=NULL) {
        switch(expr->kind) {
            case IdK:
                return expr;
            case AbsK:
                expr->children[1] = evaluate(expr->children[1]);
                return expr;
            case AppK:
                expr->children[0] = evaluate(expr->children[0]);
                expr->children[1] = evaluate(expr->children[1]);
                return betaReduction(expr);
            default:
                fprintf(errOut,"Unkown expression kind.\n");
        }
    }
    return expr;
}

Evaluator Driver
Different parts, including scanner, parser and evaluator, has been implemented separately. We need a driver method to combine them all, and it should provides an interactive interface which reads a lambda calculus expression from user input and output the evaluated expression in a human-readable format.

Here is the code:

FILE* in;
FILE* out;
FILE* errOut;

TreeNode * tree = NULL;    // used in the parser

#define BUFF_SIZE 255

int main(int argc, char* argv[]) {
    in = stdin;
    out = stdout;
    errOut = stderr;

    char buff[BUFF_SIZE];

    fprintf(out,"Welcome to Lambda Calculus Evaluator.\n");
    fprintf(out,"Press Ctrl+C to quit.\n\n");
    while(1) {
        fprintf(out,"> ");
        fgets(buff,BUFF_SIZE-1,in);
        yy_scan_string(buff);
        yyparse();

        tree = evaluate(tree);
        fprintf(out,"-> ");
        printExpression(tree);
        deleteTreeNode(tree);
        tree=NULL;
        yy_delete_buffer();
        buff[0] = EOF;
        fprintf(out,"\n\n");
    }
    return 0;
}

We set the standard input as the input and standard output as the output. The library function fgets() is used to read the user input. We use yy_scan_string() to feed the user input to the parser, so the parser will read input from this buffer rather than the standard input. The yyparse() function is the interface exposed by Yacc to run the parser. The printExpression() function is a utility that prints the expression in a human-readable format.

Let's try some expressions:

$ ./main
Welcome to Lambda Calculus Evaluator.
Press Ctrl+C to quit.

> a
-> a

> (lambda x (lambda y y) a)
-> (lambda x a)

> (lambda x x) a
-> a

Conclusion
This series of post introduces how to write a very simple evaluator for lambda calculus. It covers the topics about scanner, parser and evaluator. In order to keep it really pure, there are some limitations of the syntax, such as not constant support, cannot place parentheses around expressions to change the evaluation order from left to right. However, it is rather easy to support those features by extending the syntax. We can do it in the future.

References
1. Lambda Calculus on Wikipedia.
2. The LEX & YACC Page.
3. A lecture notes about lambda calculus, including a lambda calculus evaluator.

A Simple Lambda Calculus Evaluator - II

2011-01-17T18:19:00.002+08:00

This is the second part of a series of posts. In this post, I am going to define the concrete syntax for lambda calculus and generate the scanner and parser using Lex and Yacc(actually, they are Flex and Bison on my machine). Source code is available here.

Concrete Syntax
I am trying to keep this lambda calculus evaluator really simple and pure. So before bringing you the concrete syntax, I'd like to set some restrictions on the implementation:

Variable can only be a single lower case character from the alphabet, a...z.
Since natural numbers and booleans can be modeled in lambda calculus, no constant definition is provided in the syntax.
Every function is anonymous and only one argument is allowed.
All application expressions are left associative.

However, we can get rid of these restrictions very easily by extending the syntax. Derived from the formal definition of lambda calculus, we have following concrete syntax:
     Expression := identifier |
                            (lambda identifier Expression) |
                            Expression Expression

The first branch defines the variables. The second one defines the abstraction, and the third defines the application. The applications are not enclosed in parentheses, and they will be applied from left to right, so this syntax doesn't support the definitions of natural numbers. Just leave as it is, and we can extend it later.

Flex & Bison
The scanner and parser can be written by hand, or generated by compiler generating tools. The later method is used in this evaluator. Lex is a program that generates scanner, and it is commonly used with Yacc, which is parser generator. In this lambda calculus evaluator, the open source versions, Flex and Bison, are used. For more information, please refer to this page.

Scanner
The syntax is so simple that only two tokens are defined. The token LAMBDA is for keyword "lambda", and the ID is for variables. Here is a code snippet of the Flex definition:

// file: scanner.l

lambda        "lambda"
identifier    [a-z]
whitespace    [ \t]+
newline       [\r\n]+

%%

{lambda}        {return LAMBDA;}
{identifier}    {return ID;}

{whitespace}    ;
{newline}       ;

.               {return yytext[0];}

%%

Flex will work with Bison, so the token values of LAMBDA and ID are defined in the Bison definition file. For unmatched character, the ASCII code value will be returned as its token value, so '(' and ')' can be matched in the bison rules. We will see that in the next section.

Parser
Grammar rules
The BNF grammar is used to describe the syntax in Bison. The above concrete syntax can be simple written as:

expression    : ID
              | '(' LAMBDA ID expression ')'
              | expression expression
              ;

However, this may cause a reduce/shift conflict for Bison. The parser may be confused by whether do a reduce action or shift, when dealing with the third branch "expression : expression expression". The default action taken by Bison is shift. So the applications will be right associative rather than left associative. We need to revise the syntax to make it left associative:

// file: parser.y

expression_list    : expression_list expression
                   | expression
                   ;

expression         : ID
                   | '(' LAMBDA ID expression_list ')'
                   ;

Tree structure
Before adding the semantic actions for each grammar rule, I'd like to introduce the tree structure constructed after parsing. Our goal is to translate the lambda calculus expressions into a single root tree, which will be passed as an input to the evaluation process. According to the concrete syntax, we have three kinds of expressions: identifier, abstraction and application. Here is the definition:

// file: globals.h

/* expression types */
typedef enum { IdK, AbsK, AppK } ExprKind;

For the identifier node, only the name need to be saved in the node. For abstraction node, we need to save two child nodes, one for the identifier and the other for the expression. For application node, we also need to save two child nodes, one for the first expression and the other for the second. So we have the tree node definition as follows:

// file: globals.h

#define MAXCHILDREN 2
/* tree nodes */
typedef struct treeNode {
    ExprKind kind;
    char * name;    // only for IdK
    struct treeNode * children[MAXCHILDREN];
} TreeNode;

Every lambda calculus expression can be represented in such a tree structure. Take (lambda x x) a as an example, the syntax tree would look like:

Syntax tree:
               AppK
                /\
               /  \
            AbsK  IdK("a")
             /\
            /  \
      IdK("x") IdK("x")

In Bison, each semantic action returns a value and the default value is int. In order to construct the syntax tree, we need to set the type to TreeNode. This is a code snippet of the declaration section, with token definitions for the scanner:

// file: parser.y

%{
...

#define YYSTYPE TreeNode *

extern YYSTYPE tree;
%}

%token  LAMBDA
%token  ID

%start expression_list

%%

The tree variable will point to the root node of the resulting syntax tree.

Constructing syntax tree
Now, we are going to add some C statements in the semantic actions to construct the syntax tree. It is really simple and intuitive. Here is the full list of code:

// file: parser.y

%%

expression_list : expression_list expression
                    {
                        $$ = newTreeNode(AppK);
                        $$->children[0] = $1;
                        $$->children[1] = $2;
                        tree = $$;
                    }
                |
                 expression
                    {
                        tree = $1;
                    }
                ;

expression      : ID    
                    {
                        $$ = newTreeNode(IdK);
                        $$->name = stringCopy(yytext);
                    }
                | '(' LAMBDA ID 
                    {
                        $$ = newTreeNode(IdK);
                        $$->name = stringCopy(yytext);
                    } 
                    expression_list ')'
                    {
                        $$ = newTreeNode(AbsK);
                        $$->children[0] = $4;
                        $$->children[1] = $5;
                    }
                ;

%%

For that last rule, we add a semantic action inside the rule, as a result a temporary node which represents the ID expression will be created by Bison. So the index number should be 4 and 5 instead of 3 and 4 in the last semantic action, which may confuse beginners of Bison. The newTreeNode(ExprKind kind) function is a utility to create a tree node of type kind in the heap.

After this scan and parse step, a syntax tree represents the lambda calculus expressions is ready for evaluation. In the next post, I will show you the evaluation part of this simple lambda calculus evaluator.

A Simple Lambda Calculus Evaluator - I

2011-01-17T18:18:00.001+08:00

Recently, I wrote a very simple lambda calculus evaluator in C, with scanner and parser generated by Lex and Yacc. This series of posts introduces how to implement such a lambda calculus evaluator. This first post gives a brief introduction of the lambda calculus, including its definition and reductions, which are the essentials to the evaluation algorithms. In the second post, the concrete syntax for the lambda calculus expression and its scanner and parser are presented. The evaluation process is described in the third post. You can checkout the source code from here.

This post gives a brief introduction of lambda calculus. Most part is based on the lambda calculus page on Wikipedia. I am not going to write a formal article about lambda calculus, so only the concepts related to this evaluator are mentioned here. For more detailed information, please refer to it.

Lambda Calculus
Lambda calculus, also written as λ-calculus, is accepted as the foundation for functional programming languages. It is introduced by Alonzo Church in 1930s to model the simple semantics for computation with functions in mathematics.

Function can be considered as a black box, which accepts some inputs and sends back some output. Consider the following examples. Function increase(x) = x + 1 takes a single input, x, and returns the result by adding 1 to x. Function sum(x,y) = x + y takes two inputs, x and y, and returns the sum of them, x+y. Some ideas in lambda calculus can be introduced by make some observations of the functions.

Firstly, the function can be anonymous. That means we do not need to name the function. The function increase(x) = x + 1 can be rewritten as (x) -> x + 1.

Secondly, the name for function's argument is irrelevant. That is, choosing different names for a function makes no difference. So function (x,y) -> x + y is equivalent to (a,b) -> a + b.

Finally, any function that requires two inputs can be redefined into an equivalent function that accepts a single input, and returns another function, that in turn accepts a single input. This can be extended to three or more inputs. So function (x,y) -> x + y can be redefined as (x) -> (y) -> x + y.

The lambda calculus provides a way to model functions. Since functions can be anonymous, lambda calculus doesn't provide a means to name a function. Since the names of arguments are irrelevant, the functions with only different argument names are equivalent. Since all functions expecting more than one arguments can be transformed to equivalent functions expecting one argument, lambda calculus creates functions that accepts one single argument.

Here comes the formal definition of the lambda calculus from Wikipedia:

Lambda expressions are composed of:
    variables v₁, v₂, ..., v_n
    the abstraction symbols λ and .
    parentheses ()
The set of lambda expressions, Λ, can be defined recursively:
    1. If x is a variable, then x ∈ Λ
2. If x is a variable and M ∈ Λ, then (λx. M) ∈ Λ
3. If M, N ∈ Λ, then (M N) ∈ Λ
Instances of rule 2 are known as abstractions and rule 3 are known as applications.

With this definition, the before mentioned functions can be defined as (λx. x+1) and (λx. (λy. x+y)).

Reductions
Suppose we have two lambda expressions: (λx. x+1) and a. If we apply the first to the second, we will have (λx. x+1) a. According to the semantic, the result should be a+1. This is called a reduction. Actually, it is a β-reduction. There are three kinds of reduction:

α-conversion: changing bound variables;
β-reduction: applying functions to their arguments;
η-conversion: which captures a notion of extensionality.

Only α-conversion and β-reduction will be covered in this post, with some other necessary terms.

Free and bound variables
Variables that only exist in the scope of a lambda abstraction are said to be bound. All others are called free. For example, y is a bould variable and x is free in expression: (λy. x + y).

The set of free variables of expression M is denoted as FV(M). It is defined by recursion as follows:

FV(x) = {x}, where x is a variable
FV(λx.M) = FV(M) - {x}
FV(M N) = FV(M) ∪ FV(N)

α-conversion
Alpha-conversion allows bound variable names to be changed. For example, alpha-conversion of (λx. x) could be (λy. y).

You need to pay attention to the "bound" word, which has extended meanings. First, when alpha-converting an abstraction, only the variables bound to the same abstraction could be changed. For example, alpha-conversion of (λx. (λx. x)) could result in (λy. (λx. x)), but not (λy. (λx. y)). Second, after alpha-conversion, the new argument variable should not be captured by a different abstraction. For example, alpha-conversion of (λx. (λy. x)) could not result in (λy. (λy. y)).

Substitution
Substitution, written as E[V := E'], is the process of replacing all free occurrences of the variable V by expression E'. It is defined by recursion as follows:

    x[x := N]        ≡ N

    y[x := N]        ≡ y, if x ≠ y

    (M1 M2)[x := N]  ≡ (M1[x := N]) (M2[x := N])

    (λy. M)[x := N]  ≡ λy. (M[x := N]), if x ≠ y and y ∉ FV(N)

The y ∉ FV(N) condition in the last rule is important. Without it, the variable y, which is free in expression N, will be bound in the result abstraction after substitution. For example, it is not correct for (λx. y)[y := x] to result in (λx. x). For this case, an alpha-conversion should be applied to the expression (λx. y) before substitution, which results in (λz. y).

β-reduction

Beta-reduction captures the idea of function application. It is defined in terms of substitution: the beta-reduction of ((λV. E) E') is E[V := E'].

All the rules defined in this section is essential to lambda calculus. And they are also the basic elements for evaluation algorithm which will be presented in part III.

Encoding Datatypes
From our mathematics knowledge of middle school, we know that functions are usually applied to numbers. However, lambda calculus doesn't have any numbers? That's true! The pure lambda calculus doesn't define any data types. But we can model some data types using this basic lambda calculus. Two data types, boolean and natural number, will be introduced in this section.

Natural Number
The most common way to define natural numbers is as follows:

    0 := (λf. (λx. x))

    1 := (λf. (λx. f x))

    2 := (λf. (λx. f (f x)))

    3 := (λf. (λx. f (f (f x))))

The natural number n is a function, which takes a function f as an argument, and apply it n times to its argument.

From the definition, we can define a successor function, which takes a number n and apply one more time of function f to it:
SUCC := (λn. (λf. (λx. f (n f x))))

And the addition of two numbers, m and n, can be defined by apply m+n times of function f:
PLUS := (λm. (λn. (λf. (λx. m f (n f x)))))

Boolean
The boolean values TRUE and FALSE can be defined as follows:

    TRUE   := (λx. (λy. x))

    FALSE  := (λx. (λy. y))

And some logical operators:

    AND := (λp. (λq. p q p))

    OR  := (λp. (λq. p p q))

    NOT := (λp. (λa. (λb. p b a)))

The Wikipedia page has more details about the data types, so I won't duplicated it here.

Till now, the concepts about lambda calculus that are necessary for the evaluator have been covered. In the next post, I am going to define the concrete syntax of lambda calculus and implement the scanner and parser.

北京城惜别故友杭州市初遇新知

2010-07-29T10:38:00.006+08:00

话说天朝五十八年，本人进京求学，初至帝都便立下学成后重回江南的志愿。三载寒暑，完成了课程、实习、论文，终于迎来了毕业的时刻，心中自然十分欣喜。数日后即将离京，朋友聚会，把盏小酌，自然不在话下。本人不胜酒力，所幸席间均以饮料为主，偶尔举杯也只是点到即止。如此持续数日，恰逢世界杯决赛，遂与老章、小鲍约定共同观战。无奈比赛乏味至极，世人既知，不再赘述。次日养精蓄锐，至傍晚行李收拾妥当，胡乱吃过晚饭后便匆匆奔赴火车南站。车站前与老章、凉皮告别之际，回想于帝都经历的车马交通，游玩的名胜古迹，顿感怅然若失。虽日夜期盼离京还乡，真到离时却也不舍。告别后与小鲍登车卧榻，一宿无话。

次日清晨抵达苏州，苏南一带遭遇连日阴雨天气，与小鲍雨中话别。虽经历一番周折，所幸顺利到家。在乡下老宅深居十日有余，虽然日日粗茶淡饭，无人问津，然日间檐下卷读，午后小憩，夜间观月明星稀，花阴满庭，却能真正得到内心的宁静。

且说南大学弟高同学，为人正直，我毕业那年前往京城，次年他往杭州供职，至今已三载未见。闻知我不久后也将至杭州谋生，遂予我消息，说此前赁得一居室，如今恰有一单间空闲，邀我同住。我思其为人可靠，且住宅距供职处不过十分钟车程，便欣然接受，此事在离京前即已说定。归家后，思及尚有体检等事宜未及办理，遂决定于入职前一周如杭。世事终究不会如此顺利，动身前两天收到高同学消息，言其当晚将到京城出差，下周末方能回杭，他已安排同住的吴兄代为接待。我择日搭车前往杭州，幸得吴兄热情接待。且说这吴兄面容清秀，行事稳妥，待人也极和气。当日购物打扫安顿一一安排妥当，不在话下。后两日探查公司、联系体检，可喜的是当天下午即可取回体检报告，一干琐事均以完成，余下三四日时光竟无事可干。眼见高同学归期将至，却又生一变，接到其消息，因工作未完，需推迟数日回杭。

后事如何，下回分解。

实习结束

2010-04-23T20:26:00.008+08:00

去年6月份找实习的时候，目标是手机程序开发的职位，避免做与网页相关的web开发。考虑到年底要毕业，10月份又要找工作，所以实习时间最好在3－4个月，或者不需要每周5天全职工作。因为时间的原因，我拒绝了一家从事手机开发的小公司，说实话除了要求6个月全职实习，对其他条件我都相当满意。讽刺的是，因为对论文开题准备不足，我最终推迟了半年毕业，并且在DoCoMo一实习就是9个月。在这9个月中，除了在Android上开发了几个简单的Rest和Comet客户端，大部分的工作仍然是我厌恶的web开发。

虽然工作内容并非我原本期望的，但是这里宽松的工作环境还是给了我很多自由发挥的机会，所以做得还是很开心的。以前有很多技术我只是学过但没有真正用过，我把它们都用到了实际工作中。我还阅读了一些开源软件的源代码，并对它们进行修改和裁减，以前很惧怕阅读大量的源代码，现在几乎习以为常了。第一次实习这么长时间，临走前很是伤感。同事们送了记事本和玩偶作为纪念，很感谢他们。特别是那个互联网神兽的玩偶，很是喜欢，我决定把它带到杭州去。

作为程序员，最有成就感的事情就是在发布的产品中有自己贡献的代码。可是我两次实习的工作都带有实验性质，所以我的贡献都没有体现在产品中，多少有些遗憾。两次实习离职前，我都编写了详细的文档，把在工作中积累的经验、使用的技术和有帮助的信息都记录下来留给接替我工作的同事。我感到很自豪，因为知识的积累和传承也非常重要。

现在，终于可以把全部的时间放在自己想做的事情上了，希望不要因为放松而产生了惰性。

Tiny Extension to Ruby YAML

2010-01-28T21:41:00.007+08:00

I am using Ruby's YAML library to dump objects to yaml document. The built in library dumps all fields, but in my program I only need to serialize part of them. So I need a way to set some fields to be transient.

I searched the web, and found Xavier's yaml_helper. It can solve my problem, but not exactly what I want. It uses class attribute "persistent" to indicating the fields to be serialized. In my suitation, there are many fields in the object, and only two or three are transient. So I prefer the "transient" class attribute.

After reading the source code of yaml_helper and Ruby's YAML library, I decided to write my own. Now, you can check it from here. It is no more than 100 lines code with most copied from yaml_helper, and realy a tiny tiny extension.

谈谈课程评分

2010-01-23T23:18:00.010+08:00

刚才在百合软院版看到大二的小朋友质疑助教的帖子。事情大致如此：楼主对于自己的数据结构分数不太满意，首先指责了助教在上机作业时给大部分学生都打A的行为，进而质疑最终成绩使用了随机给分的做法。回忆自己的大学四年，我可以不计较不能搬去本部，可以不计较校车问题，可以不计较食堂问题，但是对于学院考核机制始终存在不满。评奖学金、印度实习机会、保研资格都是由成绩直接决定的，但是成绩的评定却没有做到公平、公正、公开。至少在我看来，连公开都没有做到。所以看完帖子，我站在了楼主这一边。但是看了部分回帖，真相明朗，我的看法似乎是错误的。在此，我的目的不是讨论此事到底谁对谁错，只想谈谈对于课程评分的一点感想。

有助教在回帖中说明了平时成绩和最终成绩是如何计算出来的，得到大家的一致支持。但是，我不禁想问，既然已经制定了这么完善的规则，为什么不在课程进行中就公布出来呢？非要等到有人质疑了，才公布规则？我并不是怀疑这个规则是否存在，而是想说明如果让学生在完成作业之前明确评分标准，那就可以避免这类事情的发生。记得以前上课的时候，老师也会在第一节课上公布考核方案，平时成绩占多少比重，期末考试占多少。但是很少会对每一次作业制定评分标准，这完全取决于助教的评价。就好比移动出台的规定，禁止发黄段子，违反者会被停机，但是却没有告诉消费者怎样才算黄段子。

研一的时候英语课是外教上的，每个老师要教大概200位学生，每次作业都是老师亲自批改。一个学期有5、6次作业，再加上最后的期末考试，每次作业都批改得十分认真，拼写错误、标点符号错误、排版格式不当都会被一一标记出来。提交作业的时候，会连同一份描述作业得分点的表格一起装订，批改完返还到我没手里的时候，每一项的得分都会标明。所以在期末考试前，每个人都清楚自己已经获得的分数了。老师经常跟我们说，每个学期过去后她都能收集到一把用完了的红色笔芯。如果每个课程都使用这种方式，每个作业的评分标准都在TSS上公布，检查完之后把评价反馈给学生，最后把学期成绩的累加情况也发送给每个学生，这样不就可以让所有人都心服口服了。

让我这种人闭嘴的最好方法就是使用如上的方式，但是这种方式却很难实行起来。首先，引用我导师说过的一句话：做什么事情都需要dedicated的精神，特别是科学。作为老师，或许根本没有兴趣思考如何来完善课程体系、提高教学质量。作为助教，或许从没想过如何帮助学生完成作业，掌握知识。很多时候，很多人做事情的功利性都太强了。仅仅为了每个月几百块钱的补贴，仅仅为了这一段经历，而不是为了更好的完成工作。参加志愿者，竞选研会主席，也仅仅是为了简历上那光辉的一笔。还没做事，就已经在盘算从中我能获得什么好处。有人说助教要改那么多作业，检查那么多学生，已经很辛苦了。的确很辛苦，但是这是他的职责所在，当他决定申请这个职位的时候就应该明白这一点。学生努力学习、认真完成作业，这同样不轻松。

其次，规则过于公开了就会导致很多操作完成不了。如果分数中出现了“人情分”，则很容易被其他学生发现，从而引起不满。所以规则这事“不能说得太细”，也不能让学生“知道得太多”。但是，每个学生都一样是通过高考考进来的，每个学生都一样交了那么多学费，每个学生都平等地享有被公正评价的权利，如果仅仅因为一些学生跟你关系比较熟，因为帮过你忙，因为有出国的需要，就可以随便地给予高分，那么让那些勤奋学习、认真独立完成作业的学生情何以堪呢！

踏雪

2010-01-04T22:13:00.002+08:00

黄灯下，碎雪如沙，风催人影儿南下。漫天飞花，坠地如麻。举头望，阑珊处横七竖八；俯身瞰，沙场上千军万马。驿道旁老枝轻压，雕栏内青松挺拔，遍寻那傲雪梅花。

曾游架，黄山脚下，旅居天上人家。松间寒乍，月影无崖。一线天冰封陡滑，飞来石巍然潇洒。五更起，越古刹，终守得晓破云霞。

隔桥遥望北邮大厦，忆当日阿里对话，意气风发。友问曰：“明年今日，君当何处下榻？三五年后，故地重游，或可带口携家。”无以为答。这光景愁煞，冷不防风吹雨打。感盈虚世事无常，叹青春早生华发。

踏雪寻罢，两屉小笼，一碗热汤，勾勒出白墙黑瓦，浅草篱笆。待回时，再话桑麻。

青春一梦牡丹亭

2009-12-21T19:28:00.006+08:00

因为王力宏的一首《在梅边》而产生了对《牡丹亭》的兴趣。后因学院所谓“素质教育”课程的需要，我选择了昆曲作为课题。半个月时间，身心完全沉溺于丝竹款曲之中，废寝忘食。阅读了昆曲起源发展的历史，观看了《昆曲六百年》纪录片，了解了昆曲的经典剧目。特别是花了9个小时在线欣赏了青春版《牡丹亭》。“惊梦”一出让我体会到丝竹管弦可以如此悦耳，融情于景，浑然天成；“寻梦”一出让我领悟到粉黛之下的演员如此温婉迷人；“离魂”一出让我感受到了生离死别的动人心魄。情感贯注于剧情之间，为相聚而欣然，也为离别而伤感。就如当初研究《梁祝》那般，曲终人散，仍情思难断，思绪幽幽，难以自拔。于是许下心愿，盼有朝一日能亲眼欣赏这《牡丹亭》。

近日，青春版《牡丹亭》第三度光临北大，使我得圆此梦。虽然剧情早已烂熟于胸，但是仍然被表演深深震撼。当你置身在戏院中，眼前远近是华丽的舞台灯光，左右是绵绵流长的丝竹之音，这种立体的享受是坐在电脑前完全无法比拟的，你早已融入在意境之中，就像剧中人一样。我本不相信妖魔鬼神，不相信三生轮回，可是我现在宁愿信其为真，有如此浪漫的故事，为什么不呢？我本想找些词句来形容我的感受，但发现千言万语不如一个字：美！是的，美不胜收，叫人流连忘返。正是“不入园林，怎知春色如许”。

《牡丹亭》讲述的是杜丽娘因梦而亡，又因爱而生的故事，阐述了“一往情深，生者可以死，死可以生”的真谛。虽然是以大团圆结尾，但我想这绝对算不上是喜剧。汤显祖云：“白日消磨肠断句，世间只有情难诉。”可见他在塑造杜丽娘这个人物的时候尽是肝肠寸断之情。而“寻梦”一出的音乐，正是在撩人的春色之下，蕴藏了无限的忧伤。表演谢幕后，我一如既往的怅然若失，只是这一次比以往任何一次都要强烈。或许是因为长大了，更体会到了现实的残酷。梦永远都是美好的，可是世间又有多少人在因梦而亡之后能再次重生呢？年少轻狂时追逐“如花美眷”，等到垂垂老矣之时也就只能追忆“似水流年”了。如杜丽娘般才貌过人、至情至真的女子恐怕世间早已少有。正是：此女只应梦中有，人间能得几回闻。

“但是相思莫相负，牡丹亭上三生路。”

新域名

2009-12-14T20:07:00.003+08:00

很早以前听cyf说godaddy上的info域名相当便宜，上个星期本来想买，后来注册时因为别的事情就半途而废了。昨天看到新闻说godaddy支持支付宝付款了，想起我的支付宝中尚有15元余额，于是今天又试了一次。但是，未如新闻中所说支付选项中有alipay，所以最后还是用信用卡支付的。招行的信用卡还是很方便的。买了一年的minjiezha.info域名，等以后有钱了再买.com吧。

买完之后将此博客绑定到新域名，不到十分钟居然就可以用了。我在公司无法直接访问博客，但是3位上海的朋友居然使用新域名能无障碍访问。现在在家也可以通过新域名访问，莫非GFW只过滤blogspot的域名而非屏蔽其IP地址？

找工作那些事儿

2009-12-12T18:55:00.005+08:00

10月长假过来没几天，在清华参加了淘宝的笔试。这是校园招聘开始后，我参加的第一场笔试。网申的时候，说笔试前会有短信通知。没有收到短信，所以连宣讲会都不太想去。当天上午在论坛上看到有人说宣讲会后直接笔试，于是决定去看个究竟。下午的宣讲会，我晚到了15分钟，被告知“人满为患”不让进了。只能在校园里逛了一个多小时再去笔试，题目挺难，可能是第一次笔试，思想上还没做好准备，所以笔试过程挺浮躁的，一看要花点时间做的题目，就没认真做，随便选了个答案。第二天，同学收到了面试的短信，直到晚上我都没收到，确定是笔试没过。出师不利让我很郁闷。我找工作的重心在江浙一带，淘宝是个不错的选择，而且我一直觉得肯定能拿下，没想到笔试都没过。这次失利之后，我的思想紧张起来了，提醒自己每次笔试都要认真对待。

没过几天就是搜狐的笔试了。这次主场作战，题目不算难，自认为做得不错。可是迟迟都没有收到面试通知，周围的同学也都没有收到。过了N个星期后，接到电话，说我当时填了两个职位，问我是否愿意接受第二志愿并再进行一次笔试，由于当时已经拿到满意的offer了，所以就放弃了。

百度的笔试跟搜狐差不多时间，我已经记不请哪个在先了。几道题目我做得还行，没过几天就让我去面试了。终于有面试了，记得兵败淘宝后，我发誓进不了面试我就不剪头发了。面试过程挺糟糕的，我好像只回答出了一个问题。带着“必挂”的心情回去跟同学交流了一下，得到两点启发。一是当被问到做过什么项目的时候，一定要选自己最熟悉的讲，并且被问遇到了什么问题，如何解决的时候，一定不能讲没有问题，即使真的没有问题，也要自己去发掘一下难点和闪光点；二是有的算法题即使没做出来也要把你的思考过程说一下，如果知道某个算法，但是不知道具体做法也要把算法名称说出来。当天下午就在vernkin的指导下把BM算法研究了一下。第二天登录招聘页面，状态已经变为“面试未通过”了。

你方唱罢我登场。淘宝走后，阿里旗下阿里巴巴B2B的宣讲会也到来了。宣讲会是在北航，担心它们也跟淘宝玩同一招，下了班就直抵北航。这是我参加的第一场宣讲会，听了两个多小时关于“梦想”的演讲，得知笔试安排在第二天，会后有短信通知，第三天面试，第四天发offer。笔试被安排在北科，临时还换考场，有点混乱。当然，混乱才刚刚开始。周六上午9:15面试，下午2:30还有微策略的面试，庆幸在笔试试卷上写了要求把面试安排在上午，这下怎么样都不会冲突了。填完表格后九点刚过，到等候室遇到同学，他是8:40的面试，还没被叫到。原来混乱还在继续。他9:40才去面试，我则是10:05。面试的工程师不错，我看得挺顺眼，问了若干技术问题，然后让我等二面。这次等了一个半小时，二面的估计是个manager，长得像《谈判专家》中张智霖的哥哥，很面善还一直冲着我笑。聊了过去做过的项目，学过的课程，还有我将要做的毕业设计。他让我仅仅用一个词语描述学习《编译原理》的感受，我想到的是“转换”，因为你必须告诉计算机你要做什么，所以程序员需要把解决问题的方法转换成程序代码，然后编译器再把程序转换成机器能够读懂的机器码。他认为是“规则”，因为正则表达式，BNF文法都是用来描述规则的，你只有按这些规则做，你的程序才能正确运行。他说这个问题没有标准答案，只是提醒我在学习过程中要多善于总结。二面结束已经12:30多了，要等面试官吃完饭再进行三面。三面是HR面，到这个时候我几乎确定自己能够拿到offer了。可是要是等三面结束，微策略的面试肯定赶不上了。对微策略了解不多，只知道是个不错的公司，在杭州，而且要求挺高，全英文面试。一边是几乎到手的offer，一边是很好的公司，我不知该如何选择。让先我一个小时面试的abalone询问是否可以换个时间，被告知不行。这时我灵机一动，乱有乱的好处，我让chinahr的调度人员帮我把阿里巴巴这边的三面安排在5点以后，我先去面微策略，然后再回来三面。于是兴冲冲地移师微策略。

地点是香格里拉，进入等待室，等待的人都穿着正装，我这个阿乡还真不习惯。一面是个老外，个人觉得长得跟尼古拉斯凯奇神似。问了很多问题，算法、数据结构、操作系统、数学、设计模式，Java编程都涉及了。回到等待室等待结果，心想：“快点跟我说你今天的面试就到此为止了，这样我就可以回去收我的offer。”未能如愿，还要二面。又要等一个小时，这时我想起了《当幸福来敲门》中的开场白：“Part of my life is called waiting.”二面是个中国人，问了两个问题就结束了，答得还不错，原本根本不抱希望，现在却希望大增，真是造物弄人。来不及想那么多了，直接赶回去阿里巴巴的三面。还好是周末，车子不堵，不过到的时候也已经17:45了，幸好还没结束。自我介绍完之后，HR说：“我也不问什么问题了，你看你有什么问题吧。”我非常想说：“我就不浪费后面同学的时间了。”不过心想还是低调点吧，就象征性地问了几个问题。跑了一天，都没顾上吃饭，走在北三环上的我还是挺开心的，毕竟毕业后肯定能回江浙了。

第二天上午接到电话，通知下午去签offer，于是就放弃了趋势的笔试。

且说微策略那边，我以为二面之后就出结果了。谁知先是收到晚宴的通知，小兴奋了一下，接着又是三面的通知，让我摸不着头脑。晚宴的时候，VP给我们详细介绍了公司的情况，我也是在这之后非常想去。同时也得知前三面是相同等级的技术面，只有三个面试官都通过了才能进入第四面见VP。同一桌的几个同学聊着他们ACM的经历，着实让我信心倍减。后天的第三面表现还可以，算法，程序都写出来了，唯一的瑕疵就是复杂度没有说出来。见VP时，我表达了一下愿意去杭州的想法后，就回来等结果了。

一边等待，笔试还是要继续。接下来是腾讯的笔试，我认为这是一份水平很高的试卷，题目不难，但是都很基础，数据结构、编译原理、操作系统、算法、离散数学等等。一向对腾讯没有好感的我，开始对腾讯刮目相看了。当天下午安排的是千橡互动的笔试，我肯定不会去了，就把座位让给了同学。再说回腾讯，这种好感并没有维持多久。几天后的面试，让我觉得腾讯很牛B，根本不把你当回事，从来没见过面试官不准备纸而向面试者要的，从没见过面完后不把面试者送出门的。还好我面得不错，两个题都做出来了，几天后通知我上机考试，要“自带装有VC6.0的笔记本电脑”。我报的是Java职位，而且我也不用windows（虽然可以用g++），当即决定放弃。

因为vmware的笔试，有机会踏上中科院研究生院的领地。我非常喜欢他们的教学楼，外面是红色的墙壁，内部中间是一条大长廊，抬头可以看到屋顶，两侧是整齐的教室，站在教室前的走廊上，底楼、楼梯、屋顶、行人一览无余，非常有高中的感觉，课间倚靠在栏杆上聊天，欣赏隔壁班的女生，哈哈。笔试为3小时，很专业，前半部分是选择题，要涂答题卡，后半部分是程序题。觉得做得还不错，可惜至今都没消息，肯定是没通过。跟vmware同一时间笔试的是Adobe，所以只能放弃。

第二天就是EMC的笔试，冒着大雪赶到北理。可能因为大雪的缘故，来笔试的人很少。笔试形式跟vmware类似，但是难度绝对上了几个档次，绝对是我见过最难的笔试。虽然第一题就吓到了，但定下心做还可以，特别是最后5，6道智力题，我都做出来了。第二卷四道程序题我就写了第一题，用了状态机的原理写的，我还挺得意。三个小时完全来不及，如果有谁做完了，我就只能佩服了。

阿里巴巴研发院是新成立的，这或许代表着阿里巴巴开始对技术的重视。跟一起实习的同事去参加了宣讲会，这是我参加的第二个宣讲会，也是最后一个。笔试前五分钟，听同学的小道消息说，你拿到了阿里巴巴集团其他子公司的offer后就不会再让你去面试了。很失望，早知道就不来了，那就随便考考吧。我带着极其放松的心情考完了，就一道正态分布不会做，其他基本都做出来了，真是可惜了，不然又是一次面试。没想到第二天，我还没睡醒，接到面试通知。面试官是个大我没几岁的GG，穿着非常朴素，但是水平很高，数学算法样样精通，我怀疑他是搞ACM的。从一开始我就连招架之功都没有，他可能看我笔试成绩比较高，就多给我点机会，多问了几道题，可是我还是一如既往的弱，最后只能说再见了。对于这位面试官，我只有两个字：敬佩！回去面壁了一下，决心再补算法和数学。

联发科技的笔试跟阿里巴巴研究院冲突了，因此错过一次到隔壁面试的机会（因为它的办公楼在我实习公司的隔壁）。

有道我报的是web工程师，写了整整3页程序后，被通知了面试。面试巨搓，在面试官的一再提醒下都没做出来，出来跟abalone一说，他一下子就说出了解法。走在中关村东路，我彻底领悟到算法这东西我做不来，还不如做点别的。

话说微策略过了两个星期，也该出结果了。那几天，整天盯着应届生上的论坛，看到还没人收到offer，心里就很放心。直到有一天，有人说开始发offer了，先发第一批，稍后发第二批。后来又有人收到拒信了，又有人说SE的offer发完了，见了VP但没收到到拒信的在waiting list中。又过了一天，还是没消息。在我看来这就是deadline了。晚上躺在床上努力说服自己不要郁闷了，计划未来奋斗的目标。熬夜看了场球，目睹了巴萨在寒冷的喀山被逼平了。第二天睡到十点才起床，在上班的路上接到abalone的电话，说发offer了，让我去收。我想我临走前才看的邮箱没有邮件，应该不会有了。最后，在车站上等车时收到了电话。这些天，一直在等这一刻，等待无限渴望之后终于成功的快感，等待向这些年从没得到过最想要的东西这样的遭遇大吼三声的发泄，等待抒发“春风得意马蹄急，一日看尽长安花。”的畅快……可是经历了一晚的思索后，我很平静的接受了这个结果，没有丝毫兴奋。现在想来，我倒是更怀念那种在安静的午夜万念俱灰，涅磐重生的感觉。这个offer除了让我结束了求职的历程，并没有改变我的心态和继续奋斗的决心，所以我想我是幸运的。

此后，我立刻停止了所有求职的活动。放弃了思科的笔试和EMC的面试。EMC还给我打了3个电话，询问我为什么不去面试，搞得我都不好意思了。

剩下的amdocs、大唐移动、Intel和创新工厂，投了简历后都没回音，姑且认为是简历删选没通过吧。

一直都觉得这次找工作运气很好，不管好坏，总算找到了满意的公司，满意的城市了。同样，我也深深体会到过早拿到offer不是什么好事，哪怕只是保底的，因为这会让你懈怠。

文章开始的图是我投简历的时候，每投一家公司都记录下来，想看看半年后我是什么下场。有趣的是，在我回顾的时候才发现少了微策略的logo，最想去的公司居然忘记加上了。或许这也算是天意吧。

使用GAppProxy翻墙

2009-12-04T21:22:00.006+08:00

自前日搞定Opera mini翻墙后，今天又尝试了使用GAppProxy翻墙的方法。它的原理非常简单，就是在Google App Engine（GAE）上搭建一个代理服务器。

按照gappproxy网站上的使用方法，在本机安装一个代理的客户端。关键在于找到一个搭建在GAE上可用的代理服务器，可以使用网友提供的，也可以自己申请搭建。建议自己搭建，这样不需要与别人共享流量，参考：用Google App Engine做个人代理服务器。项目中需要运行python脚本，这对于Linux用户尤为方便。

代理服务器和客户端都安装完成后，就可以使用了。为了使用方便，可以为Firefox安装AutoProxy插件，并选择GAppProxy作为默认代理，这样在浏览被屏蔽掉的网站时，就会自动使用代理了。

这种翻墙方式与Opera mini相比，不需要在手机模拟器中浏览网站，更加方便，效果也更好。

我还活着

2009-12-02T12:40:00.006+08:00

现在翻墙是越来越难了，Web代理碰到blogger就不管用了，免费VPN也越来越难找。于是我写写文章这个小小的爱好也只能为共产专制主义作出牺牲了。近日，听闻利用Opera Mini可以翻墙，于是欣然决定一试。参考文章：http://code.google.com/p/opera-mini-on-desktop/。历时一个晚上和一个上午，把遇到的一些小问题都解决了。终于可以登录blogger了，不过MicroEmulator中无法输入中文，所以翻墙后也就只能作为浏览之用了。不知道此翻墙方式能维持多久。虽然过程十分复杂，但是总算没白折腾，因为"道路是曲折的，前途是光明的"，就好像短暂的专制复辟是无法阻挡民主共和的脚步。

登录blogger后设置了mail2blogger，以前没用过，以后估计只能用这种方式了，不知道格式显示会不会有问题。

庆幸的是，在被组织fuck了24年之后，我惊喜的发现我还活着。

是的，我还活着！

古文观止

2009-09-16T21:59:00.002+08:00

过年的时候，听一位小学同学谈起了《古文观止》。回来后买了一套，共三册，是“上海古籍出版社”发行的，纸张质量很好，排版和译文也不错，最近翻阅完了，由于时间有限，很多文章只是一知半解，并未深究。但不得不承认，这是一套好书。

《古文观止》是清朝吴楚材和吴调候选编的222篇经典的古文著作。按时间顺序从春秋战国时期一直到明朝，语文书中的很多名篇都在此列。至于《古文观止》的介绍，在此不再赘述。读完之后，我有三方面的收获：

一是文学方面。当然，这是最直接也是最重要的收获。222篇文章出自历代大文豪之手，形式各异，包含序、表、辞、赋等多种题材。《归去来兮辞》，《滕王阁序》，《前赤壁赋》等都是我最爱的名作。

二是历史方面。书中的文章是按时间的先后顺序编排的，从春秋战国一直到明朝，顺着书的思路看下来，就相当把中国的历史捋了一遍。我历史知识比较匮乏，看完书后对中国历史的发展算是有个粗略的了解了。

三是政治方面。古代文人的终极目标就是谋取功名，治理天下，所以他们写的文章难免跟政治搭上关系。通过了解作者的生平及其作品，可以窥视到当时的政治环境，治理国家的方法，很多道理至今仍然通用，比如“君为轻，民为重”，“防民之口，甚于防川”，“水能载舟，亦能覆舟”等等。

小时候对古代诗词很感兴趣，可是经历了6年中学教育之后，对于国学的兴趣似乎被消磨殆尽了。现在阅读这些文章，虽然早已无法再获取功名，对于生活工作的现实意义也似乎不大，但是利用空余时间读读，也是有益无害的。“维护国学”这个话题太沉重，我能做的仅仅是维护自己最后的那一点点幸存的兴趣。

推迟毕业

2009-09-05T10:56:00.003+08:00

入学之前就计划着研究生两年半毕业。入学之后，更是无时无刻不想着两年半毕业。直到上个星期，我还一直认为今年过年前一定会毕业。现在，我只能无奈的接受推迟到三年毕业的事实。

前几天，学院发布了关于本学期毕业生答辩的时间安排。9月18日之前要交论文初稿，10月18日之前提交论文终稿，而此时，我还没给导师做完开题报告。原计划是这个星期完成开题报告的，然后马马虎虎应付下初稿，再花一个月时间唬烂个终稿出来，我想也是可以做到的。但是这有什么意思呢？也许在我提交的时候，心里都在鄙视自己。再加上10月份要开始找工作了，实习、找工作，毕业设计，三线作战难免会分心，所以最后决定推迟到明年6月毕业。

是到如今，也只能怪当初没能未雨绸缪。6月份的时候就听说有同学开题了，而我一直认为这是件很轻松的事情，9月份过来开下题就可以了，再加上导师也只是要求我们8月底或9月初开题，所以理所当然的认为还有大把的时间。更甚者，或许去年的这个时候就应该关注上一届同学的答辩安排，提前了解了，今年就不会一直想当然了。

离职

2009-06-27T22:08:00.003+08:00

离开公司整整两周了，由于网络的原因一直都没写日志，今天补上吧。

去年9月底收到offer，因为不太满意发工资的流程，当时一度还不想过来实习。但是两位面试官非常友好的态度，使我不忍回绝，最后，他们一个成了我的manager，一个成了我工作上的导师。转眼间，八个月已经过去了，虽然期间发生了很多变化，虽然我大部分时间做着与当初设想不符的事情，虽然有时候工作让我很恼火，但是我仍然过得很开心，所以我是带着感激离开的。感谢两位面试官兼同事，给了我这个在国际知名公司实习的机会；感谢我的几任manager对我工作的信任；感谢合作过的项目组同事对我工作的肯定……

这八个月中，我一直在思考我适合做什么，喜欢做什么，直到最近才找到了一点方向。呆在这里无法实现我的目标，所以我决定在实习到期后就离开。很多事情都是这样，你很想留下，别人却未必接纳你，别人接纳你了，你却又未必会留下。我必须去追求我的理想。

祝愿每个人的工作都顺顺利利的，生活都开开心心的，最重要的是身体都健健康康的。

kubuntu下使用openvpn访问blogspot

2009-06-27T20:11:00.004+08:00

blogspot被封了好久，过去一段时间一直使用web proxy来访问（当然，仅仅是浏览的话，使用google reader的https链接就可以了），虽然浏览日志没有太多不便，但是想要发布文章还是存在一点问题，所以好久没写文章了。

今天找了两个VPN：alonweb和UltraVPN。试用了一下，速度还不错。据说后者最近有点问题，不是太稳定。两个都是免费不限流量的，而且都有windows的安装包，用起来十分方便。虽然没有提供Linux的安装包，但是它们都是基于openvpn的，所以在Linux下稍作配置即可使用。

首先需要安装openvpn，在ubuntu的源里面就有：

$ sudo apt-get install openvpn

接着，需要去它们的网站上注册，注册的用户名和密码在连接VPN的时候需要提供。此外还需要下载配置文件和认证证书，alonweb的可以直接去官方网站下载：Get Started!。UltraVPN的可以在这里下载：ultravpn.conf和ultravpn.crt。

最后，运行openvpn就可以了，切记一定要使用root用户运行：

$ sudo openvpn --config alonweb.conf --ca alonweb.crt

输入用户名和密码，最后出现"Initialization Sequence Completed"表明成功了，这时使用ifconfig可以看到tun0连接。现在，就可以自由访问internet了。

下面是两篇参考的文章：

不吐不快

2009-05-07T22:10:00.007+08:00

很幸运，今天凌晨目睹了从地狱到天堂的斯坦福桥之战。虽然与巴萨一起经历了大半个梦幻的赛季，对这场比赛的结果已经无欲无求，但是前10分钟巴萨几次将球打入对方禁区，让我的心跳慢慢加快起来。随后埃辛的世界波让我想起了去年的老特拉福德，我预感到切尔西必将开始死守并将1比0的比分保持到终场。可是切尔西并没有死守，仍然坚持他们开场的打法，保持高强度的防守，并不断用有效的反击骚扰巴萨的后防。主队今天确实打得很好，几乎没给巴萨任何机会，13次射门只有0次中目标足以说明他们防守的成功。在阿比达尔被红牌罚下的那一瞬间，我已经不抱任何希望了。直到93分钟，小白的进球给了世界一个惊喜，我宁愿相信这是上天赐予的礼物。

纵观整场比赛，确实切尔西要发挥得好一些，在战术层面完全压过巴萨。不得不承认，巴萨能够晋级，靠的是运气和裁判的帮助。所以今天如果没有小白的进球，0比1告负的结果也完全可以接受。

不错，确实有裁判帮助的成分，但是有多大呢？真的很佩服中国媒体的导向性，新浪第一时间刊出了“3点球漏判2手球”的头条，搜狐头条更是说“5点球”。我不知道作者在看完比赛之后有没有再仔细研究过录像，更不知道他们是出于何种目的。于是很多没有看比赛，或者缺乏自我判断能力的球迷纷纷加入追捧的行列。反观黄建翔和李承鹏两篇稍显中立的博客却未能进入首页。

一时间，巴萨似乎成了全民公敌，从主流媒体到众多网友，都在指责巴萨。好吧，退一万步讲，就算那5个是实实在在的点球，但误判的是裁判，应该受到指责的是裁判而不是巴萨。难道要皮克手球后，像巴拉克那样对着裁判怒吼：“我手球了，该死的快来判点球阿。”然后再主动申请红牌离场？

指责巴萨无非是因为巴萨从裁判的误判中受益了。不错，从这场比赛的结果来看，巴萨似乎是受到了裁判的照顾。但是我不明白的是为什么没有人再提及阿比达尔的红牌？试想如果没有小白的进球，那么赛后指责裁判的可能就是巴萨了。这只能说明今天裁判的判罚中失误很多，而最终对巴萨有利。

评论裁判工作，仅从这一场看，确实有失公平，但是仅看这一场又是狭隘的。从10场，100场，甚至1000场来看，你会发现误判跟越位、假摔一样，都是足球的一部分。今天你因为误判受益了，那么你以前或者将来一定会因为误判而受害，这就是足球！从里杰卡尔德时期到现在的瓜迪奥拉，巴萨没有少受到误判的影响，但是他们从来不会对裁判大加指责，虽然偶尔暴怒，却绝对不会像穆里尼奥那样喋喋不休，导致主裁收到死亡威胁而封哨。

本场比赛，最有争议的莫过于“5粒点球”了，暂且不论。对巴萨不利的就是阿比达尔的那张红牌，先不论是否假摔，就算犯规，但是动作不算大，如果硬要算成阻止进球，那么之后梅西和小白在进区前沿打出二过一配合，在梅西有机会进入进区的情况下被埃辛绊倒，只出示黄牌是否判罚过轻？再回到上一回合比赛，普约尔在中圈附近犯规，被出示黄牌，直接导致这场不能上；巴拉克在比赛结束前，在禁区线上阻挡小白，此时如果不阻挡，小白直接杀入进区，是不是应该给巴拉克出示全场的第二张黄牌将其罚下？如果硬要说这场的“5个点球”判罚一二，那上一场亨利进区内被拉倒，又作何解？所以就这两场而言，正如黄建翔所言，裁判只是在还债。至于那“5粒”点球，可以参考“陆俊评哨”，赶紧去骂他吧！

再回到几年前两队的交锋。04－05赛季的欧冠，切尔西在主场4：2淘汰巴萨，而特里在70多分钟的远距离头球破门，进区内切尔西球员似有阻挡巴尔德斯之嫌，而如果比分为3：2，那么最终晋级的就是巴萨。一直为切尔西球迷所津津乐道的是：巴萨在11对11的情况下从没在90分钟内战胜过切尔西。而05－06赛季，在诺砍普进行的淘汰赛第二回合比赛，巴萨凭借小罗的精彩进球1比0领先，直到临近90分钟时，吉奥在进区内根本没碰到人，裁判却送给切尔西一个莫须有的点球，才使所谓的记录保持至今。

看完了与切尔西的对决，再来看看巴萨最近遭受的误判。上一轮欧冠首回合对拜仁，上半场梅西进区内突破被绊倒，裁判非但没判点球，还给梅西出示黄牌，因此还将发怒的瓜迪奥拉请上看台。上个星期的国家德比，小白在进区内遭受了比今天更疑似点球的犯规，裁判也没判。这些都没人再去捕风捉影，只因为巴萨早已锁定胜局。

再看联赛中，巴萨客场打赫塔菲，好端端的3：0被吹成了1：0。主场打西班牙人，裁判有争议地向凯塔出示红牌，最终导致主场失利。对阵比利亚雷尔，皮克拿到第二张黄牌被罚出场，幸好赛后西甲足联确定误判而取消了这张黄牌。如果真的要拿裁判说事，可以好好统计一下这5，6年来巴萨的38轮联赛，你一定会发现每年都会有不下十个好球被吹成越位。

除了巴萨的比赛，其他的例子也比比皆是。米兰德比阿德手球破门，而在之后的联赛里因扎吉不是也用同样的方式进球了？06年世界杯，就是黄建翔解说门那一场，希丁克的澳大利亚在比赛结束前被判争议点球。而追述到02年世界杯，希丁克带领的韩国队连克西班牙、意大利，一路闯入四强，我想除了棒子没人会相信他们靠的是绝对实力吧。

说了这么多，无非想说明误判就是足球的一部分，从大局上讲，每个球队受益和受害的比例是很接近的。说白了，就是那句老话：出来混的，总要还的。如果玩不起，那就别玩呗！

巴萨通过一场非巴萨式的胜利进入了决赛，场面不占优势，没有流畅的进攻，甚至打得有点难看。于是有人就跳出来说了：“巴萨配不上进入决赛。”难道切尔西第一回合在诺砍普的表现就配得上进入决赛？真是笑话。我就不明白为什么皇马可以连续1比0“绝杀”，曼联可以1比0小胜波尔图晋级，巴萨就偏偏要打出6：2这样的比分才能让人信服？难道就是因为巴萨坚持打4－3－3，而不是9－0－1？如果以比赛场面的优劣来决定最后的结果，那巴萨这几年获得的荣誉应该更多。去年欧冠半决赛，曼联依靠斯克尔斯的世界波主场1比0领先后，收缩防守，巴萨虽然占据主动却难以破门，最终出局。那去年的曼联是不是也配不上冠军？前几年米兰击败利物浦夺冠，看过比赛的人都知道谁的机会更多，那米兰是不是也配不上冠军？04－05赛季巴萨与切尔西首次交锋，巴萨控球率80％比20％，射门28：2，最终两回合巴萨被淘汰，天理何在？偶然性，技战术的融合，这才是足球吸引人的地方。通俗的讲，就是足球是圆的。

本无意加入这场争吵之中，只是看到“主流媒体”和一些网友的评论实在气不过去。没有知识也要有常识，没有常识也要多看看电视。想找我争论，我就以开头的图片回应吧。

使用Git管理简历

2009-04-25T10:46:00.005+08:00

每到找实习找工作的时候，做得最多的一件事就是修改简历了。随着个人经历的增长，简历的内容也会不断丰富。即便在同一个时期，对于一个有针对性的应聘者来说，投向不同公司的简历会因为职位要求而有所不同。有什么方法来管理这些简历呢？最笨拙的办法就是为每一份简历保留一个备份，以备日后查看和修改。久而久之，备份的文件会越来越多。其实，简历跟代码一样，也会有版本的变化，所以可以使用Git来进行管理。

我的简历使用latex排版，使用一个模板，每次只是去修改内容，然后运行pdflatex生成PDF文件。首先，初始化git repository，并把tex源文件加入版本控制之中。

$ git init
$ git add resume.tex
$ git commit

修改完resume.tex后，可以将修改提供到版本库：

$ git add resume.tex
$ git commit

如果此时的版本是用于提交的简历，则可为其设置tag，以备日后查看：

$ git tag XXX HEAD
$ git tag
XXX

XXX是自己为tag设置的名称，比如可以设为某公司某职位的名称。命令git tag用来查看所有的tag。

经过多次修改后，简历经历了多个版本的变更，这时如果需要查看以前某个tag的版本，可以以此tag为基础创建一个branch，命名为old：

$ git branch old XXX
$ git branch
* master
old

此时，branch old已经被创建，但是版本还是最新的版本，只需切换到branch old即可看到tag XXX的内容。

$ git checkout old

此时resume.tex就回到了创建tag时的版本，运行pdflatex，就可以查看当时提交的简历内容了。

查看完当时的简历，如果不需要了，可以删除branch：

$ git branch -D old

对于HTML，Word格式的简历也可以使用相同的方法进行管理。

自愚自乐

2009-04-01T21:46:00.004+08:00

今天虽然没有愚弄别人，也没被别人愚弄，但却发生了几件比较可笑的事情，某种程度上也算是自己愚弄了下自己。

上午正在忙着工作的时候，一个人发了个MSN消息过来：“终于等到你的节日了，节日快乐。”心想，这也太没创意了吧，而且是典型的群发。手里正忙得不可开交，所以就顺手关了。于是，就在这个愚人节中最愚蠢的耍人手法中开始了这一天。

这次本想玩个大的，好好“欺骗”一下Abalone和Zell，顺带唬一下sleepinggirl。策划了一个一石三鸟之计，并且从十天前就开始作好铺垫。结果一上午都没见那两人人影。

下午上班没多久，就发生了诡异的事情。最近的工作是测试一个Web应用，可是今天Weblogic却总是会莫名其妙的自己shutdown。每次我重启完，过一会就会自己关闭了。几次之后，当我又想启动的时候，发现启动脚本的名字被改成“startWeblogic.sh.pls.do.not.start”了。这个测试环境一直都只有我一个人在用，该不会是有人在跟我开玩笑吧。用“who”看了一下，确实有一个root用户在使用。

时间追溯到3个星期前，开发team给了我这个测试环境vm07，让我去配置好程序运行的环境，也就是安装JDK，Oracle Database, Oracle Application Server, Weblogic之类的工作。我登陆之后，发现这些软件都已经装好了，并且可以正常使用，大悦！前两天把程序部署进去了，还算顺利，今天就开始测试了。发现刚才的问题后，就去问管理员。管理员说你们用的不是vm06嘛。我想怎么可能，立刻去查邮件，果然是vm06，我实在想不通当时怎么会把“6”看成了“7”。再去vm06上一看，什么软件都没有。把这事告诉了manager，Manager说你快去装软件吧。于是就开始埋头装软件，根本无暇去愚弄Abalone了。看来还是“害人之心不可有”，本以为自己铺陈了十天的计划会成功，结果却被自己铺陈了二十天的做法戏弄了一番。

就在我忙碌地安装Database的时候，manager跟我说：“你该不是在戏弄我吧？”我只能无奈的回答：“我也希望是这样。”

终于花了2个小时把环境配好了。于是泡了杯茶，刚想跟同事说：“我来这实习做过的两件最愚蠢的事情，一件是用“rm *”把刚写好的test case全部删除，另一件就是这个了。”程序居然没有部署成功，抛出了一大堆异常。整到下班都没搞定，临走时心血来潮把vm重启了。进去之后发现Database的instance没有启动，我也不知道怎么启动，需要查一下文档，就关机走人了。

走到楼下，心中越想越不舒畅，再怎么样总得把Database启动起来吧，决定吃完晚饭回去加班。回去之后查了半天文档，没找到方法，这个需要请教下Ford Feng。时间紧，任务急，我选择了最直接的方式：卸载重装。哈哈，没到十五分钟，新的Database装好了。可是部署还是没成功，只能等明天让developer帮忙解决了。

希望明天别再出现这种事情了，不然清明节都得加班了。

学佛三书

2009-03-29T17:45:00.006+08:00

过年前那段时间工作学习都不太顺利，烦恼挺多，心中不快。都说佛学可以让人解脱烦恼，于是就想找些佛学的书来看看。网上搜了一下，很多人都推荐“学佛三书”。前段时间已经看完了，受益匪浅，不仅缓解了烦恼，现在也能以更平静的心态看待得失。刚才又订了两套送给朋友，希望对他们的生活、学习、工作、感情都能有所帮助。要是真的能帮到他们，那也算是功德一件了。现在也把这三本书推荐给大家。

“学佛三书”包括三本书：《佛学入门》、《正信的佛教》和《学佛群疑》。这三本书是由圣严法师所著，据说张国立、李连杰、罗大佑都是其弟子。这三本是佛学入门级的书籍，使用平实的语言讲解了佛教的起源，发展，宗派，教义等，还解答了许多初学者关心的与修行直接相关的问题。

《佛学入门》的第一部分讲了佛教的起源和发展，三本书中只有这一处系统的讲解了这方面的知识。第二部分是关于佛教的基本教义，包括因果和因缘论。第三部分介绍了学佛的修持方法，例如在家居士如何学佛。书中的很多章节都是作者早年在各地研讨佛教时的讲稿。

《正信的佛教》应该是三本中最精华的一本。全书提出了八十多个关系到佛教方方面面的问题，并逐个解答，这些问题中大部分都是不了解佛学的人或初学者容易疑惑或误解的问题，例如：佛陀是创世者吗，佛教的基本教理是什么，信仰佛教必须吃素吗，信仰佛教必须出家吗，怎样成为一个佛教徒，佛教为什么要皈依三宝，佛教崇拜鬼神吗，什么是四大皆空，什么是六根清净……全书通过解答这些问题，使人们正确的认识和信仰佛教，而不是偏信或迷信。读完此书，我发现以往对于佛教的认识完完全全是错误的。我想很多人应该也是这样。

《学佛群疑》的风格与《正信的佛教》如出一辙，也是一问一答，只是这些问题在修行和实践过程中更容易碰到。

如果对佛学感兴趣，那么强烈推荐读这三本书。在“如果程序语言是一门宗教”这篇文章中把Lisp比作佛教：“Lisp是佛教的禅宗：没有语法，没有集中的教条，没有神性崇拜。如果你聪明到能够把握，整个宇宙都会在你的掌控之中。”我觉得说得在理，佛教除了五戒十善，几乎没有什么规矩。佛教重在一个“悟”字，所以不仅要多看书，还要多思考，多领悟。

这三本书在卓越网上都有得买，价格也不贵，加起来才三十出头：《佛学入门》，《正信的佛教》，《学佛群疑》。

Find back Plasma in KDE 4.2.1

2009-03-14T11:39:00.003+08:00

Last week, I upgraded my Kubuntu to KDE 4.2.1 from repository http://ppa.launchpad.net/kubuntu-members-kde4/ubuntu. I was happy with that, because it is much faster than 4.2.0. After that I did some customization to the plasma desktop, adding widgets, changing theme and background, removing panel and so on. At last, I wanted to reconfig it, so I deleted all the files under ~/.kde to bring me a brand new desktop. Now, the terrible things happened. After I restarted KDE, the plasma didn't startup successfully, with a popup message: "Plasma workspace crashed...". All I could see is a white screen, no desktop, no task bar, no panels. Luckily, I can still use ALT+F2 to run programs, such as Konsole, Firefox, Dolphin and etc.

I searched the web, somebody said that you just need to remove the plasmarc and plasma-appletsrc files under ~/.kde/share/config directory, and restart KDE. I tried, but there were no such files at all. I think that's because Plasma failed during the startup process, so those two configuration files had not been created yet.

Just now, I found this thread: KDE 4.2.1 Plasma Crashes. It seems that they have the same problem with me. Someone says that the problem can be solved by removing file /usr/share/kubuntu-default-settings/kde4-profile/default/share/config/plasma-appletsrc. I tried, and it works for me. The plasmarc and plasma-appletsrc files are created under ~/.kde/share/config now. Great, I get back my Plasma.

Before removing the file, I read it and found that it pointed to a wrong background image path, and contained applets which don't exist now. And after restart plasma, there is no newly created file plasma-appletsrc under /usr/share/kubuntu-default-settings/kde4-profile/default/share/config/. So I guess this file is not used by KDE 4.2.1. Maybe it was used by KDE 4.1 or 4.0 before.

主角与配角

2009-03-13T07:52:00.004+08:00

一位年逾古稀的老太太，倚靠在躺椅上，手捧日记和相册，对着女儿或孙女讲述一段早已尘封的往事。很多电影都以这样的画面开始，进而引出一段可歌可泣的爱情故事。《剪刀手爱德华》如是，《泰坦尼克号》如是，《本杰明巴顿奇事》亦是如此。而《廊桥遗梦》只是把这换成了子女们对母亲遗物的整理。我们在为男女主人公的缠绵悱恻感动时，却很少注意到剧中的配角：女主人公的丈夫们。这种配角是幸福的，因为他们可以跟女主人公长厢厮守，生儿育女；但他们又是凄凉的，因为爱人心中的某个地方是他们从未染指的，这完完全全属于另外一个人。

人生就如这样一出戏。之于某些人，你是主角，之于某些人，你又是配角；总有某人是属于你的主角，某人注定只能成为你的配角。对于个人来讲，人生又是好几出同时上演的戏，在一些戏中你是主角，在其他戏中你又是配角。这本不足为奇，正是这些不同的角色才让故事情节更生动更丰满。就像戏剧中的生、旦、净、末、丑，让这种艺术更具表现力。正如在巴萨的进攻体系中，梅西的犀利突破固然重要，但同样不能缺少艾托奥的攻城拔寨，亨利的一锤定音，哈维的穿针引线，以及伊涅斯塔的灵巧前插，这样进攻才能更多样化，更具立体感。不同的角色都同样不可或缺，只是不同角色的表现形式不同罢了，有的必须耀眼，有的则只能沉稳，有的则必须默默无闻。我想谁都不希望看到自己的门将频频上镜，因为门将上镜了，要么就是防守体系被打穿了，要么就是他从网窝里捡球。

人总是自大的，总是喜欢以自我为中心，希望一切都围着自己转，所以总是把自己想象为主角。每当朋友失意的时候，总会这样安慰他：他们没有珍惜你是他们的损失，总有一天他们会后悔。事实上，这只是我们一厢情愿的想法。对对方来说，你根本一文不值，你连茶余饭后的谈资都不是，或许你永远都是一个没有台词不露脸的“死跑龙套的”。需要你的时候，你就得屁颠屁颠地跟着，不需要你的时候，就只能滚到千里之外。所以老俞教育我们别太把自己当回事。其实，滚到千里之外未必就是坏事，或许你就转角遇到爱了。

很多角色只是相对的，并且可以互换。当你被以某些理由拒绝之后，或许你又会用同样的理由去拒绝别人；当你因为某些原因抱怨别人的时候，或许别人也在因同样的原因抱怨你；当你被人以某种方式伤害之后，你却又会以同样的方式去伤害别人。

在宿命论者看来，这一切都是早就安排好的，并且由导演一一呈现，这位导演的名字叫做命运。我不相信命运，我相信因缘。所有事情的成败都是诸多因素共同作用的结果，天时、地利、人和缺一不可。我们无法决定事情的成败，但可以促成因缘的集散，所以我们需要广种善缘。

悲观者认为，纵然我们或多或少会充当主角，但终究难逃配角的命运。
乐观者认为，即使大部分时间我们是配角，但总有一出戏是属于自己的。

花入泥

2009-03-08T22:37:00.002+08:00

远山麦田如梯，
层层叠回忆，
庄稼秋收起，
而寂寞一望无际。

缘份总是带点或许，
或许你是我前世，
结发的妻。

花入泥我入戏，
如你如棋，宁愿我入局。
我提笔，书别离，
山静满乌啼，叹终于。

花入泥我入迷，
如你如笛，思念我入题。
山岚云雾里，苔藓正绿，
我朔溪，只为遇见你。

这个当然不是我写的，是方文山在《王牌大明星》中为宪哥的《三日三暝》重新填词所写。虽然节目中说是现场填词，但是从过程中出现的一点意外（方文山没对照原词填，将竖排的歌词写到横排上去了）来看，极有事先写好，当场默写的嫌疑。不过这不重要啦，这段词还是相当有意境的。

踢球分组中的概率

2009-02-22T18:48:00.038+08:00

以前暑假经常找同学一起踢足球，一般都能找到8个固定的同学，分成两组对抗。分组的方法是8个人围在一起，出示手心或手背，直到4个手心，4个手背的情况，就算分组成功。有时候会出现很多次都不成功的情况，很浪费时间，有个同学就想了个办法：他自己先站出去，由剩下的7个人先分，分成一组3个，一组4个的情况，最后他就直接加入3人的那一组，这样就会容易成功一点。

这样分组的方法真的会更容易吗？下面用计算概率的方法来验证。

方法一：排列组合

首先使用排列组合的思想来计算。对于原始的分组方式，每个人都有出示手心或手背两种选择，所以共有$2^8$种可能，但其中存在重复的情况，例如前2个人手心、后6个手背，与前2个手背、后6个手心的情况导致最后的分组是一样的，所以实际的情况共有$2^8/2$。只有当4个人出手心，4个人出手背，分组才成功，相当于从8个人中选出4个，为$\mathrm{C}_8^4$，但同样也存在重复情况，选择前4个人与选择后4个人的情况是一样的，所以成功的情况有$\mathrm{C}_8^4/2$。成功情况的数目除以所有情况的数目，得出成功的概率为：

$$\mathcal{P}_{old} = \frac{\mathrm{C}_8^4/2}{2^8/2} = \mathrm{C}_8^4(2)^{-8} = \frac{8\times7\times6\times5}{4\times3\times2\times1}(2)^{-8} \qquad \qquad (1)$$

现在，来计算新的分组方法成功的概率。新的方法实际上相当于7个人分组，分成一组3个和一组4个。使用相同的方法分析，可得所有可能的情况为$2^7/2$，成功的情况为$\mathrm{C}_7^3/2$。因此，新的分组方法成功的概率为：
$$\mathcal{P}_{new} = \frac{\mathrm{C}_7^3/2}{2^7/2} = \mathrm{C}_7^3(2)^{-7} = \frac{7\times6\times5\times2}{3\times2\times1}(2)^{-8} \qquad \qquad (2)$$
比较以上两个式子，不难发现两者是相等。

方法二：独立事件概率

下面使用独立事件的思想来计算概率。在没有人作弊的情况下，一个人出示手心或手背是一个独立事件，且出示手心或手背的概率各占50%（假设没有个人偏好）。那么，使用原始的分组方法，成功的情况为4个人出示手心，剩下的4个人出示手背，概率为：
$$\mathcal{P}_{old} = \mathrm{C}_8^4(\frac{1}{2})^4(\frac{1}{2})^4 = \mathrm{C}_8^4(2)^{-8} \qquad \qquad (3)$$
新的方法的概率为：
$$\mathcal{P}_{new} = \mathrm{C}_7^3(\frac{1}{2})^3(\frac{1}{2})^4 = \mathrm{C}_7^3(2)^{-7} \qquad \qquad (4)$$
以上两个式子的结果也是相等的，且也等于(1)，(2)。

推广到2n

现在将此推广到有N个人的情况，要分组成功，总人数必定为偶数，设为2n。使用独立事件的方法，可计算出原始方法的成功概率为：
$$\mathcal{P}_{old} = \mathrm{C}_{2n}^{n}(\frac{1}{2})^n(\frac{1}{2})^n = \mathrm{C}_{2n}^{n}(2)^{-2n} \qquad \qquad (5)$$
新方法成功的概率为：
$$\mathcal{P}_{new} = \mathrm{C}_{2n-1}^{n-1}(\frac{1}{2})^{n-1}(\frac{1}{2})^n = \mathrm{C}_{2n-1}^{n-1}(2)^{-(2n-1)} \qquad \qquad (6)$$
比较一下，两者也是相等。

由此可见，无论多少人踢球，新方法并不比原始方法更容易成功。

牛年第一场雪

2009-02-17T21:33:00.006+08:00

今天依然一觉睡到八点，关了闹钟，听完隔壁同学出门的声音，伸了个懒腰就爬了起来。走到窗前，惊讶地发现外面竟然成了白色的世界，睁大眼睛一看，果然是下雪了。虽然还是正月，下雪本属正常，但过去几天的“高温”几乎让我换上了T恤，哪里想得到还会下雪。于是一边惊叹一边给家人和朋友发短信。

刚出门的时候还不在下雪，可是走到车站的时候已经下得挺大了。雪片细碎，但是却很密，一会儿功夫就把行人的头发都染成白色了。我想audrey看到的话一定会非常喜欢。虽然这场雪下得很意外，但公交车还是毫不意外的在路上堵了一个多小时。

今天melody把我们上个月的工资证明送回学校。快吃饭的时候收到她的短信，说：告诉你一个好消息，我们以后不用再给学院送工资证明了，公司直接发给我们。这真是天大的好消息，心想：“难道学院良心发现了？”再一想：“这个可能性应该不大。”要扣的管理费应该还是逃不了的，不过以后不用每个月为了工资的事来回奔波三、四次了，而且每个月也能准时到帐，这已经是一个巨大的进步了。不管怎样，这的确是09年第一件值得开心的事情。原本以为只要在这实习一天，就不可能解除这副枷锁，没想到居然提前自由了，真是可喜可贺。

中午出去吃饭的时候雪仍然下得挺大。下班回家的时候依然没有停止的趋势。这场意外的雪真是没完没了了。

Personal Wiki

2009-02-07T13:16:00.004+08:00

我这人有两个毛病：记性差和喜新厌旧。明明当时记得很清楚的事情，过了3、4天就忘得差不多了。但是又对新事物特别感兴趣，比如技术，看到新的技术，就会放下手头的东西去研究新的，导致我的很多知识都是浅尝辄止，而且时间一长，连基本的都忘记了，等下次需要用的时候，又得从头学起。这时又只能到处去找文档和教程。所以决定使用Wiki作为个人知识库，在学习时把有用的资料记录下来，以便日后需要时能够很容易地找回来。

这是一个仅供自己使用的Wiki，所以安装在本机上即可，至于多用户、版本控制等与协作相关的功能都不是必需的，只要满足如下条件即可：

尽可能的lightweight，使用文件作为存储，不需要数据库和web server
中文支持当然是必需的，并且必须支持Linux平台
Open source，最好是使用我熟悉的语言写的，以便能自己进行修改
能方便地进行定制，修改布局，风格等
能方便地进行备份和迁移

首先推荐一个网站：WikiMatrix，通过输入一些要求，它就会根据这些要求推荐一些Wiki系统，并给出对它们进行比较的结果。经过一些筛选，最后确定3个候选的Wiki：

Wiki on a Stick：它只有一个html页面，使用JavaScript+CSS+HTML完成。所有的内容都保存在一个文件中，由JavaScript来切换显示的内容。这个创意很Cool，小巧且容易移动，可以将其存放在邮箱或U盘中。它的界面风格也很简洁，正是我喜欢的类型。但是它现在仍处于Beta阶段，如其页面上的提示：这是Beta版本，不建议用来保存关键数据。再看看最近一次更新也已经是一年半前的了，track中也没什么activity，项目似乎处于停滞阶段。而且，我也没看到Wiki on a Stick有成熟的user community，所以我最后没有选择它。
TiddlyWiki：TiddlyWiki与Wiki on a Stick如出一辙，在切换内容的时候加入了一些animation的效果，使界面看起来更“Web 2.0”一点。Journal是Wiki on a Stick没有的功能，用来记录某一天做的事情。TiddlyWiki现在的版本是2.4.3，应该算比较稳定了。最重要的是，它有很优秀的文档和user community，还有很多基于TiddlyWiki的变种，这使我最终选择了它。但是有两点我不是很喜欢，首先是它默认的风格，其次是在切换内容的方式，它并不是先隐藏之前的内容再显示新的内容，而是将新的内容放在页面顶端，经过多次切换后，页面就会上下跳动，让人很不舒服。这两点都是可以修改的，以后要研究一下。
doxWiki：这也是一个很小巧的Wiki，用Perl写的，同时自带了一个用Perl写的server，使用之前需要运行该server。它有一些不错的功能，比如导出html文件。

更多关于以上三个Wiki的比较，请看这篇文章：Personal wikis: Three small, simple alternatives。

除了搭建在本机的Wiki，还存在着一些提供Wiki服务的网站，可以在上面创建自己的Wiki页面。对我来说，这样的好处是可以在家里和公司访问Wiki。但是也有一些缺点，比如访问速度不快，受制于服务提供商的一些政策，没有网络的时候无法访问，所以我还是选择自己安装Wiki。在筛选的过程中找到了几个免费的不错的Wiki hosting网站：

Wiki Spot：二级域名，简洁现代的界面，多种主题……都是我的最爱，只是Wiki Spot的目的旨在建立Wiki community，它要求每个Wiki的主题必须能够形成一定的用户群，这与我的目的不符，所以只得作罢。
@Wiki：除去基本功能，提供了很多主题，页面操作也很简单明了，不过不支持二级域名。
Intodit：二级域名，主题比较少，不同主题布局都是一样的，只是颜色不同而已。不是很喜欢它的button风格，在firefox中很难看。可定制的部分不是很多，不喜欢自带的那几个tab页。

先花点时间研究一下TiddlyWiki，如果你有更好的选择，欢迎推荐给我。

兰亭风花

2009-01-05T20:46:00.019+08:00

从《东风破》的离愁，到《菊花台》的悲凄，到《青花瓷》的温婉，再到如今《兰亭序》的无奈，方文山将古典诗词的神韵融入了歌词之中，首首歌词都蕴含着风雅之音，如《东风破》易让人想起“相见时难别亦难，东风无力百花残”的名句。于我而言，尤推《兰亭序》为挚爱，这首词将古典诗词的文字和意境之美发挥到了极致。信手搜索“兰亭序”，竟在百度百科的解释中读到对这首歌词的赏析，诸多观点与我不谋而合，故借其一二，完成此文。

兰亭临帖行书如行云流水
月下门推心细如泥脚步碎

夜深人静，挑灯临摹，笔尖行于宣纸之上，思绪如云，心境如水。月光皎洁，木门轻推，但闻细碎的脚步声渐近。唐代苦吟诗人贾岛有诗：“鸟宿池边树，僧敲月下门。”，极具禅意。而正是这两句诗引出了他与韩愈的千古佳话，“推敲”一词由此而来。

忙不迭千年碑易拓却难拓你的美
真迹绝真心能给谁

流传千年的碑文容易拓，而爱人的美貌却无人能够模仿比拟。《兰亭集序》的真迹已经不复存在，我的一片真心又能与谁呢？相传唐太宗李世民极其喜爱王羲之的书法，经过一番周折终于得到《兰亭集序》的真迹，最后此真迹也作为唐太宗的殉葬品而永绝于世。如今所见的《兰亭集序》都是后世的摹本或拓本，最有名的要数“神龙本”和“定武本”，其中“定武本”出自唐代大书法家欧阳询之手。摹写真迹已为难事，而描摹爱人的美却要难上千倍。

牧笛横吹黄酒小菜又几碟
夕阳余辉如你的羞怯似醉

杜牧诗曰：“清明时节雨纷纷，路上行人欲断魂。借问酒家何处有，牧童遥指杏花村。”同有牧童和酒家，但两处的意境却不尽相同。《清明》的前两句极尽渲染了清明时节悲伤的气氛，无奈之际只能借酒浇愁，而“遥指杏花村”却又是一幅春意如画的景象，在悲伤之中，却又对未来充满希望。而歌中这两句，傍晚时分，牧童归家，笛声悠扬，斟上一盏黄酒，点上几碟小菜，是何等惬意。青山环绕，江水蜿蜒，泛舟江渚之上，渔舟唱晚，夕阳余辉映衬爱人的脸庞，美不胜收，叫人如痴如醉。而在这美好的画面背后却藏着淡淡的哀愁，而如今，却只能自斟自饮，徒有无限美的夕阳，也只能感叹黄昏已近。

摹本易写而墨香不退与你同留余味
一行朱砂到底圈了谁

真迹已绝，虽只有摹本，但墨香却也能流传万世，就如同你，虽已难觅踪影，但你的一颦一笑却会在我心中隽永流长。这一行一行的文字，究竟是在向谁诉说呢？

无关风月我题序等你回
悬笔一绝那岸边浪千叠

欧阳修有词：“人生自是有情痴，此恨无关风与月。”传说乾隆下江南，夜游西湖湖心亭，被美景吸引，于是写下“虫二”二字，意为“風月无边”。我曾游览西湖，虽未能登上湖心亭一游，但舟行湖面，已足以让人心旷神怡，流连忘返。爱人不在，“应是良辰好景虚设”，纵有这无边风月，也已无心欣赏。悬笔落款，情到深处，心潮如岸边千叠的浪般澎湃。

情字何解怎落笔都不对
而我独缺你一生的了解

“问世间情为何物？”心中有千言万语想要述说，下笔时却又不知从何说起，仿佛任何词藻都不足以表达这份感情。正是“相思树下说相思，思郎恨郎郎不知。”

弹指岁月倾城顷刻间湮灭
青石板街回眸一笑你婉约

秦观有词：“韶华不为少年留，恨悠悠，几时休。”纵使有“一顾倾人城，再顾倾人国。”的容颜，也逃不过岁月的侵袭。而我却铭记在江南古镇，你的回眸一笑。“人生若只如初见，何事秋风悲画扇？”

恨了没你摇头轻叹谁让你蹙着眉
而深闺徒留胭脂味

李白有诗：“美人卷珠帘，深坐蹙娥眉。但见泪痕湿，不知心恨谁。”从“弹指岁月”到“徒留胭脂味”，这四句似在讲述民间女子被帝王选妃入宫，却冷落于后宫之中，只得与胭脂为伴的悲惨遭遇。

人雁南飞转身一瞥你噙泪

“碧云天，黄花地，西风紧，北雁南飞，晓来谁染霜林醉？总是离人泪。”

掬一把月手揽回忆怎么睡

夜色寂静，一缕月光洒在床头，回忆泛滥，辗转反侧，难以成眠。又似“长天净，绛河清浅，皓月婵娟。思绵绵，夜永对景，那堪屈指，暗想从前。”却只怨“明月不谙离恨苦，斜光到晓穿朱户。”

又怎么会心事密缝绣花鞋针针怨怼
若花怨蝶你会怨着谁

“自古多情空余恨”，多情本易自扰，才换来如今的无尽怨怼，只可惜“天长地久有尽时，此恨绵绵无绝期。”
“翻阶蛱蝶恋花情”，《蝶恋花》词牌多用来抒写缠绵悱恻之情，而其中数柳永，欧阳修和苏轼的几首最为有名。若花怨蝶，你又怨谁？“馀音落蕊坐相催，可怜绝世为谁媒。”

雨打蕉叶又潇潇了几夜

《青花瓷》中也有芭蕉和雨，是我最喜欢的词句，“帘外芭蕉惹骤雨，门环惹铜绿。”一个“惹”字勾勒出了轻柔浪漫的画面。而此处的“打”字却平添了几分沧桑之感，“风又飘飘，雨又萧萧。……流光容易把人抛，红了樱桃，绿了芭蕉。”正如“山河破碎风飘絮，身世浮沉雨打萍。”

我等春雷来提醒你爱谁

到最后，我也只能等待，待来年滚滚春雷敲醒大地之时，你会爱我吗？

Liar Paradox and Halting Problem

2008-12-03T22:11:00.007+08:00

Liar Paradox
首先来看一下什么是liar paradox。Liar paradox的雏形来自于一个叫作Epimenides的克里特人，他说：“所有克里特人都是说谎者。”这常常被认为等同于liar paradox，其实不然，因为如果他说的是真话，那么他就在说谎；如果他在说谎，说明至少还有一个克里特人说的是真话，这并不矛盾。最早的liar paradox版本是由生活在公元前4世纪希腊的麦加拉学派（Megarian）哲学家Eubulides提出的。他说：

A man says that he is lying. Is what he says true or false?

如果他说的是真的，那么他在说谎；如果他说的假的，那么他没在说谎。

后来又出现了一些liar paradox的变种，比较有名的有：

This sentence is false.

下面的悖论又名"Jourdain's Card Paradox"：有一张卡片，一面写着：

The sentence on the other side of this card is true.

而在卡的另一面却写着：

The sentence on the other side of this card is false.

Halting Problem
Halting Problem是计算理论中的经典问题。它的意思，简而言之就是：对于一段程序和有限的输入，决定其是终止还是永久运行。说白了就是设计一个算法来判断一段程序是否会进入死循环。Alan Turing在1936年证明了不存在这样的算法。

在SICP课程的最后一讲[4]中，为了说明不是任何事物都是可计算的，使用了这样一个例子来证明不存在halting problem的算法。

首先，假设存在这样的算法，则存在函数(halts? p)：

（halts? p)
=> #t if (p) terminates
=> #f if (p) does not terminates

现在有如下程序：

(define (contradict-halts)
    (if (halts? contradict-halts)
        (loop-forever)
        #t))

(contradict-halts)
=> ???????

很容易，我们可以定义(loop-forever)为：

(define (loop-forever)
((lambda (x) (x x))
(lambda (x) (x x))))

这就是著名的Y combinator。

这里使用的就是liar paradox的精髓，如果这段程序会终止，则让它无限循环；如果程序不终止，则让它返回#t。

Resources
[1]. Liar paradox on Wikipedia.org
[2]. Some paradox
[3]. Halting problem on Wikipedia.org
[4]. Video courses of SICP

Understanding Scope

2008-11-29T13:40:00.028+08:00

Scope是Programming Languages中的重要概念。我的第一门Programming Language是C++，记得当时买的参考书专门用了一章的篇幅来讲解scope，罗嗦了一大堆，当时搞清楚了，事后很快就忘记了。后来学习Java，PHP和Ruby等语言，都有scope的概念，不过都大同小异。掌握了scope的内涵，任何语言的scope都不难学习。

What is Scope?
Wikipedia上对scope的定义是[1]：

In computer programming, scope is an enclosing context where values and expressions are associated.

首先，scope是一个"enclosing context"，它是一个上下文环境，并且是封闭的。其次，在这个环境中，"values and expressions are associated"，也就是说在这个环境里，expression被绑定到特定的值，但是出了这个环境，该expression就不再绑定到这个值了。

有一个笑话，话说南京人把三轮电动摩的称作“马自达”，这种车体积小巧，马力不大，开起来噪音很大，而且外壳也不是很牢固。在乡下开开还可以，要是在城里主干道上行驶，不仅危险系数很高，而且还会影响市容。所以在金陵饭店门口挂了个牌子：马自达不得入内。于是外地开着马自达来南京的商人，看到牌子都被吓跑了。

同样是“马自达”这个词（expression），在全国这个scope中指汽车马自达（value），而在南京scope中就变成了三轮摩的（value）。古语有云：“橘生淮南则为橘，生于淮北则为枳”，也是这个意思。由此可见，无论是expression还是其他事物，都应该放在特定的scope和环境中进行评价，很有哲学意味吧。

有些语言提供了namespace的机制，比如C++中的using namespace和ruby中module。Namespace也是一个scope，只不过它用了一个标识符来表示这个scope。这样，在谈论expression时，就可以指定在哪个scope中确定其值。比如上面的笑话中，在“马自达”前加上“南京话中的”这个状语，就不会引起误会了。

Why Scope?
在计算机发展的早期，内存大小和CPU的计算能力都很有限，程序通常也很小，数据被存放在一个地方，程序的任何部分都可以访问数据。但是，随着计算机的发展，程序变得越来越庞大，有很多部分组成，也需要很多程序员共同开发而成。这样，把程序不同部分需要的数据混合在一个地方就会造成混乱。比如程序的不同部分中用到相同的变量名，但是它们表示的是不同的数据，这样就很难确定程序的不同部分是否使用了正确的数据。

所以，就需要引入scope的特性，这样就能控制程序的不同部分访问它们各自的数据。通常，scope有两个作用。(1) define the visibility[1]：定义变量在特定的scope中才可见。这样，默认地，程序的某个部分只能访问该部分中的数据，而不会访问其他部分的数据。最常见的情况是在程序的不同部分可以定义相同名称的变量，它们指向不同的数据，而不会引起命名的冲突。(2) reach of information hiding[1]：得到隐藏的信息。比如使用namespace来访问其他scope中的数据。

Lexical Scoping
根据scope的定义，scope是expression和value关联的地方，那么，是根据什么原则把expression和特定的value关联到一起的呢？有两种scope类型：lexical scoping和dynamic scoping。先来说说lexical scoping。

Lexical Scoping（又称Static Scoping）有很多定义[5]，但从其名称可知，lexical scoping只与程序语句的组织有关，而与程序运行时无关。变量只在其定义的block中可见，离开此block变量就不存在了。因此，在编译的时候就可确定变量绑定的地址，即可通过分析程序本身来确定变量的绑定，而无须运行程序。Lexical scoping意味着[4]：

an identifier at a particular place in a program always refers to the same variable location — where “always” means “every time that the containing expression is executed”, and that
the variable location to which it refers can be determined by static examination of the source code context in which that identifier appears, without having to consider the flow of execution through the program as a whole.

现代的Programming Languages大多使用lexical scoping，比如C，C++，Java，Ruby，PHP，Scheme等。

如下用C写的代码：

int x=0;
int f() { return x;}
int g() { int x=1; return f();}

or in Scheme：

(define x 0)
(define (f) x)
(define (g)
    (let ((x 1))
    (f)))

函数g的返回值为0，因为在定义函数f的时候，x绑定到全局的x，即0，所以无论什么时候运行f，结果都是0，所以g的结果也为0。

对于不支持High Order Procedure的语言（如C），实现lexical scoping只需使用一个symbol table记录变量的scope和memory address，从中查询变量即可，这是很高效的，因为每个变量的位置在编译时就确定了。而对于支持High Order Procedure的语言（如Scheme），则需要为每个函数保存其定义时依赖的环境（函数及其定义的环境组成了一个Closure）[6]。

使用lexical scoping有助于代码的模块化，也有助于程序员根据绑定来推出变量的值，减少错误的发生。这也是现代Programming Languages大多使用lexical scoping的原因。

Dynamic Scoping
Dynamic Scoping无法在编译时确定变量的绑定，需要在程序的运行过程中才能确定。在运行过程中，每个变量都有一个对应的stack来保存绑定。例如，每次变量x被定义的时候，都会向x对应的stack X中push最新的绑定，当x离开当前scope后，就pop stack X。访问x的值时，每次获得的都是栈顶的绑定。

早期的Lisp语言都是使用dynamic scoping的，后来都渐渐加入了lexical scoping特性。现在Emacs Lisp仍然使用dynamic scoping。而Perl和Common Lisp则允许变量定义时指定其scope类型。

这时，在上面的例子中，函数的返回值为1。因为在g的函数体内定义了x=1，这时就向x的Stack中push了x＝1的绑定，这时再调用函数f，f返回的x则是从栈顶取出来的绑定，即x=1。在这个例子中，函数f的返回值不再是确定的，它依赖于被调用时x的值。

Dynamic scoping比较容易实现。在寻找某个变量的值时，可以遍历activation record，直到找到为止，这种方法叫作deep binding。还有一种效率更高的方法，如上描述，为每个变量维护一个绑定的stack，每次只需对栈顶元素进行操作即可，这种方法叫作shallow binding。如下图所示：

Dynamic scoping可以给程序带来很大的灵活性，在实现函数的时候不需要去推理变量的绑定，而只需专注于系统的当前状态。利用这种好处需要有良好的文档支持。但是它的缺点也很明显，首先它不利于模块化，设想一下如果使用dynamic scoping，那么现在那么多的java framework都可能无法正确运行。其次，由于无法知晓运行时的环境，会给程序带来意想不到的危险。因此，现代programming language几乎都不使用dynamic scoping。

Scope的一个重要作用是解决命名冲突。设想一个极端的情况，程序中所有变量都不重名，那么无论使用lexical scoping还是dynamic scoping，运行结果都是一样的。由此可见，两者的差别在于对重名变量的绑定方式的不同。从本质上讲，对于每个标识符，两者都需要维护一个stack来决定当前使用的绑定，而lexical scoping是在编译的时候维护这个stack，而dynamic scoping则是在运行时维护。

Conclusion
Scope是决定expression与value关联的上下文环境。使用Scope可以解决命名冲突，定义变量可见性，以及获取隐藏的信息。Lexical scoping和dynamic scoping是scope的两种类型。

References
[1] Scope (programming) on Wikipedia.org
[2] Scope in Programming Languages
[3] Introduction to Programming/Scope
[4] Lexical Scope on GNU.org
[5] Lexical scope definition
[6] Structure and Interpretation of Computer Programs

惊魂一刻

2008-11-26T23:32:00.006+08:00

Kubuntu 8.10发布快一个月了，因为担心升级后会出现问题影响日常使用，所以一直使用着经典的KDE 3.8。上周末终于禁不住诱惑，狠下心升级到了8.10。升级过程非常顺利，没有出现任何问题。虽然KDE 4谈不上“惊艳”，但我还是挺喜欢的，界面设计很精致，很professinal，特别喜欢新的Konsole，默认的配色很漂亮。唯一有问题的是播放器，无论是mplayer，smplayer，还是kaffeine，打开视频文件后，都会导致黑屏，就只能重启系统了。kaffeine有50%的可能出错，而mplayer和smplayer几乎每次都会出错。由于kaffeine还没有KDE 4的版本，现在我使用的还是KDE 3的版本，所以也可以理解。

使用的这几天，每天播放视频都会黑屏，所以今天黑屏后，依然如往常强行关机、重启。这次重启时在check /home分区时出错了，提示需要手动运行fsck。以前也遇到类似的问题，就顺手运行：

$ fsck

啊！忘记指定分区了，这样就去check主分区了，直接导致了主分区损坏，重启后grub报error 17错误，无法进入系统了。

不急不急！我有Live CD。运行Live CD后就开始google了。看了“Grub Error 17 问题之简单解决“后心想可以解决了。可是运行find命令的时候，又报出grub error 15的错误。搜出来的解决方案也很多，进入/boot查看内核文件之类的，这时我发现了问题的所在。在使用如下命令mount主分区时，提示这是不正确的文件系统类型，而同样的做法mount /home分区却是成功的。

$ sudo mount -t ext3 /dev/sda1 /media

由此可见，一定是刚才的fsck导致/dev/sda1上的文件系统损坏了。又google了一下，几个帖子都说他们最后的解决方法都是重装系统。这时心里一惊，真的要重装吗？订的Kubuntu 8.10的盘还没到，手头又只有7.10的盘。刹那间，一个念头闪过，何不用fsck再修复一下/dev/sda1呢？

$ sudo fsck -y /dev/sda1

这下系统能启动了，再用fsck修复一下/home分区就OK了。

$ fsck /dev/sda5

一个小时后，又重新进入系统了。一个误操作导致了虚惊一场，不过还是希望能快点解决播放视频黑屏的问题，这样我也不用整天强行关机了。

立冬苦吟

2008-11-12T19:51:00.003+08:00

残阳西下，秃树黄叶风尘沙。歌舞声罢，月似狼牙，寒光照枯桠。去时何足夸，来日泪无涯。老骥瘦马，看尽长安花。

下车

2008-11-01T13:22:00.007+08:00

每周四晚上都会去本部上课，九点下课搭同一班车回去。跟往常一样，今天车上的人也挺多的。根据经验，往后门附近走，很快就会有位子。我一个劲挤到了车后面。果然，没过几站，就在倒数第二排找到了座位。刚坐下，从斜对面的座位上跑过来一个小学生，手里抱着装满东西的购物袋，一边在我旁边的座位坐下，一边朝我后面的座位喊了声“妈妈”。原来是母子俩一起出来的。这一幕勾起了我小时候跟妈妈进城的回忆。

汽车过了一站，又有一些乘客下车了，车里已经不挤了。见最后一排有个空位，小学生就爬了上去。他妈妈连忙阻止他，叫他别上去，那边前面没有遮挡，不安全。这时坐在旁边的一个男人站了起来，让小学生坐在里面的一个位子。小学生边坐下，边说：“没关系，这不还有我爸在嘛。”原来那个男人是他爸。他们一家三口就这样坐在汽车的最后一排，儿子在父母中间。

车里的电视正在播放一个关于离婚调解的节目，我看得出神，没有再关注他们。只是小学生的一句：“真希望现在能堵一会车。”让我的注意力从电视转回车内。

车又进站了，那个小学生抱着购物袋，他爸爸提着书包，在车门前等候下车。可是他妈妈没有下车，只见小学生朝我后面挥手告别。直到下车了，他还在路边依依不舍的挥手。这让我感到十分疑惑，为什么他们没有一起下车呢。

车快要到达终点站了，车里显得空荡荡的。我很想回头看看，可是我仍然望着窗外。只是偶尔能听到后面传来的阵阵抽泣声。

我是灾星

2008-10-31T20:40:00.011+08:00

闲来无事，回想了两三年来发生的一些事情，发现它们都有一个共同点，就是原本好端端的事情，只要我一涉足，就会因为种种原因而不能顺利完成。看来，我的确是个“灾星”。

大三上学期，突然萌生了兼职的念头。在网上投了几份简历，有一家公司很快就联系了我。这是一家美国公司，招兼职的是一个华人留学生，他说希望能把这样的机会留给中国的学生。还打了几次越洋电话给我，说对我的情况挺满意，已经提交给他的leader了，问题不大，不过希望我能去学习一下PHP。于是花了一个星期学会了PHP。之后，就被告知由于投资商的资金出了问题，这个项目被无限期搁置了。至于是如其说言，项目真的无法进行，还是他的leader不同意录用我而找的借口，就不得而知了。

大三下学期，一个同学的叔叔在政府工作，负责一个项目，做一个网站，收集全市几百家企业的信息，供政府内部使用。由同学介绍找到了我，通了几次电话，确定要把项目交给我做了，唯一的要求就是要找一个老师过去跟他的领导谈一下项目开展及酬劳问题，因为他的领导是一个上了年纪的老干部，我们这种“小孩”去跟他谈太嫩了，不合适，以后开发的事情就可以由我自己完全负责。去找了老师，不过那段时间比较忙，要到月底才行。对方说时间方面没关系，只要能过去一次就可以了，我可以提前过去聊一下需求之类的，这样也算是确定要做这个项目了。于是约好了同学，买好了火车票，准备周末就过去。这样的行程准备了两次，但都没去成，第一次是因为市里出了交通事故，第二次是因为省里领导要过去检查。一托就到了月底，最终老师也没去谈，这里面的种种也不提了。等我暑假回去的时候，对方说之前是领导刚上任，俗话说“新官上任三把火”，所以想弄个政绩工程，现在过了段时间，位子坐稳了，就不想做了。有机会的话以后再跟我合作。

大四开学前一个月，回到学校，网上有个创业团队在招人，对用到的技术挺感兴趣的，就加入了。团队有五、六个人，都是南大软院或计算机系的。跟带头的人见了面，感觉不错，还签了保密协议等文件。说是创业，其实也就是几个学生做个Web项目，然后上线测试。我负责数据库的设计和Lucene搜索的实现。开始的时候每周都有例会，大家热情都很高。计划10月份就要上线。我花了不到两周的实现把手头能做的工作基本都做了，接下来就是等另一个伙伴工作完成，我再继续。可是一周，两周，三周都没有等到，连例会都没出现。而每次例会都在反反复复的讨论一定要用什么技术，这个功能是现在实现还是以后实现，很久以后我们应该要有什么功能……进度几乎停止。随着大家热情的消退，并且都忙于个人事务，项目实际上已经停止。于是上线时间从10月推到11月，又从11月推到12月。后来，带头的人终于无奈的宣布项目失败。至今，那段Lucene代码仍躺在我的workspace中。过了段时间再跟他聊的时候，他告诉我他对Rails和REST十分着迷，决定彻底放弃Java。

从大二开始学习J2ME，之后做了几个相关的项目，几乎每天都会上j2medev学习交流，因此认识了站长mingjava。大四刚开学的时候，得知我想保研去北京，他就邀请我去他创业的公司实习。我很感兴趣，后来去北京保研面试的时候还特地去他的公司参观了一下。9月底保研结果就出来了，当时几乎决定国庆之后就要去北京实习了，mingjava也开始替我关注租房的信息。后来发现保了研之后还有很多手续要办，体检、报名、采集信息，一直要到11月底才能全部完成。这与他希望的时间出入太大，所以只能放弃了这次机会。心想以后到了北京，还是有机会的。到了次年4月份再跟他聊的时候，得知由于投资方觉得没有前途，项目已经终止了。

大四下学期临近毕业了，曾经合作过的黄san跟我说他朋友有个项目，后台有些工作要做，就是设计下数据库，用Spring写点service，挺简单的，想让我花个十天半个月做一下，“顺便补充一下小金库”。过了三天，他告诉我项目快定了，很快就可以做了。之后就再也没有下文了，我想可能又是因为项目没能开展吧。

我一直认为读研的最大收获是遇到了我的导师，一年跟着他学到了很多。今年4月份的时候，他在邮件中告诉我们他一直在筹建的实验室一个月之内就可以完成了，感兴趣的学生可以进入实验室跟他合作。我当时一心打算在他的实验室做到毕业，从没计划去企业实习。可是到了5月，他告诉我们他换了投资方，所以要过一段时间才可以；6月份的时候，他告诉我们他正在做demo，可能要过三四个月才行；9月份的时候，他告诉我们：你们还是先找个实习吧，去公司体验体验，等我把实验室建好了，你们感兴趣的话还可以回来，如果我们没能合作也没关系，只要你们学到了做研究的方法就够了。于是，我只能开始找实习了。

刚开始找实习的时候并没打算全职工作，就想找个兼职，解决下生计问题，还可以有很多时间自己看书学习。看到一个院里师兄发的兼职信息，跟他聊了一下，他觉得我挺合适的，不过因为他之前的两个项目已经完成了，都处在维护期，所以还没什么工作可做。有一个项目正在谈，下周就会有定论。第一次跟合作者约好了时间，结果对方因为有事推迟了，第二次因为之前的事情没有解决，又没谈成。他在邮件里告诉我约好了下周谈，从此就再也没有回音，至今不知道谈没谈成。

虽然兼职没有找到，但是很幸运，我被甲骨文录取为实习生了。据说是某个老大提出要做一个项目，特地招实习生去做这个项目的，周期为8个月。面试的时候听说这个项目肯定要做，而且挺急的，所以最好能尽快on board。可是现在上班还不到一个月，老大们就“拍脑袋”说不做了，要知道在这段时间里，技术调查工作已经基本完成，而带我的工程师已经把项目的架构都写好了。所以现在还不明确我接下来要做什么事情，下周才能确定我的工作内容。想到是因为当初要做项目才招我为实习生的，现在却要花7个月的时间做别的工作，真的挺搞笑的。

To be continued...

成功，我还没上路唉。

萧萧秋叶诉离愁

2008-10-11T21:54:00.004+08:00

初到大兴，也是一个这样的秋天，不过那是初秋时节，虽然暑气未消，但是早晚已有明显的凉意。喜欢这里早晨明媚的阳光，喜欢清晨略带凉意的气息，喜欢如苍穹般清透的天空，喜欢露似珍珠月似弓的夜晚，喜欢这里的一草一木，当然还有令无数学子神往的声望。

但是，人生并不只如初见那般美好……就像许多炎黄子孙在这片华夏大地上只能“暂住”一样，我们也必须在毕业前一年多，提前办理离校手续。暑假后回到学校，经历了一次又一次离别，好朋友都陆陆续续的离开了学校。现在，终于轮到我了。原本打算陪老章一起住到年底，新年过来一起搬走。可是学院的规定使我不能继续留下来了。上班，看房，搬家，5天时间，我完成了这些事情，此时我正坐在租的房间里承受孤独。

这次走的很仓促，仓促的来不及诉说离愁别绪。以后每每回味起这400个日日夜夜，酸甜苦辣都会涌上心头，个中滋味，我想只有经历过的人才能明了。时过境迁，很多事都如昙花一现，但愿还有些事，有些人能只如初见。

今早醒来，沐浴在明媚的阳光中，意识到这已是我最后一次享受这早晨的时光。从此，大兴的生活就告一段落了，虽然还能经常回来看看，但是下次回来的时候，我已经不属于这里了。

夜深了，可是了无睡意。“明月不谙离恨苦，斜光到晓穿朱户”，此刻更体会到什么叫做夜凉如水。又回想起中午“一瓢浊酒尽余欢”的场面，今宵注定梦寒。

知足

2008-10-03T22:20:00.004+08:00

九月携秋意，
风吹树影摇。
缥缃通古韵，
自饮亦逍遥。

You will never smoke alone

2008-09-13T08:34:00.001+08:00

Yo，这篇日志，给毛里，今天是你的生日，so，you gotta be happy！

记得那是六年级，二选一，我来到你的班级。依稀记得你，胸前挂着钥匙，遵守纪律热爱学习，老师常常夸你是个好孩子，值得大家学习，要向你学习。其实，我离开小泾，不是为了来跟你争第一，虽然排名第四我不服气，但你是当之无愧的第一。

时间来到1997，隔壁学校的第三个班级。三年时光除了学习，还有足球将我们紧紧联系在一起。都说毕业了就要各奔东西，我们却有幸继续同行。高三那年，我们一起晚归早起，考试，压力，汇成我们共同的经历。

但是，天下没有不散的筵席，你我终需面对分离。从此，一年见不到两次。都说若是知己，天涯两处都是比邻，really，我也深深明白这个道理。每年假期，with homies，踢场球完个痛快淋漓。足球不是游戏，而是持续升温的友谊。

十多年的朋友，我们知根知底。你说，magic，2008让我们一起打破魔咒。可是刚刚过去的暑假却满是忧愁。难受，是出于同样的感受。原来我们都渴望自由，谈起感情会皱起眉头。有人要放手，有人想回头，有人回头却又放手，留你在这独自守候。算了吧，感情是生活的毒瘤，这场show的剧情实在太丑陋。她不想留，just let her go，反正生命要继续yo。

现在不是垂头丧气的时候，抬头，别发抖，烟头啤酒只会让你忘记什么叫做追求。Life is still a struggle，再多的trouble也无法让我们放手。现在向前走，把伤口藏在左边口袋背后，you know，这是男人的logo。不爽就来my home，because you will never smoke alone。

我爱你爱之党员liangpi

2008-09-05T13:50:00.006+08:00

说起liangpi，其实我更喜欢称他为良总，但是liangpi为人一直比较低调，在他看来那些自称“总”的人只是为了满足个人的虚荣心。我想在他心中，真正让他感到自豪的是作为一名党员。闲来无事，liangpi会跟我们谈谈国家大事；而当我们谈起关于迷信的事情时，liangpi总是会立刻表明立场：我是党员，党员都是无神论者。

初识liangpi，觉得他是一个腼腆、老成、正直的小伙子。相处了一年，才发现liangpi也有很多与众不同的特点。他跟俄罗斯撑杆跳高冠军伊辛巴耶娃有个共同的爱好，就是不断打破自己的记录。在他看来，记录就是用来打破的。于是，昨天liangpi的离开，代表着5202的最晚睡觉和最晚起床时间就此被封存了。第一次被liangpi震撼是在开学后不到一月的时候，半夜起来，发现liangpi还坐在电脑前，一看时间，已经快2点了（现在看来这不算什么，但那时才开学，大家都比较低调，所以睡得比较早）。然而，这仅仅是个开始。当每天2，3点睡已经成为习惯后，我们所有人都认定这位来自山东的年轻人将代表年轻的一代向前辈们发起挑战，挑战人类的极限。我们关心的不是他能否打破记录，而是他能将这记录提高到什么程度（请允许我借用奥运会田径评论员用来评论Bolt的这段话）。于是，4点、5点、6点，记录一次次地被打破。直到有一天，8点，我起床不久，liangpi才悄然入睡。至此，liangpi已将最晚睡觉时间（上午8点）和最完起床时间（下午4点）两项记录收入囊中。此后，liangpi再也没有打破这两项记录，或许他身体状况不佳，或许他已失去了不断打破记录的热情？我们不得而知。

那么是什么动力支持着liangpi独自熬过漫漫长夜呢？一整夜他究竟在做什么呢？实况！对，就是实况。liangpi是个十足的实况迷。尽管经过了长久地心理斗争，他还是没能抵挡住实况的诱惑。在无数次的卸载之后，你总会在一个平常的午后，不经意地看到liangpi又玩起了实况。在那么多寂寞的夜晚，liangpi通常会选择鲁能泰山，从最低级别的联赛开始，一直将其带到顶级联赛，直到取得欧洲冠军杯。后来，liangpi还参加了学院的实况比赛，最后止步于八强。值得一提的是在1/4决赛的时候，liangpi在2比0领先的大好局势下，因为放松导致被3：2逆转，真是令人扼腕叹息。

都说喜欢玩实况的人多半是球迷，我想，liangpi似乎也是个球迷吧。他喜欢皇马、米兰，喜欢罗纳尔多，欣赏穆里尼奥，当然还有他最爱的山东鲁能。但为什么要说“似乎”呢？因为他从来不看直播，也从来不下比赛看。即便在那些熬夜有比赛的夜晚，他也是最多打开新浪，看看比分直播。记得liangpi跟我说过，等鲁能来北京打比赛了，我们可以一起去工体看，可惜至今没能实现。幸好今年在我们的强迫下，liangpi跟我们一起观赏了欧冠和欧洲杯决赛，也算是弥补了一点缺憾。

大兴这地方没什么好去处，我们唯一的娱乐就是打乒乓了。liangpi打球风格用一个字形容就是“稳”，极其地稳。不是绝好的机会他绝不会发力扣杀，而且他动作幅度很想小，几乎看不到他上半身会有什么摆动。不过有时候，他也会耍耍小伎俩，比如发球时会看着右边，结果将球发到右边。还会故意将球打到手背上，以改变球的方向。我们一起参加了学院的乒乓球比赛，虽然一局未赢，但这段经历是难忘的。

说了这么多都是关于娱乐的，但是liangpi绝对不是一个贪玩，不思进取的人。且不说担任综合实践大组长，抑或是帮导师做事如何如何努力，就凭他一年来从来没有翘过一节课，还去蹭课旁听了一学期的算法这一项就已经冠绝软院了。

在感情上，liangpi虽然算不上达人，但绝对不是菜鸟。liangpi教育我们：不要把感情生活写在日志上，就算写了，也要发布一个删减版，所以在此将感情部分略去。

昨天，在一个雷声轰隆，烟雨朦胧的夜晚，我们送走了亲爱的liangpi同志。是的，他就这样离开了我们，离开了5202。liangpi什么时候才会再回来呢？什么时候我们还能再见面，还能一起打一场告别赛吗？“这个不好讲的，en……，确实不太好讲。”

逝

2008-06-18T09:42:00.004+08:00

得知奶奶病危的消息是在十天前了，端午节的上午打电话回家，爸爸沉重地说奶奶身体不好，姑姑什么的都回来了，叫我不要担心。我知道这次可能真的熬不过了，很想立刻就回家，可是考试时间冲突，爸爸说别急着回，等他的电话吧。

接下来的每一天我都在祈祷，希望可以考完试回家看看奶奶。可是终究没有等到那一天，6月17日晚11点多，她就这样永远离开了我们。上午接到爸爸的电话，顿时手足无措，又是该死的考试，回去了肯定就赶不回来了。爸爸叫我别回了，“不要回家，不要影响考试”，这是奶奶前几天千叮咛万嘱咐的。

五年前的三月，就是我高考的那年，奶奶第一次查出了这个病。可能原本就已经得病了，只是在一次劳动中的跌倒导致了病情的爆发。第一次检查结果说是尿毒症，可能没多久时间了。还记得爷爷在的时候，最大的心愿就是看到我考上大学，可是他却连我中考都没能看到。就是在中考那年，也是三月，爷爷走了。就快高考了，奶奶又不行了。老天真的就不能满足两个老人家这个小小的心愿嘛，在去医院的车上，我禁不住泪流满面。后来复诊说还没严重到这个程度，不过一个肾脏已经开始萎缩了。

出院后，经亲戚介绍，找到了一个有专治肾病祖传秘方的医生，在他那里点了中药，此后中西药兼服，过了不到半年，奶奶的病情有了好转，从可以自己照顾自己，到一度都可以做家务和农活了，这一点我们全家都是反对的，可是他们那一代人，有了力气了，就不肯闲着。就这样，大学四年，奶奶的病情虽然偶尔有所反复，但是都没有出现大的状况。

毕业后留在学校做了一个月的项目，在回家的火车上，妈妈告诉我奶奶又住院了，是前几天的事了，怕我担心就一直都没告诉我。于是下了火车就直接去医院了，看到爸爸凝重的神情就知道情况不妙，这次已经发展到尿毒症了。第一眼奶奶，奶奶就说：“奶奶不能再做饭给你吃了。”那一刻，我心如刀割。又是一个暑假，又是一个即将开始新的学习生活的时候。独自在家的那几天，真真切切地体会到了失落，寂寞和绝望。好在奶奶出院后，仍然坚持服用中药和西药，病情又有所好转，虽然已经很难恢复到以前那样了。

今年寒假回学校的时候，奶奶的身体已经大不如前了，只能勉强照顾自己。没想到，那一次的离开，竟成了永别。

四月份的时候，奶奶再次住院。这一次已经到了非常严重的地步了，医生已经没办法治疗了。这个情况，爸爸十天前才告诉我的。十多天来，爸爸妈妈，两个姑姑一直都陪着奶奶走过了最后这段路。最后一次跟奶奶说话是在一个多月前，听得出电话那边的声音已经很虚弱了，奶奶还一个劲地嘱咐我要多喝牛奶，保重身体。她以前很不注意保护自己的身体，现在得病了才知道了要教育我们好好保重身体。

原本可以利用两门考试间的5天时间回家的，可是爸爸一直都没让我回去。因为奶奶责怪爸爸把她病危的事情告诉我，并多次嘱咐一定不要让我回去，一定不能影响考试。

不敢想象暑假回家后是什么心情，从此家里就少了一个人了，再也看不到奶奶在门口等我回家，再也不能听到奶奶在楼下催我吃饭，再也不会看到奶奶从口袋里掏出花生和瓜子给我吃，再也不会听到奶奶唠唠叨叨不许我去踢球了……有的只是像那天去年夏天那样，独自一人留在家中。

爷爷奶奶那代人年轻的时候都受过苦，开河务农，年轻的时候就把身体都累坏了，到老了，大多数都会得个什么病的。到老了都是省吃俭用，自己什么都不舍得，宁可把好的留给下一代。在他们看来，自己苦点都没什么关系，只要子孙过的幸福就足够了。

不知道这个世界人死后是不是还有灵魂。如果有，希望以后的一切，奶奶在天上都可以看到。

Hello Android

2008-06-13T16:15:00.015+08:00

安装完了Android SDK，现在来开发个Hello World试试。不想用Eclipse这种重型的IDE，就使用Android提供的Python脚本和Ant来构建。

创建项目
Android提供了activityCreator.py这个Python脚本用来创建项目，运行：

activityCreator.py --out HelloAndroid com.android.hello.HelloAndroid

其中，--out HelloAndroid指定输出的目录， com.android.hello.HelloAndroid 指定继承了Activity的类。执行完如上命令后，将得到如下目录结构：

|--- HelloAndroid/
   |--- AndroidManifest.xml # Android应用程序的描述文件
   |--- bin/    # 存放编译打包后的二进制文件的地方
   |--- build.xml    # Ant脚本
   |--- res/    # 存放外部资源的地方
   |--- src/    # 存放源文件的地方

编译构建
在HelloAndroid目录下运行ant命令来编译构建项目。编译后，在src/com/android/hello下自动创建了R.java文件，这是保存一些resources信息的文件。同时，在bin目录下也生成了HelloAndroid.apk等文件，该文件包含了应用程序，是模拟器执行的对象。

部署运行
程序打包完之后需要部署到模拟器上才能运行。这里使用adb来部署。首先启动emulator，启动完成之后，运行如下命令来完成部署：

adb install bin/HelloAndroid.apk

部署完成之后，可以在模拟器中的所有程序中找到HelloAndroid，运行之即可。

删除程序
测试完成之后，可以从模拟器中删除HelloAndroid程序，这里使用adb shell来完成。首先还是保证emulator已经启动，然后依次运行如下命令来删除程序：

adb shell
cd data/app/
rm HelloAndroid.apk

发现adb shell是个好东西，就跟linux的shell程序一样，可以看到模拟器中的文件系统。

kubuntu下配置Android SDK

2008-06-11T23:32:00.006+08:00

Android不需要安装配置，就跟Eclipse一样，只要java环境配置好了，解压了就可以直接使用了。这里的配置只是在kubuntu中配置一下PATH，从而能够在任何目录下调用Android提供的工具。
1. 到下载页面下载Android SDK，解压下载到的zip文件。
2. 将解压后的目录移动到想要安装的地方，例如：

sudo mv android-sdk_* /opt/android

3. Android目录下的tools文件夹存放着常用的工具，将tools文件夹添加到PATH中。修改~/.bashrc文件，添加如下行：

export ANDROID_HOME=/opt/android
export PATH=$PATH:$ANDROID_HOME/tools

4. 重启console，输入emulator命令，如能运行Android的模拟器表明配置成功。

升级到kubuntu8.04

2008-04-27T11:39:00.005+08:00

期盼已久的8.04终于在24号发布了。原本想过一个星期，等源稳定了，再看看别人升级有没有什么问题，自己再更新的，因为一天到晚都要用电脑的，万一出个什么问题影响学习就不好了。结果今天早上起来再也忍不住了，就一咬牙开始升级了。

Kubuntu8.04有两个版本，一个是KDE3的，这个是官方支持的，另一个是KDE4的remix版，是由Kubuntu社区支持的，因为KDE4下的软件还不多，很多软件都在移植到KDE4下，所以要到8.10的时候官方才会使用KDE4。所以我还是选择了KDE3的版本。

升级过程是按照kubuntu.org上的upgrade方法进行。周末学院的网络果然不错，用的是上海交大的源，速度很快，平均速度应该在2M/s，不到十分钟就下好了更新软件包。升级过程也很顺利，除了报了几次x11-common，xorg的错误外，其他都是一次完成。这个问题我在升级后，更新了一下系统，就解决了。

总的来说，Kubuntu8.04没有太多令人兴奋的新特性，开关机速度还是差不多，界面上的边框和进度条之类的稍微美观了一点。到目前为止我发现的主要变化有：

新加入的文件浏览器Dolphin，觉得速度要比Konqueror快一些，界面也简洁许多，我很喜欢，现在就用这个了。
Firefox升级到了3 Beta 5，由于我用的本来就是英文版，所以没有遇到网友所说的无法显示简体中文的问题。但最大的问题是add-ons不兼容，tab mix plus，del.icio.us等还没有Firefox3的版本，幸好DownThemAll已经更新了，所以先凑合着用吧。
换上了WenQuanYi Zen Hei字体。在7.10的时候，我就尝试过正黑字体，但是对于小号字体，明显发虚，所以又删除了。在8.04下又试了一次，效果好很多了，虽然对于特别小的字体还是有发虚的现象，但是大多数情况下都很正常，字体也挺好看的，唯一不足的地方就是字体的锯齿还是有点明显。

有图为证：

Dolphin File Manager

Firefox 3 Beta 5

林荫道

2008-04-24T10:18:00.004+08:00

寝室的窗户正对着一条小路，道路不长，还不到20米，两边是两排并不粗壮的树，右边连着一片草坪。每天，我几乎都会无数次地转头看它。现在是春末夏初，两旁的树木已经变成翠绿，长出了繁茂的枝叶。绿色的草坪上也零星散落着点点黄花。大部分的时间，它都是静静地躺在那里。阳光，树影洒落其间。有时候，会有淡淡蝶影；有时候，微风吹过，地上的光影就会浮动；有时候，又会有三两人影徜徉其中。

一直想象着某个午后散步其间的感觉。鸟语花香，光影斑斓，一定可以听到时间在慢慢流淌的声音，一定可以嗅到幸福的气息。很多次都想亲身去体验一下，可是，我从来没有这样做。可能是因为忙于学习，可能是因为懒惰，可能是因为担心别人看到了，会觉得我傻兮兮的，于是我从来都没有去走过。我不知道如何跨出第一步，我怕它太短了，一会就走完了；我怕它的路面并不平坦，满是石子；我怕它的尽头并不如想象的美好；我怕我没有选对合适时机和天气，以致于无法体会它全部的美好；我怕走了两遍，三遍就会厌倦了……所以，我至今没有走过，尽管我仍如往常那样的向往。

或许有一天，我会因为需要去财务部交学费而经过那里；又或许等到了离开这个寝室的那一天，我依然还在憧憬，憧憬……

过了把戏瘾

2008-04-11T13:41:00.006+08:00

无聊的领导总会想出无聊的方法来浪费我们的学费和时间，继上次《素质教育》课要求我们每人写一个篇介绍文艺的报告后，这次又要求每个小组表演一段英语短剧。虽然很不情愿，但是既然不能避免，那就去享受吧。

听到英语短剧，第一时间进入我脑海的就是本科时Alley他们表演的《闻香识女人》（Scent of a Woman）中最后校长召开听证会的那一段。他们演绎得很到位，当时我就产生了自己也去表演一次的冲动。于是在我的强烈推荐之下，其他组员都同意了。

由于对剧情比较了解，我率先抢到了Slade这个角色，是由我非常喜欢的演员Al Pacino 出演的。Slade在剧中发表了三长段气势磅礴的演讲，批判校长和学校的所为。我能把他演一遍，就算只有Al Pacino 的五层，也已经非常过瘾了。这次表演主要以模仿为主。我把电影中的片段反复看了十几遍，学习他的吐词，动作和神态，要诀是一定要演出Slade那种激情澎湃的气势。跟组员排练了两次，今天中午就跑去表演了。

表演过程很顺利，每个人组员都发挥的很好。Gao中规中矩地表演了Headmaster，liangpi也把Charlie犹豫不绝的感觉表现了出来。Abalone演绎的George就更赞了，结合了很多小动作和表情，把人物当时说谎的心态都表现了出来，难怪下去之后有人夸他是演技派呢。我对自己的表现也很满意，觉得跟Al Pacino演绎的Slade还是有几分神似的。不管别人的评价如何，整个过程我还是很享受的，演完之后就觉得很过瘾。可惜没能把我们表演的场景拍下来阿。:(

以前从来没有演个戏，不知道是什么感觉。亲身体验之后，才知道要把任何一个角色演好都是很困难的，所以特别佩服那些优秀的演员。要演好，真的需要全身心的投入。

十渡春色

2008-04-03T16:40:00.011+08:00

早就计划着要出去春游了。四月的第一天，约了一伙同学去十渡玩了。去之前google了一下，据说十渡有“北方桂林”之称，有山有水，住农家小院，还能烧烤。于是满怀憧憬的踏上了旅途。

最破的火车
十渡是个小站，所以从北京西站出发，只有四位数字的火车才停，也就是那种又慢又脏的绿皮车。以前只是听说，现在居然要亲身体验这种绿皮车了。上车一看，果然名不虚传。地上很脏，椅子也是木板加海绵的那种，还有很多人抽烟，里面简直是乌烟瘴气，是我这么大坐过的最破的火车了。还好我们人多，又有座位。上车之后，就把准备好的零食铺开，边吃边打牌，三个小时居然很快过去了。

烧烤
下车之后就被接到七渡那边住的地方。大家都饿了，于是还没坐定我们就决定开始烧烤，先把下午买好的鸡翅等洗干净，再生炭。以前出去烧烤都是烤熟的香肠，鸡翅之类的，这次居然要烤生的，直到吃上第一个鸡翅为止，我都一直怀疑能不能烤熟。烤了半小时之后，洒上孜然，再涂点辣酱，味道居然跟店里面卖的差不多，又香又酥。之后，又点了几个农家菜，茶足饭饱之后，都快十一点了。

夜宿农院
我们所在的景区叫“孤山寨”。住的地方就在山脚下，晚饭后我们摸着黑爬上了农家小院。杀人杀到两点半就休息了。我睡靠窗的那个床，可能是武侠剧看多了，总担心“山寨”里会有人从窗户闯进来，又不敢盯着窗户看，害怕会突然有个黑影闪过。最后，还是在忐忑中入睡了。

孤山寨
平安的度过了一晚。早上睁开眼睛时，看到窗外阳光明媚，是个好天气，一整晚的恐惧顿时烟消云散了。今天的主要任务是爬山。原本以为这里会有青山，绿水，桃花，最后让我彻底的失望了。山上还是枯黄一片，山间也只能看到几条细流，桃树虽然开花了，但都是零零散散的分布在山上。当天的游客非常少，除了我们大概只有3，4队吧。走在山间，只能体会“荒凉”二字。走上山头眺望，看着远处绵延起伏的山岭，顿时领悟到南方和北方的山本就应该是不同的。南方的山上绿树成荫，呈现的是纤细的线条，给人悠远的感觉；而北方的却呈现粗犷的线条，给人气势磅礴的感觉。如果说南方的山用“秀丽”来形容的话，那么北方的山就应该是“壮丽”。

算命
回来的时候还是只能坐绿皮车。在过道里熬了几站后终于找到座位了。为了打发时间，rainy就用纸牌给我们“算命”玩。最常出现的词就是：“小人”、“贵人”、“情人”、“虽然”、“但是”、“总的来说”了。虽然大家都是带着娱乐的心态，但是最后算出来的结果居然还有某种逻辑关系，还能自圆其说，逗得我们哈哈大笑。

有图为证：

PS: 今天起床后惊奇的看到wikipedia和blogspot被解封的新闻，开始还以为是愚人节的礼物，试了一下果然可以了，希望这次不要又是短期的解封。

春风又绿江南岸

2008-03-26T09:06:00.003+08:00

桑下蚕，南归燕，鸭浴清水潭。桃花犹笑他日暖，杨柳拂面几时寒。杏雨纷纷，绿绦绵绵，篱外泥酥新草浅。春风又绿江南岸，明月何时邀我还？

春分已过，清明将至，现在的江南应该早已是一派“草长莺飞二月天，拂堤杨柳醉春烟”的景象了。冬去春来，江南的春天依然年复一年的归来。但是春天的江南已不能重复昨天的故事。

孩提时代每年春天必定要做的事情就是养蚕。初春的时候，小孩子都会把去年孵在旧报纸上的蚕卵放在贴身衣物里。于是，某个下午，跟小伙伴嬉戏回家后，惊奇的发现蚕卵已经孵化成很多“蚕宝宝”了。打开报纸，会有很多发丝粗细的黑黑的小东西在蠕动。拿一片羽毛很小心的把它们拂到旧皮鞋盒里，再放上几片桑叶，“蚕宝宝”就会自己爬上去啃噬起来。经过几次蜕皮，蚕的身体会变成白色，粗细如小指一般。这时候蚕的食量也猛增，甚至可以听到啃噬桑叶时的沙沙声。等到身体带有黄色，表明蚕要开始结茧了。把结好的茧摘下来，放在旧报纸上，等待数日，蚕就会破茧而出，这时候已经进化成蛾了。交配之后，蛾就会把卵产在旧报纸上，同时也结束了自己的生命。我则把旧报纸收起来，等待来年再孵。如今，随着农村的开发，已经很难看到桑树了，春天养蚕的小孩子应该几乎没有了。社会的进步带来了很多，却也带走了很多。

大地复苏，鸟儿也会从南方飞回来了。南归的燕子会在普通人家的屋檐下筑剿繁殖，等有了小燕子，叽叽喳喳之声就会不绝于耳。据说捣毁燕子窝是不吉利的，所以在农村，家家户户的屋檐下都可以看到燕子窝。不过近几年，这种现象已经很少见。不知道是燕子已经找到更好的地方乐不思蜀了，还是现在的人们已经不再友好了。

平常的午后，时常能遇上几场细雨。躲在屋檐底下，感受着缕缕拂面的春风，看着小草在雨水的浸润下愈发清脆透亮，听着细雨打在叶子上发出轻微的沙沙声。听雨固然悠闲，戏雨却更让人兴奋。还记得有一次在外婆家，跟哥哥在雨中奔跑跳跃，任凭雨丝沾湿发梢，雨水也与额上的汗水交融在一起，仿佛整个身体也与春的气息融合在一起。

今年3月，包哥选择了一个阳光明媚的日子订婚了。很可惜没能跟弟兄们一起喝他的订婚宴。再过半年就要结婚了，之后，一个接一个的也都要成家了。不知道以后还能不能如往常一样“酒逢知己千杯少”了。

春风又绿江南岸，明月何时邀我还。

朝花夕拾杯中酒

2008-02-26T09:25:00.002+08:00

庭前黄叶依旧，故人渐已白头。落花若随流水意，酌酒夜光相授。花前拈花花虽瘦，月下留月月更愁。凭栏独自等候，伊人知否？

五六岁的时候，妈妈经常会带我去她的厂里。这是一排坐落在马路边上的平房，办公室里只有两张写字台和几把椅子，庭前有一株很大的树，一到夏天，就会掉下米粒大小的果粒。有位20岁出头的叔叔常常会逗我玩，他还会变“魔术”。把庭前捡到的果粒放在一个玻璃杯中，再在玻璃杯中装满水，用一张纸片盖住杯口，把杯子倒过来，水居然不会流出来。对于幼小的我说这是多么神奇的一瞬间，以致20年后的我还依稀记得。今年寒假，妈妈说又遇到那个叔叔了，已经好多年没有见过了，现在他在一个村子里从事养殖业。回想这么多年的光阴，就在弹指间，周围的变化让人都来不及好好回味。那些白墙红瓦早已不在，那棵大树也早已消亡。20年，让儿童成长为青年，让青年变成了中年，让一个人从对成人世界自由自在生活的憧憬，变成了对孩提时代无忧无虑生活的怀念。不敢想象20年后，父母老去的模样。到了那个时候，也许再也不能在冬季清晨醒来时，让妈妈坐在床边谈心；也许再也不能在夏天慵懒的午后，和爸爸一起健身；也许再也不能在除夕上午，亲手给大门换上新的对联……也许到了那个时候，也只能感叹：寄蜉蝣于天地，渺沧海之一粟。

进入大学的第一个生日，好友送给我一对情侣杯，说是等我有了女朋友，可以把其中的一个送给她。我把它放在寝室的桌子上。每次放假回到学校后，我都会擦去上面的灰尘。直到大学毕业的时候，这对礼物依然没有拆封。离开学校的时候，行李太多不方便带走，就把它留在了寝室。不知道丢弃了这对杯子，意味着丢弃了长久以来的束缚，还是意味着永久丢弃了打开那道大门的钥匙？

一个很小的塑料杯子，还不到拳头那么大。装满水，在灯光下显现出晶莹剔透的感觉。对我来说，它除了装饰可能再没其他用途。这是一位朋友送给我的，有一段时间我们联系甚密。可是后来，就像她突然走进我的生活那样，她又突然的消失了，甚至音信全无。毕业离校时，不知道什么原因，我莫名其妙的把那杯子留在了寝室。于是，我把它弄丢了，这辈子再也找不回来了。

大三时买的一个陶瓷杯子，我一直用到现在。还有一个调羹，虽然两者不是来自同一包装，但是却配合的天衣无缝。从寝室生活到外出实习，从毕业暑假回家到北漂求学，它一直都在我的身边。无论是淡而无味的开水，还是热而新鲜的牛奶，我们都一起品尝。虽然也有很多次苦涩的咖啡，但是相信有一天，我一定会泡上一杯甜甜的蜂蜜。

那些日子－－写在“卡卡”生日之际

2008-01-06T00:00:00.000+08:00

“卡卡”生日快乐！是否还记得那些日子，我们：

一起奋斗

一起调侃“小囡”

一起欢呼

一起出去HIGH

一起失落

虽然现在天各一方，但是

朋友一生一起走

浦口往事(Once upon a time in Pukou)

2008-01-01T20:27:00.000+08:00

这一年，我大学毕业了，告别了生活了四年的浦口，告别了陪我一起走过四年激情燃烧的岁月的朋友和兄弟们，告别了留下无数回忆的南京。这一年，我重新出发了，迎来了研究生的生活，迎来了新的朋友，迎来了一个全新的开始。下一年，生活是否还会上演那些留在浦口的一幕幕往事？

07年的开端，留给我的印象只有忙碌，是的，忙碌得天昏地暗。一天连续10小时以上的编程，一直持续了20天，为的只是成功完成项目，安心的回家过年（结果大年初一在家还在改程序）。这是人生第一个具有商业用途的项目，虽然没有任何报酬，但是能够认识cyfdecyf，Vernkin，Jay，虎哥，还有后来的Taylor，却比任何物质回报都珍贵。之后我们又一起完成了新的项目，一直到我离开的那一刻。半年来，“大家一起写程序，发牢骚，聊天，开玩笑”（引自cyfdecyf日志），真的很开心，正是因为你们的陪伴，当大四好朋友都出去实习的时候，我一人留在浦口才没有觉得这么孤单。在浦口最后的日子也是跟你们一起渡过的，还记得临走时最后去的地方就是219了。相信我们一定能够再见面的，南京或者上海。当然，还有跟Vernkin的约定。

清明节回家给爷爷扫墓了。自从初三爷爷去世后，就从来没去扫过墓。尽管这次爸爸和奶奶都说不回家也没关系，但我还是坚持要回家，因为我知道这次再不去扫墓，可能以后就更没机会了。看着我上大学是爷爷最大的心愿。我考上了昆山最好的高中，考上了江苏最好的大学，现在又要去中国最好的大学了，可惜这一切爷爷都没能看到。

四月中旬，终于完成了对自己的承诺：在离开南京之前好好的玩一下景点。在兼职导游阿圆的陪伴下，游览了明孝陵和中山陵。在紫霞湖畔，我欣赏到了07年最美丽，最难忘的风景。要感谢阿圆的精心安排，这一天过的很开心。而这一天中最大事情却发生在吃晚饭时，在不经意谈论过去的事情时，居然引出很多震撼的事情。之后便直接导致了Susan的“烧桥事件”。在整个过程中，我一直认为自己所说所做的都是正确的，却不晓得伤了朋友的心，事后才觉得非常后悔。还记得当时对Susan说的：“我们认识这么多年了，怎么可能说不是朋友就不是朋友了！”现在还想告诉Susan：真正的朋友，是看透了你还能对你好的人。

五一之后，出去实习的同学也陆陆续续回来了，准备毕业设计。宿舍里，学院里似乎又变得热闹起来。我深知这是最后的时光了，所以珍惜每一次班级活动和团聚的机会。拍毕业照，毕业旅行，散伙饭，卖旧书，还有无数次的小型聚餐，都已成为我记忆中的亮点。有太多的名字需要罗列，有太多的地方需要怀念，有太多的故事需要回味。可是分开的时候，我并没有太多感伤，因为总觉得不是永远的分开，要见总能见的。现在才知道分开了，也没多少机会再相聚了。送别了每一个好友，直到Tony Chen离开的那个下午，我亲自关上了415的房门，也尘封了那一段激情燃烧的岁月。

还是因为项目，还是没有任何报酬，还是20多天，我还得留在软院。虽然经历了几次挣扎想要离开，但是最后还是决定留下来跟组员们一起“战斗”到最后。朋友都说我很傻，我只是想给老师一个交代，给组员们一个交代，给自己一个交代。

八月上旬一个很平常的上午，我静静的离开了南京。一下车就直接奔去医院了，因为在车上得知奶奶已经住院几天了，爸爸为了不让我担心所以一直都没告诉我。这一次的病情比以往更严重了，躺在病床上消瘦的奶奶，还一个劲地叫我不要担心，要照顾我自己。我真的很害怕就此失去奶奶。看着眉头紧锁的爸爸，真的想为他分担一点，为他出出主意，可是又帮不上什么忙。想象着要是自己遇到这种情况该怎么办，顿时觉得作为一家之长，作为一个男人真的很辛苦。

那段时间，整天都是一个人在家，自己做饭，自己吃饭，很多事情涌上心头，那种失落和孤独，我这辈子都不想再有第二次。幸运的是没过几天，奶奶病情有所好转，出院回家了。就像高考之后的那个暑假一样，每天给奶奶做饭、煎药，却十分珍惜那段日子。

后来，舅舅又因为出车祸要动手术。这几件事让我深深体会到生命的脆弱，所以也学会了珍惜每一天，珍惜每个人。

9月份开学了，终于来到了北大软件学院。刚开始的时候觉得还可以，可是渐渐的就发现很多不满的地方，学院更是被我们称为company，一个只想着怎么赚钱的地方。唯一值得满意的是我选择了一个很好的导师，他整天给我们灌输的东西让我的思想和认识有了很大的转变，或许他真的会改变我的一生。室友也很不错，乒乓争霸，等差数列般的上床时间，一项项的记录，都是生活中的经典。

这个学期，终于跟Abalone和Zell合作了一个项目，本来大二的时候就可以的，现在终于完成了这个迟到了3年的约会。而且我对项目的质量也很满意。

07年的最后一天居然还能见到迅翁，真不容易阿，可惜只有短短的一个多小时，下次再见面可真的不知道要到什么时候了。怀念以前跟你夜聊到5点的日子。

一觉醒来发现已经是08年了。生活，我们走着瞧吧。

Russell's Paradox

2007-12-10T15:54:00.000+08:00

Russell's Paradox是set theory中非常有名的悖论。

先来看一下set theory中一个有意思的集合：属于自己本身的集合，也就是说一个集合它包含了自己。例如，以所有集合为作用域来考虑，包含所有正方形的集合R，那么集合R并不包含自己，因为R是一个集合，而不是正方形。但是，取R的补集S，即所有非正方形的集合，那么S不是正方形，所以S是自己的一个元素，即S属于自己。可见，世界上存在很多这种包含自己本身的集合。

现在，令R为所有不属于自己的集合的集合（好绕阿！集合R中的元素也是集合），也就是说：

R ＝ {A | A不属于A}

那么，现在考虑R是否属于R。如果R属于R，那么这违背了R不属于自己的集合属性；如果R不属于R，那么根据集合R的属性，R应该是集合中的一个元素。这就是Russell's Paradox。

有一个与Russell's Paradox相关的理发师的故事。理发师在理发店前的牌子上写道：“我给镇上所有不给自己理发的人理发，而且我也只给这些人理发。”于是，有人问他：“那你自己怎么办呢？如果你不给自己理发，那么照你的说法就应该给自己理发；如果你给自己理发，那么你又不应该给自己理发，因为你只给不给自己理发的人理发。”理发师不知如何回答。

A cool proof of Pythagorean Theorem

2007-12-10T15:46:00.000+08:00

More proofs are here: Pythagorean Theorem and its many proofs.

《我们无处安放的青春》中的父爱

2007-12-08T17:31:00.000+08:00

昨天中午到今天下午，一口气把《我们无处安放的青春》全部看完了，确实是一部非常感人的片子。不过最感动我的并不是男女主角之间的爱情，而是周校长（陈道明饰）对女儿周蒙（江一燕饰）的父爱。

一开始，这是一个让人觉得非常严厉的父亲，管教女儿的穿着，行为，反对女儿谈恋爱。渐渐地，从反对到接受，又到鼓励，特别是对儿子的理解和对儿媳妇的忍让，又让人觉得这是一个通情达理的父亲。而得知自己得了绝症后，对女儿表现出来的无微不至的关怀和悉心教导，又体现出了这种父爱温柔的一面。在手术之前，他留给了女儿一份最重要的东西，就是教导女儿如何独自面对人生未来旅途的话语。虽然自周校长到了北京之后，剧中再也没有出现过他的画面，但是每当周蒙遇到挫折，意志消沉或感到孤单时都会响起他留下的那些鼓励的话语，让人觉得他始终都没有离开，更是让人潸然泪下。

REM moves forward

2007-12-04T21:40:00.000+08:00

ZK已经发布到3.0了，NetBeans也升级到6.0了。最近收到一些REM用户的邮件，希望REM能够升级到NetBeans 6.0，并且支持ZK2.5和3.0。由于半年来一直忙于其他事情，再加上对REM兴趣的减退，这个项目已经有7，8个月没有更新过了。

一个月前发布了一则help wanted，可惜没有回应。今天收到Fred的邮件，他是SUN的一个职员，有兴趣来接管REM。很高兴REM能够为ZK开发带来方便，也很高兴终于有人愿意来继续维持这个项目。于是很快把manager的权限给了Fred。他在回信中说已经把当前的版本做了一个tag，并做了一个port到NetBeans 6.0的branch，应该一整晚就可以完成了。

一直觉得REM是一个不错的项目，可惜一直没时间将她完善到我预想的那样。希望Fred接管后可以让REM更加完善，给ZK开发者带来更多便利。

第一篇日志：小虫高飞

2007-11-25T22:08:00.000+08:00

这是在itput上翻出来的一篇日志，是我2年前写的，题目为“小虫高飞”，这应该是我写的第一篇日志。时光荏苒，当时的小虫现在已经长大了，可是依然在寻找一篇能让自己高飞的天空。或许种种挫折和变化都是为了指引小虫飞向那片更广阔的天空。最初认为只要努力了就一定会成功。后来从愤怒到无奈。现在相信，只要努力了，付出了，就算没能取得成功，也没什么可惜的了，毕竟“谋事在人，成事在天”。

不知道是命中注定还是机缘巧合，抑或是一时冲动，在高考成绩出来后的第二天，我就迷迷糊糊的签订了以软件为专业的合同。计算机，这是一个我未曾也从未想要染指的行业，可是，这将成为我今后四年学习的主要方向，甚至是我一辈子赖以生存的行业。在计算机科学这座大山面前，我只能算一只渺小的小虫，我甚至连WINDOWS的基本操作都不是很熟练。我所能安慰自己的是从头学习一项技术所具有的挑战性。
时光匆匆，如今我已经度过了2年的大学生活，转眼即将步入大三。虽然我没有能够如愿成为高手，但相比两年前我已经有了巨大的进步。两年来那么多基础课的学习，已使我窥探到软件殿堂神圣的一角，我才开始对她有些许的了解。也许只有当你了解了一件事物，你才能真正体会他的高深莫测。之于软件工程的博大精深，我充其量只是一个懵懂的孩子，有很多学问待我去思索研究。软件开发不是结果，而是一个过程，一个不断更新完善的过程，这需要一辈子或是几代人的共同努力。就一门JAVA就需要用一生去阅读。
JAVA是我接触的第二门高级语言，不知道为什么，我对他情有独钟，也许就像他的图标一样，值得人们去反复的品味和阅读。人生在世，不是为了走向死亡这个终点，而是为了享受和体会生活的乐趣。我会用我的一生去品读JAVA，品味人生。希望在这里能够记录我成长的点点滴滴。
昔日的小虫正在吸取大自然的甘露，不断的蜕化成长。相信通过艰苦的努力，小虫定会有高飞了一天。

kubuntu7.10下配置texlive + CJK + UTF-8中文环境

2007-11-25T21:29:00.000+08:00

首先要感谢Yufei告诉并帮助我配置了支持UTF-8编码的中文环境。本文在“kubuntu7.10下配置latex中文环境”的基础上进行了些修改。
1. 安装texlive和cjk-latex的方法不再多说，如下：

sudo apt-get install texlive
sudo apt-get install cjk-latex

2. 在home目录下创建目录.texmf，修改/etc/texmf/texmf.cnf，设置TEXMFHOME的值，如TEXMFHOME = $HOME/.texmf。

mkdir .texmf
sudo vi /etc/texmf/texmf.cnf
#设置TEXMFHOME = $HOME/.texmf，保存退出

（TEXMEFHOME的默认路径是$HOME/texmf，如果在home目录下创建texmf，则无需修改texmf.cnf文件）
3. 在$HOME/texmf下创建zh_CN目录，并将windows（C:/WINDOWS/Fonts/）下的字体文件（SIM*,sim*）拷贝到zh_CN目录下。字体文件可以存放在任意位置。
4. 下载mkutf8cjkfonts.txt文件，修改起后缀名为sh，并使用如下命令转换字体格式为UTF-8支持的字体（此脚本需要用到程序ttf2pt1，使用apt-get安装即可）：

sh mkutf8cjkfonts.sh zh_CN/SIMLI.TTF li li
sh mkutf8cjkfonts.sh zh_CN/SIMYOU.TTF you you
sh mkutf8cjkfonts.sh zh_CN/simsun.ttc song song
sh mkutf8cjkfonts.sh zh_CN/simfang.ttf fang fang
sh mkutf8cjkfonts.sh zh_CN/simkai.ttf kai kai
sh mkutf8cjkfonts.sh zh_CN/simhei.ttf hei hei
mktexlsr

5. 让latex识别安装的字体：

sudo vi /var/lib/texmf/web2c/updmap.cfg
#在末尾添加Map cjk.map，保存退出
sudo texhash
sudo updmap

6. 最后，编写hello.tex来测试是否配置成功，内容如下：

\documentclass{article}
\usepackage{CJKutf8}

\begin{document}
\begin{CJK}{UTF8}{song}
你好
\end{CJK}
\end{document}

一定要usepackage{CJKutf8},并且在CJK环境中指定使用UTF8编码。生成pdf文件：

pdflatex hello.tex

打开hello.pdf，如果显示正常，表明配置成功。

无法忍受MSN邮箱了

2007-11-22T12:31:00.000+08:00

不知道是网络的原因还是msn邮箱的原因，自从msn的邮箱变成windows live之后速度就一直非常慢，查看一个邮件半天都刷不出来。因为我的Firefox是2.0的，只能使用Live的经典版，每次登录后显示的第一个页面只能看到有多少新邮件，而看不到具体的邮件列表，页面的主要部分都用来显示广告了。需要点击“收件箱”才能看到邮件列表，而这一步通常又非常慢。真的无法忍受了，还是gmail好，速度快，用户体验又好。以后就尽量多用diego003 at gmail.com这个邮箱吧，那个msn的邮箱用了这么久，放弃它还真有点舍不得。

保护环境从身边做起

2007-11-16T13:50:00.000+08:00

今天上英语课的时候受到了一次震撼。Carol拿出她的布做的bag，说这袋子她已经用了十几年，她去超市都是用这个bag的。她很hate塑料袋，因为塑料袋对环境污染很严重。这么说她从十几年前就有了保护环境的意识，并且切实做了十几年。一个60多岁的老太太，在我看来，能如此重视环保真的很不容易，这或许跟她在美国从小接受的教育有关吧。

其实“环境”这个概念对于我们大学生来说再熟悉不过，说到白色污染，它的危害人人都能说上一大把。但是在现实生活中，又有多少人能在做事情的时候真正考虑到环保的？

我自己就从来没做到过，或许这就是中国人一个普遍的缺点，说起来一大套，却没有实际行动。我决定从明天开始用实际行动进行环保，到外面买饭不拿木制的一次性筷子，去超市尽量不拿塑料袋……虽然这些都是小事，但是我相信人人从身边小事开始，只需要改变一点点，环境就会有很大的改善。

使用rubygems安装rails

2007-11-14T14:36:00.006+08:00

以前一直是使用sudo apt-get install rails来安装rails的，最近下载了redmine的源代码，想在自己机子上配置使用，但是在使用rake db:migrate创建数据库的时候报出require 'action_web_service'的错误，查了一下怀疑是安装rails的时候没有安装actionwebservice包的缘故，于是决定使用rubygems重新一下rails。使用sudo apt-get install rubygems虽然提示需要下载相应的安装包，但是下载时只有404错误。查了一下，听说ubuntu是不提供rubygems的apt-get安装的，原因好像是为了防止冲突。只能自己下载rubygems的包安装。把rubygems和rails都安装完后，再次配置redmine，一次就成功了。以此确定是因为用apt-get安装rails的问题，所以还是建议使用rubygems来安装rails，毕竟这是官方推荐的安装方式。现在把安装步骤写下来。
使用apt-get安装ruby的方法跟平常一样，在此不再赘述。首先从http://rubyforge.org/projects/rubygems/下载rubygems的安装包，当前最新版本是0.9.4。

$ tar xzvf rubygems-0.9.4.tgz
$ cd rubygems-0.9.4
$ sudo ruby setup.rb
$ sudo gem update --system

使用如上命令安装并更新rubygems。然后使用如下命令来安装rails及其依赖：

$ sudo gem install rails -y

会依次显示安装了actioncontroller，activerecord等包，正常退出则说明安装成功了，可以运行一下rails命令来测试一下。

workshop的提议

2007-11-07T16:01:00.000+08:00

今天下午在寝室里谈论《Internet高级编程》作业的时候，abalone提出了一个创意：以后在我们寝室内部，每个人轮流介绍一个话题，可以是自己特别熟悉的，也可以是比较感兴趣的，也可以是最近在研究的比较新的，内容可以涵盖技术或技术以外的任何方面，目的是传播知识，增进交流。以前abalone在公司有过类似的活动。我们可以定期开展，比如每个周五。我听了觉得很好，而且我们可以先在内部实行，以后可以邀请更多的人一起来参加，这样会更有意思。时间长了，甚至还可以办成BarCamp的形式。
说干就干，虽然近期学习比较忙，但还是定在下个周五晚上开始第一次。这次我先来，准备介绍一下latex。哈哈，要好好准备一下。

英文locale使用SCIM拼音输入法

2007-10-29T01:05:00.000+08:00

本文介绍在kubuntu的英文locale下如何安装配置SCIM输入法。
首先，使用如下命令安装SCIM输入法及相关组件：

sudo apt-get install scim scim-modules-socket scim-pinyin scim-gtk2-immodule im-switch libapt-pkg-perl

然后配置在英文locale下使用SCIM，在home目录下执行：

mkdir .xinput.d
ln -s /etc/X11/xinit/xinput.d/scim en_US

完成之后重启XWindow即可使用SCIM了。

前两天不知道为何，SCIM的拼音输入法莫名其妙丢失了，在网上搜了一下，可能是拼音字库损坏了，只需删除.scim/pinyin目录即可，在home目录下执行：

rm -r .scim/pinyin

kubuntu7.10下配置latex中文环境

2007-10-23T20:38:00.000+08:00

之前已经安装好了latex，现在对其进行配置，使latex支持中文。
1. 为了支持中文，需要安装cjk-latex包，使用命令：

sudo apt-get install cjk-latex

2. 在home目录下创建目录.texmf，修改/etc/texmf/texmf.cnf，设置TEXMFHOME的值，如TEXMFHOME = $HOME/.texmf。

mkdir .texmf
sudo vi /etc/texmf/texmf.cnf
#设置TEXMFHOME = $HOME/.texmf，保存退出

（TEXMEFHOME的默认路径是$HOME/texmf，如果在home目录下创建texmf，则无需修改texmf.cnf文件）
3. 在$HOME/texmf下创建zh_CN目录，并将windows（C:/WINDOWS/Fonts/）下的字体文件（SIM*,sim*）拷贝到zh_CN目录下。字体文件可以存放在任意位置。
4. 下载gbkfonts文件，并使用如下命令转换字体格式：

./gbkfonts zh_CN/SIMLI.TTF li
./gbkfonts zh_CN/SIMYOU.TTF you
./gbkfonts zh_CN/simsun.ttc song
./gbkfonts zh_CN/simfang.ttf fang
./gbkfonts zh_CN/simkai.ttf kai
./gbkfonts zh_CN/simhei.ttf hei
mktexlsr

5. 让latex识别安装的字体：

sudo vi /var/lib/texmf/web2c/updmap.cfg
#在末尾添加Map cjk.map，保存退出
sudo texhash
sudo updmap

6. 最后，编写hello.tex来测试是否配置成功，内容如下：

\documentclass{article}
\usepackage{CJK}

\begin{document}
\begin{CJK}{GBK}{song}
你好
\end{CJK}
\end{document}

一定要将文件保存为GBK编码，latex不支持UTF-8编码的中文字符。生成pdf文件：

pdflatex hello.tex

打开hello.pdf，如果显示正常，表明配置成功。

REST on Rails的教程

2007-10-23T17:51:00.000+08:00

在网上找到的两篇不错的REST on Rails的教程：

安装latex

2007-10-22T22:12:00.000+08:00

在kubuntu7.10下安装latex套件。使用命令：

sudo apt-get install tetex-bin tetex-base

来安装latex相关的套件。执行如上命令后会提示还需要安装其他一些包，例如与texlive相关的包，选择yes，并完成安装。
运行一个helloworld来测试是否安装成功。创建文件hello.tex，内容如下：

\documentclass{article}

\begin{document}
Hello World!
\end{document}

然后执行：

pdflatex hello.tex

此时会生成hello.aux，hello.log，hello.pdf等文件，打开hello.pdf，如显示正常，表明安装成功。

升级到kubuntu7.10

2007-10-22T00:05:00.000+08:00

kubuntu7.10已经发布了4天，今天终于把我的系统从7.06升级到了7.10。据说sudo apt-get dist-upgrade不能保证成功升级，应该使用

sudo apt-get install update-manager-core
sudo do-release-upgrade

升级到最后的时候，报了几个跟tetex相关的错误，是latex引起的。重启之后发现两个重要的问题，一个是使用beryl或compiz窗口管理器时，窗口的边框无法显示，最近一直嫌beryl把我的机器托慢了，所以干脆就删除了beryl的相关组件，只用kwin窗口管理器。第二个是kopete无法登录，每次都是报crashed的错误。下载了kdelibs4c2a_3.5.8-0ubuntu3_i386.deb（对于amd64使用kdelibs4c2a_3.5.8-0ubuntu2_amd64.deb）fix package，使用

sudo dpkg -i kdelibs4c2a_3.5.8-0ubuntu3_i385.deb

安装后kopete就正常了。
现在还没发现别的问题，感觉速度好像更快了，而且窗口的色调比以前更亮，不过好像没有特别令人兴奋的改变。

轻描淡写

Domain name changed

Lazy CEK Machine

CEK Machine

CK Machine

CC and SCC Machine

Textual Machine

Recursion and Y Combinator

Eager and Lazy Evaluation

Solving Partially Reduced Problem

Constants and Builtin Functions

A Simple Lambda Calculus Evaluator - Extended

A Simple Lambda Calculus Evaluator - III

A Simple Lambda Calculus Evaluator - II

A Simple Lambda Calculus Evaluator - I

北京城惜别故友 杭州市初遇新知

实习结束

Tiny Extension to Ruby YAML

谈谈课程评分

踏雪

青春一梦牡丹亭

新域名

找工作那些事儿

使用GAppProxy翻墙

我还活着

古文观止

推迟毕业

离职

kubuntu下使用openvpn访问blogspot

不吐不快

使用Git管理简历

自愚自乐

学佛三书

Find back Plasma in KDE 4.2.1

主角与配角

花入泥

踢球分组中的概率

牛年第一场雪

Personal Wiki

兰亭风花

Liar Paradox and Halting Problem

Understanding Scope

惊魂一刻

立冬苦吟

下车

我是灾星

萧萧秋叶诉离愁

知足

You will never smoke alone

我爱你爱 之 党员liangpi

逝

Hello Android

kubuntu下配置Android SDK

升级到kubuntu8.04

林荫道

过了把戏瘾

十渡春色

春风又绿江南岸

朝花夕拾杯中酒

那些日子－－写在“卡卡”生日之际

浦口往事(Once upon a time in Pukou)

Russell's Paradox

A cool proof of Pythagorean Theorem

《我们无处安放的青春》中的父爱

REM moves forward

第一篇日志：小虫高飞

kubuntu7.10下配置texlive + CJK + UTF-8中文环境

无法忍受MSN邮箱了

保护环境从身边做起

使用rubygems安装rails

workshop的提议

英文locale使用SCIM拼音输入法

kubuntu7.10下配置latex中文环境

REST on Rails的教程

安装latex

升级到kubuntu7.10

北京城惜别故友杭州市初遇新知

我爱你爱之党员liangpi