В этом посте будет исследовано, как математическую концепцию можно постепенно переформулировать во всё более «вычислительных» понятиях, от высокоуровневого языка, далее до машинного кода и, наконец, до прямого исполнения компьютером. Для этого определю одну и ту же логику в нескольких разных, но перекликающихся друг с другом форматах:

1. Математика — чистая математика.

2. Haskell — язык для функционального программирования.

3. C — язык для императивного программирования.

4. Ассемблер — сравнительно удобочитаемое представление машинного кода.

5. Машинный код для архитектуры x86-64 — вот это уже интересно.

Если вам интересно, какие отличия бывают между языковыми стилями или любопытно, как ваш код может выглядеть после компиляции — добро пожаловать под кат!

Факториалы в математике

Факториал — это произведение целого числа и всех прочих целых чисел выше нуля. Существует множество способов выразить это определение, например вот так:

Здесь утверждается, что n! — это произведение всех целых чисел от 1 до n. Например, факториал от  5 равен:

5! = 1 * 2 * 3 * 4 * 5 = 120

Вот несколько первых факториалов:

Важная область применения факториалов — подсчёт общего количества возможных перестановок в множестве. Например, строку «cat» можно переупорядочить 6 способами: «cat», «act», «atc», «tac», «tca» и «cta». В этой строке три буквы, а 3! = 6.

В строке «a» всего один символ, и поэтому переупорядочиванию она не поддаётся. Отсутствие перестановок равноценно одной перестановке и выражается как: 1! = 1.

Подобные вещи широко распространены в анализе алгоритмов. Об алгоритме, в котором требуется учесть все возможные перестановки входных данных, говорят, что он выполняется за факторное время. В нотации Big O это имеет вид: O(n!). Алгоритмы такого рода очень плохо масштабируются, поэтому полезно будет научиться распознавать их заранее, чтобы изначально искать более быстрый способ решения задачи.

Факториалы на функциональном языке

Подобно тому, как существует множество способов выразить что-либо математически, так есть и множество вариантов, как можно описывать сущности компьютеру. Начнём с языка Haskell, у которого, кроме всех прочих достоинств, очень классный логотип:

Haskell — чисто функциональный язык. В общем и целом это означает, что на этом языке мы не указываем компьютеру, что делать. Вместо этого в программе описано, каковы сами сущности. Когда программа на Haskell написана, в дело вступает компилятор Haskell, задача которого — найти способ преобразовать эти определения в понятные компьютеру инструкции.

Рассмотрим следующую функцию на Haskell, вычисляющую факториал предоставленного ей числа:

factorial :: Int -> Int
factorial n = product [1..n]

Если вы пока не баловались функциональными языками, этот код может показаться вам весьма странным.

В первой строке сказано, что факториал — это функция, принимающая целое число и возвращающая другое целое число. Вот другая, слегка отформатированная версия этой строки. В ней специально расставлены пробелы так, чтобы было понятнее, какой синтаксический элемент за что отвечает:

-- факториал – это функция, принимающая целое число и возвращающая другое целое число
   factorial ::                             Int          ->        Int

Строго говоря, эта первая строка необязательна, но считается хорошим тоном её включать. Язык Haskell достаточно умён, чтобы, как правило, самостоятельно выяснять эту информацию по сигнатурам типов, но сигнатуру функции всё равно полезно документировать, чтобы облегчить жизнь не только другим программистам, но и себе в будущем.

Во второй строке определяется тело функции, которое можно трактовать как «факториал от n равен произведению всех целых чисел от 1 до n». Вот ещё одна версия функции с пояснениями элементов синтаксиса:

-- Факториал от n равен произведению всех целых чисел от 1 до n
       factorial    n      =          product                     [1 .. n]

Обратите внимание: мы не объясняем Haskell, как вычислять факториал, а даём ему определение, что такое факториал. В этом и заключается одно из важнейших отличий между функциональными и императивными языками.

Давайте ещё подробнее разберём это определение. Когда функцию вызывают с каким-либо числом n в качестве аргумента, часть выражения справа от знака равенства вычисляется, и возвращается ответ:

