当前位置：文江博客话题详情

lisp是如何用汇编语言实现的？

发布于 2024-11-04 20:59:40 字数 161 浏览 0 评论 0原文

许多（可能是全部？）编程语言由汇编语言组成，

lisp如何用汇编语言实现？

谷歌有什么好的参考、手册、教程或关键字吗？

有什么官方规则/约定来构建你自己的 lisp 实现吗？

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

谢谢

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

假面具 2024-11-11 20:59:40

虽然其他评论和帖子是正确的，但这个问题过于模糊，可能有点混乱，我忍不住分享一些建议。我收集了许多关于实现 Lisp 的链接和书籍，因为我最近对语言实现产生了一些兴趣。当然，这是一个深入的话题，但是阅读与 Lisp 相关的内容尤其引人注目，因为如果您在 Lisp 中实现 Lisp 编译器或解释器，并且只使用 read.这使得作者能够快速进入编译或解释的核心。这些推荐是我已经读过、开始读或正在读的书，大部分涉及Scheme，而不是Common Lisp，但仍然可能会引起一些兴趣。

如果您没有语言实现方面的背景，并且从未有幸阅读经典 Lisp 和 Scheme“元循环求值器”，我会推荐计算机程序的结构和解释。如果您已经看过 Lisp-in-Lisp（或Scheme-in-Scheme...），您可以跳过。在 SICP 的最后两章中，作者介绍了几种不同的 Lisp/Scheme 解释器和一些变体，以及字节码编译器和虚拟机。这简直是一本精彩的书，而且免费。

如果您没有时间阅读 SICP，或者不想仅仅为了了解解释和编译章节而费力地阅读它，我会推荐小阴谋家。尽管它很短并且是为 Lisp 和Scheme 的新手准备的，但如果你从未见过用 Lisp 编写的 Lisp 解释器，他们确实提供了一个，而且这是一本相当令人愉快的书，但由于可爱的风格，可能并不适合所有人。

还有另一本类似于 SICP 的免费书籍，名为 Scheme 及其实现简介，我没有读过，但作为一些参考。那里有关于解释器和编译器的部分，它似乎比 SICP 更深入一些，还处理一些更棘手的事情，比如解析。它可能需要一个编辑器，但它仍然是一个令人印象深刻的产品。

有了如何在 Lisp 中使用 Lisp 的好主意，您就可以在较低级别上实现 Lisp。

Lisp in Small Pieces 经常被推荐。我已经阅读了其中的大部分内容，可以说这绝对是一本很棒的书，充满了细节。我会用细梳子仔细回顾一下，因为当你不理解的东西时很容易浏览。我还努力从作者的网站获取代码来运行；如果你明白了，我建议使用 Gambit Scheme 并运行依赖于 Meroonet 和 Meroon 的代码，来自此发行版。 Lisp in Small Pieces 提供了许多用Scheme 编写的解释器以及字节码编译器和C 编译器。

Lisp in Small Pieces 运行速度很快，而且非常密集。如果这对您来说太多了，也许可以从编程语言要点开始。我读过一些，相当不错，但更多是翻译。显然，其中一个较旧的版本（第一个？我不确定......）包含一个编译器。三个版本之间似乎有很多变化，但第一个版本在亚马逊上超级便宜，所以你可以去看看。

至于编译成 C 语言，这是一个很粗俗的话题，有很多毛茸茸的地方。编译到 C 会带来所有这些奇怪的角落问题，例如如何优化尾部调用和处理闭包、一流的延续和垃圾收集，但它非常有趣，并且许多“真正的”Scheme 实现都走这条路。 Marc Feeley 对此的演讲非常有趣，标题为 The 90 C 编译器的分钟方案。

我在编译一直到汇编方面的资源较少，但是有一篇经常推荐的论文，介绍了Scheme到x86的编译，名为编译器构建的增量方法。它对读者的要求很少，但我发现它速度太快并且没有填写足够的细节。也许你会有更好的运气。

