About
RSS

Bit Focus


C++ inline 坑爹真相

    准备两个文件 a.cpp b.cpp, 内容如下
/* a.cpp */

#include <iostream>

void b();

inline void echo()
{
    std::cout << 0 << std::endl;
}

int main()
{
    echo();
    b();
    return 0;
}

/* b.cpp */

#include <iostream>

inline void echo()
{
    std::cout << 1 << std::endl;
}

void b()
{
    echo();
}
    然后执行
$ c++ a.cpp b.cpp -o a.out && ./a.out
    也许会出现两个 0, 或者两个 1, 但是不会出现 0 1 这样的组合, 更不会链接冲突了. 如果有任何跳过生成目标文件直接到生成可执行文件的顾虑, 尝试下面的方法结果是一样的
$ c++ -c a.cpp
$ c++ -c b.cpp
$ c++ -o a.out a.o b.o
$ ./a.out
    甚至最直接地, 如果查看两个中间文件的符号
$ nm a.o
$ nm b.o
    会在两次结果中都看到一条名为 _Z4echov 的记录, 这就是 echo 函数被 name-mangling 之后的标识.

    C++ 文档和标准中过度赞扬 inline 这个关键字, 然而一笔带过的是, 编译器可以选择忽略 inline 标记, 至于忽略了会有什么后果, 如何链接等细节都一字不提. 如果这是一个封装行非常良好的编译器特性, 那也就没什么. 但实际上这里敷衍了一些重要事实, 既然 0) 有的函数即使程序员写了 inline, 编译器可以不进行 inline, 则 1) 很有可能出现这样的函数, 并在编译后被生成到目标文件中去, 而且 2) 由于 inline 函数一般实现在头文件中, 那么 3) 编译器在编译每一个包含了这个头文件的 cpp 文件时, 都会将该函数符号生成到对应目标文件中去, 而若要 4) 链接这多个目标文件不发生链接冲突, 只好由 5) 编译器或者链接器耍一些手段来保证, 可是 6) 耍了手段, 却有可能造成上面的问题发生.

    与 inline 失败的函数有关的真相是, 编译器会为 inline 函数做上标记, 链接器根据这个标记, 从目标文件中找到这个函数的多处实现, 不负任何责任地选取其中一个作为正身, 并抛弃其它的实现, 无论这些实现是否相同 (链接器也无从判断是否相同).
    开头的例子非常猎奇, 但是也不排除这样日常的情况: 0) lib 作者因为各种原因, 让 inline 失败的函数编入 lib; 1) 这个函数没有在文档中被提及, 头文件也隐藏得很好; 2) 引用 lib 的程序员定义了一个同 namespace 且同名的 inline 函数 (当然最有可能在全局名字空间这么干了). 于是就悲催了.

    现在再回头看一下 inline 的描述
  • 要想 inline, 得先 inline
  • 若是 inline, 未必 inline
    这是不是有种在看葵花宝典开头的感觉?

Permanent Link: /p/379 Load full text

Post tags:

 inline
 C++

ArchLinux 64 位重装记

    本本上一直是 Win7 Home 和 32 位 ArchLinux (下称 arch) 双系统. 不过, 吐槽一下, Win7 跟 WinXP 之间巨大的操作差异让我真心戒掉了 Windows, 就像 Gnome3 的巨大变化让我转投了 Xfce 一样. 另, 要与时代接轨 (虽然刚才好像我对新东西都很抵触) 想尝试一下 64 位系统, 所以决定: wipe out & reintall. 这里记录一下自己重装的过程, 让以后的折腾有所参考.

前期准备

    其实最重要的就是前期准备了. 准备好了后面装系统改配置都是轻松加愉快啊.

备份配置

    备份必要的配置文件当然是必须的.
    首先告诉大家一个好消息, 最让人纠结的 xorg.conf (一般放在 /etc/X11/xorg.conf) 不需要. 貌似现在 arch 启动 X 并不需要这个文件了 :D
    如 pacman.conf 这样的文件可以备份一下, 我实在不太记得住 archlinuxfr 的网址. 此外, arch 现在还启动了 multilib 计划, 可以把下面这个加入 pacman.conf
[multilib]
Include = /etc/pacman.d/mirrorlist
    其它的还有 /etc/locale.gen 以及 /etc/host* 这些文件.
    如果有修改 /etc/bash_aliases 或 /etc/vimrc 等等, 不过这些一般也没谁去改吧, 盯好自己的 ~/.bashrc ~/.bash_profile ~/.vimrc 就好了.
    如果你跟我一样使用 compiz 来卖萌, 记得可以使用 ccsm 将 compiz 的设置导出到文件哦.
    个人目录下其它值得备份的文件还有 .bash_history .fonts .mplayer 等等, 看各自的需求了.
    当然别忘了其它重要的文件比如小电影什么的.

已安装的软件包

    接下来一件比较重要的事情就是看看系统现在装着哪些软件, 装好新系统后立刻把它们都装上, 在 arch 下通过
$ pacman -Q
来查询安装的所有软件, 包括 aur. 导出这个列表
$ pacman -Q | awk 'BEGIN { print "echo -n \"pacman\" -S"} { print "echo -n \" " $1 "\"" }' | sh > install-packages
    最后, 准备安装镜像.
    再看一眼旧的系统, 马上就要说再见了哦.

安装

    用 ArchLinux 安装镜像启动后, 会进入这样一个 shell 交互环境
root@archiso ~ #
之后就是全手动安装了. 这么坑的设定, 萌生退意也是理所当然的了...

格式化磁盘

    如果没有必要重新格式化磁盘, 请跳过这个步骤.
    首先要搞清楚硬盘在挂在哪个地方, 一般是 /dev/sda, 使用 U 盘安装的用户将还会看到 /dev/sdb, 或者 sda 是 U 盘而 sdb 才是磁盘. 对应地请小心行事, 不要误删数据了.
    如果不想退的话, 先从格式化分区开始吧. 下面是用 parted 进行分区 (以在 /dev/sda 上安装为例, 高亮的部分是输入, 其它是 shell 或 parted 回显)

Permanent Link: /p/376 Load full text

Post tags:

 ArchLinux

Google & Baidu 图片识别搜索测评之二次元

Permanent Link: /p/368 Load full text

Post tags:

C++ 对象构造时的异常与 RAII 的救赎

    在上一篇文章中简单介绍了一下 RAII 的原理, 举了个读文件的例子. 这个例子稍微单薄了一些, 它只封装了一个需要 RAII 机制管理的资源 (FILE*). 软件工程中流行的观念是, 不具备扩展性, 经不起追加功能的东西注定会悲剧. 现在假如需要给这货增加个缓冲区, 也许这样是可以的
struct File {
    File(char const* filename, int buffer_size)
        : file(fopen(filename, "r"))
        , buffer(new char[buffer_size])
    {
        if (NULL == file) {
            throw std::runtime_error(std::string("fail to open ") + filename);
        }
    }

    ~File()
    {
        fclose(file);
        delete[] buffer;
    }
private:
    FILE* file;
    char* buffer;

/* other members */
};
    在 buffer 分配失败时, 一般会抛出 std::bad_alloc.
    这个类型的破绽相当多, 稍不注意就有可能漏资源. 首先是刚刚提到的 buffer 分配失败抛异常, 那么假如这个时候 file 已经打开成功了, 它会被关闭么? 其次, 假设 buffer 成功分配, 但这时 file 打开失败, 那么 buffer 是否会被释放呢?
    很不幸的, 两者的答案都是. 还是那句话, 因为 File 的构造函数没有走完, 这时抛出异常, 那么析构函数不会被执行. 因此, 不要尝试构造控制多于一个资源的类型. 而遇到这种需求, 应该拆分资源, 然后将这些单元类型进行聚合, 如
struct File {
    explicit File(char const* filename)
        : file(fopen(filename, "r"))
    {
        if (NULL == file) {
            throw std::runtime_error(std::string("fail to open ") + filename);
        }
    }

    ~File()
    {
        fclose(file);
    }
private:
    FILE* file;

/* other members */
};

struct Buffer {
    explicit Buffer(int buffer_size)
        : buffer(new char[buffer_size])
    {}

    ~Buffer()
    {
        delete[] buffer;
    }
private:
    char* buffer;

/* other members */
};

struct BufferedFile {
    BufferedFile(char const* filename, int buffer_size)
        : file(filename)
        , buffer(buffer_size)
    {}

    File file;
    Buffer buffer;

/* other members */
};

Permanent Link: /p/363 Load full text

Post tags:

 RAII
 Exception Handling
 C++

从 Python 的 with 到 RAII

    在上一篇文章中提到了 Python 的 with 结构, 其背后的思想正是 RAII. 在 C++ 中, RAII 的样子看起来跟 Python 中的会非常不一样, 还是以打开读取文件为例子
#include <cstdio>
#include <stdexcept>
#include <iostream>

struct File {
    explicit File(char const* filename)
        : f(fopen(filename, "r"))
    {
        if (NULL == f) {
            throw std::runtime_error(std::string("fail to open ") + filename);
        }
    }

    std::string readLine()
    {
        char buffer[256] = { 0 }; // just for demo
        if (NULL == fgets(buffer, 256, f)) {
            if (!feof(f)) {
                throw std::runtime_error("error occurs while reading file");
            }
            throw std::out_of_range("end of file")
        }
        return buffer;
    }

    ~File()
    {
        fclose(f);
    }
private:
    FILE* const f;
};

int main()
{
    try {
        File file("litsu");
        while (true) {
            std::cout << file.readLine();
        }
    } catch (std::runtime_error e) {
        std::cerr << e.what() << std::endl;
    } catch (std::out_of_range) {}
    return 0;
}
    注意看 try 块中间的语句, 看起来流程很清晰, 完全不像 Python 里面那样, 还要弄个 with 块, 多一级缩进. 都说 C++ 代码没 Python 的精神, 然而在这种小地方 C++ 反而超过了 Python 呢.

    其实, Python 的 with 块更像个语法糖, 上篇文章中有提到, 双层 try 在 Python 中能等效地解决这个问题, 只是看起来丑很多. 这个问题的根本在于, Python 这样不具备 RAII 特性的语言没能处理好对象从不可用状态切换到可用状态的状态过渡. 回顾一下双层 try 结构的处理方式
def readFile():
    try:
        f = open('sawako', 'r')
        pass
        try:
            process(f.readlines())
        except:
            print 'error occurs while reading file'
        finally:
            f.close()
    except:
        print 'error occurs while reading file'

Permanent Link: /p/358 Load full text

Post tags:

 Exception Handling
 C++
 RAII
 Python

码中萌

Source

Qt

Q_Q
Q_D
这两个真的是 Qt 中定义的宏来的.

C

int V = 0, _ = 1, U = 2, o = 3;
int ___ = , l_l = 0;
assert('_');
assert(V^_^V);
assert(-_-U);
assert((o, o));
assert(U>_<U);

assert((
___,  ___
 |  _  |  U
 | l_l |  o
));

Lisp

(define < 0)
(define o 0)
(> o <)

注释

HTML

<!--...-->

Shell 注释

#= o=

C

/* _ */

Permanent Link: /p/349 Load full text

Post tags:

 C
 Shell
 Lisp
 ASCII Art
 Qt

Python: try finally with 简介

    用 Python 做一件很平常的事情: 打开文件, 逐行读入, 最后关掉文件; 进一步的需求是, 这也许是程序中一个可选的功能, 如果有任何问题, 比如文件无法打开, 或是读取出错, 那么在函数内需要捕获所有异常, 输出一行警告并退出. 代码可能一开始看起来是这样的
def read_file():
    try:
        f = open('yui', 'r')
        print ''.join(f.readlines())
    except:
        print 'error occurs while reading file'
    finally:
        f.close()
    不过这显然无法运作, 因为 f 是在 try 块中定义的, 而在 finally 中无法引用.

    如果将 f 提取到 try 块外部, 如
