类型的本质和函数式实现

类型的本质和函数式实现

(感谢 @文艺复兴记(todd) 投递此文)

在上一篇文章《二叉树迭代器算法》中,我介绍了一种基于栈的二叉树迭代器实现。程序设计语言和Haskell大牛@九瓜 在看过之后评论到:

这里用了 stack 来做,有点偷懒,所以错失了一个抽象思考机会。如果我们能够理解二叉树到线性表的转换过程,完全可以把 Iterator 当作抽象的线性表来看,只要定义了关于 Iterator 的 empty, singleton, 还有 append 操作,实现二叉树的 Iterator 就变得非常直观。

“错失了一个抽象思考机会”是什么意思呢?我理解九瓜的意思是基于栈的实现虽然是正确的,但它缺乏对于迭代器类型本质的理解,不具有通用性。如果能对迭代器进行合适地抽象就可以像二叉树递归遍历一样自然地得出二叉树迭代器,甚至其他更复杂的数据结构,只要我们能写出它的遍历算法,迭代器算法都可以自然推出。

类型的本质

九瓜提到了通过empty, singleton和append操作对Iterator进行抽象,我本来打算直接根据这个思路介绍函数式的二叉树迭代器实现,但是考虑到其实首要的问题在于理解类型的本质,而并不是所有人都具备这个基础,不如先普及一下类型基础再进入具体实现。那么下面我们就先来认识一下类型到底是什么?我们先以来看看表示元素对的Pair类型,可能有人一提到Pair类型马上就会在脑海中浮现出下面的结构:

struct Pair {
    int left;
    int right;
}

其实,这种理解是非本质的,Pair完全可以用2个元素的数组来表示,第一个元素表示left,第二个元素表示right:

struct Pair {
    int elements[2];
}

上面的两种不同表示是类型的不同实现,而类型的本质是由操作(Operation)和操作间的关系或不变式(Invariant)所定义的,我们称之为类型规范(Type Specification)。比如,Pair类型是这样定义的:

Type Pair:
    Operations:
        Pair make_pair(int x, int y)
        int get_left(Pair pair)
        int get_right(Pair pair)
    Invariants:
        get_left(make_pair(x, y)) == x  //对x, y构造的Pair取左元素等于x
        get_right(make_pair(x, y)) == y  //对x, y构造的Pair取右元素等于y

也就是说只要是满足Pair类型规范,即定义了make_pair,get_left, get_right这3种操作,并且这些操作满足上面两个不变式,那么它这就是Pair类型。我们再来看看稍微复杂一点的Stack类型:

Type Stack:
    Operations:
        Stack make_stack()  //构造空栈
        Stack push(Stack stack, int x)  //将元素x压栈,返回新栈
        int top(stack)  //获取栈顶元素
        Stack pop(Stack stack)  //将栈顶元素弹栈,返回新栈
    Invariants:
        top(push(stack, x)) == x  //栈顶元素为最后一次压栈值
        pop(push(stack, x)) == stack  //对stack压栈后再弹栈等于原来的stack

Stack类型规范简言之就是FILO(先入后出),如果要形式化就是上面的不变式。为了加深理解,我们现在切换到测试视角来看一看,如果请你来编写一个Stack类的单元测试用例,你应该怎么写呢?许多朋友都不清楚单元测试到底测什么?怎么测?我见过不少人用一个测试用例单独对push做测试,用另一个测试用例对pop单独做测试,其主要原因就在于缺乏对类型本质的理解。其实,只要理解了类型的本质我们就知道孤立地看push或pop是没有任何意义的,它们的意义是在FILO关系下相互解释的,所以测试当然是基于类型规范来测试FILO不变式!这种基于类型规范的测试是一种黑盒测试,与类型的内部实现细节无关,只要单元测试覆盖了类型所定义的所有操作和不变式,那么不管内部怎么实现或优化,测试用例都不需要调整。反之,如果深入到了类型的内部实现做白盒测试,那这样的测试用例实际上就不再是反映其类型规范了,它会随着实现细节的调整而失效。