product [1..n]

Сначала давайте рассмотрим ту часть, которая в квадратных скобках:

[1..n]

Это диапазон списков. Эта структура данных в Haskell подобна массиву — то есть представляет собой упорядоченную коллекцию значений одного и того же типа. Можно иметь списки целых чисел, чисел с плавающей точкой, строк, пользовательских типов и даже списки списков.

Здесь .. указывает, что данный список является диапазоном. Так создаётся список всех целых чисел от 1 до n. Таким образом, если n равно 5, то получится список, содержащий 5 значений:

[1, 2, 3, 4, 5]

После того, как диапазон списков вычислен, он передаётся функции произведения, вот так:

product [1, 2, 3, 4, 5]

Функция произведения принимает список чисел, перемножает их все и возвращает результат. Таким образом, получится:

1 * 2 * 3 * 4 * 5

Оказывается, ответ равен 120, что равноценно 5! — именно тому числу, что нас интересует. Какое счастливое совпадение!

Как только определена функция факториала, приведённая выше, можно получить факториал любого числа, вызвав подобный код:

factorial 0 -- возвращает 1
factorial 3 -- возвращает 6
factorial 5 -- возвращает 120

Факториалы в императивном языке

Рассмотрев, как математическая идея факториалов может быть выражена в стиле функционального программирования, пойдём на уровень глубже и повторим ту же реализацию на языке C. С мне очень нравится, жаль только, что логотип у него не такой крутой, как у Haskell:

Напомню, что при программировании на функциональных языках, подобных Haskell, мы обычно даём определение сущностям и предоставляем языку возможность самостоятельно вывести нас к ответу. Напротив, при программировании на императивном языке требуется объяснить компьютеру, какие вычисления он должен выполнить — то есть нужно написать последовательность шагов для компилятора.

Рассмотрим следующую функцию факториала, написанную на C:

int factorial(int n)
{
    int ret = 1;

    while (n > 1)
    {
        ret *= n;
        n--;
    }

    return ret;
}

В основе неё лежит ровно та же логика, что и в версии на Haskell, просто мы иначе её описали.

Вот что в общем виде делает эта функция:

1.       Устанавливает ret в 1. Это будет возвращаемое значение.

2.       Умножает n на ret.

3.       Вычитает 1 из n.

4.       Повторяет шаги 2-3 при условии, что n больше 1.

5.       Возвращает значение, содержащееся в ret.

Разберём эту функцию построчно и посмотрим, как всё это делается.

int factorial(int n)
{

С этого начинается функция факториала. Здесь постулируется, что факториал — это функция, принимающая целое число n и возвращающая другое целое число. Эта информация не поддаётся переводу на естественный язык, как сигнатура типа Haskell, но можно попытаться:

// Возврат целого числа, факториал — это функция, принимающая целое число под именем n
                int  factorial         (                    int       n)

Порядок этого синтаксиса таков, что воспринимается немного неуклюже, но в этой строке заключён тот же смысл, что и в сигнатуре функции Haskell.

    int ret = 1;

Так объявляется новое целое число под именем ret, и ему присваивается значение 1. Это будет возвращаемое значение. Мы будем раз за разом умножать эту переменную на n и возвращать то, что у нас получится, когда будем готовы.

    while (n > 1)
    {

Так начинается цикл. Часть while (n > 1) нужна для многократного выполнения кода, заключённого в фигурные скобки { ... } в тех случаях, если n больше 1. Если перед началом работы функции n равно 0 или 1, то этот цикл вообще не станет выполняться.

        ret *= n;

При каждом прогоне цикла умножаем n на ret и сохраняем результат в ret.

        n--;

Затем вычитаем 1 из n. Таким образом, n будет возрастать на каждом прогоне цикла.

    }

Это окончание тела цикла. Когда выполнение программы доходит до этой точки, мы возвращаемся к началу цикла и запускаем его снова, предполагая при этом, что условие в строке where по-прежнему остаётся истинным.

    return ret;
}