def read_file():
    f = open('azusa', 'r')
    try:
        print ''.join(f.readlines())
    except:
        print 'error occurs while reading file'
    finally:
        f.close()
那么, 问题在于当打开文件失败, 抛出异常将不会被捕获.

    挫一点的方法自然是, 再套一层 try
def read_file():
    try:
        f = open('sawako', 'r')
        try:
            print ''.join(f.readlines())
        except:
            print 'error occurs while reading file'
        finally:
            f.close()
    except:
        print 'error occurs while reading file'
    当然这不仅仅是多一层缩进挫了, 连警告输出都白白多一次呢.

    正规一点的方式是, 使用 Python 引入的 with 结构来解决, 如
def readFile():
    try:
        with open('mio', 'r') as f:
            print ''.join(f.readlines())
    except:
        print 'error occurs while reading file'
    当文件打开失败时, 异常自然会被 except 到; 否则, 在 with 块结束之后, 打开的文件将自动关闭.

    除了打开文件, 还有其它这样可以用于 with 的东西么? 或者说, 怎么自定义一个什么东西, 让它能用于 with 呢?
    直接回答后一个问题吧, 秘密在于 Python 虚拟机在 with 块退出时会去寻找对象的 __exit__ 方法并调用它, 把释放资源的动作放在这个 __exit__ 函数中就可以了; 另外, 对象还需要一个 __enter__ 函数, 当进入 with 块时, 这个函数被调用, 而它的返回值将作为 as 后引用的值. 一个简单的例子是

Permanent Link: /p/328 Load full text

Post tags:

 Exception Handling
 Python
 RAII

Permanent Link: /p/318 Load full text

Post tags:

 Story
 Tian-jing-sha

Python 中函数交叉引用中的问题与解决方法

    Python (下面的讨论都是基于 2.7 版本的) 中, 先定义的函数可以调用后定义的函数, 比如下面这段代码
def first():
    return second()

def second():
    return 0

x = first()
    不过, 这种调用是有局限性的, 稍作修改为下面这个样子
def first():
    return second()

x = first()

def second():
    return 0
就会产生符号错误, 解释器给出的信息是符号 second 不存在.

    Python 作为一门解释型语言, 出现这样的事情很有可能是这样的原因, 假设现在正在交互模式下执行, 那么输入
def first():
    return second()

x = first()
到此为止, second 这个符号确实还没有被定义, 故产生错误. 但是如果上述代码内容是写在文件里的, 那么 Python 完全可以扫描整个文件以获得充分的上下文信息, 并正确地检测出 second 函数定义, 只是 Python 没有这么做.

    熟悉 C++ 的同学这时候肯定跳出来了, 因为在 C++ 类空间中, 这种引用是合法的, 如
struct type {
    int first()
    {
        return second();
    }

    type()
        : x(first())
    {}

    int second()
    {
        return 0;
    }

    int x;
};
不过, C++ 这种事情其实极其危险的, 比如下面这一段代码
struct type {
    int first()
    {
        return second();
    }

    type()
        : x(first())
    {}

    int second()
    {
        return x;
    }

    int x;
};
这实际上使用了还处于量子态的 x 来初始化它自身, 虽然这样的代码只有手贱的程序员在极其罕见的情况下才会写出这样的代码 (比如我在写这篇博客的时候), 但是本着编译器的职责, 完全应该想方设法让这种情况编不过去.

    好了, 还是先回到 Python 上来, Python 不允许这样的代码编译过去, 是因为这个原因么? 假设有下面的程序成功被解释执行
def first():
    return second()

x = first()

def second():
    return x

Permanent Link: /p/314 Load full text

Post tags:

 Compiler Construction
 Python
 C++

C++ 2011 中调用对象的 Rvalue Reference 成员函数重载

    之前提到的 rvalue reference 还有一点没有结算, 其实本来早就想写完它, 但是尝试了很久, 最后到 stackoverflow 上问来问去才最终解决, 那就是当某个对象是 rvalue 时, 怎么调用 rvalue 的成员函数重载.
    之前在有关 rvalue 函数重载的讨论中说到参数是 rvalue 的情况, 很自然地, 如果认为 (简单起见, 非 virtual 的) 对象成员函数等价于普通函数加上一个 this 参数, 那么如何分辨 this 参数是 left value 还是 rvalue 呢? 受到对象成员函数可以根据 const 修饰与否来重载这个现状的启发, 对于对象本身是 rvalue 的重载当然很可能是为成员函数加上某种修饰, 类似下面这个样子
struct Type {
    void func();                     // for normal left reference
    void func() const;               // for const left reference
    void func() rvalue-qualified-id; // for rvalue reference
};
    想法当然好, 而且确实有这么一回事, 只是标准敢正常一点么? 下面上真实代码, 这段代码目前似乎只能在 clang++ (我试验的版本是 2.9) 上编译通过
#include <cstdio>

struct Type {
    Type() {}

    void func() &
    {
        puts("a");
    }

    void func() const&
    {
        puts("b");
    }

    void func() &&
    {
        puts("c");
    }
};

int main()
{
    Type a;
    a.func();

    Type const b;
    b.func();

    Type().func();

    return 0;
}
    输出是
a
b
c
    前两个函数重载看起来很怪异? 原因是, 如果成员函数重载中只要有一个函数是给 rvalue 用的 (也就是函数后面有 && 修饰), 那么其它重载也必须标注上一个 & 号. 读的时候去掉前两个重载的 & 就很容易看明白了. 而最后一个重载正是给 rvalue 用的. 这样变态地使用符号, 看来标准委员会看来是毫不介意 C++ 逐渐演化成既不表意又不象形的新世纪面向对象强化版 Brainfuck. 真的在代码中写这种东西的死 coder 是伤不起的!

Permanent Link: /p/303 Load full text

Post tags:

 C++
 Function Overload
 Right Reference
 C++11
 Left Value

C++ Howto: 在栈上构造一个对象

    C++ 2011 标准引入的各种符号让我感到 C++ 已经快变成一门妖术了. 考虑到很多不明真相的 C 程序员同学们觉得 C++ 妖术是 C with classes, 那么这里先介绍一下 C++ 魔法大典中最基本东西: 怎么运用编译器的魔力在栈上召唤一个对象?

    假设现在有个类叫做 type, 它有个无参数的构造函数, 那么下面的代码
type object();
是巫师学徒们常犯的错误, 这个语句实际上是声明了一个叫做 object 的函数, 它返回一个 type 对象. 施展无参构造魔法的正确咒语是
type object;

    此外, 还有一个很吐血的咒术是
type(object);
同样是定义一个名字为 object 类型为 type 的对象. 是否很震惊? 其实这里的括号是可以任意加的, 如
type object;
type(object);
type((object));
    它们的效果相同. 如果它们写在一起, 后边的会跟第一个发生定义冲突.

    如果现在它有个构造函数需要一个 int 类型参数, 那么下面这两种代码
type object = 0;
type object = type(0);
是不正确的, 哦, 不, 至少是不严谨的, 而且看起来就是土气的 C 程序++, 而不是 C++ 魔法, 正确的咒语是
type object(0);
因为当 type 的构造函数是如下定义时第一种写法是编不过去的
struct type {
    explicit type(int);
};
而第二种写法确实读起来更象是 "调用构造函数, 初始化对象" 两步, 不过它实际上要用到复制构造函数, 虽然很可能编译器有足够强大的魔力优化掉这一次对象复制, 但如果把复制构造函数 delete 掉或者置于 privateprotected 封印之下, 编译器会给出一个恼人的错误.

PS: 在 The C++ Programming Language (C++ 程序设计语言) 一书中, 11.3.3 中有提到一个例子
    ... For example,
     complex b = 3;
    means
     complex b = complex(3);
我认为这一处是错误的, 原因如上所说.

    好, 现在再回到刚才那个括号打水漂的定义方式, 下面这种写法
int a = 3;
type(a);
后面一句是在召唤一个临时的 type 对象么? 当然不是, 编一下就会知道, 那仍然是在定义一个名字为 a 的对象, 即使 type 没有无参构造函数.

Permanent Link: /p/292 Load full text

Post tags:

 C++
 Constructor
 Copy Constructor

C++ 异常不怎么常见知识点 --- 后传

    上一篇timothyqiu 同学回复提到通过 std::set_unexpected 指定一个处理方法, 在函数抛出与异常声明不相符的异常时调用. 比如下面这样
#include <stdexcept>
#include <iostream>

void func_throws() throw (std::out_of_range)
{
    throw std::logic_error("danger!");
}

void throw_another()
{
    throw std::out_of_range("safe");
}

int main()
{
    std::set_unexpected(throw_another);
    try {
        func_throws();
    } catch (std::out_of_range e) {
        std::cerr << e.what() << std::endl;
    }
    return 0;
}
    有了这个处理函数后, 确实异常被神奇般地抓住了.

    不过换个写法, 如果处理函数里面也继续抛 std::logic_error
#include <stdexcept>
#include <iostream>

void func_throws() throw (std::out_of_range)
{
    throw std::logic_error("danger!");
}

void throw_another()
{
    throw std::logic_error("not safe!");
}

int main()
{
    std::set_unexpected(throw_another);
    try {
        func_throws();
    } catch (std::out_of_range e) {
        std::cerr << e.what() << std::endl;
    }
    return 0;
}
    程序照崩.

    也就是说, 处理函数相当于替换原来的函数, 在错误处原地重新抛出一个异常, 但异常必须匹配原来函数的异常声明, 否则异常仍然无法捕捉. 明显扯淡么, 随便找两个异常声明不搭界的函数, 这货不就不管用了么, 总不能随抛随设吧.

    当然, 标准还规定了一个很犀利的异常类型, 叫做 std::bad_exception, 如果把这家伙加进异常声明, 那就给力了
#include <stdexcept>
#include <iostream>

void func_throws() throw (std::out_of_range, std::bad_exception)
{
    throw std::logic_error("danger!");
}

void throw_another()
{
    throw;
}

int main()
{
    std::set_unexpected(throw_another);
    try {
        func_throws();
    } catch (std::bad_exception e) {
        std::cerr << e.what() << std::endl;
    }
    return 0;
}
    好了, 原来的异常在 throw_another 里面摇身一变, 成了 std::bad_exception, 不过看 std::cerr 吐出来的东西, 信息都消失了啊, 这不是坑爹么.
    其实说到底, 这跟写成
void throw_another()
{
    throw std::bad_exception("std::bad_exception");
}

Permanent Link: /p/275 Load full text

Post tags:

 C++
 Exception Handling

C++ 异常不怎么常见知识点

    之前也反复有人推荐 Google 的 C++ Coding Style, 昨天看到一位老师写的解读 Google C++ code style 谈对 C++ 的理解, 文后的讨论大多集中在 Google 不允许 C++ 异常. 我这里就不多插嘴了, 不过有些关于异常的基本情况还是想略聊一聊.
    文中的例子使用 g++ 4.5.2 和 clang++ 2.9 编译测试通过.

    如果一个函数声明了异常声明与该函数实际抛出的异常不匹配, 那么这个异常不会被捕获到. 也就是说 catch (...) 不是银弹.
#include <stdexcept>

void func_throws() throw (std::out_of_range)
{
    throw std::logic_error("danger!");
}

int main()
{
    try {
        func_throws();
    }
    catch (std::out_of_range) {}
    catch (std::logic_error) {}
    catch (...) {}
    return 0;
}
    补丁: std::set_unexpected 函数与不预期的异常

    而一个有趣的 C++ 规定是, 如果一个函数没有任何异常声明, 则该函数有可能抛出任何异常. 这个规定的一个隐喻是, 一切 C 函数都有可能抛出任何异常. 虽然 C 连异常是什么都不知道, 不过没关系. 因为 C 函数是异常透明的.
    比如下面的例子
