Одним из основных моментов конференции Strange Loop 2016 года в Сент-Луисе был доклад Tom Hall Unlimited Register Machines, Gödelization and Universality, который я рекомендую вам посмотреть на Strange Loop. YouTube канал".
Выступление Тома было вдохновлено главой Семь раскрытых секретов вычислительной мощности из книги американского философа Дэниела Деннета Насосы интуиции и другие инструменты мышления. В нем Деннет говорит:
Компьютеры, без сомнения, являются самыми мощными мыслительными инструментами, которые у нас есть, не только потому, что они избавляют от рутины многих интеллектуальных задач, но и потому, что многие концепции, изобретенные учеными-компьютерщиками, сами по себе являются превосходными мыслительными инструментами.
Компьютеры могут выполнять невероятно сложные задачи, но эти задачи состоят из относительно простых шагов. Если мы сможем понять, как эти простые шаги составлены для создания сложных программ, мы сможем рассуждать о том, как другие сложные машины могут быть построены из простых шагов. Например, его можно использовать для рассмотрения того, как возможно, что человеческий мозг состоит только из миллиардов простых нейронов, но при этом может демонстрировать чрезвычайно сложное поведение.
Помимо того, что это очень интересная философская тема, создание и понимание того, как могут быть написаны программы для простой регистровой машины, является интересной проблемой разработки программного обеспечения.
В своем выступлении Том продемонстрировал тему, используя неограниченную регистровую машину, написанную на ClojureScript. Решил попробовать построить в Вязе.
Неограниченное количество регистрационных машин
Неограниченная регистровая машина (URM) — это идеализированное вычислительное устройство, которое полезно для обучения основам работы компьютера. По этой причине он особенно актуален в данном контексте. Любой правильно определенный URM является эквивалентом Тьюринга и, следовательно, также эквивалентен машинам фон Неймана, таким как наши смартфоны или ноутбуки. Все, что может делать ваш ноутбук, может выполнять и URM, хотя и гораздо медленнее.
URM содержит конечное число регистров и может выполнять программы. Регистры помечены адресом (регистр 1, регистр 2 и т. д.) и могут содержать одно положительное целое значение. Программы — это последовательности инструкций, которые может выполнять URM. Как и регистры, инструкции помечаются цифрами 1, 2, 3 и т. д., поэтому к инструкции можно обращаться по индексу.
URM, описанный Деннетом, понимает три инструкции. Эти:
Выход:остановить выполнение. На этом программа завершена
Inc a x:увеличить значение регистра a и перейти к инструкции x
Deb a x y: если значение регистра a уже не равно нулю, уменьшите его и перейдите к инструкции x. Если оно уже равно нулю, оставьте значение без изменений и перейдите к инструкции y
Так, например, простая программа для двойного увеличения значения регистра 1 выглядит так:
1. Inc 1 2 2. Inc 1 3 3. Exit
Вот еще одна программа для обнуления содержимого регистра 1:
1. Deb 1 1 2 2. Exit
И еще немного интереснее, вот программа, которая прибавляет значение регистра 3 к значению регистра 4 и помещает результат в регистр 1, оставляя значения регистров 3 и 4 без изменений:
1. Deb 3 2 4 2. Inc 1 3 3. Inc 2 1 4. Deb 2 5 6 5. Inc 3 4 6. Deb 4 7 9 7. Inc 1 8 8. Inc 2 6 9. Deb 2 10 11 10. Inc 4 9 11. Exit
Вы можете увидеть эти и некоторые другие программы в действии в живой демонстрации.
Внедрение URM в Elm
Я реализовал URM в Elm вместе с простым пользовательским интерфейсом для визуализации машины и несколькими примерами программ. Сейчас это довольно просто, но вы можете увидеть, как это работает здесь, и найти код на GitHub. В оставшейся части поста я хотел бы описать код Elm для ядра машины.
Elm позволяет создавать программы без исключений во время выполнения благодаря тому, что это язык со статической типизацией. В Elm вы моделируете свою проблему, создавая свои типы, что, к счастью, довольно просто благодаря хорошо разработанной системе типов.
Мы можем начать с представления регистров нашей машины с помощью типа Elm Array. Это дает нам удобный способ чтения и записи значений наших регистров с помощью функций get и set модуля Array.
registers : Array Int
Мы также можем использовать тип Array для представления нашей программы, но сначала нам нужно определить наши инструкции. Поскольку мы знаем, что у нас всего три типа инструкций, мы можем использовать тип объединения Elm.
type Instruction
= Exit
| Inc Int Int
| Deb Int Int Int
program : Array Instruction
Здесь мы говорим, что инструкция должна быть Exit, Inc или Deb, и что Inc помечен двумя значениями Int, а Deb помечен тремя значениями Int.
После определения типа инструкции мы можем сказать, что наша программа представляет собой массив инструкций.
Чтобы представить состояние нашей машины в любой заданный момент, мы создаем псевдоним типа для записи, которая включает в себя регистры, программу, флаг, указывающий, вышла ли машина, и программный счетчик для отслеживания следующей инструкции для выполнения. .
type alias State =
{ registers : Array Int
, program : Array Instruction
, exited : Bool
, programCounter : Int
}
Теперь создадим ступенчатую функцию. Эта функция принимает состояние URM и возвращает новое состояние после выполнения следующей инструкции. Как и все замечательные программы, это гигантский кейс.
step : State -> State
step state =
let
cmd =
nextInstruction state
in
case cmd of
Exit ->
{ state | exited = True }
Inc register nextInstr ->
{ state
| programCounter = nextInstr
, registers =
incrementRegister state.registers register
}
Deb register successIndex branchIndex ->
let
( newRegisters, decremented ) =
decrementRegister state.registers register
nextInstr =
if decremented then
successIndex
else
branchIndex
in
{ state
| programCounter = nextInstr
, registers = newRegisters
}
Если мы пройдемся по этой программе, то увидим, что сначала получаем следующую инструкцию в строке 5. Функция nextInstruction здесь не показана, но в основном она извлекает инструкцию из программы состояний на основе счетчика программ.
Теперь мы переходим к нашим трем случаям.
В случае Exit мы просто возвращаем новое состояние с установленным флагом выхода.
Для случая Inc мы возвращаем новое состояние с ProgramCounter, обновленным до правильной инструкции, и новым массивом регистров, который является результатом функции incrementRegister. Эта функция показана ниже:
incrementRegister : Array Int -> Int -> Array Int
incrementRegister registers index =
let
arrayIndex =
index - 1
value =
Array.get arrayIndex registers
|> Maybe.withDefault 0
in
Array.set arrayIndex (value + 1) registers
Здесь происходит небольшой обман. Когда мы получаем текущее значение регистра, если он не существует, мы по умолчанию равны нулю. Поскольку Array.set с индексом за пределами привязки возвращает массив без изменений, вся эта функция не работает, если регистр не существует. Также обратите внимание, как мы переключаемся с индексации на основе 1 на индексацию на основе нуля, поскольку регистры помечены 1, 2, 3 и т. д., в то время как тип Array использует индексацию на основе нуля.
Случай Deb немного сложнее. Соответствующая функция для incrementRegister здесь — decrementRegister. Это возвращает кортеж, содержащий новое значение регистров, а также флаг, указывающий, можно ли уменьшить значение регистра. Затем мы используем флаг, чтобы определить, какой будет следующая инструкция, прежде чем вернуть новое состояние.
Для полноты здесь показан decrementRegister:
decrementRegister : Array Int -> Int -> ( Array Int, Bool )
decrementRegister registers index =
let
arrayIndex =
index - 1
value =
Array.get arrayIndex registers
|> Maybe.withDefault 0
decremented =
value > 0
newValue =
if decremented then
value - 1
else
0
in
( Array.set arrayIndex newValue registers, decremented )
Надеюсь, теперь это легко понять. У нас тот же «мошеннический» подход к внешним регистрам, и мы добавляем некоторую базовую условную логику для определения нового значения регистра.
И это все! Весь мой URM реализован на 121 строке кода Elm. Стоит помнить, что, поскольку URM является эквивалентом Тьюринга, эти 121 строка кода могут делать все, что может делать машина фон Неймана внутри любого ноутбука. На самом деле, поскольку это настоящая универсальная машина, кульминацией выступления Тома является демонстрация того, как, проявив немного творчества, можно написать программу URM, которая сама имитирует работающую URM, то, что мы чаще называем виртуальной машиной. .
Больше никаких секретов!
Финал семи секретов вычислительной мощности Деннета заключается в том, что «Секретов больше нет!» и демонстрация этого момента является целью создания такой URM. Все усовершенствования, найденные в современном оборудовании, являются просто более эффективными способами делать то же самое, что и эта регистровая машина.
Я использовал свое приложение, чтобы объяснить работу компьютеров нескольким инженерам, не занимающимся программным обеспечением, и обнаружил, что это не займет много времени, чтобы понять его.
Я также нашел много забавных программ для него. Это, безусловно, было хорошим напоминанием о том, как далеко продвинулись языки программирования при переключении между написанием громоздких программ URM и гораздо более простым кодом Elm.
Заинтересованы в оказании влияния? Присоединяйтесь к команде carwow!
Чувствуете себя в обществе? Присоединяйтесь к нам в Twitter и LinkedIn :-)