Как только цикл завершится, мы возвращаем значение, содержащееся в ret, и заканчиваем функцию.

Эту функцию факториала можно вызвать вот так:

    factorial(5);

При вызове этой функции со значением 5 происходят следующие шаги:

1.       ret устанавливается в 1.

2.       n равно 5, а 5 > 1, поэтому тело цикла будет выполняться.

3.       ret умножается на 5 и становится равно 5.

4.       n уменьшается на единицу, таким образом, становится равно 4.

5.       n равно 4, а 4 > 1, поэтому тело цикла снова выполняется.

6.       ret умножается на 4 и становится равно 20.

7.       n уменьшается на единицу, таким образом, становится равно 3.

8.       n равно 3, а 3 > 1, поэтому тело цикла снова выполняется.

9.       ret умножается на 3 и становится равно 60.

10.    n уменьшается на единицу, таким образом, становится равно 2.

11.    n равно 2, а 2 > 1, поэтому тело цикла снова выполняется.

12.    ret умножается на 2 и становится равно 120.

13.    n уменьшается на единицу, таким образом, становится равно 1.

14.    n равно 1, а 1 не больше 1, поэтому цикл завершается.

15.    ret в значении 120 возвращается вызывающей стороне.

Факториалы в ассемблере

Несмотря на стилистические отличия, функции как на C, так и на Haskell остаются относительно высокоуровневыми. Таким образом, когда вы пишете такой код, вам не приходится особенно вдаваться в частности работы с машиной. Компиляторы C и Haskell сами могут преобразовать ваш код в удобоваримую форму для целевого компьютера. Но как выглядит тот код, который они генерируют?

Здесь мы углубляемся в ассемблер. Ассемблер — это символьное выражение машинного кода. В основном инструкции ассемблера строго соответствуют инструкциям машинного кода.

Поэтому невозможно что-либо постулировать на ассемблере так, как это делается в C и Haskell: в сравнительно высокоуровневых языках проделывается большая работа по адаптации синтаксиса к человеческому мышлению. Но при работе с ассемблером часть этой работы ложится на плечи программиста, который сам должен подстраиваться к частностям работы железа.

На самом деле, с точки зрения синтаксиса существует несколько вариантов ассемблера. В данном случае мы будем работать с Netwide Assembler, также именуемым nasm. Прежде, чем двигаться далее, давайте разберёмся с по-настоящему важными вещами. Вот логотип nasm:

Боюсь, Haskell по-прежнему впереди, но этот логотип совсем не плох.

Вот функция факториала, записанная синтаксисом nasm для архитектуры компьютера x86-64:

factorial:
    mov rdi, 1

  .loop:
    cmp rax, 1
    jle .done

    imul rdi, rax
    dec rax

    jmp .loop

  .done:
    ret

Ладно, что же здесь происходит? Если вы можете осмыслить этот код, то либо вы уже знакомы с ассемблером, либо вы гораздо умнее меня. В коде на C и Haskell хотя бы есть полноценные слова и знакомые выражения. Но, хотя стиль кода и существенно изменился, логика здесь осталась примерно та же самая, более-менее в том же порядке, что и в предыдущих версиях.

Рассмотрим следующую версию, сопровождаемую комментариями. Она позволяет составить примерное впечатление о том, что делает каждая строка на C:

factorial:        ; int factorial(int n) {
    mov rdi, 1    ;     int ret = 1;

  .loop:          ; .loop:
    cmp rax, 1    ;     if (n <= 1)
    jle .done     ;         goto .done;     // Этот страшный goto!

    imul rdi, rax ;     ret *= n;
    dec rax       ;     n--;

    jmp .loop     ;     goto .loop;         // О боже, ещё один!

  .done:          ; .done:
    ret           ;     return ret;
                  ; }

Соответствие не вполне точное, но, когда комментарии расставлены, этот код должен казаться чуть менее странным.

При всей разнице в описании базовая логика здесь точно такая же, как и в версии на C. Это неслучайно: язык C тонким слоем намазан поверх ассемблера, и большинству его конструкций можно найти весьма точное соответствие в ассемблере на самых разных машинах.