#include <stdexcept>

extern "C" void exception_pass();

void func_throws()
{
    throw std::logic_error("danger!");
}

void upper_cpp_func()
{
    exception_pass();
}

int main()
{
    try {
        upper_cpp_func();
    } catch (std::logic_error) {
        return 0;
    }
    return 1;
}

extern "C" void exception_pass()
{
    func_throws();
}
    在异常发生后的 stack unwind 阶段, C 函数调用栈帧与 C++ 函数栈帧的处理方式相同. 执行结果是一样的. 但这并不意味着一种好的 C/C++ 编程方式, C 是没有 RAII 的!
    另外, 分离编译再链接时行为会不同, 可能出现异常无法被捕获的情况.

Permanent Link: /p/256 Load full text

Post tags:

 Exception Handling
 C
 C++

表达式求值之优先关系矩阵法

    YACC 或者 ANTLR 或者 PLY 之类的东西是很不错啦, 不过当面对一个类似 C(++) 这么变态的需要将语法和符号表勾搭在一起的语言形式时, 还是可以考虑一下使用 Python 纯手工打造.

    搞定表达式求值这种现代高级程序设计语言中基础部分, 用 LR(n), LALR 分析之类的当然是可行的, 假定需要支持括号和下面这些运算
算符
优先级由高到低+ - (正负号)^ (幂运算)* /+ - (加减号)
结合方式数值左边右结合左结合左结合
    先搞个产生式集合 (运算符就不搞什么转义了, | 表示或)
Expr := Term +|- Expr
     := Term
Term := Exponential *|/ Term
     := Exponential
Exponential := Factor ^ Exponential
            := Factor
Factor := +|- Factor
       := Number
       := ( Expr )
    接着还要再计算 FIRST 集啊什么的, 等到最后写成代码, 秀吉都嫁人了.

    所幸这个世界上无痛的解决方案还是挺多的, 比如为符号设定优先级, 使用优先级来指导算符是应该移进还是规约. 这个方法可称为优先关系矩阵法.
    这里仍然会用到移进 (Shift)规约 (Reduce) 这两个术语, 不过它们的意义跟 LR 分析法里面的有些不同. 在 LR 分析中, 符号指的是词法分析中得到的 Token, 而不是运算符, 也就是说数和运算符, 以及其它任何东西都放在同一个栈中; 而在运用优先关系法的表达式分析过程中, 符号栈包括两个不同的栈, 一个专门用来存运算符 (这个栈称为算子栈), 另一个存放数或者已解析的表达式 (这个栈称为表达式栈). 在这里, 移进表示将运算符压入算子栈, 或将数压入表达式栈; 而规约指的是, 根据运算符的元数, 从表达式栈中弹出指定数目的
    遇到一个数时无条件移进, 而遇到运算符则要视情况决定移进还是规约, 而所谓的情况就是算符优先级. 比如下面这个表达式
3 + 4 * 5 + 6
    首先读入 3, 移进

表达式栈
3
算子栈
(空)

    然后是 +, 算子栈栈顶为空, 没得比, 那好, 先移进

表达式栈
3
算子栈
+

    继续, 4 移进, 接着是 *, 比一下, 发现 * 优先级较栈顶的 + (加号, 不是正号) 优先级高, 那肯定得移进

表达式栈
3 4
算子栈
+ *

    接着移进 5, 再往后又是一个 + (加号), 这时栈顶的 * 优先级高于它, 所以可以开始规约流程: 从算子栈弹出 *, 它是二元的, 于是再从表达式栈弹出栈顶 (刚刚压入的 5) 和次栈顶 (4), 将这三者组成表达式 4 * 5, 再压回表达式栈 (下面以一个二叉树的形象描述)

表达式栈
3   *
   / \
  4   5
算子栈
+

    还没完呢, 现在的算子栈顶 + (加号) 与手头上拿着的 + (加号) 平级, 由于加号是左结合的, 所以应当继续规约, 得到

表达式栈
  +
 / \
3   *
   / \
  4   5
算子栈
(空)

    现在算子栈又空了, 于是 + (最后强调一次, 加号) 压栈, 最后是 6, 移进之, 结束时, 整个算符栈从头到尾规约一次, 大功告成.

    回顾一下刚才的过程, 规则是
  • 前面说过的, 数无条件入栈
  • 如果算子栈为空, 移进当前算子
  • 如果算子栈顶的优先级高于当前算子, 或者两者优先级相等, 但当前符号是左结合的, 那么进行规约, 直到不满足规约条件
  • 算子无法规约时则移进
    这一些初步地写成代码类似这样

Permanent Link: /p/250 Load full text

Post tags:

 Compiler Construction
 Python
 Tutorial

C++ 2011 中的 Left Value 与 Rvalue Reference

#include "某 C++ 概念之序篇"

答: std::stringstream() 产生的临时变量无法匹配类型 std::stringstream&.

    但是 std::stringstream() 可以匹配类型 std::stringstream const&, 也就是说, 如果函数 std::stringstream& operator<<(std::stringstream& os, double d) 的签名和实现作修改成下面这个样子就行了
std::stringstream const& operator<<(std::stringstream const& os, double d)
{
    const_cast<std::stringstream&>(os).operator<<(d);
    return os;
}

    之前扯过 C++ 已经没有语法意义上的左值了, 不过这里似乎有一点点很微妙的, 跟左值很类似的东西, 那就是, C++ 引用. 任何一本 C++ 入门书籍里面都会花一些篇幅来讨论引用, 其基本意义, 无非是某个东西的别名, 因此, 这某个东西对于引用而言显然是至关重要的.
    最基本的一点是, 如果被引用的东西是临时变量 (顺便一提, 如果是字面常量这种比较尴尬的情况, 视同临时变量) 怎么办? 比如之前代码样例 A 中的情况?
    这就牵扯到 C++ 中正统的 left value. 因为 left 已经不再有任何 "左" 相关的意义的, 所以我不太想在本文中把这货称之为 "左值" (实际上英文在这些方面更加灵活, 比如 Copyleft 这词跟 left 也没太大关系, 用来吐槽则非常不错).

    一个东西如果是 left value, 那么它就可以被赋值给 left value 引用, 所谓 left value 引用嘛, 就是就是类似 std::stringstream& 的引用类型, 而暗含 const 的类型的引用则不算
typedef int const int_const;
int_const& this_is_not_a_left_value_reference;
    那究竟什么是 left value 呢?
    一个语句之后仍然存在的变量, 表达式, 或者这样类似的 "具有值属性的什么东西" 就是 left value. 而
std::cout << (std::stringstream() << d).str().length() << std::endl;
这句之后, 显然临时构造的 std::stringstream() 就被析构了, 因此这家伙不算是 left value, 自然也就无法被 std::stringstream& 所引用.
    那常数为什么不算 left value 呢? 当然, 可以认为常数居阴阳之外, 别谈语句之后, 吐核退出, 就算是宇宙毁灭, 什么 π 啊 e 啊还活得好好的; 不过, 从计算机的角度来理解, 常数是 CPU 指令的立即数, 所以别谈语句之后, 只要这条指令结束, 它就没了.

    然而, C++ 一个很邪恶的规定是, 即使一个东西不是 left value, 它仍然可以绑定 const 引用, 比如以下语句都是合法的
std::pair<int, int> const& pair = std::make_pair(0, 1);
std::stringstream const& strm = std::stringstream();
std::string const& x = "Raki suta";
int const& i = 0;
    这样直白地写出来是有点让人觉得不舒服, 不过作为函数调用的参数则好得多, 比如之前的代码片段 B 那样

Permanent Link: /p/232 Load full text

Post tags:

 Move Semantic
 Operator Overload
 C++
 Right Reference
 Copy Constructor
 Left Value
 C++11

某 C++ 概念之序篇

    C++ 虔诚的信徒们, 请阅读下面的代码, 回答码后的问题
/* 完整样例 A */
#include <iostream>
#include <sstream>

std::stringstream& operator<<(std::stringstream& os, double d)
{
    os.operator<<(d);
    return os;
}

int main()
{
    double d;
    std::cin >> d;
    std::cout << (std::stringstream() << d).str().length() << std::endl;
    return 0;
}
问: 为什么上述代码无法通过编译?
/* 代码片段 B */
#include <map>
#include <string>
#include <stdexcept>

struct key_error
    : public std::logic_error
{
    explicit key_error(std::string const& what)
        : std::logic_error(what)
    {}
};

std::string const& lookup(std::map<std::string, std::string> const& map
                        , std::string const& key)
            throw(key_error)
{
    std::map<std::string, std::string>::const_iterator i = map.find(key);
    if (map.end() == i) {
        throw key_error("key ``" + key + "'' not found in map");
    }
    return i->second;
}
问: 上述代码中的 lookup 函数有什么隐患?

答案已揭晓, 点此查看, 谢谢关注.

Permanent Link: /p/222 Load full text

Post tags:

 C++11
 Copy Constructor
 Move Semantic
 C++
 Operator Overload
 Left Value
 Right Reference

Qt 囧形: QRect

    Qt 中的整点矩形类 QRect 的表示很独特, 存放的是左上角坐标和右下角坐标 (准确地说, 是 int x1; int y1; int x2; int y2;). 对 QRect 取上下左右都是闭区间上的边界, 比如
QRect rect(QPoint(0, 2), QSize(8, 8));
rect.left();   // 0
rect.right();  // 7 : 0 + 8 - 1
rect.top();    // 2
rect.bottom(); // 9 : 2 + 8 - 1
    其实也没什么大问题, 因为确实就是这样. 但是, 自古以来就被训练成左开右闭思维的键盘打击手们, 一不小心就会出错, 比如下面的 Python 列表切片代码示例, 取一个列表的一半, 后一半
list = range(0, 8)
list[0: len(list) / 2]         // [0, 1, 2, 3]
list[len(list) / 2: len(list)] // [4, 5, 6, 7]
    而如果给 QRect "切片", 求一个矩形的左半边和右半边, 代码则看起来像
QRect rect(QPoint(0, 2), QSize(8, 8));

QRect leftHalf(rect);
leftHalf.setRight(leftHalf.left() + leftHalf.width() / 2 - 1);

QRect rightHalf(rect);
rightHalf.setLeft(rightHalf.left() + rightHalf.width() / 2);
    设置右边界的代码修正这个 -1 看起来非常非常不自然. 而在实际运用中, 经常会遇到各种 +1 -1 的修正.

    至于 Nokia 的开发者们自己是不是搞清楚了 QRect 我也不太清楚, 不过 QPainter::drawRect(QRect const&) 这个函数是看起来有 bug 的样子, 比如下面这个例子
#include <QApplication>
#include <QToolButton>
#include <QBrush>
#include <QPainter>

struct TestButton
    : public QToolButton
{
    void paintEvent(QPaintEvent*)
    {
        QPainter painter(this);
        painter.setBrush(Qt::NoBrush);

        painter.setPen(QPen(Qt::white, 1));
        painter.drawRect(rect().adjusted(3, 3, -3, -3));

        painter.setPen(QPen(Qt::blue, 1));
        painter.drawRect(rect().adjusted(2, 2, -2, -2));

        painter.setPen(QPen(Qt::green, 1));
        painter.drawRect(rect().adjusted(1, 1, -1, -1));

        painter.setPen(QPen(Qt::red, 1));
        painter.drawRect(rect());
    }
};

int main(int argc, char* argv[])
{
    QApplication app(argc, argv);
    TestButton button;
    button.show();
    return app.exec();
}
    放大了看, 最外侧红框的右边和下边都不见了.

Permanent Link: /p/219 Load full text

Post tags:

 Qt
 QRect
 C++

