Теоретический минимум по Computer Science

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

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

• чтения и записи данных в памяти;

• условного ветвления (если адрес памяти имеет заданное значение, то перейти к другой точке в программе).

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

Недавно было показано, что команда ЦП под названием MOV («перемещение») является полной по Тьюрингу. Это значит, что ЦП, который выполняет только команду MOV, способен делать все то, что может полноценный ЦП. Другими словами, любой тип программного кода вполне реально выразить исключительно с помощью команды MOV[76].

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

Рис. 7.8[77]

Операционные системы

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

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

Вот почему в своей работе программы опираются на операционную систему. Благодаря ее помощи они легко работают с различными аппаратными средствами. Программы совершают специальные системные вызовы, чтобы ОС выполнила необходимые операции ввода-вывода. Компиляторы переводят команды ввода-вывода в надлежащие системные вызовы.

Однако разные ОС часто используют несовместимые системные вызовы. Системный вызов печати чего-либо на экране в Windows отличается от такового в Mac OS или Linux.

Вот почему, если вы компилируете программу для выполнения в Windows с процессором x86, она не будет работать в Mac с таким же процессором. Скомпилированный программный код должен быть ориентирован не только на конкретную архитектуру процессора, но и на конкретную операционную систему.

Оптимизация при компиляции

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

Именно поэтому вам не следует жертвовать простотой чтения кода в пользу его микрооптимизации. Компилятор так или иначе применит все тривиальные оптимизации. Посмотрите на этот фрагмент кода:

function factorial(n)

····if n > 1

········return factorial(n — 1) * n

····else

········return 1

Кто-то скажет, что его лучше заменить на этот эквивалент:

function factorial(n)

····result ← 1

····while n > 1

········result ← result * n

········n ← n — 1

····return result

Да, выполнение процедуры factorial без рекурсии использует меньше вычислительных ресурсов. Но это еще не повод менять программный код. Современные компиляторы автоматически перепишут простые рекурсивные функции. Вот еще один пример:

i ← x + y + 1

j ← x + y

Компиляторы избавятся от повторного вычисления x + y и сделают вот такое преобразование:

t1 ← x + y

i ← t1 + 1

j ← t1