Принципиальная разница между версией на ассемблере и версиями на C/Haskell заключается в том, что в ассемблере отсутствуют сигнатуры типов. В ассемблерной версии нигде не определяется, какие значения будет принимать на вход, и какие будет выдавать на выход функция факториала. Напротив, ожидается, что значение n будет загружено в регистр rax ещё до того, как будет вызвана функция. Перед выходом эта функция оставляет возвращённое значение в регистре rdi — опять же, предполагается, что вызывающая сторона будет знать, где искать этот ответ. Нигде в коде это явно не артикулировано: чтобы пользоваться данной функцией, в принципе нужно заранее знать, как она работает. В идеале код должен содержать комментарии, либо эта информация должна быть дана во внешней документации. В противном случае придётся читать код самой функции, чтобы методом проб и ошибок выяснить, как же её использовать.

Начиная работу, функция устанавливает rdi в 1, это и будет возвращаемое значение. Далее она многократно умножает это возвращаемое значение на значение, содержащееся в rax, на каждой итерации вычитая из rax единицу. Как только rax достигнет 0 или 1, функция завершается, а возвращаемое значение остаётся в rdi, чтобы им могла пользоваться вызывающая сторона. Если предположить, что вызывающая сторона записала целое число в регистр rax до того, как вызвать функцию факториала, то после возврата функции в регистре rdi определённо будет находиться факториал именно этого целого числа.

Если вам интересно не только сопоставить эти инструкции с C-подобным синтаксисом, но и узнать, что именно делает каждая из них — читайте далее!

Подробное исследование ассемблерной версии

Для начала — небольшое разъяснение. Процессор не «мыслит» такими переменными как int ret = 1 или ret *= n;. Нет, у него есть некоторое количество регистров. В каждом регистре может храниться фиксированный набор данных. Если процессор 64-разрядный, то в каждом его регистре общего назначения можно сохранить 64 бита информации.

Выполняя инструкции, программа может загружать данные в эти регистры, а затем выполнять над данными математические операции.

Поскольку регистры — это крошечные фрагменты памяти в аппаратной части ЦП, выполнение операций над данными в регистрах происходит молниеносно. Ведь процессору не приходится дожидаться, пока данные отправятся в системную память или вернутся из неё.

Вот несколько наиболее востребованных регистров:

Регистрами общего назначения вы в основном можете пользоваться так, как посчитаете нужным. Другие регистры зарезервированы под конкретные цели, и для них существуют правила, указывающие, как эти регистры можно использовать или изменять.

Процессор может производить вычисления лишь над теми данными, что загружены в регистры. Так, чтобы сложить два числа, нужно сначала приказать компьютеру загрузить каждое из чисел в регистр, а потом приказать сложить значения, содержащиеся в этих регистрах. 

Давайте построчно разберём ассемблерную функцию и в деталях посмотрим, как именно она работает.

factorial:

Это начало функции факториала. Следующее после двоеточия имя часто называется меткой. Можно приказать компьютеру перейти (jump) к этой метке в любой момент, когда нам потребуется, чтобы выполнился следующий за этой меткой код.

В самом начале функции мы исходим из того, что вызывающая сторона записала в регистр rax некоторое целое число n.

    mov rdi, 1

Результат этой функции мы возвратим в регистре rdi. Эта инструкция задаёт 1 в качестве исходного значения rdi. Мы понятия не имеем, в какое значение установлен этот регистр в начале выполнения функции, так как при вызове функций регистры автоматически не очищаются. Прежде, чем использовать регистр, потребуется установить его в какое-либо значение.

  .loop:

Это ещё одна метка, соответствующая началу цикла. Поскольку перед ней стоит точка, эта метка является локальной, то есть локальной в пределах той функции, где мы находимся. Можно перейти к .loop: в любой момент, когда мы захотим выполнить данный цикл.

    cmp rax, 1

При каждом прогоне цикла первым делом нужно проверить, не должен ли цикл уже завершиться.

