Каковы структуры данных на самом низком уровне?
Я недавно посмотрел лекцию SICP, в которой Суссман продемонстрировал, как можно реализовать Схемы. conscar а также cdr не используя ничего, кроме процедур.
Это пошло примерно так:
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))
Это заставило меня задуматься; Что такое структуры данных? Когда язык создается, реализуются ли структуры данных как абстракции, созданные процедурами? Если они состоят из процедур, то какие процедуры на самом деле находятся на самом низком уровне?
Я предполагаю, что я хочу знать, что находится в нижней части цепочки абстракций (если только это не абстракции полностью). В какой момент он становится аппаратным?
4 ответа
Хитрость в том, что вам не нужно заботиться. cons, cdr а также car являются абстракциями, и поэтому их реализация не должна иметь значения.
То, что у вас есть, есть так называемые "церковные пары", мы строим все из функций. В современных машинах мы строим все из строк 1 и 0, но на самом деле это не имеет значения.
Теперь, если вам интересно, как все эти абстракции реализованы в вашей конкретной реализации, это зависит. По всей вероятности, ваш компилятор / интерпретатор прыгает через обручи за кулисами, выделяя cons Ячейки как плотно упакованная пара указателей (или аналогичных) и превращение ваших функций в строку из 0 и 1, формирующую соответствующий машинный код и соединяющую его с указателем на его среду.
Но, как я уже сказал, вся прелесть создания этих абстракций в том, что вам не нужно заботиться как пользователь:)
Классный вопрос!
Он становится аппаратным, когда кто-то передает его вызовам процессора (CPU). Если вам нужно прочитать руководство от производителя микросхемы, чтобы понять, как делать то, что вы хотите сделать, вы на том уровне, который вы описываете.
http://www.micro-examples.com/pics/087-PIC16-SECRET-OPCODE-instructionset.JPG
Вот краткий обзор пути от физики к оборудованию и к коду для пользователей: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-002-circuits-and-electronics-spring-2007/video-lectures/lecture-1/ хотя я не думаю, что это связано с лямбда-исчислением. (Но вы просто говорите, что именно это вдохновило вопрос - это не вопрос сам по себе, верно?)
Существует шаг, когда человек, который пишет язык, должен взаимодействовать с инструкциями процессора, например, https://en.wikipedia.org/wiki/X86_instruction_listings || https://en.wikipedia.org/wiki/X86_calling_conventions.
Познакомьтесь с программированием ядра или подумайте о встроенных системах (в микроволновой печи, на крыле самолета), ARM или мобильных устройствах - это то, что люди программируют на чипсетах не для ноутбуков.
Люди, которые пишут 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; кто-то написал операционную систему на ассемблере.
Еще более крутой материал, на который можно взглянуть, может быть этот парень, который говорит, что на самом деле довольно легко и весело учиться x86 язык ассемблера. (!)
http://blog.iqsdirectory.com/wp-content/uploads/files/punch-card%20operator.jpg
Вы также можете вспомнить старые времена, когда между программным и аппаратным обеспечением было меньше расстояний (например, программирование с помощью перфокарты). К счастью, люди написали "высокоуровневые" языки, которые больше похожи на то, как люди говорят и думают, и меньше похожи на перемещение какой-то ленты. Структуры данных, возможно, не самая очевидная вещь из повседневного разговора, но они более абстрактны, чем [lists a sequence of GOTO and STORE instructions...],
НТН
Подложка в нижней части цепочки абстракций варьируется в зависимости от аппаратного обеспечения, но, вероятно, это будет своего рода машина регистрации, которая будет иметь какой-то набор встроенных команд.
Последняя глава SICP посвящена этому слою. Книга не представляет какого-либо реального оборудования, но представляет собой абстрактную (ага, черепахи!) Регистрационную машину, которая напоминает то, что на самом деле может происходить... которая, как представляется, смоделирована в Схеме, просто для дополнительного метациркуляционного веселья. Я нашел это трудно читать, но стоит.
Если вы заинтересованы в такого рода вещах, вы также можете попробовать Кнут.
Существует несколько оснований для цепочек абстракций. В зависимости от основной задачи компьютерный ученый может выбрать тот, который подходит лучше. Наиболее распространенными являются машина Тьюринга и лямбда-исчисление.