拿去吧, 四字节整数类型

    对于 C(++) 之流在平台相关这种水深火热之中挣扎的语言, 对机器字长, 以及整数类型字长在一些情况下是极其敏感的. 所以每个大型项目建设之前, 在某个头文件里面定义一大堆 int32 或者是 unsigned8_t 之类的固定字长类型显得非常必要, 而且让工程看起来很专业的样子. 然而, 由于标准库中没有, 项目之间又互相不信任, 结果是几乎每个库都会自定一套, 比如 boost 就有 int8_t, int_least8_t 等类型, 而 Qt 更是拿出了叫做 qulonglong 的类型来卖萌. 虽然说是跨平台, 但是如果迁移平台时使用了错误版本的库呢? 因此有时依然需要写一个类似下面的程序来人肉验证
int main()
{
    std::cout << sizeof(int4_type) << " "
              << sizeof(int8_type) << std::endl;
    return 0;
}
    然而, 人都是不可靠的, 如果有人对你说, 喔, 我跑了上面的程序, 结果是 "4 8", 也许你仍会强迫症一样, 自己再验证一次. 好了, 也许你已经厌烦了, 这么一点破事情, 难道不能交给机器做么?
    理想的解决方案是, 只需要这样一个模板就好了
template <int _SizeOf>
struct IWantAnIntegralTypeOf;

int main()
{
    IWantAnIntegralTypeOf<4> this_is_a_4_bytes_int;
    IWantAnIntegralTypeOf<8> this_is_a_8_bytes_int;
    return 0;
}
不是吗?

    这是完全可行的, 实际上, 可以把 C 支持的所有内建整数类型先拿出来, 组成一个类型链表来搜索, 像下面这样
struct __null__ {};

struct c_char {
    typedef char type;
    typedef __null__ next;
};

struct c_short {
    typedef short type;
    typedef c_char next;
};

struct c_int {
    typedef int type;
    typedef c_short next;
};

struct c_long {
    typedef long type;
    typedef c_int next;
};

struct c_long_long {
    typedef long long type;
    typedef c_long next;
};

struct __head__ {
    typedef c_long_long next;
};
    接下来, 弄个模板来搜, 搜索当然是用模板偏特化的方法
template <typename _TypeNode, int _SizeOf, bool _SizeMatched>
struct type_finder;

template <typename _TypeNode, int _SizeOf>
struct type_finder<_TypeNode, _SizeOf, true>
{
    typedef typename _TypeNode::type type;
};

template <typename _TypeNode, int _SizeOf>
struct type_finder<_TypeNode, _SizeOf, false>
{
    typedef
        typename type_finder<
                typename _TypeNode::next
              , _SizeOf
              , _SizeOf == sizeof(typename _TypeNode::next::type)>::type type;
};

Permanent Link: /p/217 Load full text

Post tags:

 Generic Programming
 Metaprogramming
 C++
 Template

软件翻译与 locale

    看了一篇会 "吐核" 的终端, 了解到 wget 还有烦人的 "eta(英国中部时间)" 提示, 看来软件翻译这档子事还真是很能产生喜感的.

    在 Linux 环境下, 主流的软件翻译方法是通过工具抓取源代码中的需翻译字符串到外部文本文件, 形成一个字典, 翻译之后在运行期加载. 更专业一点就是, 从软件本身要能国际化 (internationalization, 一般简写为 i18n, 因为 i 和 n 之间有 18 个字符), 支持从源代码中提取字符串来翻译; 而翻译这个步骤则成为本地化 (localization, 简称 l10n).
    要让软件具备国际化属性, 这必须程序员们亲自努力, 为需翻译字符串附加一些修饰. 如下面这个程序
int main(int argc, char* argv[])
{
    if (1 == argc || 0 == strcmp("hello", argv[1]))
    {
        puts("Hello");
    }
    else
    {
        puts("World");
    }
    return 0;
}
是很难具备国际化能力的, 因为文本扫描程序无法区分哪些字符串是需要翻译的.
    要加上区分信息很简单, 比如
#define TRANSLATE_THIS(x) x

int main(int argc, char* argv[])
{
    if (1 == argc || 0 == strcmp("hello", argv[1]))
    {
        puts(TRANSLATE_THIS("Hello"));
    }
    else
    {
        puts(TRANSLATE_THIS("World"));
    }
    return 0;
}
    将文件保存为 hello.c, 使用 xgettext 工具提取字符串
$ xgettext hello.c --keyword=TRANSLATE_THIS -o hello.po
那么 xgettext 将提取被宏 TRANSLATE_THIS 所包括的所有字符串到 hello.po 纯文本文件中.
    在 po 文件中, 每个被提取的字符串是一个 msgid, 而翻译则是接下来一行中的 msgstr, 现在所有的 msgstr 都空着, 在 po 文件中直接写入翻译结果并保存即可. 此外还要指定 po 文件头部有文件编码等信息.
    翻译完成后, 在本地创建 locale 相关目录, 再使用 msgfmt 工具编译 po 文件为二进制文件, 并放入 locale 目录中
$ mkdir -p $LANG/LC_MESSAGES && msgfmt hello.po -o $LANG/LC_MESSAGES/hello.mo
这个目录的意义待会儿再解释.
    使用纯文本编辑器盯着 po 文件翻译条目是很累很无趣的事情, 好在有许多工具可以选取. 比较流行的有 poEditQt Linguist. 接下来继续讨论程序的事情.

    到此为止, 程序本身还不具备本地化的能力, 因为宏 TRANSLATE_THIS 什么也没干, 程序本身的逻辑并没有变化, 也不知道如何导入翻译目标字符串替换原有字符串. 现在将宏定义换掉, 使用 locale 中的组件来完成本地化工作

Permanent Link: /p/208 Load full text

Post tags:

 Locale Programming
 l10n
 Tutorial
 C
 i18n

ASCII Art 让开机充满爱

    之前有位爱心人士提议更改 Linux SSH 登入歡迎畫面為新世紀福音戰士裡的 Nerv 的 Logo, 然而, 对于我等宅男而言, 只在登录 SSH 时出现个 Nerv Logo 是不够的, 每次开机的时候来上一次也是必须的.

    简单方案是在启动脚本里加一句 cat, 不过最好不要加在 rc.sysinit 脚本开始, 因为这时内核还没有切分辨率. 我个人觉得效果最好的是加进 rc.multi 开头, 这时有充分的时间展示 (特别是如果恰好要硬盘检查), 而且之后也不容易被刷屏刷掉 (对于 DAEMONS 不是很多的同学).

    至于 cat 的文件内容, 嗯, 下面是我自己制作的一份 Nerv Logo, 比较大, 38 行, 最宽处 67 字符, 通常的终端字体在 14 吋本本的显示器 (1366×768 或 1280×800) 都能放下.

Permanent Link: /p/194 Load full text

Post tags:

 ASCII Art
 Lucky Star
 Logo
 Nerv

std::unique_ptr<cookbook>

    std::unique_ptr 是 C++11 标准的 STL 中, 用来取代 std::auto_ptr 的指针容器 (如果在代码中使用了 std::auto_ptr, 使用 gcc 4.5 之后的版本加上 -std=c++0x -Wall 参数编译时, gcc 会报出警告 std::auto_ptr 已经过时).

    同 std::auto_ptr 一样, std::unique_ptr 的基本功效也能当作简单的自动对象管理指针来使用, 如
#include <memory> /* for std::unique_ptr */
#include <iostream>

struct echo {
    echo()
    {
        std::cout << "ctor" << std::endl;
    }

    ~echo()
    {
        std::cout << "dtor" << std::endl;
    }

    echo(echo const&) = delete;
};

void test()
{
    std::unique_ptr<echo> echo_ptr(new echo);
}

int main()
{
    test();
    std::cout << "." << std::endl;
    return 0;
}
输出应该如
ctor
dtor
.
    类型 echo 在构造和析构时的输出信息可以帮助掌握对象的生命周期. 如上述程序中, echo 对象在 test 函数结束时析构.

    std::unique_ptr 的复制构造函数被 delete 处理了, 所以类似下面的代码会出错
std::unique_ptr<int> a(new int(0));
std::unique_ptr<int> b(a); // ERROR
            // deleted function
            // ‘std::unique_ptr<...>::unique_ptr(std::unique_ptr<...> const&)'
    如果确实需要复制一份整数的值, 需要可以做如下操作
std::unique_ptr<int> b(new int(*a));
    而如果是想要将 a 所持有的指针转移到 b 中, 需要显式调用 std::move 将来移交指针控制权
std::unique_ptr<int> a(new int(0));
std::unique_ptr<int> b(std::move(a));
    此时 a 中的指针会变为 NULL. 明确的转移语义由 std::move 函数表达, 与 std::auto_ptr 暧昧的构造函数不同, std::move 明确指出 std::unique_ptr 对象是通过转移构造进行参数传递的.

    当函数需要使用 std::unique_ptr 作为参数或返回值时, 可以是如下几种形式

Permanent Link: /p/181 Load full text

Post tags:

 C++
 C++11
 unique_ptr
 Move Semantic
 Tutorial

C++ 到底怎么使用流来输出对象

    书上写的做法当然是类似
struct my_type {
    void set_x(int xx);
    void set_y(double yy);

    my_type(int xx, double yy)
        : x(xx)
        , y(yy)
    {}

    friend std::ostream& operator<<(std::ostream& os, my_type const&);
private:
    int x;
    double y;
};

std::ostream& operator<<(std::ostream& os, my_type const& m)
{
    return os << m.x << ' ' << m.y;
}
    一般使用这样没问题, 不过在想要写得很省略的用况下, 这样就很纠结
my_type m(10, 20.0);
std::stringstream ss;
std::string image = (ss << m).str(); // WRONG!
因为 operator<< 返回的类型已经变成没有 str() 取得字符串函数的基类 std::ostream& 了. 看起来要什么流类型进来什么流类型出才行, 比如
struct my_type {
    void set_x(int xx);
    void set_y(double yy);

    my_type(int xx, double yy)
        : x(xx)
        , y(yy)
    {}

    friend template<typename _OS>
    _OS& operator<<(_OS& os, my_type const&); // WRONG
private:
    int x;
    double y;
};

template <typename _OS>
_OS& operator<<(_OS& os, my_type const& m)
{
    os << m.x << ' ' << m.y;
    return os;
}
不过很遗憾, 泛型函数无法做朋友
    那要不先把 my_type 对象弄成字符串了, 再把字符串输出好了
struct my_type {
    void set_x(int xx);
    void set_y(double yy);

    my_type(int xx, double yy)
        : x(xx)
        , y(yy)
    {}

    std::string str() const
    {
        std::stringstream ss;
        ss << m.x << ' ' << m.y;
        return ss.str();
    }
private:
    int x;
    double y;
};

template <typename _OS>
_OS& operator<<(_OS& os, my_type const& m) // ACTUALLY NOT NEEDED ANY MORE
{
    os << m.str();
    return os;
}
这看起来多疼啊.

    一个可能的方案是, 为每个自定义类型实现 str() 成员函数 (有必要的还可以虚一下), 然后全局声明一个
template <typename _OS, typename _T>
_OS& operator<<(_OS& os, _T const& t)
{
    os << t.str();
    return os;
}
也许这样会好很多.

Permanent Link: /p/177 Load full text

Post tags:

 C++
 Operator Overload
 Output Stream