Напомню, что n сохранено в rax. Эта инструкция сравнивает записанное в rax значение с 1. Она ничего не делает с этой информацией, а просто готовит те вещи, с которыми мы позже сможем поработать.

    jle .done

Эта инструкция работает над предыдущей инструкцией сравнения. Здесь jle означает «jump if less than or equal to» (перейти в случае, если значение меньше или равно x). Таким образом, если rax меньше или равно 1, то выполнение кода сразу перейдёт в стадию готово (done): это метка, завершающая цикл. В противном случае, выполнение продолжится до следующей инструкции, которая запустит тело цикла.

    imul rdi, rax

Если программа не выскочила из цикла к метке .done:, то известно, что n должно быть равно 2 или выше. Эта инструкция умножает rdi на rax и сохраняет результат в rdi.

    dec rax

Эта инструкция уменьшает rax на единицу, то есть вычитает 1. Если значение в rax равно 5, то эта инструкция установит его в 4.

    jmp .loop

Эта инструкция переходит обратно к метке .loop:, и с этого цикл начинается снова.

  .done:

Как только работа с циклом закончится, выполнение кода перейдёт сюда:

    ret

Теперь результат вычисления факториала должен находиться в rdi. Эта инструкция завершает функцию, в результате чего выполнение кода возвращается к той точке, в которой мы остановились, когда была вызвана эта функция. Возвращаемое значение n! останется в регистре rdi, чтобы им могла воспользоваться вызывающая сторона.

Как видите, вся заложенная здесь логика очень похожа на логику из версии C. Реализация сравнительно высокоуровневых конструкций, например цикла while из C, требует перескакивать между метками и отдельными инструкциями сравнения, но работает всё одинаково. Эта функция гораздо хуже самодокументирована, так как в ней нет формального определения типов, но в остальном она принимает всё тот же ввод и возвращает всё тот же вывод.

Факториалы в машинном коде

Выше мы рассмотрели функцию факториала, написанную на ассемблере, но может ли компьютер выполнять её напрямую? Ну… почти. Ассемблер можно считать мнемоникой для работы с машинным кодом — то есть каждая ассемблерная инструкция соответствует одной инструкции машинного кода. Но в ассемблере инструкции обозначаются сокращёнными английскими словами и десятичными числами, человеку так понятнее читать и писать.

Можно ассемблировать код вручную, для этого есть удобная справка по адресу ref.x86asm.net. Подробный рассказ о сборке машинного кода вручную — это, пожалуй, тема для отдельного поста. Но просто из интереса давайте рассмотрим, как ассемблерная функция может соотноситься с машинным кодом.

Обратите внимание: здесь я опущу некоторые распространённые оптимизации.

Полюбуйтесь!

48 bf 01 00 00 00 00 00 00 00 48 3d 01 00 00 00 7e 0c 48 0f af f8 48 ff
c8 e9 ec ff ff ff c3

Это функция факториала, записанная в машинном коде. Всё понятно, верно? Рад, что вам понятно, спасибо, что дочитали!

...

Да, мне тоже приходится через это продираться, но примерно так компьютер и видит машинный код. Это большой лоскут байт, находящийся где-то в памяти. В регистре rip хранится адрес одного из этих байтов. Выполняя инструкцию, компьютер проверяет значение rip, чтобы узнать, куда оно указывает, а затем декодирует данные, которые там находит. Таким образом, руководствуясь набором правил, компьютер разбирается, какая инструкция понимается под какой последовательностью байт.

Декодировав информацию, ЦП делает то, что предписывает инструкция. По умолчанию rip должна указывать на следующую инструкцию, которая должна быть выполнена после команды, выполненной только что. Таким образом, в следующий раз, когда ЦП будет выполнять инструкцию,  rip будет указывать уже на следующую инструкцию в памяти. Поэтому инструкции будут выполняться последовательно. Но в некоторых случаях (например, при переходах) инструкция изменяет регистр rip так, чтобы он указывал куда-то ещё — и выполнение становится скачкообразным.

