最低级别的数据结构是什么？

Question

[我很认真地观看了SICP的演讲，苏斯曼展示了如何仅凭程序就能实现Scheme的cons car和cdr。

它是这样的：

(define (cons x y)
  (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))

这让我开始思考；数据结构是什么呢？创建语言时，数据结构是否由过程建立为抽象结构？如果它们仅由程序组成，那么最低级别的程序实际上是什么？

我想我想知道的是抽象链底部的内容（除非它一直都是抽象的）。在什么时候成为硬件？

Answer 1

诀窍是您不必在意。 cons，cdr和car是抽象，因此它们的基本实现无关紧要。

您拥有的就是所谓的“教堂对”，我们从功能中构建一切。在现代机器中，我们使用1和0的字符串来构建所有内容，但实际上，这并不重要。

现在，如果您想知道如何在您的特定实现中实现所有这些抽象，那取决于。您的编译器/干扰程序很可能会在幕后跳来跳去，将cons单元分配为紧密堆积的一对指针（或类似指针），然后将您的函数转换为0和1的字符串，从而形成适当的机器代码并将其与指向其环境的指针。

但是就像我说的那样，构建这些抽象的全部好处是，您不必以用户身份关心：）

Answer 2

抽象链底部的基板根据硬件而有所不同，但可能是某种注册机，它将具有某种本机指令集。

SICP的last chapter就是关于这一层的。本书没有介绍任何现实生活中的硬件，而是一台抽象的（ahem乌龟！）注册机，类似于实际发生的事情……恰好在Scheme中建模，只是为了额外元圆的乐趣。我觉得这本书很难读，但是值得。

如果您对此类型的东西感兴趣，您可能也想看看Knuth。

Answer 3

[抽象链存在多个底层。根据基础任务，计算机科学家可以选择一个更合适的任务。最常见的是Turing Machine和Lambda Calculus。

Answer 4

很酷的问题！

[只要有人将其交给呼叫处理器（CPU），它就会变成硬件。如果您必须阅读芯片制造商的手册以了解如何做自己想做的事情，您描述的级别。

_{（来源：micro-examples.com）}

这里是从物理到硬件再到代码再到用户的路径的概述：http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-002-circuits-and-electronics-spring-2007/video-lectures/lecture-1/，尽管我认为这与lambda演算无关。 （但是您只是说这是启发问题的原因，这本身不是问题，对吗？）

[编写语言的人必须与处理器指令交互，例如https://en.wikipedia.org/wiki/X86_instruction_listings ||。 https://en.wikipedia.org/wiki/X86_calling_conventions。

[观察kernel programming或考虑嵌入式系统（在微波中，飞机机翼上），ARMs或移动设备-这些是人们使用非膝上型芯片组编程的东西。

编写BLAS（线性代数求解器库）的人们有时会陷入这种细节水平。例如https://en.wikipedia.org/wiki/Math_Kernel_Library或https://en.wikipedia.org/wiki/Automatically_Tuned_Linear_Algebra_Software。当他们说BLAS被“调整”时，它们是什么意思？他们正在谈论嗅探有关您的处理器的事实，并更改内部-内部-内部循环如何做出决策，以减少配置物理事物的时间。

如果我没记错的话，高级编程语言（例如C;））不会假设它们将在哪个系统上运行，因此它们发出不可知论的调用的速度比他们事先知道的要慢十倍†拨打哪种电话。每一个。时间。这种事情可能使您发疯，但这是技术人员时间与最终用户性能之间的经典工程折衷。我猜想，如果您成为内核程序员或嵌入式系统程序员，则可以帮助杜绝全球计算机上所有浪费的时钟周期-处理器变热，因为它们浪费了很多毫无意义的来回往返。 （尽管世界上发生的事情显然更糟。）

†：我只是快速地搜索了BLAS加速的速度，是的，可能是15或20的倍数。因此，我认为我并没有夸大/误解我所听到的关于浪费运动的信息。顺便说一句，在发电方面也有类似的事情：发电的最后一步（涡轮机）效率只有20％。难道所有的浪费只会使您发疯吗？是时候成为一名工程师了。 ;）

---

您可以签出的一个很棒的项目是MenuetOS；有人用汇编器编写了一个操作系统。

还有一些更酷的东西可能是this guy，他说学习x86汇编语言实际上非常容易而且很有趣。 （！）

_{（来源：iqsdirectory.com）}

您还可以回顾过去的软件和硬件之间的距离较近的日子（例如，使用打孔卡进行编程）。值得庆幸的是，人们已经编写了“高级”语言，这些语言更像人们的交谈和思考方式，而不是四处走动。数据结构可能不是日常对话中最明显的事物，但它们比[lists a sequence of GOTO and STORE instructions...]更抽象。

HTH