更深一层来看,不仅是在Pair,Stack这样的微观层面,在一个系统的宏观层面同样可以采用类型视角,即考察系统定义了哪些操作?这些操作之间有什么样的关系或不变式?比如,你如何从类型的角度来看待MySQL这样一套数据库系统?MySQL系统定义了哪些操作?这些操作之间必须满足怎样的关系和不变式?不仅如此,类型视角除了可以应用于计算机系统,甚至还可以应用于生活中的事物,比如,你到超市购物可以寄存自己的包,在寄包的时候会获得一张密码条,取包时可以通过密码条打开箱子。你能从超市寄包这个例子中看出类型来吗?如果你看出来了,说明你对类型的理解真正融会贯通了!

类型的函数式实现

上面我们介绍了类型的本质在于操作和操作间的关系,下面我们要关注的是类型的实现。在上面的例子中,Pair的内部结构到底是什么,是一个left和一个right成员?还是一个两元素的数组?没有讲,也没关系,就好像Windows的Handle和Linux的FileDescriptor一样,它们都是一个标识,你并不需要关心它的值本身,你只需要用几个相关的函数创建和操作它就行了(上面超市寄包例子中的密码条和Windows中的Handle是什么关系,你看出来了吗?你需要理解密码条的内容吗?)。换句话说,只要满足类型规范,具体实现是可变的,使用者只依赖于类型规范而不依赖于其具体实现。这在面向对象语言中意味着接口保持不变而具体实现可以变化(这里把public方法视为一种广义的接口)。

下面,我们还会看到的是不仅类型的内部实现可以变化,而且可以根本没有什么所谓的内部实现。这是什么意思呢?让我们来思考一下,是不是Pair内部一定要有什么东西来保存构造函数传入的left和right?我们能跳出这个定势吗?在函数式编程中,我们能做到:

//Javascript
function make_pair(x, y) {
    // 返回一个支持get_left和get_right操作的闭包(Closure)
    return {
        get_left : function() { return x },
        get_right : function() { return y }
    }
}
function get_left(pair) {
    return pair.get_left();
}
function get_right(pair) {
    return pair.get_right();
}
// Test case
console.log(get_left(make_pair(1, 2))) //1
console.log(get_right(make_pair(1, 2))) //2

上面的关键代码在于make_pair的内部返回的不是一种具体的数据结构,而是一个支持get_left和get_right操作的闭包(Closure),将来可以通过get_left和get_right来提取x, y。这种基于闭包的实现和我们通常采用的基于数据结构的实现的本质区别在哪里呢?不难发现,基于闭包的实现和类型规范是直接对应的,它并没有引入类型规范之外的东西,而基于数据结构的实现则隐藏了实现的细节。换句话说,如果要验证实现代码的正确性,对于前者只需要比对着类型规范,对于后者我们可能需要去仔细理解推敲其所采用的数据结构。对于Pair这样简单的结构二者差别不大,甚至基于数据结构的实现更简单,但是对于复杂的类型就容易体现出闭包实现的优势了。为了加深理解,我们再来看一个Stack的函数式实现:

//Javascript
function make_stack() {
    return null
}
function push(stack, x) {
    return {
        top : function() { return x },
        pop : function() { return stack }
    }
}
function top(stack) {
    return stack.top()
}
function pop(stack) {
    return stack.pop()
}
// Test case
var stack = make_stack()
stack = push(stack, 1)
stack = push(stack, 2)
stack = push(stack, 3)
console.log(top(stack)) //3
stack = pop(stack)
console.log(top(stack)) //2
stack = push(stack, 4)
console.log(top(stack)) //4

上面的所有函数都是采用了无副作用的纯函数式设计,可能习惯面向对象编程的朋友不是很习惯,不过这不影响我们对类型的讨论,而且它也很容易改造成面向对象的风格,感兴趣的朋友可以自己尝试对上面的代码进行简单的包装让它看起来像面向对象的样子。

函数式二叉树迭代器