上面的很多建议都来自一年多前对 Hacker News 的怪物评论，来自 mahmud< /a>.它引用了许多 ML 资源，并使用延续进行编译。我的学习还没有到那一步，所以我不能说什么是好什么是不好。但这是一个非常有价值的评论。参考的著作包括 Andrew Appel 的“Compiling with Continuations”和 Paul Wilson 的“Uniprocessor Garbage Collection Techniques”论文。

祝你好运！

Although the other comments and posts are right, this question is overly vague and maybe a bit confused, I can't help but share some recommendations. I've collected a number of links and books on implementing Lisp as I have recently developed a bit of a fascination with language implementation. It's a deep topic, of course, but reading the stuff related to Lisp is especially compelling because you can skip a lot of the intense reading on parsing if you implement a Lisp compiler or interpreter in Lisp, and just use read. This allows the authors to get to the meat of compilation or interpretation quickly. These recommendations are books I've read or started or am reading, and mostly deal with Scheme, not Common Lisp, but still might be of some interest.

If you've got no background in language implementation, and have never had the pleasure of reading about the classic Lisp and Scheme "metacircular evaluators", I would recommend Structure and Interpretation of Computer Programs. If you've seen Lisp-in-Lisp (or Scheme-in-Scheme...) you can skip ahead. In the last two chapters of SICP, the authors present a few different interpreters for Lisp/Scheme and a few variants, as well as a byte-code compiler and a virtual machine. It's simply a brilliant book, and free.

If you don't have time to read SICP, or don't want to slog through it just to get to the interpretation and compilation chapters, I would recommend The Little Schemer. Even though it's very short and intended for newcomers to Lisp and Scheme, if you've never seen a Lisp interpreter written in Lisp, they do present one, and it's quite a delightful book, but might not be for everyone due to the cute style.

There's another free book on Scheme similar to SICP, called An Introduction to Scheme and its Implementation, which I haven't read but used as a reference for a few bits. There are sections on interpreters and compilers in there, and it seems to go a bit deeper than SICP, dealing with hairier things like parsing too. It maybe needed an editor, but it's an impressive offering nonetheless.

With a decent idea of how to do Lisp in Lisp, you can approach implementing Lisp in something lower level.

Lisp in Small Pieces is frequently recommended. I've read most of it, and can say it's definitely a great book, full of nitty gritty stuff. I'm going back over it with a fine comb, because it's easy to skim when you don't understand stuff. I also struggled with getting the code from the author's site to run; if you get it, I recommend using Gambit Scheme and running the code that relies on Meroonet with Meroon, from this distribution. Lisp in Small Pieces presents a number of interpreters written in Scheme as well as a byte-code compiler and a compiler-to-C.

Lisp in Small Pieces moves fast, and it's quite dense. If it's too much for you, perhaps start with The Essentials of Programming Languages. I've read some of it and it's quite good, but it's more interpreters. Apparently one of the older editions (1st? I'm not sure...) included a compiler. There seems to be a lot of change between the 3 editions, but the first is super cheap on Amazon, so check it out.

As for compilation to C, this is kind of a gross subject with lots of hairy bits. Compilation to C brings up all these weird corner issues, like how to optimize tail-calls and handle closures, first-class continuations and garbage collection, but it's pretty interesting, and a lot of "real" implementations of Scheme go this route. Marc Feeley's presentation on this is pretty interesting, titled The 90 Minute Scheme to C compiler.

I have fewer resources on compiling all the way down to assembly, but there is a often recommended paper which introduces compilation of Scheme to x86, called An Incremental Approach to Compiler Construction. It assumes little of the reader, however I found that it simply goes too fast and doesn't fill in enough details. Maybe you'll have better luck.

