如何用汇编语言实现lisp？

Question

许多(可能都是？)编程语言由汇编语言组成

如何用汇编语言实现lisp？

谷歌有什么好的参考,手册,教程或关键词？

用于构建自己的lisp实现的任何官方规则/约定？

如尾递归应遵循一些实施例规则或其他东西..

谢谢

Answer 1

虽然其他评论和帖子都是正确的,但这个问题过于模糊,可能有点困惑,我不禁分享一些建议.我已经收集了许多关于实现Lisp的链接和书籍,因为我最近对语言实现有点着迷.当然,这是一个很深刻的话题,但阅读与Lisp相关的内容特别引人注目,因为如果在Lisp中实现Lisp编译器或解释器,并且只是使用,那么你可以跳过很多关于解析的强烈阅读read.这使作者能够快速掌握编辑或解释的内容.这些建议是我读过或开始或正在阅读的书籍,主要涉及Scheme,而不是Common Lisp,但仍有一些兴趣.

如果你没有语言实现的背景,并且从未有过阅读有关经典Lisp和Scheme"metacircular evaluationators"的乐趣,我会推荐计算机程序的结构和解释.如果您已经看过Lisp-in-Lisp(或Scheme-in-Scheme ...),您可以跳过.在SICP的最后两章中,作者为Lisp/Scheme和一些变体提供了一些不同的解释器,以及字节码编译器和虚拟机.它只是一本精彩的书,而且是免费的.

如果您没有时间阅读SICP,或者只是为了进入解释和编译章节而不想轻松阅读,我会推荐The Little Schemer.尽管它很短,并且适用于Lisp和Scheme的新手,如果你从未见过用Lisp编写的Lisp解释器,它们确实提供了一本,这本书非常令人愉快,但由于可爱的风格,可能不适合所有人.

还有另一本关于Scheme的免费书,类似于SICP,称为"方案简介及其实现",我没有阅读,但作为几位的参考.那里有关于解释器和编译器的部分,它似乎比SICP更深入,处理像解析一样的毛茸茸的东西.它可能需要一个编辑器,但它仍然是一个令人印象深刻的产品.

有了如何在Lisp中使用Lisp的理解,你可以在较低级别实现Lisp.

经常推荐Lisp in Small Pieces.我已经阅读了大部分内容,并且可以说它绝对是一本很棒的书,充满了细节.我正用精梳梳理它,因为当你不懂东西时很容易撇去它.我也很努力地从作者的网站上获取代码来运行; 如果你得到它,我建议使用开局计划和运行依赖于Meroonet与Meroon,从代码这个分布.Lis Pie in Small Pieces提供了一些用Scheme编写的解释器,以及一个字节码编译器和一个编译器到C语言.

Lisp in Small Pieces移动速度很快,而且非常密集.如果对你来说太过分了,也许可以从编程语言要点开始.我已经阅读了一些内容并且它非常好,但它更多的是解释器.显然其中一个旧版本(第一个？我不确定......)包括一个编译器.这三个版本之间似乎有很多变化,但第一个版本在亚马逊上非常便宜,所以请查看.

至于编译为C,这是一个有很多毛茸茸的重要主题.编译到C会带来所有这些奇怪的角落问题,例如如何优化尾调用和句柄闭包,一流的延续和垃圾收集,但它非常有趣,而且很多"真正的"Scheme实现都是这条路线.Marc Feeley对此的介绍非常有趣,名为The 90 Minute Scheme to C编译器.

我在编译到汇编时的资源较少,但是有一篇经常被推荐的文章介绍了Scheme到x86的编译,称为编译器构造的增量方法.它假定读者很少,但我发现它只是过快而且没有填写足够的细节.也许你会有更好的运气.

上面的很多建议来自一年多前来自mahmud的关于黑客新闻的怪物评论.它引用了许多ML资源,并使用continuation进行编译.在我的学习中我没有那么远,所以我不能说什么是好的.但这是一个非常有价值的评论.参考作品包括Andrew Appel的"Compiling with Continuations"和Paul Wilson的"Uniprocessor Garbage Collection Techniques"论文.

祝好运!

Answer 2

我过去曾想过它(然后使用C内核).当然没有单一的"组装",但对于x86/32bit,这就是我的计划:

基本值存储在64位节点中,其中三个最低位用作标记,含义如下:

000 -> cell (64 bits are basically two pointers: car/cdr)
001 -> fixnum (64-3-1 bits usable for values)
010 -> vector (32-3 bits for size and 32 bit for pointer to first element)
011 -> symbol (32 bits pointing to values in global env, 32 pointing to name)
100 -> native code (32 bits pointing to executable machine code, 32 bits to args)
101 -> float (using 64-3-1 bit by dropping 4 bits from mantissa)
110 -> string (using 32-3 bits for size and 32 bits pointing to bytes)
111 -> struct (32 bits pointing to definition, 32 bits pointing to content)

如果假设所有分配都是8字节的倍数(合理的,单元大小为8字节),则在考虑指针时仍可使用3位.实现一个简单的垃圾收集器("活动"位)需要一个额外的位.在C实现中,我最终根据节点类型在各个部分(例如,如果是指针的高32位的最低有效位)中分配该位.

我的想法是拥有两种类型的存储器:"节点存储器"(具有上述布局),它在页面中分配并与空闲列表一起重用,"二进制存储器"用于可变大小的字符串/代码/数组.

根据节点类型需要特定代码以实现touch递归地标记为由活动节点引用的活动节点的功能.

所有这些当然只是一种天真的方法,但我仍然在"C"中工作,我确信我也可以在汇编中完成(我的C代码在void *任何地方使用,所以基本上只是一个便携式32位汇编程序).对于我的C实现中的惰性,我只使用32位浮点数和整数(使用更高的32位)而不是使用所有可用位.

Answer 3

查看Clozure Common Lisp,了解用于实现lisp的汇编语言示例.Clozure CL主要在Common Lisp本身中实现,但是有一个用C编写的内核和一些用于汇编的低级功能.

例如,这是一个来自compiler/X86/x86-lapmacros.lisp的宏,它CAR在x86硬件上实现了一个原始函数,其中一个汇编指令分别为32位和64位:

(defx86lapmacro %car (src dest)
    (target-arch-case
       (:x8632
          `(movl (@ x8632::cons.car (% ,src)) (% ,dest)))
       (:x8664
          `(movq (@ x8664::cons.car (% ,src)) (% ,dest)))))

如图所示,汇编代码本身以Lisp形式编码.移植到另一个平台涉及(除其他外)将这些低级操作转换为另一种汇编语言并交叉编译以在新平台上创建运行时.

ECL(Embeddable Common Lisp)通过编译成C来采用另一种方法.这使得将实现移植到具有C编译器的平台变得方便.