上面我们介绍了类型的本质和函数式实现,下面我们再来看看Iterator类型又该如何定义和实现呢? 思路当然还是从操作入手,考虑Iterator类型对应了哪些操作,它们的关系是什么?上面九瓜提示了Iterator类型可以抽象为线性表List类型,或者说Iterator本质上是一个List。为什么呢?其实,只要跳出“如何表示数据结构”的思维,从类型角度思考就很容易理解,因为Iterator和List都定义了相同的操作,Iterator的使用者完全不关心也不知道它背后到底是链表还是二叉树,你对Iterator的操作和一个List的操作完全一样。正是这个原因,STL等范型库才能通过Iterator将算法和数据结构解耦。

怎么定义一个List类型呢?九瓜提到的empty(), singleton()和append()实际上就是和List打交道最多的Lisp语言的经典定义方式。Lisp是基于s-expression的,s-expression既可以视为线性表又可以视为树,本质上Lisp为List类型了构造、取首元素和取剩余元素等几种操作:

Type List:
    Operations:
        List empty()  //构造空表,通常由()这个文字量表示
        List singleton(Element e)  //构造包含一个元素的表,通常由(e)这个文字量表示
        Element first(List list)   //取list的第一个元素,通常又叫car操作
        List rest(List list)  //取list除第一个元素外的剩余部分,通常又叫cdr操作
        List append(List list1, List list2) //连接两个表
    Invariants:
        append(empty(), list) == list  //空表和表list连接后等于表list
        append(list, empty()) == list  //空表和表list连接后等于表list
        first(singleton(e)) == e  //对singleton(e)取首元素等于e
        rest(singleton(e)) == empty()  //对singleton(e)取首元素外的剩余部分的结果为空表
        append(first(list), rest(list)) == list  //对list的首尾两部分进行连接等于list本身
        if list1 is not empty then
            first(append(list1, list2)) == first(list1)  //对非空表list1于表list2的连接取首元素等于对非空表list1取首元素
        if list1 is not empty then
            rest(append(list1, list2)) == append(rest(list1), list2)  //对非空表list1于表list2的连接取首元素等于对非空表list1取首元素

有了上面的分析,我们相应地写出下面的List实现:

//Javascript
function empty() {
    return null
}
function singleton(e) {
    return {
        first: function() { return e },
        rest: function() { return null }
    }
}
function first(list) {
    return list.first()
}
function rest(list) {
    return list.rest()
}
function append(list1, list2) {
    if (null == list1) return list2
    if (null == list2) return list1

    return {
        first : function() { return first(list1) },
        rest : function() { return append(rest(list1), list2) }
    }
}

在此基础上可以进一步实现二叉树迭代器:

function make_binary_tree_iterator(node) {
    return {
        first : function() {
            return null != node.left ? first(make_binary_tree_iterator(node.left)) : node
        },
        rest : function() {
            var left_it = (null == node.left ? null : make_binary_tree_iterator(node.left))
            var root_it = singleton(node)
            var right_it = (null == node.right ? null : make_binary_tree_iterator(node.right))
            var it = append(append(left_it, root_it), right_it)
            return rest(it)
        }
    }
}
//======== Test case ========
var tree = {
    value : 1,
        left : {
            value : 2,
            left : { value : 4, left : null, right : null },
            right : null
        },
        right : {
            value : 3,
            left : null,
            right : { value : 7, left : null, right : null }
    }
}
for (var it = make_binary_tree_iterator(tree); null != it; it = rest(it)) {
    console.log(first(it).value)
}

上面的make_binary_tree_iterator在List类型的基础上按照二叉树遍历过程构造了一个List。不知道你是否注意到了,为什么它不像下面这个例子一样直接返回一个List,而要构造一个闭包呢?

function make_binary_tree_iterator(node) {
    var left_it = (null == node.left ? null : make_binary_tree_iterator(node.left))
    var root_it = singleton(node)
    var right_it = (null == node.right ? null : make_binary_tree_iterator(node.right))
    return append(append(left_it, root_it), right_it)
}

这里关键的区别在于闭包是惰性求值的,也就是说只有当真正开始迭代遍历的时候才会逐渐对各个函数进行求值,而上面的函数递归调用是非惰性的,会从一开始就把所有结点展开成线性表。如果你对这一点还不能很好地理解,可以尝试在各个函数中加log跟踪函数的调用过程。

总结