Hello Closure

    C++0x 搞了 lambda 算子, Java 更耐不住寂寞, 直接上了 Clojure, 函数式或伪函数式编程大潮一波波地袭来, 我终于还是下定决心, 直接去学习来自远古时代的 Lisp.
    当然了, 既然都是图灵完全的, C++, Python 什么的, 跟 Lisp 的实际表达能力差不多. 不过呢, 就像之前我对 STL 里 std::for_each 的吐槽那样, 语言不给力, 要表达出想要的东西会很麻烦. 在动手写了一些 Lisp 代码之后我觉得, Lisp 在这方面不会成问题.
    问题倒是, Lisp 代码似乎很难读懂, 括号很容易看错, 而且脑子里面要有一台能容纳至少七八个调用栈帧的 Lisp 虚拟机, 吃力啊.
    我倒也不指望成为 Lisp 达人, 以后用 Lisp 写各种各样的煮咖啡程序什么的, 只是想换换脑子, 让我找找 “原来代码还能这样写” 的感觉.

    言归正传, 说说 Lisp 的闭包. 所谓闭包, 是是带有编译期绑定自由变量且是第一级对象的函数.
    不愧是 Wikipedia, 描述太精准了, 让人难以看明白. 下面先简介一下这几个术语.
    自由变量指的是不在函数参数或函数域中的变量 (全局变量不算), 比如嵌套函数中内层函数引用的外层函数的参数或局部变量时, 这样被引用的变量; 甚至没有压根儿没有声明的变量 (当然前提是编译器支持这样的行为).
    不过上面说的后一种情况, 根本没声明的变量, 就不满足编译期绑定这个条件了. 此外, 一些动态名字查找的行为也会导致这个规则失效.
    所以诸如 sin, cos 之类的数学库函数都不是闭包, 它们并不引用自由变量.
    而第一级对象这个约束条件则更多的是要求语言支持, 第一级对象要求对象能够被存入变量, 能被作为函数参数或函数返回值, 能被聚合进对象, 能够运行期构造, 并且任意取名都不会影响其行为, 这些条件全部满足. Java 语言就不能将函数存入变量, 或作为参数返回值; 而 C++ 在 C++0x 标准之前没有嵌套函数, 无法构造出引用除了全局变量之外自由变量的函数, 所以这些语言的函数都不是闭包.
    概念就这么多, 下面开始闭包的基本应用, 以 Scheme 为例, 解释器使用 Guile.

    这里是一个简单闭包的例子
(define (multiple-by n)
        (define (multiple x) (* x n))
        multiple
)
    这里嵌套在内部定义的 multiple 就是闭包原型, 它引用了定义在 multiple-by 中的参数 n 作为自由变量. 调用 multiple-by 则可以得到一个闭包实例, 如
(define multiple-by-3 (multiple-by 3))
那么再
(multiple-by-3 4)
就能得到 12.

    Lisp 支持 lambda 算子语法来简化函数定义, 同时减去为函数起名字的麻烦, 如上例可以改成
(define (multiple-by n)
        (lambda (x) (* x n))
)
    闭包能引用自由变量的特性是很奇妙的, 把上面的例子改成下面这样
(define (multiple-by n)
        (lambda (x) n)
)
虽然这个时候它已经完全名不副实了, 调用 multiple-by 产生的闭包再被调用时只会傻乎乎地一个劲地返回相同的值.

    这倒是一个另类的闭包, 它的实际作用不是运算, 而是数据运载. 也就是说, 闭包的作用不一定是执行某种操作, 而可以是存放数据的对象. 比如下面这个例子, 就利用闭包构造了一个 pair

Permanent Link: /p/174 Load full text

Post tags:

 Closure
 Lisp

Yet Another BitFocus Site

    博客也换了好几茬了, 域名这也是第二个了, 各种原因. 现在又弄了一个站点, 不知道能坚持到什么时候. 这次略创造性地, 把 ARecord 的根做了个封面, 把博客搭在 blog 这个 CName 下面, 而很具有迷惑性的 www 那个 CName 则挂着 GAE, 不知道走错路的小朋友会不会偶然撞墙或者发现站点剧变. 此外就是 mail.bitfoc.us 挂在 Google App 这个很不错, 推荐大家去折腾一下, 免费账户就给 10 个 7G+ 的 GMail 个性域名账户哦.

    开年第一周, 上了六天班, 周末还加了一记, 虽然加班实际上也没做什么事情, 还让我偷空把这个站点给买了修了整了, 不过怎么说也是兆头不好啊.

    之前的博客在年前挂掉了, 写了一篇算是总结的东西只好挂在豆瓣上, 现在想想总归是一篇吐槽文, 也就不再转回博客上了, 只是最后用的那句歌词还是贴在这里, 算是对自己新一年的勉励:

除了装作无畏的战士一样, 什么也做不了 (恐れを知らない戦士のように 振る舞うしかない / Unistall / 石川智晶)

    歌词是比较惨, 很能体现鄙司鄙项目组现在的工作气氛. 不过说回来, 描述现在的学习气氛也差不了太多, 看了看 SICP, 觉得之前都白学白搞了, 也完全不知道将来会发现什么, 领悟什么.

Permanent Link: /p/155 Load full text

Post tags:

 Blog
 Bit Focus

C++ 中捕获整数除零错误

    继承自 C 的优良传统, C++ 也是一门非常靠近底层的语言, 可是实在是太靠近了, 很多问题语言本身没有提供解决方案, 可执行代码贴近机器, 运行时没有虚拟机来反馈错误, 跑着跑着就毫无征兆地崩溃了, 简直比过山车还刺激.
    虽然 C++ 加入了异常机制来处理很多运行时错误, 但是异常机制的功效非常受限, 很多错误还没办法用原生异常手段捕捉, 比如整数除 0 错误. 下面这段代码
#include <iostream>

int main()
{
    try {
        int x, y;
        std::cin >> x >> y;
        std::cout << x / y << std::endl;
    } catch (...) {
        std::cerr << "attempt to divide integer by 0." << std::endl;
    }
    return 0;
}
输入 "1 0" 则会导致程序挂掉, 而那对 try-catch 还呆在那里好像什么事情都没发生一样. 像 Python 一类有虚拟机环境支持的语言, 都会毫无悬念地捕获除 0 错误.

使用信号

    不过, 底层自然有底层的办法. 这得益于硬件体系中的中断机制. 简而言之, 当发生整数除 0 之类的错误时, 硬件会触发中断, 这时操作系统会根据上下文查出是哪个进程不给力了, 然后给这个进程发出一个信号. 某些时候也可以手动给进程发信号, 比如恼怒的用户发现某个程序卡死的时候果断 kill 掉这个进程, 这也是信号的一种.
    这次就不是 C 标准了, 而是 POSIX 标准. 它规定了哪些信号进程不处理也不会有太大问题, 有些信号进程想处理也是不行的, 还有一些信号是错误中断, 如果程序处理了它们, 那么程序能继续执行, 否则直接杀掉.
    不过, 这些错误处理默认过程都是不存在的, 需要通过调用 signal 函数配置. 方法类似下面这个例子
#include <csignal>
#include <cstdlib>
#include <iostream>

void handle_div_0(int)
{
    std::cerr << "attempt to divide integer by 0." << std::endl;
    exit(1);
}

int main()
{
    if (SIG_ERR == signal(SIGFPE, handle_div_0)) {
        std::cerr << "fail to setup handler." << std::endl;
        return 1;
    }
    int x, y;
    std::cin >> x >> y;
    std::cout << x / y << std::endl;
    return 0;
}
    可以看出, signal 接受两个参数, 分别是信号编号和信号处理函数. 成功设置了针对 SIGFPE (吐槽: 为什么是浮点异常 FPE 呢?) 的处理函数 handle_div_0, 如果再发生整数除 0 的惨剧, handle_div_0 就会被调用.
    handle_div_0 的参数是信号码, 也就是 SIGFPE, 忽略它也行.

底层机制

Permanent Link: /p/100 Load full text

Post tags:

 POSIX
 C
 Exception Handling
 Signal
 C++

C++ 转移构造

    这篇文章中的例子均可在 GCC 4.5.1 版本和 Clang 2.8 版本编译, 在某些较老或优化不尽相同的编译器上, 下面的例程可能并不能获得与文中所述一致的结果.
    不过, 这篇文章的重点并非讲述 C++ 中关于复制构造函数的优化, 而是为了说明 C++0x 标准中出现的 Move Semantic 所试图解决的问题之一, 所以对关于复制构造函数的例子有大致理解即可.
    重点是, 如果希望完整地编译文中最后一部分中出现的任何 0x 标准相关的代码, 强烈推荐 GCC 4.5.x 版本编译器.

    废话少说, 先来一段代码:
#include <iostream>

struct cp_ctor_doubling {
    cp_ctor_doubling(int ii)
        : i(ii)
    {}

    cp_ctor_doubling(cp_ctor_doubling const& rhs)
        : i(rhs.i * 2)
    {}

    int const i;
};

cp_ctor_doubling create(int i)
{
    return cp_ctor_doubling(i);
}

int main()
{
    cp_ctor_doubling c(create(10));
    std::cout << c.i << std::endl;
    return 0;
}
问: 输出多少? A. 10 B. 20 C. 40 D. 以上答案都不正确.
    嗯, 也许有得到 B 和 C 的, 得到 D 的同学也许该试着为自己的编译器报个 bug 了, 如果得到 A, 那么恭喜, 您的编译器已经具备对于复制构造函数最基本的优化能力了.
    C 语言忠实信徒揶揄 C++ 编译器会背着程序员做的 "额外的事情" 时, 历来会想到 C++ 的类复制构造函数. 然而, 现实不仅仅是这样, 编译器还会做出更多额外的事情, 比如把不必要的复制构造函数调用优化掉, 或者更准确地说, 把一些临时对象给优化掉, 于是复制构造函数根本不会被调用到.
    如果对上述例子中的编译优化有任何疑虑, 可以尝试下面这段代码
#include <iostream>

struct cp_ctor_not_impl {
    cp_ctor_not_impl(int ii)
        : i(ii)
    {}

    cp_ctor_not_impl(cp_ctor_not_impl const&);

    int const i;
};

cp_ctor_not_impl create(int i)
{
    return cp_ctor_not_impl(i);
}

int main()
{
    cp_ctor_not_impl c(create(10));
    std::cout << c.i << std::endl;
    return 0;
}

Permanent Link: /p/94 Load full text

Post tags:

 C++
 C++11
 Move Semantic
 Copy Constructor

C++ 中的左值

请使用 x86 32位 ArchLinux GCC 4.5.0 环境编译文中 C++ 示例代码, 不过只要是 GCC 或 clang++ 编译结果应该都相仿.

作为一个特别的语言, C++ 中的左值是*语义*概念而非*语法*概念, 这一点甚至也可以认为是沿袭自 C 语言. 在任何其他语言中讨论 “什么是左值” 这个概念时, 会简短使用 “变量可以是左值”, “表达式不能是左值”, “常数不能作为左值” 等等, 诸如 “变量”, “表达式”, “常数” 这些都是语法概念, 所以刚才这些说法都是左值的语法约定. 确实一些语言使用语法约束来规定左值, 比如 Python, 下面的 Python 代码

class A:
    pass

a = A()
a + 1 = 0

编译时会报 “SyntaxError: can’t assign to operator”, 是 *Syntax* 哦. -甚至连- JS -这样乱的语言-也有类似的例子, 比如

var f = function() {};
f() = 0;

在执行的时候会报 "ReferenceError: Invalid left-hand side in assignment" --- Chromium.

在 C 里面表达式, 或者函数的返回值, 或者两者的混合, 只要语法恰当, 返回值类型又是一个可写指针, 那么通过对该指针引用的方式来赋值, 如

int* f() { return NULL; }

*(f() + 1) = 0;

这一特性在 C++ 那放荡不羁的类型系统里得到了极大的加强, 完全不再受制于语法的约束, 编译器只需要先根据运算符优先级搭起语法树, 至于左值判定什么的都留在以后的语义分析再来.

而这一切的开端仅仅是因为 C++ 支持一个指针的替代, 也就是引用, 这样连前缀星号都省略了.