Вышеприведённый код представлен в шестнадцатеричной системе. Каждый элемент шестнадцатеричного числа занимает один байт. Этот код можно с тем же успехом представить как последовательность нулей и единиц (8 на байт) или в десятичном выражении (число от 0 до 255 на каждый байт). Например:

Не столь важно, каким образом представлены данные. При желании вы могли бы изобрести ваш собственный формат кодировки, правда, никто, кроме вас, не знал бы, как его читать.

Поскольку пользы от этого лоскута байт мало, давайте разобьём его на инструкции:

48 bf 01 00 00 00 00 00 00 00   mov rdi, 1

48 3d 01 00 00 00               cmp rax, 1
7e 0c                           jle .done       ; Переход вперёд на 12 байт

48 0f af f8                     imul rdi, rax
48 ff c8                        dec rax

e9 ec ff ff ff                  jmp .loop       ; Переход назад на 20 байт

c3                              ret

Пожалуй, самая существенная разница между этой версией и ассемблерной (кроме того, что короткие англоподобные словечки преобразуются в бульон шестнадцатеричных цифр) — в том, что здесь нет меток. Дело в том, что метки вроде factorial: и .done: предоставляются в ассемблерах просто для удобства. В машинном коде переход делается так: меняется значение в rip, чтобы эта инструкция указывала куда-то ещё.

Рассмотрим ассемблированную версию jle .done:

7e 0c                           jle .done       ; Переход на 12 байт вперёд

Разберём, что означает каждый байт в этой инструкции:

Таким образом, 7e приказывает компьютеру сделать переход, а куда — зависит от предыдущей инструкции cmp. 0c указывает, куда именно переходить, если переход состоится. 0c — это 12 в шестнадцатеричном представлении. В совокупности это означает, что нужно перейти на 12 байт вперёд от актуальной позиции.

При исполнении инструкции rip будет указывать на следующий после этой инструкции байт. Поэтому при выполнении 7e 0c (jle .done) rip будет указывать на 48 0f af f8 (imul rdi, rax). При переходе значение rip будет увеличено на 12, в результате чего он будет указывать c3 (ret) до самого конца. Таким образом, следующей будет выполнена инструкция 48 0f af f8 (imul rdi, rax) либо c3 (ret), в зависимости от того, каков будет результат выполненного сравнения.

Что насчёт переходов назад? Принцип работы тот же, только используется отрицательный сдвиг. Рассмотрим код jmp .loop, совершающий переход обратно к началу цикла:

e9 ec ff ff ff                  jmp .loop       ; Переход на 20 байт назад

Эту инструкцию можно разделить на две части, как и предыдущую:

Таким образом, e9 приказывает ЦП совершить переход, а ec ff ff ff указывает, что перейти нужно на 20 байт назад. При выполнении этой инструкции rip будет указывать на c3 (ret) в конце функции. Применив к rip дельту -20, мы добьёмся, что поток выполнения откатится на 20 байт назад к 48 3d 01 00 00 00 (cmp rax, 1), в результате чего цикл выполнится снова.

Предоставляя метки и совершая переходы по меткам, а не по сдвигам, работать становится значительно удобнее — именно поэтому в ассемблерах и есть такая фича. Без них для реализации управляющих структур, например, условных операторов или циклов, пришлось бы подсчитывать байты. Всякий раз при добавлении, удалении или даже изменении инструкций вам пришлось бы заново пересчитывать значения всех смещений при переходах. Таким образом, польза ассемблеров далеко не ограничивается переводом псевдоанглийских сокращений вроде jmp или rax в их двоичные эквиваленты.

Если не считать того, что метки заменяются относительными смещениями, а вся прочая информация преобразуется в двоичный формат, логика машинного кода не отличается от ассемблера, который, в свою очередь, очень близок к C. Складывается впечатление, что все языки и форматы состоят в каком-то родстве друг с другом. Страшно!

Заключение

Здесь мы рассмотрели, как можно выразить одну и ту же идею на всё более низкоуровневых языках вплоть до машинного кода. Надеюсь, этот опыт получился интересным и, возможно, даже открыл вам на что-то глаза. Спасибо, что дочитали!