本文介绍了类型的本质在于它所定义的操作以及操作之间的关系和不变式。类型的实现关键在于满足类型规范的要求,而具体实现是可以变化的,使用者和测试用例都应该只依赖于类型规范而不依赖于具体实现。函数式的类型实现往往和类型规范是直接对应的,简单通用,但可能有性能问题,而命令式的类型实现往往会引入复杂的内部数据结构,但是其优点是高效。这两种实现并不是完全互斥的,有时候可以将二者相结合达到简单与高效的结合。


关注CoolShell微信公众账号可以在手机端搜索文章

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

——=== 访问 酷壳404页面 寻找遗失儿童。 ===——


本广告收入已由广告主捐给Wikipedia

好烂啊有点差凑合看看还不错很精彩 (18 人打了分,平均分: 4.33 )
Loading...

类型的本质和函数式实现》的相关评论

  1. 函数式是符号运算,本质来讲是无类型。类型是编译型语言,或是建立在命令式基础上的语言,让编译器,解释器如何去理解符号所做的内存操作。而函数式语言是不关心内存的那些事的。只不过,现阶段的语言建立在命令式基础上,尤其是模仿函数式的语法。记住了,那只是模仿,并不是函数式那回事。

  2. 博主您好,看完很有感触,于是想实现“超市密码条”的例子,如下
    Type Storage:
    operation:
    Storage empty( ) //构造空的储物柜
    int store( Storage S, int obj ) //存储物品至储物柜,返回密码
    int get( Storage S, int key ) //使用密码取出物品
    invariations:
    get( S, store( S, obj ) ) == obj

    实现:
    fuction empty( ){
    return {
    get: function() { return null; }
    }
    }

    function store( Storage s, int obj ) {
    return s.store( obj );
    }

    fuction get( Storeage s, int key ){
    return s.get( key ); //恕我愚钝,这里我只能找到这种实现~
    }

    然后我回头看,问题来了:
    1. 在实现 store( Storage s, int obj ) 时, 里面凭空冒出了个 s.store(), 这个是 Type Storage声明之外的东西 ,同样在 get( Storage s, int key ) 也是冒出了 s.get() ;
    可不可以认为这样 Type Storage 的类型定义已经被 “撑破”了呢?
    2. 原先在 Type Storage 里定义的关系: get( S, store( S, obj ) ) == obj, 在实现里并没有体现出来,我知道自己陷入以前的思维里去了——“方法封装起来粘贴到对象上”,但现在真想不透,这个应该如何处理呢?
    3. 留意到文中的List, append() 是基于 first(), rest(); singleton() 是基于 emppty() 和 first() 的,这是不是说我定义的 store() 粒度还是太大了? 是不是里面还隐含了哪些基本的Operations我没挖掘出来呢?

  3. 问个问题:
    js实现list的时候
    为什么这条Invariant不用添加 :
    append(first(list), rest(list)) == list //对list的首尾两部分进行连接等于list本身
    是因为可以从
    first(append(list1, list2)) == first(list1) //对非空表list1于表list2的连接取首元素等于对非空表list1取首元素
    rest(append(list1, list2)) == append(rest(list1), list2) //对非空表list1于表list2的连接取首元素等于对非空
    推倒出来吗?如何推? 谢谢~

  4. @Marvin

    不要误导人啊。
    函数式、符号运算、类型系统、解释执行还是编译这些完全是独立的概念。
    你把他们都混淆在一起。举个例子,

    Lisp 多范式的语言
    支持函数式编程,但它其实并不是函数式语言(不论Common Lisp还是Scheme都有副作用操作),
    该语言的特点是符号运算,类型系统有些方言强,但大多都是弱的,大多支持编译和解释执行。

    Javascript 面向对象的语言
    好吧,有人说它就是伪装成C风格的Lisp。它是弱类型,支持函数式编程的多范式,支持编译但多半都是解释。
    符号运算能力不亚于Lisp,当然不够优雅。

    Haskell 纯函数式的语言
    和Lisp相比符号运算简直是弱爆了,但强类型、支持编译也支持解释执行。

    还有其他宣称的函数式语言Ocaml,Erlang, Scala, F#这些多半是强类型的支持编译也支持解释的。

  5. 文中关于类型本质那部分,那不就是《数据结构》里面一开始就提到过的ADT(抽象数据类型)嘛,并且书上的定义更加数学化。

  6. @fanhe
    是哪本《数据结构》?,我翻了下《数据结构与算法分析——C语言描述》(原书第二版)中对于List, Stack就只是定义了一些函数(接口),然而函数(接口)之间的关系却没有定义,显然LZ的Type Specification更抽象普遍(不关心内部实现),更具体(接口关系)

  7. ForgetFul :
    @fanhe
    是哪本《数据结构》?,我翻了下《数据结构与算法分析——C语言描述》(原书第二版)中对于List, Stack就只是定义了一些函数(接口),然而函数(接口)之间的关系却没有定义,显然LZ的Type Specification更抽象普遍(不关心内部实现),更具体(接口关系)

    就是这本,里面说所谓抽象数据类型,主要是指对象和对象关系,只是里面对于对象关系的描述基本等于没说。
    抽象数据类型本意就是描述数据类型的。
    其实所谓的抽象也只是一种和其他对象交互的标准/协议而已。
    文中所指的类型的本质就是一种抽象,也就是一种协议而已。
    显然,很多时候,只要遵守这个协议,内部是如何根本不用关心。

  8. @onixie
    你说我误导,今天有空,就来谈有误导的事吧。

    你举了很多语言的例子,但请注意区分,一门语言和一门语言的实现。
    不要让一个实现来代替了它背后的东西。

    一个Lisp语言的实现,支持了编译和解释,它就代表了Lisp想要的表达了吗?
    请注意,我原文中说,“现阶段的语言建立在命令式基础上”,
    本质是来讲,当今的其于指令机器并不能实现函数式理想的,
    当年也有人研究lisp机,见http://baike.baidu.com/view/3732013.htm

    你理解的误导是说我讲的和大多数人说的现实不一样。而我告诉你的是,现实存在
    的东西并不是原有东西的本质,即现实就在误导你。比如,我说的历史和历史课本
    不一样,你说我在误导你,而我会说历史课本在误导你。

    当然我们讨论的东西没有历史课本那样严重,歪曲事实。

  9. @Marvin
    目前自然中还没有找到函数式的东西,Lisp机也只是硬件模拟,按照你的想法,Lisp机也没有做到函数式理想
    其实即使在人类大脑中,计算如:
    f(x) = x + 2,
    f(f(f(f(f(f(3)))))) = ?
    的时候,也需要缓存,不会一下次得出结果

    如果用硬件实现IL指令集,JVM指令集,我们也可以做出.Net机,Java机

    还有,无关主题,我们要支持皓哥抵制baidu ;)

  10. 有几个每调一次就构造一个新对象,只是利用js的闭包特性自动记录了传入的参数,随便一个函数的调用都涉及到大量的递归和新对象的构造,好像构造对象完全免费无开销的一样,这种感觉不太好。

  11. @Marvin
    函数式=“无类型”?
    Ocaml、ML和Haskell的存在感233。。。
    ……你认为“原有”的东西是什么?如果我说类型理论独立于函数式语言之外历史不短了,你有什么见解么。
    你说的无类型指的是啥?
    如果你要说真正意义上的“无”类型,那么请先搞清楚untyped lambda calculus的局限性再说。
    如果你要说的是Lisp传统的manifest type,请不要用误导性的说法。
    如果你要说的是你的原创研究,那么请拿出内容。
    至于lisp machine嘛,别指望会有纯血统的比较好……举个实际的例子,通用图灵机很容易在O(1)时间实时计算一个程序的memory footprint,用物理上纯粹的lisp machine怎么做?而在这个层次之上的lisp machine和实现REPL从语言设计和使用的角度来看本质上难度都没太大的差别。

  12. 虽然个人觉得博主把类型本质 和函数式语言的例子放在一篇文章中讲有点唐突。
    不过对于类型的理解和这个函数式迭代器的例子真心太有启发了!!

  13. 感谢博主, 终于看懂了, 不废话, 上c++版:
    #include “tree_definition.h”
    #include
    #include
    using namespace std;

    struct List{
    function first;
    function rest;
    };

    TreeNode_p_t first(List_p_t list1)
    {
    return list1 == NULL? NULL : list1->first();
    }

    List_p_t rest(List_p_t list1)
    {
    return list1 == NULL? NULL:list1->rest();
    }

    List_p_t Empty() {
    return NULL;
    };

    List_p_t Singleton(TreeNode_p_t e) {
    List *node = new List();
    node->first = [=]()mutable{
    return e;
    };

    node->rest = [=]()mutable{
    return (List_p_t)NULL;
    };
    return node;
    }

    List_p_t Append(List_p_t list1, List_p_t list2)
    {
    if(NULL == list1) return list2;
    if(NULL == list2) return list1;

    List *node = new List();
    node->first = [=]()mutable{
    return first(list1);
    };

    node->rest = [=]()mutable{
    return Append(rest(list1), list2);
    };
    return node;
    }

    List_p_t make_inorder_tree_iterator(TreeNode_p_t node)
    {
    if(!node)
    return NULL;
    List_p_t listNode = new List();
    listNode->first = [=]()mutable {
    return NULL != node->lchild ? first(make_inorder_tree_iterator(node->lchild)) : node;
    };
    listNode->rest = [=]()mutable {
    List_p_t left_it = (NULL == node->lchild ? NULL : make_inorder_tree_iterator(node->lchild));
    List_p_t root_it = Singleton(node);
    List_p_t right_it = (NULL == node->rchild ? NULL : make_inorder_tree_iterator(node->rchild));
    List_p_t it = Append(Append(left_it, root_it), right_it);
    return rest(it);
    };
    return listNode;
    }

    List_p_t make_preorder_tree_iterator(TreeNode_p_t node)
    {
    if(!node)
    return NULL;
    List_p_t listNode = new List();
    listNode->first = [=]()mutable {
    return node;
    };
    listNode->rest = [=]()mutable {
    List_p_t left_it = (NULL == node->lchild ? NULL : make_preorder_tree_iterator(node->lchild));
    List_p_t root_it = Singleton(node);
    List_p_t right_it = (NULL == node->rchild ? NULL : make_preorder_tree_iterator(node->rchild));
    List_p_t it = Append(Append(root_it,left_it), right_it);
    return rest(it);
    };
    return listNode;
    }

    List_p_t make_postorder_tree_iterator(TreeNode_p_t node)
    {
    if(!node)
    return NULL;
    List_p_t listNode = new List();
    listNode->first = [=]()mutable {
    if(NULL == node->lchild && NULL == node->rchild)
    return node;
    return NULL != node->lchild ? first(make_postorder_tree_iterator(node->lchild)) : first(make_postorder_tree_iterator(node->rchild)) ;
    };
    listNode->rest = [=]()mutable {
    List_p_t left_it = (NULL == node->lchild ? NULL : make_postorder_tree_iterator(node->lchild));
    List_p_t root_it = Singleton(node);
    List_p_t right_it = (NULL == node->rchild ? NULL : make_postorder_tree_iterator(node->rchild));
    List_p_t it = Append(Append(left_it, right_it), root_it);
    return rest(it);
    };
    return listNode;
    }

    当然, 也可以衍生自己的iterator:
    class InorderLazyIterator : public Iterator {
    public:
    InorderLazyIterator(TreeNode_p_t node):m_list(NULL) {
    m_list = make_inorder_tree_iterator(node);
    }
    virtual TreeNode_p_t next() {
    TreeNode_p_t node = first(m_list);
    m_list = rest(m_list);
    return node;
    }
    private:
    List_p_t m_list;
    };

  14. onixie :
    @Marvin
    Haskell 纯函数式的语言
    和Lisp相比符号运算简直是弱爆了,但强类型、支持编译也支持解释执行。

    不能简单评价Haskell的符号计算能力为“弱爆”,至少在符号运算一个较常应用的领域符号求导(Symbolic Differentiation)上,Haskell可以将更先进的自动求导(Automatic Differentiation)完全的融入它的类型系统中。
    http://hackage.haskell.org/package/ad
    至少目前是我见过的最优雅的自动求导工具。

发表评论

电子邮件地址不会被公开。 必填项已用*标注