另一方面, C++ 中的运算符重载机制又极大地扩展其左值概念的超凡脱俗, 并且 C++ 程序员似乎从来也未有过 “哦, 这只是个示例程序, 尽量别引入复杂特性” 这样的想法, 即使是经典的 Hello World 程序中, 也毫不吝惜地显摆着运算符重载这种高级特性.

#include <iostream>

int main()
{
    std::cout << "Hello, world\n";
}

从这个例子扩展出一个赋值语句几乎毫不费力, 只需要在函数体第一行加个 = 之后随手发挥就好.

#include <iostream>

int main()
{
    std::cout << "Hello World\n" = std::cerr;
    return 0;
}

当然这份代码会报错但不是因为左值不合理, 而是 --- 赋值操作符被设为私有函数或赋值操作符重载被删除了 (C++11 中).

如果希望的话, 可以进一步参考下面这个操作符重载错乱的例子 (它可能由一位危险的 C++ 实习生在主键盘区 += 坏掉的机器上编写的)

struct type {
    int x;

    type& operator+(type& rhs)
    {
        this.x = rhs.x;
        return *this;
    }

    type& operator=(type& rhs)
    {
        this.x += rhs.x;
        return *this;
    }
};

int main()
{
    type a, b, c;
    a + b = c;
    return 0;
}

所以在 C++ 的世界里, 左值跟赋值运算操作符已经没有半点关系了, 倒是只要类型能够匹配上, 运算符重载就能通过编译, 看起来再离奇的算式都没问题.

不过, 如果非要扯赋值运算符, 它跟其它二元运算符有什么不同?

这差异还确实有, 那就是, 赋值运算符必须是成员非静态的, 也就是说下面的编译无法通过

Permanent Link: /p/85 Load full text

Post tags:

 C++
 Left Value
 Operator Overload

char** 不能赋值给 char const**

C 和 C++ 允许把指向 "某物" 的指针赋值给指向 "不可改变" 的 "某物" 的指针, 如

char* call = "fsck";
char const* call_const = call;

而且, 如果确定不会更改所知向的对象, 那么推荐加上 const, 这是 C++ 的代码编写建议之一. 但是, 要把指向 “某物” 的二级指针赋值给... 见鬼, 简单的说, 下面这种赋值, 任何一个负责任的 C++ 编译器会报出指针不兼容错误:

char* call = "fsck";
char** ptr_to_call = &call;
char const** ptr_const_to_call = ptr_to_call; // error

C/C++ 这样做, 目的其实是在于防范将 char const* 赋值给 char* 的意外行为. 这样说也许很难理解, 那么请看下面这段示例代码

Code Snippet 0-0

char const* CALL = "fsck";

void bind(char const** m)
{
    *m = CALL;
}

int main(void)
{
    char* s;
    bind((char const**)&s); // explicit convert
    s[1] = 'u'; // crash on write
    return 0;
}

在调用 bind 时, 采取强制转换来规避编译错误. 而此时调用 bind 就出现了问题, 它把 char const* 类型的 CALL 变量赋值给了实际上是 char*s, 结果就是在紧接下来的那个赋值中, 程序由于尝试去写只读内存区而崩溃. 有崩溃有真相, 这就是对标题的解答.

另一个类似的例子是, 子类对象的二级指针不能赋值给父类对象的二级指针, 如

Code Snippet 0-1

struct base {};
struct inherit : base {};

void f(void)
{
    inherit** i = NULL;
    base** b = i; // error
}

Permanent Link: /p/83 Load full text

Post tags:

 C
 C++
 const

GCC 的花招: 嵌套函数

    这里所说的 GCC 不是 GNU Compiler Collection, 而是单单指代 GNU C Compiler. 这篇文章并不打算讲标准 C 中的任何东西, 而是要聊聊一个 GCC 的特性: 嵌套函数.
    先来个例子, C 版的 for_each 结合嵌套函数 (必须存为 .c 文件, 使用 gcc 编译才能通过, g++ 压力大)
#include <stdio.h>

void for_each(int* begin, int const* end, void (* fn)(int*))
{
    while (begin < end) {
        fn(begin++);
    }
}

#define ARRAY_SIZE 5

int main(void)
{
    int a[ARRAY_SIZE];
    int n;
    void read(int* x)
    {
        scanf("%d", x);
    }
    for_each(a, a + ARRAY_SIZE, read);
    scanf("%d", &n);

    void add(int* x)
    {
        *x = *x + n;
    }
    for_each(a, a + ARRAY_SIZE, add);

    void print(int* x)
    {
        printf("%d ", *x);
    }
    for_each(a, a + ARRAY_SIZE, print);
    printf("end\n");
    return 0;
}
    这代码的紧凑程度虽然跟闭包没得比, 但是使用与定义能放在一起, 就算是一大进步了. 另一个福利在 add 函数, 它引用了一个局部变量 n, 是在外层函数 main 中定义的. 而 n 的使用并不在 main 的可控范围内, 也许它绕过 for_each 的栈帧, 再继续向上被 add 引用. 这听起来像魔法一样, 幸而 gcc 是个开源软件, 不必担心使用这个特性时会让自己的灵魂落入某个兼职程序员的邪恶巫师手中. 但是这到底是如何实现的呢? 要我讲解 gcc 源码我还没有这个能力, 不过 gcc 有个功能可以让我们比较方便地窥探出其中的技术内幕
$ gcc 源文件 -S -o 目标文件
这样源文件会被编译成汇编指令, 接着分析汇编指令好了.
    上面那个例子情况比较复杂, 不妨分析下面这段简短的代码
void func(int a, int* b, int c)
{
    int nested(void)
    {
        return a + c;
    }
    *b = nested();
}
    这段代码在我机器上 (环境: x86 / Ubuntu 9.10 / GCC 4.4.1) 编译得到的汇编代码如下

Permanent Link: /p/82 Load full text

Post tags:

 Assembly
 GCC
 for_each
 Nested Function

STL 悲剧之 for_each

    这篇文章谈一个我使用 STL 中 for_each 的负面心得. 我对这个东西在当前 C++ 语法下约束是否能广泛使用持有怀疑态度, 至于能否替代所有的 for 循环, 我持完全否定观点! 如果您发现文中提及的这档子事情本质上是我不了解 STL 而自寻死路, 请不吝赐教, 在下方回复, 在下感激不尽.

    在 Google 中输入 "for_each" 然后猛击 "I’m feeling lucky", 这时我幸运地跳转到大名鼎鼎的 sgi 的网站里, 页面中有个例子
template<class T> struct print : public unary_function<T, void>
{
    print(ostream& out) : os(out), count(0) {}
    void operator() (T x) { os << x << ' '; ++count; }
    ostream& os;
    int count;
};

int main()
{
    int A[] = {1, 4, 2, 8, 5, 7};
    const int N = sizeof(A) / sizeof(int);

    print<int> P = for_each(A, A + N, print<int>(cout));
    cout << endl << P.count << " objects printed." << endl;
}
    从泛型党的视角看来, 这例子非常不错, 完备而规范地演示了 for_each 的用法. 从此泛型党成了大赢家, 除了 for_each 内部, 外面的代码再也不需要 for 这个关键字了.
    而那些说写 C++ 代码像谈话一样简短, 基本上泛型编程完全不及格的程序员, 在写上面功能的时候一般会这样做
int main()
{
    int A[] = {1, 4, 2, 8, 5, 7};
    const int N = sizeof(A) / sizeof(int);

    int i;
    for (i = 0; i < N; ++i)
        cout << A[i] << ' ';
    cout << endl << i << " objects printed." << endl;
}
    在喷这个改编版的丑陋之前, 不妨先淡定下来, 想想这个例子到底想做什么, 无非是给个数组 (或者其它什么容器) 把每个成员输出 (或者做个什么其它简单的操作), 并记录被操作的元素个数. 然而, 完成这个操作的代码量与它的功能相比, 臃肿得令人发指. 所以, 在用了几次 for_each 之后, 我完全丧失了当初的激情, 变得极其懒惰, 不愿意把简单的操作抽取到函数外部构造成一个对象然后传递给 for_each; 在维护自己以前写的代码时, 也会偷偷把 for_each 改回 for 循环, 因为有的时候我实在不知道伙伴们把我弄出来的那个函数对象类型给维护到哪里去了.
    当然, 我并不认为这是 for_each, 或者 STL, 或者泛型的错. 在我心目中, 泛型思想是风骚的, for_each 的设计是超前的, 问题出在 C++ 语法这个悲剧帝身上, 或者说, 硬要用 C++ 这个传统的面向过程加面向对象语言的语法来包装对象, 来实现类似高阶函数这种函数式编程中的特性, 是悲剧的根源所在. 不仅是 for_each, 连 find_if 等类似的 STL 函数都差不多一样的下场, 与其构造一个精妙绝伦的函数对象类型, 程序员还不如老老实实写个破循环来得实在.
    一个振奋人心的消息是, C++ 新标准即将发布了, 它会支持闭包对象, 那样的话, for_each 以及其它函数就不会像现在这么处境尴尬了.

Permanent Link: /p/81 Load full text

Post tags:

 C++
 STL
 for_each

STL set 悲剧指导

    这篇文章谈一个我使用 STL 中 set 容器的负面心得. 是的, 我已经被这丫的杀得超神了, 快来人阻止它吧! 如果您发现文中提及的这档子事情本质上是我不了解 STL 而自寻死路, 请不吝赐教, 在下方回复, 在下感激不尽.

    最坏对数时间插入, 删除, 查询, 迭代遍历, 这些听起来都无比诱人, 它们由 STL 中的 set 容器鼎力支持. 然而, set 的只读制度是非常龌龊的, 简而言之, 只要你敢往这个坑里面放, 你就得接受它们以后再也无法修改的命运. 比如下面这段例子
#include <set>
#include <string>

using std::set;
using std::string;

struct student {
    string name;
    int grade;

    student(string const& name_, int grade_)
        : name(name_)
        , grade(grade_)
    {}

    bool operator<(student const& rhs) const
    {
        return name < rhs.name;
    }

    bool operator==(student const& rhs) const
    {
        return name == rhs.name;
    }
};

int main(void)
{
    set<student> students;
    students.insert(student("Li Lei", 5));
    students.insert(student("Han Meimei", 5));
    students.insert(student("Jim Green", 5));

    for (set<student>::iterator i = students.begin();
         students.end() != i;
         ++i)
    {
        ++(i->grade);
    }
    return 0;
}
    student 类的 key 是 name, 跟 grade 没有关系, 原则上来说, 修改后者并不会破坏 set 的存储结构. 然而, 编译器一棒子打死, 不许改, 除非剩下的成员全部 mutable 修饰.
    只读制度悲剧的根源在于, set 所谓的 key 撑死只是个假象, value_type 这玩意儿就是 key_type 本身.
    伪 key 导致的不仅仅是不能改, 重要的是还不能查! 看看 set::find 函数的参数, 要的又是阴魂不散的 key_type. 这意味着什么? 意味着 Han MM 同学报出她名字的时候, 还查不出她几年级, 而必须要利用她的名字, 伪造一个充气娃娃放进去才能找到! 看到这里我就败了, 这明摆着就是不让我用 set, 让我转投 map 么? 一个也许可行的方案是
#include <map>
#include <string>

using std::map;
using std::string;

struct student_periphery {
    int grade;
};

map<string, student_periphery> students;
这样建模的话也是够狗血的, 如果哪个函数拿着一份 student_periphery 问怎么查出学生姓名, 那就更悲剧了.

Permanent Link: /p/79 Load full text

Post tags:

 set
 C++
 STL

django 架设网站入门指南[贰]

上节回顾 – ORM 和数据库

创建 admin 应用

    打开 guestbook/urls.py 仔细研究一下注释, 会看到有几行写着, 取消注释来激活 admin. django 的 admin 应用是一个非常不错的后台. 现在就来开启它吧
