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

Question

我再次观看了一场SICP讲座,其中Sussman演示了如何实施Scheme cons car并且只cdr使用procudures.

它是这样的:

(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

很酷的问题！

\n

每当有人将其交给处理器 (CPU) 调用时，它就变成硬件。如果您必须阅读芯片制造商的手册才能了解如何做您想做的事情，那么您就处于您所描述的水平。

\n

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

\n

以下是从物理到硬件到代码到用户的路径概述：http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-002- Circuits-and- electronics- spring-2007/video-lectures/lecture-1/虽然我不认为这与 lambda 演算有关。（但你只是说这就是激发问题的原因\xe2\x80\x94它本身并不是问题，对吧？）

\n

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

\n

查看内核编程或考虑嵌入式系统（在微波炉中、飞机机翼上）、ARM或移动设备\xe2\x80\x94，这些是人们使用非笔记本电脑芯片组进行编程的东西。

\n

编写 BLAS（线性代数求解器库）的人有时会深入到这种细节级别。例如https://en.wikipedia.org/wiki/Math_Kernel_Library或https://en.wikipedia.org/wiki/Automatically_Tuned_Linear_Algebra_Software。当他们说 BLAS 已“调整”时，他们的意思是什么？他们谈论的是嗅探有关处理器的事实，并改变内部-内部-内部循环的决策方式，以减少物理配置方式上浪费的时间。

\n

\n _{（来源：hswstatic.com）}

\n

如果我没记错的话，高级编程语言（例如C;)）不会假设它们将在什么系统上运行，因此它们会进行不可知的调用，其运行速度比它们提前知道的情况慢十倍\xe2\x80\xa0拨打哪种电话的时间。每一个。时间。这种事情可能会让你发疯，但这是技术人员的时间与最终用户的性能之间的经典工程权衡。我想如果你成为一名内核程序员或嵌入式系统程序员，你可以帮助结束全球计算机上所有浪费的时钟周期\xe2\x80\x94处理器变得很热，因为它们浪费了很多无意义的返回和-向前。（尽管世界上显然还有更糟糕的事情正在发生。）

\n

\xe2\x80\xa0：我只是快速搜索了 BLAS 加速有多少，是的，它可能是 15 或 20 左右。所以我不认为我夸大/记错了我听到的关于浪费运动的内容。顺便说一句，发电中也存在类似的情况：发电的最后一步（涡轮机）的效率只有 20% 左右。所有这些浪费难道不会让你发疯吗？！是时候成为一名工程师了。;)

\n\n

您可以查看的一个很酷的项目是MenuetOS；有人用汇编语言编写了操作系统。

\n

然而，更酷的东西可能是这个人说学习 x86汇编语言实际上非常简单且有趣。（！）

\n

\n _{（来源：iqsdirectory.com）}

\n

您还可以回顾过去，当时软件和硬件之间的距离较短（例如，使用打孔卡进行编程）。值得庆幸的是，人们编写了“高级”语言，它们更像人们说话和思考的方式，而不是像移动磁带一样。数据结构可能不是日常对话中最明显的东西，但它们比[lists a sequence of GOTO and STORE instructions...].

\n

华泰

\n