1.内容概览
前四章：介绍了基本的数据结构，atom，list，s-expression；基本的函数原语，primitive。
第五章<Oh My Gawd*：It's Full of Starts>：讲的是如何在nested list中对所有的atom进行操作。即所谓的高阶函数。
第六章：四则运算及其他一些基本运算。四则运算的本质都可以用递归加上add1,sub1来实现。
第七章：集合及其相关操作。
---------------------------------------------------------------------------
以上部分的内容都是比较简单和繁琐。接下来的才是精华。
第八章：collector funciton(即continuation)。Continuation Passing Style。
continuation是一种函数调用机制。我们熟悉的函数调用方法一般是采用栈帧(Stack Frame）来记录从顶层函数到当前函数的所以context。
而continuation不采用堆栈来保存上下文。网上关于continuation中介绍不少，说它不同于栈的先进后出的线性管理contexts的方式，而是采用图和树来管理context。这样的好处就是可以从图中任意一个context节点跳到另一个context节点？这个我没有深入研究了。
little schemer这本书中只提到continuation在递归中的作用。在原函数递归层次间传递一个collector函数，而根据本次原函数的执行结果，通过复杂化collector函数的参数从而实现保存了本次函数执行的context。
第九章：partial function（，which may recurse enternally）。所以我们找一个funcion（will-end），来判断任意function是否为partial function。但will-end是违背哥德尔不完全定理的。这个就是计算逻辑中著名的停机测试悖论（类似的有停机问题，理发师悖论）。
接下来，书中讲到了Y-combinator及其证明。Y-combinator用于构建递归。
第十章：
Schemer的解释器（Interpretor）。可以解释（func（必须是用lambda直接表示的func，而不能只是一个funcname）,realarg1,realarg2....）之类的表达式。Intrepretor会最终将源码翻译成（primitive_func realarg1,realarg2,...)。而primitive_func是内置的，从而得到结果。从而最终得到程序结果。
2.递归的实现
由于lambda函数都是没名字的，无法自己内部调用自己。我们需要Y-combinator来实现递归，让我们以power(n)函数为例：
1)lambda n. If_Else n==0 1 n*<self>(n-1)
2)let F = lambda n. IF_Else n==0 1 n*F(n-1)看上去不错，是吗？可惜还是不行。因为let F只是起到一个语法糖的作用，在它所代表的lambda表达式还没有完全定义出来之前你是不可以使用F这个名字的.
3)把<self>参数化，构造伪递归函数：let P=lambda self n. If_Else n==0 1 n*self(n-1)
P(P,n)=n*P(n-1)。而P(n-1)错误。有两种4),5)补救方法。
4)<self>应该有两个参数：
let P = lambda self n. If_Else n==0 1 n*self(self, n-1)
5)想法去掉self(self,n)中的self
还是让let P = lambda self n. If_Else n==0 1 n*self( n-1)
干脆我们假设出一个“真正”的递归阶乘函数：power(n)。而只要我们把这个真正的阶乘函数传给P就可算出真的阶乘
P(power,n)=power(n)
=>P(power,)=power(,) power是P的不动点。而不动点是唯一的？？
6)如何通过P找到power？
let power_gen = lambda self. P(self(self))
P(power_gen(power_gen))=power_gen(power_gen) ！
7)Y combinator
let Y = lambda F.
let f_gen = lambda self. F(self(self))
return f_gen(f_gen)
所以只要提供类似P的伪递归函数F，我们就能通过Y combinator得到我们所需的真正的递归函数。
3.scheme解释器源码
原文中的scheme解释器是用scheme来实现的。原书中的解释器的执行代码和被解释的scheme代码混在一起，而且两者又是同一种格式，令人容易混淆。所以我用python改写实现了一下书中的scheme解释器。
解释过程：
s为带解释的代码。
value(s)->meaning(s,..)->expression_to_action(根据文本代码的头一个元素判断代码的类型(type)，然后决定采用和action）->_XXX函数
1）如果代码类型是*application：则调用apply函数执行代码；
2）如果代码非*application：则返回代码所代表的数据；
3) apply 分 执行primitive函数（解释器原生函数）和non-primitive函数（用户定义函数）两种情况。在上行2）中，解释器会给函数名加上primitive和non-primitive前缀，来指示解释器来进一步apply响应代码。
最后apply执行的代码格式为：
(primitive primitive-name) (args..)
(no-primitive (table formals body) ) (args..)
#(table formals body)被称为闭包closure。closure中的formals会和外部的args被成对地填入table中，用于保存实参信息。然后body中的各部分则将继续被解释器层层解 析。同时形参也会根据table被解析为实参。被解释和body连同实参一起再次被传给apply。如此循环。直到被解释为primitive函数时，从而代码最终被执行。
#By Binyaun: in order to distinguish scheme parentheses(brackets) from python brackets,we use m(..) instead.
#Schme example:
#(f a b)
#f <=> (lambda(x,y)(cons x,y))
# result:(a b)
#DESING: We use '[' and ']' to represent '(' and ')' in scheme
#And function 'value' is the interpretor
#f=[lambda,[x,y],[cons,a,b]]
#list=[f,a,b];
#value(list)
#Output:
#[a,b]
import types
import exceptions
def isAtom(a):
if type(a)==type([]):
return False
else:
return True
def isNumber(a):
try:
int(a)
return True
except exceptions.ValueError:
return False
def atom_to_action(exp):
if isNumber(exp):
return '_const'
elif exp=='#t':
return '_const'
elif exp=='#f':
return '_const'
elif exp=='cons':
return '_const'
elif exp=='cdr':
return '_const'
elif exp=='car':
return '_const'
elif exp=='add1':
return '_const'
elif exp=='lenth':
return '_const'
elif exp=='null?':
return '_const'
elif exp=='lambda':
return '_lambda'
#The 'print' is for test
elif exp=='print':
return '_const'
else:
return '_identifier'
def list_to_action(exp):
if len(exp)==0:
return '_void'
first=exp[0]
if isAtom(first):
if first=='quote':
return '_quote'
elif first=='lambda':
return '_lambda'
elif first=='cond':
return '_cond'
#if the list is just a list of numbers without function ahead
elif isNumber(first):
return '_consts'
else:
return '_application'
else:
return '_application'
def expression_to_action(exp):
if isAtom(exp):
return atom_to_action(exp)
else:
return list_to_action(exp)
# Core function.It turns texual code strings into excutable functions
def meaning(e,table):
if len(e)==1:
e=e[0]
return globals()[expression_to_action(e)](e,table)
def _void(e,table):
return []
def _const(e,table):
if isNumber(e):
return e
elif e=='#t':
return '#t'
elif e=='#f':
return '#f'
else:
return ['primitive',e]
def _consts(e,table):
if(len(e)==1):
return [_const(e[0],table)]
else:
return [_const(e[0],table)]+_consts(e[1:],table)
def _quote(e,table):
return e[1]
def evcon(lines,table):
if lines[0][0]=='else':
return meaning(lines[0][1],table)
elif meaning(lines[0][0],table)=='true':
return meaning(lines[0][1],table)
else:
return evcon(lines[1:],table)
def _cond(e,table):
return evcon(e[1:],table)
def init_table(name):
return []
def lookup_in_entry_help(name,names,values,entry_func):
#print 'entry_func(name): ',
#print entry_func,
#print '(',
#print name,
#print ')'
#print 'names: ',
#print names
print 'values',
print values
if names==[]:
return entry_func(name)
#return
if names[0]==name:
if len(values)==0:
return []
return values[0]
else:
return lookup_in_entry_help(name,names[1:],values[1:],entry_func)
def lookup_in_entry(name,entry,entry_func):
return lookup_in_entry_help(name,entry[0],entry[1],entry_func)
def lookup_in_table(name,table,table_func):
if table==[]:
return table_func(name)
else:
return lookup_in_entry(name,table[0],value(['lambda','name',lookup_in_table(name,table[1:],table_func)]))
def _identifier(e,table):
return lookup_in_table(e,table,init_table)
def _lambda(e,table):
# local variable can't be returned as following
#ret[0]='non-primitive'
#ret[1]=[table]+e[1:]
#return ret
return ['non-primitive',[table]+e[1:]]
def evlis(args,table):
#print "EVLIST: ",
#print args
if args==[]:
return []
elif len(args)==1:
return [meaning(args[0],table)]+evlis([],table)
else:
return [meaning(args[0],table)]+evlis(args[1:],table)
def isPrimitive(l):
if l[0]=='primitive':
return True
else:
return False
def isNonPrimitive(l):
if l[0]=='non-primitive':
return True
else:
return False
#applay has been a built-function in python,so apply2 identifier is used instead
def apply2(fun,vals):
print "Apply func: ",
print fun,
print(vals)
if isPrimitive(fun):
return apply_primitive(fun[1],vals)
elif isNonPrimitive(fun):
return apply_closure(fun[1],vals)
def apply_primitive(name,vals):
if name=='cons':
return doCons(vals)
elif name=='car':
return doCar(vals)
elif name=='cdr':
return doCdr(vals)
elif name=='add1':
return doAdd(vals)
elif name=='lenth':
return doLenth(vals)
elif name=='print':
#The following line are for python3
#print("PRINT:", end=" ")
print "PRINT: ",
return vals[0]
#..................
#..................
elif name=='null?':
return isNull(vals[0])
else:
return "primitive command "+name+" can't be found"
def doCar(vals):
if len(vals)!=1:
return
else:
return vals[0][0]
def doAdd(vals):
return int(vals[0])+1
def doCdr(vals):
if len(vals)==0:
return
elif len(vals[0])==1:
return []
else:
return vals[0][1:]
def doCons(vals):
return vals
def isNull(val):
if val==[]:
return 'true'
else:
return 'false'
def apply_closure(closure,vals):
return meaning(closure[2],[[closure[1],vals]]+closure[0])
def _application(e,table):
if len(e)==1:
return apply2(meaning(e[0],table),evlis([],table))
else:
return apply2(meaning(e[0],table),evlis(e[1:],table))
def value(e):
return meaning(e,[])
def doLenth(l):
if len(l)==0:
return 0
else:
return len(l[0])
#(define Y_combinator
#(lambda(le)
#((lambda (f) (f f))
#(lambda (f)
#(le (lambda (x) ((f f) x)))`
#))))
def Y_combinator(pseudo_func):
return ['lambda',pseudo_func,[['lambda',['f'],['f','f']],['lambda',['f'],[pseudo_func,['lambda',['x'],[['f','f'],'x']]]]]]
#return [['lambda','f',['f','f']],['lambda','f',[pseudo_func,['lambda','x',[['f','f'],'x']]]]]
if __name__=="__main__":
#test
print("***********assistant function test*************")
print(atom_to_action('a'))
print(isAtom('a'))
print(isAtom(['a','b']))
print(isNumber('1234'))
print(isNumber('abcd'))
print(list_to_action(['a','b']))
print(expression_to_action('a'))
print(expression_to_action(['a','b']))
print("***************application test**************")
print(value(['print','12']))
print(value(['print',['quote','abcde']]))
print(value([['lambda',['x','y'],['cons','x','y']],['quote','a'],['quote','b']]))
print("***************lambda test*******************")
f=['lambda',['x','y'],['cons','x','y']]
print(value(f))
aList=[f,'1','2']
print(value(aList))
print("***************cond test*********************")
#Let's make up a exmaple isNull_cond_test to test cond
#IN SCHEME code :
#(define isNull_cond_test
#(lambda(x)
#(cond
#((null? x) (print (quote YES)))
#(else
#(print (quote NO)))
#)))
firstClause=[['null?','x'],['print',['quote','YES']]]
elseClause=['else',['print',['quote','NO']]]
isNull_cond_test_body=['cond',firstClause,elseClause]
isNull_cond_test=['lambda',['x'],isNull_cond_test_body]
print(value([isNull_cond_test,[]]))
print(value([isNull_cond_test,['1','2']]))
print("***************primitive test****************")
print(value(['1']))
print(value(['1','2']))
print(value([]))
print(value('cons'))
print(value(['cons']))
print(value(['quote','a']))
print(value(['cons','1','2']))
print(value(['car',['1','2']]))
print(value(['car',[['quote','a']]]))
print(value(['null?',[]]))
print(value(['null?',['1','2']]))
print(value(['car']))
print(value(['cdr']))
print(value(['cdr',['1','2']]))
print(value(['add1','123']))
print(value(['lenth',['1','2','3','4']]))
print(value(['lenth',[]]))
print("***********func as parameter test************")
wrapper=['lambda',['func','arg'],['func','arg']]
testWrapper=[wrapper,'lenth',['1','2','3','4']]
print(value(testWrapper))
#realization of recursion
print("********recursion /Y-combinator test**********")
#Let's define our pseudo-lenth
#(define pseudo-lenth-func
#(lambda (list,self_func)
#(cond
#((null?list) 0)
#(else (add1 (self_func (cdr list))))
#)))
firstClause=[['null?','list'],0]
elseClause=['else',['add1',['self_func',['cdr','list']]]]
pseudo_lenth_func_body=['cond',firstClause,elseClause]
pseudo_lenth_func=['lambda',['list','self_func'],pseudo_lenth_func_body]
print(value(pseudo_lenth_func))
real_lenth_func=Y_combinator(pseudo_lenth_func)
print(value(real_lenth_func))
#The program hasn't pass Y-combinator test yet
#print(value([real_lenth_func,['1','2','3','4']]))