from django.conf.urls.defaults import *

# Uncomment the next two lines to enable the admin:
from django.contrib import admin
admin.autodiscover()

urlpatterns = patterns('',
    # Example:
    # (r'^guestbook/', include('guestbook.foo.urls')),

    # Uncomment the admin/doc line below and add 'django.contrib.admindocs'
    # to INSTALLED_APPS to enable admin documentation:
    # (r'^admin/doc/', include('django.contrib.admindocs.urls')),

    # Uncomment the next line to enable the admin:
    (r'^admin/', include(admin.site.urls)),

    (r'^$', 'guestbook.home.views.display'),
    (r'^echo/$', 'guestbook.home.views.echo'),
    (r'^save/', 'guestbook.home.views.save_message'),
)
    因为是应用, 所以呢, 还得去 settings.py 登记
INSTALLED_APPS = (
    'django.contrib.auth',
    'django.contrib.contenttypes',
    'django.contrib.sessions',
    'django.contrib.sites',
    'django.contrib.admin',
    'guestbook.home',
)
    最后要记得执行数据库同步来创建 admin 相关的表
$ guestbook/manage.py syncdb
    现在转到 http://localhost:8000/admin/ 会看到登录提示页面啦. 现在填入第一次 syncdb 时输入的帐号密码就能登入了. 不过现在的 admin 还很挫, 甚至不能管理留言. 进入 guestbook/home 目录, 创建 admin.py 源文件, 加入如下内容
from guestbook.home.models import Message
from django.contrib import admin

admin.site.register(Message)
    刷新页面, 唉, 没有反应, 因为服务器仅监视那些改动过的文件并重新载入, 这次是单独添加的文件所以没有自动重置, 所以得重启服务器才行. 然后, 就能在 admin 应用中看到留言对象并修改它们了.

定制 admin

Permanent Link: /p/77 Load full text

Post tags:

 django
 Tutorial
 Web Server
 Python

django 架设网站入门指南[壹]

上节回顾 – 配置 基本视图和逻辑

数据库配置

    仍然在 settings.py 中, 找到 DATABASE_ 开头的项目. 现在用 sqlite3 作为数据库, 它已经集成在 python 2.5 以后的版本中, 这样就省去了安装配置的环节. 现在修改这些项目
DATABASE_ENGINE = 'django.db.backends.sqlite3'
DATABASE_NAME = 'guestbook/db_file'
这里 DATABASE_NAME 同样需要给出文件的绝对路径, 原理跟之前模板目录那个一样, 如果不能确定每次的工作目录, 那么就填绝对 db_file 的路径吧. 保存设置, 然后执行数据库同步操作
$ guestbook/manage.py syncdb
会输出提示
Creating table auth_permission
Creating table auth_group
Creating table auth_user
Creating table auth_message
Creating table django_content_type
Creating table django_session
Creating table django_site

You just installed Django's auth system, which means you don't have any superusers defined.
Would you like to create one now? (yes/no):
这些是 django 为内置的用户, 会话等类型建立的表, 最后询问是否立即建立一个超级用户. 这里答 yes (仅一个 y 是不行的唉), 然后输入用户名, 电子邮箱和密码. 最后会建立表的索引, 然后结束. 现在, 你可以在 guestbook 目录下看到文件 db_file 了, 它是数据库使用的文件.

ORM 和数据库操作

    django 的 ORM 非常轻松. 打开 home 目录下的 models.py, 建立留言类型
from django.db import models

class Message(models.Model):
    name = models.CharField(max_length=32)
    content = models.CharField(max_length=32)
    dt = models.DateTimeField(auto_now=True)
注, 使用 django 的 ORM, 该类型需要继承于 models.Model, 而要往数据库中放的数据项, 需要是 models 模块中的对应的域类型. 至于 auto_now=True, 它指出时间和日期在该对象插入数据库时自动使用当前日期时间.
    类型弄好了, 得再同步一次数据库. 这些操作可以不重启服务器
$ guestbook/manage.py sql home
$ guestbook/manage.py syncdb
    回到 guestbook/home/views.py, 增加函数 save_message, 让它将表单数据存入数据库, 并重定向回到首页

Permanent Link: /p/76 Load full text

Post tags:

 Web Server
 Tutorial
 Python
 django
 ORM

django 架设网站入门指南[零]

安装

    根据 django 官方文档, 需要 python 2.3 或更高版本. 不过按现在的 python 普及程度, 想必大家的机器上都有 python 2.5 或 2.6 了. 我的操作系统是 ubuntu 9.10, 自带的是 2.6 版本.
    debian 用户安装 django 很简单, 只需要
# apt-get install python-django
就可以了, 其它发行版看有没有类似的方法. 或者在官方站点下载源代码安装
    祝好运.

建立项目 startproject

    首先找到一个地方, 建立一个项目 guestbook, 我们将在这个项目中搭建一个留言板.
$ django-admin startproject guestbook
有些系统中 django-admin 并非一个命令, 需要
$ python django-admin.py startproject guestbook
    执行完这个之后, 当前目录下会创建一个名为 guestbook 的目录, 里面包含了一个最简单的服务器: 显示一个主页. 执行
$ python guestbook/manage.py runserver
启动后会看到类似以下输出
Validating models...
0 errors found

Django version 1.1.1, using settings 'guestbook.settings'
Development server is running at http://127.0.0.1:8000/
Quit the server with CONTROL-C.
这时, manage.py 已经在本地 8000 端口创建了一个服务器, 赶快打开浏览器去访问吧!

    为 guestbook/manage.py 加上可执行属性 (在 ubuntu 9.10 下该属性已经自动添加了)
$ chmod u+x guestbook/manage.py

创建应用 startapp

    在 django 世界的哲学里, 每个功能称之为一个应用. 创建应用也使用 manage.py 来完成. 比如现在用以下命令创建一个首页应用
$ guestbook/manage.py startapp home
这时 guestbook 目录下会多出一个 home 目录, 里面有这些文件
__init__.py
models.py
tests.py
views.py
    比较烦的是, 这时得回去修改设置, 打开 settings.py 查找 INSTALLED_APPS, 在这一坨里面加一行
INSTALLED_APPS = (
    'django.contrib.auth',
    'django.contrib.contenttypes',
    'django.contrib.sessions',
    'django.contrib.sites',
    'guestbook.home',
)
    这样 home 应用才算是有了名分. 好, 现在再来实现功能. 因为现在只是处理页面, 所以只需要在 guestbook/home/views.py 里面修修补补就好了. 打开它, 其实相当于是个空文件, 把这一段代码放进去
from django.http import HttpResponse

def display(req):
    return HttpResponse('<html><body>hello, django!')
    我知道你已经不耐烦了, 如果你曾经写 php 的话. 不过现在还有最后一步, 修改路径映射. 打开 guestbook/urls.py, 在里面加一句话

Permanent Link: /p/74 Load full text

Post tags:

 Web Server
 Tutorial
 django
 Python

Makefile 与 C 语系头文件依赖自动解析

h1. 如何获得源文件依赖的头文件?

这一部分内容与 Makefile 毫无关系, 它由编译器完成.

以 g++ 为例, 可以尝试使用以下方法输出 .cpp 文件依赖的头文件

g++ -M [your cpp file]

乱糟糟的, 不是吗? 这是因为 g++ 把依赖的库文件也给列出来了. 忽略库文件, 则使用这样的命令

g++ -MM [your cpp file]

显然, 这些东西扔到标准输出是毫无用处的, 可以对其进行重定向

g++ -MM [your cpp file] > [some file]

但是这还是有问题, 只把依赖关系放进文件当然不行, 编译源文件的指令还没弄出来呢. 下面就得另外想办法了.

h1. 怎么添加编译指令并运行它们?

添加指令本质上就是追加文件内容, 方法有难有简单, 最简单的无非是写个脚本 echo 并追加重定向到文件中. 在这篇粗陋的文章里就用这招了. 好, 写个 Makefile 脚本

[target.o]:[your cpp file]
....g++ -MM $< > Makefile.tmp
....echo "....g++  $< -c" >> Makefile.tmp
....make -f Makefile.tmp

这里的四个点号 (....) 表示一个制表符, 嗯, 是的, Makefile 只能用万恶的制表符来缩进, 而且还必须缩进; Makefile.tmp 一定不要是当前的 Makefile, 要不然就出现文件覆盖的悲剧了...

结果就是, 一旦 make 到这个目标, 它会生成一串依赖关系和构建方法到另一个 Makefile, 然后把编译这等脏活累活都甩给那个倒霉的家伙.

h1. 怎么转移目标?

如果上述目标仍然写成 xxx.o : xxx.cpp, 那么如果仅仅是依赖的头文件被修改了, 这个目标仍然不会被 make 到. 一个很挫的方法是, 不要把目标定为 xxx.o 文件, 相反, 弄成一个永不会生成的目标比较好, 比如叫 xxx.d 这个名字.

下面上一个完整的例子. 这个例子中有个叫做 DEP 的 Makefile 变量没有被声明过, 嗯, 这将是你的事情. 请将所有需要编译并连接的 cpp 源文件列个表, 然后修改它们的后缀变成 d, 那么 DEP 的值就是这个表.

Code Snippet 0-0

CXX=g++
CXXFLAGS=-Wall -pg
MKTMP=Makefile.tmp

all:object

object:$(DEP)
....$(CXX) $(CXXFLAGS) *.o -o $@

%.d:%.cpp
....$(CXX) -MM $< > $(MKTMP)
....echo "....$(CXX) $< $(CXXFLAGS) -c" >> $(MKTMP)
....make -f $(MKTMP)

clean:
....rm -f *.o
....rm -f test.out
....rm -f $(MKTMP)

再次提醒, 制表符出没注意. (可利用编辑器的全文替换, 4 点换成 1 制表符)

假如现在目录下有 main.cpp, class0.cpp, class1.cpp, 那么定义

DEP=main.d class0.d class1.d

将这句话插进上述源码中的开头位置然后 make 即可.

h1. 怎么收拾掉乱七八糟的输出?

接脏活的临时工经常会反馈出一些无聊的信息, 比如进入这个离开那个的, 如果希望保持控制台的清洁, 那么把不想看的都扔进垃圾桶吧

make > /dev/null

不要担心看不到 warning 和 error, 它们是通过 stderr 输出的, 而上述重定向只会干扰 stdout.

Permanent Link: /p/63 Load full text

Post tags:

 C
 C++
 Makefile

编译期数值计算程序设计思路

阅读这篇文章需要了解基本的 C++ 模板语法规则, 以及模板的泛化, 偏特化, 当然还包括完全特化这些基本概念. 这篇文章将给出基于 C++ 模板的 Metaprogramming 程序设计中需要注意的事项以及渐进式设计思路.

0. 基础

这一段介绍 Metaprogramming 基础, 包括模板模式匹配规则, 使用模板实现循环或分支的基本方法. 对 Metaprogramming 已经有了解的同学可以跳过这一段.

本质上来说, 现代计算机的核心任务是数值计算, 周边任务是 I/O. 现代几个主流的编程语言, 如 C/C++/Java, 它们的语法组织方式与现代计算机的主流体系结构是 "平行" 的, 即, 语句的先后顺序表示它们的逻辑顺序, 而这种顺序与人的一贯思维顺序又是相同的 (在计算机中表达式的计算顺序会与书写顺序稍有不同, 但却很符合人类的思路); 可以说这是什么样的爹生什么样的崽, 什么样的人造什么样的语言和计算机.

