关于如何用一个无类型lamda演算写程序

iisnow

(本来也只是在书上看到了一些东西，拿出来和大家分享下，少部分原创，难免有问题)
想法是：只使用Ruby的变量引用以及proc的创建与调用来实现Ruby其他的东西
可能觉得会没有意义，但多多少少有些计算本质上的理解
(其实就是创造一种小语言，但是这种语言靠Ruby对lambda的演算实现。。。)

使用Ruby的proc：
大概了解下proc并说明下后面例子的书写规则以及一些注意事项
1.->x{x+1}.call(0)  #=>1
2.->x,y{x+y}.call(3,4)  #curry化之后为
        ->x{->y{x+y}}.call(3).call(4)
3.p 和 ->x{p.call(x)} 等价
4.后文中的proc将全部使用curry化之后的写法，并使用[]调用(代替call)
        类似于->x{->y{x+y}}[3][4] #=> 7
5.为了方便调试，会使用Ruby的功能对proc进行一定的输出       
6.在自己试验的时候，会发现实际上运行效率非常之低
        数值过大容易出现stack too deep等报错（所以尽量远离POWER）
                       
       
        1.数字常量:先仅考虑自然数(N)
                参考自然数与自然数集的定义
                        0={}=>∅,
                        1={0}=>{∅},
                        2={0,1}=>{∅,{∅}},
                        3={0,1,2}=>{∅,{∅},{∅,{∅}}}
                        .....
                定义常量
                        ZERO   = ->p{->x{        x       }}
                        ONE     = ->p{->x{       p[x]    }}
                        TWO     = ->p{->x{      p[p[x]] }}
                        .....
                       
                (N 就是对变量x进行了N次p处理的意思，和上面的定义貌似没有什么关系，
                        可能了解的人会知道，这种叫邱奇数/邱奇编码，Church encoding
                        而理解这种编码的人，可能就会很方便的理解下面的某些内容)
                为了方便调试转换，定义一个ruby的方法
                def to_int(proc)
                        proc[->n{n+1}][0]
                end                                
               
                to_int(ZERO) #=>0
                to_int(ONE) #=>1
               
        2.布尔值常量
                由于布尔值的功能一般就是选择而已，实现这种对立关系即可
                定义为
                        TRUE_ = ->x{->y{x}}
                        FALSE_ = ->x{->y{y}}
                       
                同理定义一个转换方法               
                def to_bool(proc)
                        proc[true][false]
                end
               
                to_bool(TRUE_)  #=> true
                to_bool(FALSE_)  #=> false
               
        3.流程控制
                顺序语句:沿用Ruby
                判断语句:if--else
                        IF = ->condition{
                                                ->truestatement{
                                                        ->falsestatement{
                                                                        condition[truestatement][falsestatement]
                                                                        }
                                                                }
                        这里利用了布尔值  的选择方式来完成语句控制
                        但实际上这个proc对truestatement和falsestatement都没有处理，所以就直接简化为       
                                IF = ->c{c}
                               
                                IF[TRUE_]['true']['false'] #=> "true"
                循环语句:for,while...
                        循环语句其实理论上来讲是可以迭代为判断语句的：
                                while(condition){body}    =>
                                if(condition){body,while(condition){body}} else break
                                实际上while没有处理任何内容
                                for等同理
       
        4.数值对
                提供了最最基本的数据结构
               
                PAIR = ->x{->y{->f{f[x][y]}}}
                LEFT = ->p{p[->x{->y{x}}]}
                RIGHT = ->p{p[->x{->y{y}}]}
               
                pair_ = PAIR[ZERO][TWO]
                to_int(LEFT[pair_]) #=> 0
                to_int(RIGHT[pair_]) #=> 2
               
        5.简单运算
                （参考邱奇数的含义）
                ①自增:
                        根据数字的定义
                                INCREMENT = ->n{->p{->x{p[n[p][x]]}}}
                                (即在数字的基础上再次调用一次p，注意n为数字)
                               
                                THREE = INCREMENT(TWO);
                                to_int(THREE) #=> 3
                ②自减:
                        在数字的基础上再次调用一次p很简单做到，那如何得到调用p之前的proc呢？
                        我们利用数值对，将一个数字和他增加前的数字保存起来
                        PAIR[p][INCREMENT[p]]
                       
                        为了保证迭代，定义这样一次增加为滑窗从[0,0]开始（因为在自然数集中，0之前并没有数字）
                        SLIDE = ->p{
                                PAIR[ RIGHT[p] ]
                                        [ INCREMENT[ RIGHT[p] ] ]
                                }
                        通过n次SLIDE操作，就会得到right为n的数字，同时，left就是n-1
                       
                        DECREMENT = ->n{
                                LEFT[
                                        n[SLIDE][PAIR[ZERO][ZERO]]
                                ]
                        }
                        注意n为定义的数字，而他的数值的定义就是对PAIR[ZERO][ZERO]执行多少次SLIDE
                       
                ③四则运算(伪)
                        意义自行体会
                        ADD                   = ->m{->n{n[INCREMENT[m]]}}  #或者 ->m{->n{m[INCREMENT[n]]}}  
                        SUBSTRACT = ->m{->n{n[DECREMENT[m]]}}
                        MULTIPLY    = ->m{->n{n[ADD[m]][ZERO]}}   #或者 ->m{->n{m[ADD[n]][ZERO]}}
                        除法需要一个递归要实现，暂时先不考虑
                        POWER                 = ->m{->n{n[MULTIPLY[m]][ONE]}}
                       
                        FIVE = ADD[TWO][THREE]
                        TEN = MULTIPLY[TWO][FIVE]
                        HUNDRED = POWER[TEN][TWO]
               
        6.判断
                判断一个定义的数字常量与另一个数字常量相等   等价于
                判断二者差操作与ZERO相等               
                理论上来讲，各种数字的对比均可以化归为与0的比较以及各种运算的结合
               
                我们先实现是否为0(ZERO)相等               
               
                IS_ZERO = ->n{
                        n[->x{FALSE_}][TRUE_]
                }
                (因为只有常量ZERO返回变量本身)
               
                to_bool(IS_ZERO(ZERO)) #=> true
                to_bool(IS_ZERO(TWO)) #=> false
               
                利用IS_ZERO实现是否小于等于
                IS_LESS_OR_EQUAL = ->m{->n{IS_ZERO[SUBSRACT[m][n]]}}
                这里利用了我们实现减法时候的一点小问题：2-3=0
                        所以事实上这里的SUBSRACT是这样的一种运算：SUB[x][y] = x<y ? 0 : x-y，有兴趣可以查阅monus，或者叫点差
                       
        7.布尔操作
                其他的判断方法，其实可以根据<=和==外加&&、||、！来实现
                而这些操作实际上可以通过控制语句来实现
               
                AND = ->b1{->b2{IF[b1][IF[b2][TRUE_][FALSE_]][FALSE_]}}
                OR = ->b1{->b2{IF[b1][TRUE_][IF[b2][TRUE_][FALSE_]]}}
                NOT = ->bl{IF[bl][FALSE_][TRUE_]}
               
                这样：大于、小于之类就都OK了
                IS_BIG_THAN = ->m{->n{NOT[IS_LESS_OR_EQUAL[m][n]]}}
               
        8.递归
                递归问题的引入在实现求模运算时出现
                        根据模数的定义
                        MOD = ->m{->n{IF[IS_LESS_OR_EQUAL[n][m]][MOD[SUBSTRACT[m][n]][n]][m]}}
                        (其实就是
                                def mod(m,n)
                                        if(n<=m)
                                                mod(m-n,n)
                                        else
                                                m
                                        end
                                end)
                        使用这个mod的方法自然没有问题，
                        但是对于proc，这种递归形式的调用会在Ruby对proc内部求值的时候进入无限循环
                        虽然可以利用proc的等价原则（p 和 ->x{p[x]} 等价）,避免这个问题
                               
                        MOD = ->m{->n{IF[IS_LESS_OR_EQUAL[n][m]][->x{MOD[SUBSTRACT[m][n]][n][x]}][m]}}
                        这样，在IF的truestatement中，Ruby就没有必要返回一个值，而是一个->x{p[x]}的proc，
                        然后再被求值就没有问题了。
                       
                        但是实际上这种使用本身给自己定义的方式并不是运算时候真正的操作，
                        毕竟用f = g(f)这种只能算是一种通项式，f应该是有他的最简式的
                       
                这种递归的例子，我们引入这个算子代替
                Z = ->f{->x{f[->y[x[x][y]]]}[->x{f[->y{x[x][y]}]}]}
                （实际上他本来的式子是：->f{->x{f[x[x]]}[->x{f[x[x]]}]},引入了y进行了等价转换）
                意义请自行解析后体会，实际上就是将proc本身作为proc的第一个参数调用的意思
               
                MOD = Z[->f{->m{->n{IF[IS_LESS_OR_EQUAL[n][m]][->x{f[SUBSTRACT[m][n]][n][x]}][m]}}}]
               
                to_int(MOD[TEN][TREE]) #=>1
               
        9.除法的实现
                上面提到了除法需要递归实现，现在我们有了递归的方法，那么怎么实现除法呢
                整数的除法大致为
                def div(m,n)
                        if(n<=m)
                                div(m-n,n)+1
                        else
                                0
                        end
                end
               
                DIV = Z[->f{
                        ->m{
                                ->n{
                                        IF[IS_LESS_OR_EQUAL[n][m]][
                                                ->x{
                                                        INCREMENT[f[SUBSTRACT[m][n]][n]][x]
                                                }
                                        ][ZERO]
                                }
                        }
                }]
       
        10.List的实现
                利用PAIR的结构以及利用链表的想法实现一个可变长的数字数组，就称之为列表会好一点
                我们通过左节点的布尔值元素判断数组的开始
               
                EMPTY     = PAIR[TRUE_][TRUE_]
                UNSHIFT  = ->l{->x{PAIR[FALSE_][PAIR[x][l]]}}   #向l列表的首位添加x，并将左节点置为FALSE_标记
               
                IS_EMPTY = LEFT
               
                FIRST = ->l{LEFT[RIGHT[l]]}                #因为第一个Left为标识位，Right才是数据
                REST = ->l{RIGHT[RIGHT[l]]}
               
                list = UNSHIFT[UNSHIFT[UNSHIFT[EMPTY][ONE]][THREE]][FIVE]
               
                to_int(FIRST[REST

]) #=>3
                #考虑下
                to_int(FIRST[REST[REST
]])   #=>会是多少
               
                为了方便调试，定义一个转成array的方法
                def to_array(proc)
                        arr = []
                        until to_bool(IS_EMPTY[proc])
                                arr.push(FIRST[proc])
                                proc = REST[proc]
                        end
                        arr
                end       
               
                这样就有一个个的proc构成的arr了
                而打印就使用
               
                to_array(list).map{|p| to_int(p)}  #=>[5,3,1]
       
        11.字符串常量
                字符常量的实现应该一开始就完成的，
                但是事实上由于字符串本就是字符的数组，故实现数组后我们再讨论的这个
               
                对于字符，我们需要实现的只是编码而已，即字符与数值常量的对应
                并且也没有必要一定是ASCII之类的，我们自己定义一个就好了

                R = TEN  
                #这样的话，‘0’-‘9’就方便的对应了0-9，
                #也就是说ONE 就是 ‘1’,这样单个的数字就不需要to_s就已经是对应的字符本身了
                U = INCREMENT[R]
                B = INCREMENT[U]
                Y = INCREMENT[B]
                M = INCREMENT[Y]  
                等等
               
                而字符串的话就
                RUBY = UNSHIFT[UNSHIFT[UNSHIFT[UNSHIFT[EMPTY][Y]][B]][U]][R]
               
                为了方便显示这个“字符串”
                def to_char(c)
                        '0123456789Rubym'.slice(to_int(c))
                end
               
                def to_string(s)
                        to_array(s).map{|c| to_char(c)}.join
                end
               
                SIX = INCREMENT[FIVE]
                EIGHT = POWER[TWO][THREE]
                NINE = INCREMENT[EIGHT]
                month = UNSHIFT[UNSHIFT[UNSHIFT[UNSHIFT[EMPTY][EIGHT]][TWO]][M]][NINE]
                date = UNSHIFT[UNSHIFT[UNSHIFT[UNSHIFT[UNSHIFT[month][Y]][SIX]][ONE]][ZERO]][TWO]

                to_char(TWO) #=>"2"
                to_string(RUBY)  #=>"Ruby"
                to_string(date)  #=>"2016y9m28"
       
        12.范围的实现
                对于for循环，我们将for var in range转化为了while
                但是实际上这个range要怎么转化呢
               
                range转为数组的方法大致如下
                def range(m,n)
                        if m<=n
                                range(m+1,n).unshift(m)
                        else
                                []
                        end
                end
                没错就是熟悉的递归方式
               
                所以实现的方式自然就是
                RANGE = Z[->f{
                                ->m{
                                                ->n{
                                                        IF[IS_LESS_OR_EQUAL[m][n]]
                                                                [->x{
                                                                        UNSHIFT[
                                                                                f[INCREMENT[m]][n]
                                                                        ][m][x]
                                                                }
                                                                ][EMPTY]
                                                                }
                                                        }
                                                }]
                                               
                to_array(RANGE[ONE][HUNDRED]).map{|p| to_int(p)}  #=>[1,2,3,4,.....,99,100]
                (可能耗时会很长)
       
        13.递归的避免
                RANGE的实现利用了递归Z算子，其实也可以利用我们定义数字的含义去定义
               
                参考这个方法
                def count(pair)
                        [pair.first.unshift(pair.last),pair.last-1]
                end
               
                count([[],10]) #=>[[10],9]
                count(count([[],10])) #=>[[9,10],8]
                ...
               
                count的运行次数用定义数来弄就好了
                COUNT = ->p{PAIR[UNSHIFT[LEFT[p]][RIGHT[p]]][DECREMENT[RIGHT[p]]]}
                RANGE = ->m{->n{LEFT[INCREMENT[SUBSTRACT[n][m]][COUNT][PAIR[EMPTY][n]]]}}
               
                (其实就是运行n-m+1次count得到结果的left)
       
        14.map的实现
                我们观察到了to_arr(list).map{|p| to_int(p)}中的map方法
               
                对于Enumerable类的实现的map
                我们转化为一种复写的操作，即遍历内每一个元素执行指定运算后，将结果统一push到一个组中
                最终返回这个新的组，这种形式的操作自然会想到inject
                大致想法：
                        def map(list,proc)
                                list.inject([]){|relist,ele| relist.push(proc(ele))}
                        end
                       
                这里我们先来实现inject操作
                实际上inject也就是一个简单的递归而已,不断取list的首位进行运算
                INJECT = Z[->f{
                                ->l{
                                                ->x{
                                                        ->g{
                                                                IF[IS_EMPTY[l]][x][
                                                                        ->y{
                                                                                g[f[REST[l]][x][g]][FIRST[l]][y]
                                                                        }
                                                                ]
                                                        }
                                                }
                                }
                        }]                #这里使用了y变量等价转换了一次，g为inject的proc参数
                       
                所以
                MAP = ->l{
                        ->f{
                                INJECT[l][EMPTY][
                                        ->k{
                                                ->x{
                                                        UNSHIFT[k][f[x]]
                                                }
                                        }
                                ]
                        }
                }               
               
                aflist = MAP[RANGE[ONE][FIVE]][ADD[TWO]]
                to_array(aflist).map{|p| to_int(p)}  #=>[3,4,5,6,7]
               
        15.List的push实现
                在list的末尾添加元素，使用INJECT方法
               
                PUSH = ->l{
                        ->x{
                                INJECT[l][UNSHIFT[EMPTY][x]][UNSHIFT]
                        }
                }
               
        16.数值to_s的实现
                这个我们经常使用的功能，是如何实现的，我们大致描述下
                def to_s_pre_(n)
                        pre_n =
                                if n<=9
                                        []
                                else
                                        to_s_pre_(n/10)
                                end
                        pre_n.push(n%10)
                end
                这一步将数值转为一个个数值的数组，根据编码to_char，然后join就OK了
               
                TO_NUM_ARR = Z[->f{
                        ->n{
                                PUSH[
                                        IF[IS_LESS_OR_EQUAL[n][NINE]]
                                        [EMPTY][
                                                ->x{
                                                        f[DIV[n][TEN]][x]
                                                }
                                        ]
                                ][MOD[n][TEN]]
                        }
                }]
                这个就实际上已经是to_s的实现了(因为字符串就是字符的数组，而我们的数字就是字符本身)
               
                to_string(TO_NUM_ARR[POWER[TWO][EIGHT]])  #=>"256"
                (这个例子比较耗时)
               
               
        END：
                肯定会有人说这文章是不是有毛病之类的，其实写这个，或者说分享这个东西是因为
               
                1.方便大家撞壁
                        想象一下把
                        def add2(x)
                                x+2
                        end
                        y = add2(1)
                       
                        改成
                        num = ->p{->x{p[x]}}
                        add2 = ->m{->n{n[->n{->p{->x{p[n[p][x]]}}}][m]}}[->p{->x{p[p[x]]}}] #相信应该都知道做了什么
                        add2[num]
                        然后暗示下
                        def to_int(proc)
                                proc[->n{n+1}][0]
                        end
                       
                2.好吧，上一个理由是我瞎说的，大家也别当真，也不要真的这样弄
                        本来这里使用的很多想法都是化简为繁，并不符合图灵的思想，
                        但是这些内容还是希望能在计算理论方面想给大家一点启示，
                        说不定某些神，看过这个后，再去读读那些年完全读不懂的汇编原理，
                        就可以给予语言上的创新，甚至创造语言呢是吧
                       
                3.其实大家完全可以把1、2的理由当玩笑，就当看看脑筋急转弯就好了
                        然后大家试试实现一些文中没有提到的东西，开开思维就好了
                       
                       
最后附上一些代码,有啥问题自己想吧,不要问我，最近烦心事有点多               

shitake

具体可参考丘奇数和LISP

taroxd

《Understanding Computation》