A lot of the above recommendation comes from this monster comment on Hacker News from over a year ago, from mahmud. It references a number of ML resources, and compilation using continuations. I haven't gotten that far in my study, so I can't say what's good or not. But it's an incredibly valuable comment. The referenced works include Andrew Appel's "Compiling with Continuations" and Paul Wilson's "Uniprocessor Garbage Collection Techniques" paper.

Good luck!

回复收藏 0 原文

星星的轨迹 2024-11-11 20:59:40

我过去考虑过这个问题（然后改用 C 内核）。当然，没有单一的“程序集”，但对于 x86/32 位，这就是我的计划：

基本值存储在 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)

考虑指针时，3 位仍然可用如果所有分配都假定为 8 字节的倍数（对于 8 字节的单元大小来说是合理的）。实现简单的垃圾收集器需要一位额外的位（“活动”位）。在 C 实现中，我最终根据节点类型将该位分配到各个部分（例如，如果是指针，则为高 32 位的最低有效位）。

我的想法是拥有两种类型的内存：“节点内存”（具有上述布局），在页面中分配并与空闲列表一起重用，以及“二进制内存”，用于可变大小的字符串/代码/数组。

根据节点类型需要特定的代码来实现 touch 函数，该函数递归地将活动节点标记为活动节点所引用的活动节点。

所有这些当然只是一种幼稚的方法，但我仍然让它在“C”中工作，并且我确信我也可以在汇编中做到这一点（我的 C 代码在任何地方都使用 void * 所以基本上只是一个可移植的 32 位汇编器）。由于我的 C 实现中的懒惰，我仅使用 32 位来表示浮点数和整数（使用较高的 32 位），而不是使用所有可用位。

I thought about it a bit in the past (then resorted to using a C kernel instead). Of course there is no single "assembly", but for x86/32bit this is what I was planning:

Basic values are stored in 64-bit nodes with three lowest bit used as tag with the following meaning:

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)

3 bits remain usable when considering pointers if all allocations are assumed to be a multiple of 8 bytes (reasonable with a cell size of 8 bytes). One extra bit would be needed for implementing a simple garbage collector (the "alive" bit). In the C implementation I ended up allocating this bit in various parts (e.g. least significant bit of higher 32 bits if that was a pointer) depending on the node type.

My idea was to have memory of two types: "nodes memory" (with the layout described above) that was allocated in pages and reused with a free list, and "binary memory" to be used for variable sized strings/code/arrays.

Specific code is needed depending on the node type to implement a touch function that recursively marks as alive nodes referred by an alive node.

All this is of course just a naive approach, but still I got it working in "C" and I'm sure I could have done that also in assembly (my C code is using void * everywhere so is basically just a portable 32-bit assembler). For lazyness in my C implementation I only used 32 bits for floats and for integers (using the higher 32 bits) instead of using all available bits.

回复收藏 0 原文

楠木可依 2024-11-11 20:59:40

查看Clozure Common Lisp，了解用于实现 Lisp 的汇编语言示例。 Clozure CL 是大部分是用 Common Lisp 本身实现的，但有一个用 C 编写的内核和一些汇编中的低级功能。

例如，下面是来自 compiler/X86/x86-lapmacros.lisp 的宏，在 x86 硬件上实现原始 CAR 函数，其中一条汇编指令分别适用于 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 编译器的平台变得很方便。

Take a look at Clozure Common Lisp for an example of assembly language used in implementing a lisp. Clozure CL is mostly implemented in Common Lisp itself, but there is a kernel written in C and some low level functionality in assembly.

For example, here is a macro from compiler/X86/x86-lapmacros.lisp implementing a primitive CAR function on x86 hardware, with one assembly instruction for respectively 32bit and 64bit:

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

As shown, the assembly code is itself encoded in Lisp form. Porting to another platform involves (among other things) to translate these low level operations into another assembly language and cross-compile to create a runtime on the new platform.

ECL (Embeddable Common Lisp) takes another approach by compiling into C. This makes it convenient to port the implementation to platforms that have a C compiler.

回复收藏 0 原文