然而, 在 C++ 模板世界中, 这个规则被打破了. 从分类上来说, Metaprogramming 更类似于函数式编程, 而不是传统的 C++ 程序设计. 在这个异世界中, 程序员不被允许使用循环或者分支语句, 包括函数返回语句都不允许: 在函数式编程中起码还有函数返回, 而在 Metaprogramming 中, 由于一切函数都没有被调用 (还在编译呢), 因此一切的值都谈不上返回, 它们只是存在于模板符号表中, 一旦编译结束便烟消云散.

当然, 没有循环, 分支这些编程语言中的基本元素, 并不意味着程序员只被允许设计顺序程序. 只不过, 在这里, 一切分流动作都被转化为了另一个语言特性: 模式匹配. (这一点与函数式编程非常相似)

下面一段代码展示了模式匹配的威力:

Code Snippet 0-0

#include <iostream>

template <unsigned I>
struct limit_to_2
{
    static unsigned const R = 2;
};

template <>
struct limit_to_2<1>
{
    static unsigned const R = 1;
};

template <>
struct limit_to_2<0>
{
    static unsigned const R = 0;
};

int main(void)
{
    std::cout << limit_to_2<0>::R << std::endl;
    std::cout << limit_to_2<1>::R << std::endl;
    std::cout << limit_to_2<2>::R << std::endl;
    std::cout << limit_to_2<3>::R << std::endl;
    return 0;
}

模板 limit_to_2 为传入的整数设置了一个上限, 当传入模板的参数为 0 或者 1 时内部定义的 R 值与参数相同, 否则将 R 设置为 2. 这看起来很像是 switch-case 语句, 0 和 1 分别是两个 case, 而未特化的模板则是 default.

但是, 这样做有一些不方便, 如果所设的上限非常高, 那岂不是要为低于限制的情况写很多特化? 所以引入分支是非常必要的. 下面这个例子展示了如何利用模式匹配来实现编译期分支:

Permanent Link: /p/50 Load full text

Post tags:

 Template
 Metaprogramming
 C++

划分问题与连续自然数幂和之通项公式

无限区间上 n 个不同的点可以把该区间分为多少段?

答案很明显, 当然是 (n + 1) 段啦. 另一个稍有难度的题目是, 无限平面上有n条直线, 问这些直线至多能把平面分成多少份? 在平面上画啊画就能归纳出解来的. 那么, 用 n 个平面, 最多能将无限三维空间划分成几个部分呢? 这个就略复杂了, 难道先建个 3D 模型, 然后归纳? 这个方法可行, 不过太浪漫和浪费了. 另外, 如果这个问题开始讨论维度更高的情形, 这种方法就行不通了. 那么, 问题来了:

使用 n 个 d 维 "*平整*" 的几何体, 来对无限 (d + 1) 维空间进行划分, 最多可以得到多少个部分?

不知道这个问题是否有官方名称了, 暂时称之为划分问题吧. 在这里, "平整" 指的是在该维度的空间中, 这些几何体的方程应该是线性的, 比如在 3 维空间中, 平面方程都可以表示为线性方程组 { $A_1 * x + B_1 * y = C_1$; $A_2 * x + B_2 * y = C_2$ }, 而在 1 维空间中的点就比较惨了, 就是 x = C, 不过还算是线性的. 其实大家只要有个基本的认识就行了, 不必这么刻板深究, 这篇文章中介绍的方法是没有严格证明的, 只是说说思路.

对能够画出来的各种维度进行一下归纳, 可以发现这样一个规律, 最开始开始的几次, 划分得到的空间区域是指数增长的:

  • 1 点分直线可以把直线分为 2 份
  • 1 直线分平面可以把平面分为 2 份, 2直线分平面可以把平面分为 4 份
  • 1 平面分空间可以把空间分为 2 份, 2平面分空间可以把空间分为 4 份, 3 平面分空间

可以把空间分为 8 份

这些规律可以*不完全归纳*假设为: n 个 d 维平整无限体分 (d + 1) 维无限体, 当 $n <= d$ 时, 可以分为 $2^n$ 份.

此外, 已知的结论有:

  • n 个点分直线至多将直线分为 (n + 1) 份;
  • n 条直线分平面至多将平面分为 ($(n^2) / 2 + n / 2 + 1$) 份;
  • n 个平面分空间至多将空间分为 ($(n^3) / 6 + 5 * n / 6 + 1$) 份;

所以再*不完全归纳*假设: n 个 d 维平整无限体分 (d + 1) 维无限体, 得到的份数 m 是 n 的一个幂多项式, 最高次项次数为 (d + 1).

由这些假设, 划分问题将可以用非常暴力的代数手段来解. n 个 d 维平整无限体分 (d + 1) 维无限体, 分得的空间数目 m 满足:

$ m = a_d * n^(d+1) + a_(d-1) * n^d + ... + a_0

这里 $a_x$ 是该多项式的系数.

现在代入 (n, m) = {(0, 1), (1, 2), ..., (d, $2^d$)}, 得到一个 (d + 1) 元一次方程, 这样就可以唯一地解出 $a_d$, $a_(d-1)$, ..., $a_0$ 这 (d + 1) 个系数.

类似的 (未经证明的) 方法同样可以用来连续自然数幂求和问题: 对于自然数 m 和给定的自然数 n, 求通项公式

$ a(m) = 0^n + 1^n + 2^n + ... + m^n

同样, 设出通项公式方程 (注: 没有常数项)

$ a(m) = a_k * m^(k+1) + a_(k-1) * m^k + ... + a_0 * m

然后根据没有化简的普通方程, 代入 m = { 1, ..., k }, 计算出前 k 个 a(m) (这个过程会很痛苦), 然后代入通项公式解方程 (唔, 这会更痛苦).

当然这只是另一个替代方案而已. Bernoulli 对自然数幂和公式的也做过研究, 他的方式是递推的, 运动量没有这个暴力方法大.

Permanent Link: /p/45 Load full text

Post tags:

 Algebra
 Algorithm
 Geometry

泛型编程中的策略类

在编译期想要组合策略, 除开人肉内联不算, 有很多方式. 比如弄很多很多的 bool 参数

template <bool AllowDuplicate, bool SortElements, bool CheckOutOfRange>
struct just_another_container;

这看起来就是一个参数灾难, 如果某个地方出点小的模板编译错误, 哼哼~

当然, 另一种简单的替代方案就是把所有的 bool 整合在一起, 形成一个位段

template <unsigned Policy>
struct just_another_container;

这种情况实际上缺点更多, 比如维护位域会很麻烦, 有可能在这个声明之前有这些枚举

enum {
    ALLOW_DUP_MASK = 1,
    SORT_ELE_MASK = 2,
    CHECK_OUT_OF_RANGE_MASK = 4,
};

考虑这个容器有个 insert 函数, 它很可能需要考虑是否允许重复元素

template <unsigned AllowDuplicate>
void insert(element_type e);

而令人郁闷的是, 在 C++ 中不允许给函数偏特化, 也就是说这样写

template <>
void insert<0>(element_type e);
template <>
void insert<ALLOW_DUP_MASK>(element_type e);

是无法编译的! 要绕过这道坎, 得把 insert 函数放入一个模板结构体

template <unsigned AllowDuplicate> struct insert_s;
template <>
struct insert_s<ALLOW_DUP_MASK>
{
    static void insert(just_a_container& container, element_type& e);
};

这样做代价高昂, 首先, insert 被当作孤儿一样的抛弃, 那么类中的任何非 public 成员都不再对它开放, 当然, 为了这么个简单的小玩意儿声明 friend 也是可行的, 但是多了不觉得烦吗?

另外, 在调用策略行为进行特化时一般只针对特定的位, 那么将该策略位从组合策略中分离出来, 代码中将充斥着这样的运算

Policy & ALLOW_DUP_MASK
Policy & CHECK_OUT_OF_RANGE_MASK

比如

void another_member_function()
{
    element_type ele;
    // wanna call insert function of policy = Policy
    insert_s<*Policy & ALLOW_DUP_MASK*>::insert(*this, ele);
    // ...
}

这样做非常麻烦, 如果某个地方漏了 & 或者跟错误的掩码进行了运算, 哼哼~

不过, 泛型程序设计有自己的方法, 那就是, 多继承!

不要吓到了, 是的, 在 C++ 远古时代, 多继承被认定为獠牙猛兽. 不过那都是跟 C++ 运行时多态相关的. 步入泛型新纪元的 C++ 又迎来了多继承第二春, 它可以显著改善上述问题.

将上面的声明编程

template <*typename Policy*>
struct just_another_container;

然后加上这些结构体声明

struct policy_base {};
struct allow_dup : public policy_base {};
struct sort_ele : public policy_base {};
struct check_out_of_range : public policy_base {};

组合策略, 只需要声明一个策略类型继承想要的策略, 并把它传入容器就能达到目的, 比如

Permanent Link: /p/36 Load full text

Post tags:

 Generic Programming
 C++
 Template

闰年判定

已经转移到

http://zlo.gs/p/neuront/leap-year-test-algorithm

Permanent Link: /p/25 Load full text

Post tags:

 Algorithm

已知两圆圆心坐标及半径求两圆交点

在一个二维平面上给定两个圆的圆心横纵坐标、半径共 6 个参数, 求交点. 即实现下面的 C 函数

int intersect(struct circle_t const circles[], struct point_t intersections[]);

其中 point_tcircle_t 的定义分别是

Code Snippet 0-0

struct point_t {
    double x;
    double y;
};

struct circle_t {
    point_t center;
    double r;
};

函数 intersect 的输入参数为两个圆, 返回交点个数, 另外, 交点详细信息将被存入另一个参数数组 intersections 中. 由于两个圆之多有 2 个交点, 因此该函数可以如下形式调用:

Code Snippet 0-1

#include <stdio.h>

int main(void)
{
    struct circle_t circles[2];
    struct point_t points[2];

    /* 从 stdin 输入圆参数
     * 按照如下格式
     * $(x_0, y_0, r_0)$
     * $(x_1, y_1, r_1)$
     */
    scanf("%lf%lf%lf%lf%lf%lf",
          &circles[0].center.x, &circles[0].center.y, &circles[0].r,
          &circles[1].center.x, &circles[1].center.y, &circles[1].r);

    // 如果两个圆相同
    // *注意:* 由于 x, y, r 都是浮点数, 使用 == 进行判同可能导致问题
    // 作为示例代码还是姑且这么写了
    if (circles[0].center.x == circles[1].center.x
        && circles[0].center.y == circles[1].center.y
        && circles[0].r == circles[1].r)
    {
       puts("The circles are the same.");
       return 0;
    }

    switch (*intersect(circles, points)*) {
        case 0:
            puts("No intersection.");
            break;
        case 1:
            printf("(%.3lf %.3lf)n", points[0].x, points[0].y);
            break;
        case 2:
            printf("(%.3lf %.3lf) (%.3lf %.3lf)n",
                   points[0].x, points[0].y,
                   points[1].x, points[1].y);
    }
    return 0;
}

用程序实现求交点方法可以有多种, 比较极端的甚至可以用到二分逼近, 反正计算机的计算能力跟笔算是两个世界; 不过本文还是老实一点, 仍试着来解方程. 在求解过程中, 除了用到圆的标准方程

$ (x - x_0)^2 + (y - y_0)^2 = r_0^2

(其中 $(x_0, y_0)$ 是其中一个圆的圆心, $r_0$ 是其半径; 当然对另一圆也是如此, 此处省略之) 圆的参数方程也将会被用到

$ x = r_0 * cos(A) + x_0

$ y = r_0 * sin(A) + y_0

现在, 设其中其中至少有一个交点 (没有交点的情况可以简单利用圆心距大于半径之和来判定), 换言之存在某个 $A_s$ 使得存在对应的点 $(x_s, y_s)$ 于两个圆的方程都成立, 即

Permanent Link: /p/14 Load full text

Post tags:

 Algorithm
 C
 Geometry

0 1 2 3 4 5 6 7 Page 8 9 10 11 12


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site