治疗白癜风费用 https://jbk.39.net/yiyuanfengcai/zn_bjzkbdfyy/本文的主要目的就是在C中实现一个基于lambda演算的编程语言,例如Lisp。在学习了相关知识和评估了可行性之后,我们尝试使用少于行C代码来实现Lisp。#includestdio.h#includestdlib.h#includestring.h标准头文件:stdio.h提供printf和puts,getchar从stdin中提取字符。stdlib.h提供calloc在程序运行时动态分配内存。string.h提供strcmp来比较两个字符串,strdup为字符串做副本。#definedebug(m,e)printf("%s:%d:%s:",__FILE__,__LINE__,m);print_obj(e,1);puts("");这个debug宏用于在程序无法工作时帮助排除故障,还可以添加一行debug(evaluating,exp),以可读形式打印出文件,行号,消息和Lisp表达式表示。typedefstructList{structList*next;void*data;}List;该List结构是用来表示代码和数据的基本数据结构。它是一个带有两个指针的单向链表:next指向列表中的下一个项目,data指向符号或另一个列表结构。data可以投到一个char*或一个List*。List*symbols=0;全局变量symbols表示符号列表的头部。当符号被解析时,我们将在符号列表中查找它,如果它不在那里,我们将添加它。这样我们可以使用等号比较运算符"=="来比较两个符号。当Lisp程序中重复多次使用相同的符号时,它会节省存储空间,不过,如果电脑中有8GB的RAM内存则不需要额外注意节省空间。staticintlook;/*lookaheadcharacter*/staticchartoken[32];/*token*/由于符号可以包含多个字符,因此遇到不属于符号的字符时,我们会将其改变为一个完整的符号。非符号字符包括空白符(空格,制表,换行等和语法字符,如括号()。为了确定符号是否已经到达,我们需要向前看一个字符。look变量存储就是向前看一个字符,如果这个字符包含一个非符号字符,那么就停止阅读这个符号。token变量是一个字符数组存储从输入读出的当前符号。请注意,token的大小为32,因此符号的最大长度将是31个字符,token是一个NULL终止字符串,所以标记始终以字符。#defineis_space(x)(x==
x==)#defineis_parens(x)(x==(
x==))上面的两个宏实主要是为了可读性和程序的可维护性和可扩展性。is_space,如果该字符是空格或换行符,则返回true。is_parens如果该字符是括号,则返回true。staticvoidgettoken(){intindex=0;while(is_space(look)){look=getchar();}if(is_parens(look)){token[index++]=look;}else{while(look!=EOF!is_space(look)!is_parens(look)){token[index]=;函数gettoken负责从标准输入中读取字符,并确定是否发现括号或符号。首先它将跳过所有空格。如果look变量是括号,则将其存储在token输入流中的下一个字符中look。如果不是括号,则认为它属于一个符号。继续向前看并保存字符,直到EOF到达文件末尾,或者look是空格或括号。index将当前位置存储在token数组中,以便每次存储符号所属的字符时增加该位置。最后,令牌被终止。#defineis_pair(x)(((long)x0x1)==0x1)/*tagpointertopairwith0x1(alignmentdependent)*/#defineuntag(x)((long)x~0x1)#definetag(x)((long)x
0x1)List结构中,data指针既可以是char*,也可以是List*其它列表。我们指示指针类型的方法是通过设置指针上的最低位。例如,给定一个指针指向的地址0x100230,如果是一对,我们将用一个位或1来修改这个指针,这样地址就变成0x100231。这种修改指针方式的问题在于如何将普通未标记的地址传递给标记为1的指针。很多计算机系统和操作系统为了性能优化,会在设定的边界上分配内存,这被成为内存对齐。如果以8位边界为例,这意味着当内存被分配时,它的地址将是8的倍数。例如,地址0x100230的下一个是0x100238。内存也可以对齐到16位,32位。通常,它在machineword上对齐,这意味着如果你有32位的CPU和总线,也意味着是32位对齐。更多内容可以查看:。实际上,每当我们调用calloc时,总会得到一个地址(0),这样我们就可以设置它。如果地址是一对,is_pair将返回非零值(这意味着我们需要取消最低的位来获得地址)。它使用一个位和1来确定这个。untagmacro以位和1的补码切换最低位。tagmacro改变最低位或1。#definecar(x)(((List*)untag(x))-data)#definecdr(x)(((List*)untag(x))-next)在典型的Lisp/Scheme中有两个基本操作,car返回一个头部列表,cdr返回尾部列表。它们是以IBM计算机上的操作命名的,具体信息可以查看。#definee_truecons(intern("quote"),cons(intern("t"),0))#definee_false0e_true和e_falsemacro是用于在实现中便利定义真假,基本上非零代表是真的,如果他们所拥有的价值能够以人类可读的形式打印出来,那将会有所帮助。List*cons(void*_car,void*_cdr){List*_pair=calloc(1,sizeof(List));_pair-data=_car;_pair-next=_cdr;return(List*)tag(_pair);另一个Lisp/Scheme基本操作是cons,它构造了一对指针,List结构中包含data指针和next指针。具体可查看: