Музей языков

Поисковик из прошлой главы выбросил из наших учебников весь код: для мешка слов программа — шум из for и print. Но программу так читать нельзя. В строке a, b = b, a % b важен каждый знак и каждая позиция: поменяйте местами a и b справа — и алгоритм Евклида перестанет находить делитель. Как же одна программа понимает другую — интерпретатор понимает наш код, компилятор переводит его в машинные команды? Прежде чем учить машину читать программы, посмотрим, что ей придётся читать.

А читать придётся много. Языков программирования не десять и не сто.

В интернет-энциклопедии истории языков программирования HOPL собраны языки с XVIII века до наших дней. Сколько их там?

около 300 около 2 000 почти 9 000 около 50 000

8945 языков и около 7800 связей «кто на кого повлиял». Большинство из них давно никто не запускает, но несколько десятков живы и сегодня, а самому старому из живых почти семьдесят лет.

Зачем людям столько языков, если любой из них, как мы увидим в подвале, умеет вычислить то же, что и любой другой? Ответ лучше искать в экспонатах. Эта глава — музей. В каждом зале выставлена одна и та же программа: наибольший общий делитель чисел 1071 и 462 по алгоритму Евклида — вы уже писали его в задаче главы 5. Ответ везде один — 21. Меняется всё остальное: как записана программа, когда и кем она могла быть написана и что в ней считается главным.

Начнём с запасника. Экспонаты из него пока без табличек: по виду программы угадайте язык и год его рождения. Это легче, чем кажется. У языков, как у почерков, есть приметы эпохи: заглавные буквы и номера строк, скобки, необычные значки, слова английского языка вместо знаков.

Запасник: экспонаты без табличек

Год угадывается неплохо. Ранние программы кричат заглавными буквами — на перфокартах строчных не было — и прыгают по номерам строк. Потом появляются begin … end и фигурные скобки, ещё позже — стрелки и аккуратные отступы. Но всё это внешность, а языки различаются глубже. Пройдём по залам.

Зал 1. FORTRAN, 1957: от лени

Вот наш экспонат в том виде, в каком его написали бы в 1960-х, на FORTRAN IV или FORTRAN 66 — ранних стандартах языка.

Каждая строка — одна перфокарта на 80 колонок, и у колонок свои роли. C в первой колонке делает карту комментарием, в колонках 1–5 стоит метка — номер, на который можно прыгнуть; сам оператор пишется с седьмой колонки по 72-ю.

Читается программа сверху вниз, как рецепт. M = 1071 — не уравнение, а команда «положи 1071 в ячейку M». Строка 10 — знаменитый арифметический IF на три выхода: если N отрицательно, прыгнуть на метку 20, если ноль — на 30, если положительно — на 20. Так в одной строке записан цикл while n != 0: строки 20–GO TO 10 — его тело, а MOD — остаток от деления. Типов переменных программа не объявляет вовсе. В FORTRAN их задавала первая буква имени: переменные на I, J, K, L, M, N — целые, остальные — дробные. Поэтому числа здесь живут в M, N и K, а не в A и B: A = 1071 было бы числом с плавающей точкой.

Так выглядит императивное программирование: программа — это последовательность команд, каждая меняет содержимое памяти, а переходы решают, какая команда следующая. Это портрет машины фон Неймана из главы 32: ячейки, счётчик команд, прыжки. FORTRAN спрятал регистры и адреса за именами и формулами, но думать предлагал по-прежнему командами. Через двадцать лет Бэкус сам выступил против этого: в лекции при вручении премии Тьюринга в 1977 году он спросил, можно ли освободить программирование от «стиля фон Неймана». Ответ к тому времени давно искали в соседнем зале.

Зал 2. Лисп, 1958: программа из скобок

С Джоном Маккарти мы встречались в главе 10: в 1958 году — летом в IBM, с осени в MIT — он придумывал язык для задач искусственного интеллекта и взял для записи функций λ-нотацию Чёрча. Статья о новом языке вышла в апреле 1960 года в Communications of the ACM и называлась «Рекурсивные функции символьных выражений и их вычисление машиной». Лисп — второй по старшинству язык высокого уровня из тех, на которых пишут до сих пор; старше только FORTRAN. Вот наш экспонат на его современном наследнике, Common Lisp. Функция называется euclid, потому что gcd в Common Lisp уже встроена.

Первое, что бросается в глаза, — скобки и порядок слов. Любая запись в Лиспе имеет вид (что-сделать с-чем с-чем): сначала функция, потом аргументы. (mod a b) — остаток, (= b 0) — сравнение, даже знак равенства стоит впереди. Второе заметить труднее: в программе нет ни одного присваивания. FORTRAN менял содержимое ячеек M и N, пока N не обнулится. Лисп ничего не меняет: функция говорит, что НОД пары $(a, b)$ равен НОДу пары $(b, a \bmod b)$, и вызывает себя — рекурсия из главы 9 вместо цикла. Это функциональное программирование: программа описывает, как одни значения получаются из других, а не в каком порядке переписывать память.

Но в музее Лисп стоит за другое. Прочтите его программу как данные. Каждая пара скобок — список, внутри — слова, числа и другие списки. Определение функции — список из четырёх элементов: defun, имя, список параметров и тело. Тело — тоже список из четырёх: if, условие, ответ «да», ответ «нет». Запишем то же самое списками Python и нарисуем.

Программа на Лиспе — уже готовое дерево выражения, вроде тех, что мы обходили в главе 17. Для FORTRAN или Python текст сначала нужно разобрать: понять, что в a + b * c умножение выполняется раньше, где кончается условие и начинается тело. В Лиспе разбирать почти нечего: скобки уже расставлены, и программа может строить и менять другие программы как обычные списки. Мы тоже напишем интерпретатор Лиспа — в главе 51.

Зал 3. COBOL, 1959: язык для начальника

Программа разделена на «отделы», как служебная записка. В отделе данных каждая переменная описана как поле бланка: PIC 9(5) — пять десятичных цифр, не больше и не меньше. Поэтому программа напечатает GCD = 00021, с нулями впереди, как в графе ведомости. Нули здесь не для красоты: деньги в COBOL считаются в десятичных цифрах, и сотые доли не теряются так, как терялись в двоичных дробях главы 28. В отделе действий — почти английские фразы: «раздели A на B, получив частное Q и остаток R, перенеси B в A». Цикл PERFORM UNTIL … END-PERFORM появился в стандарте 1985 года; в 1960-м писали длиннее, через отдельные абзацы-подпрограммы.

Парадигма та же, что у FORTRAN, — императивная, а расчёт на другого читателя. FORTRAN писали для учёных, COBOL — чтобы программу мог прочесть руководитель отдела, который не знает формул, но знает, что такое остаток на счёте. Программы на COBOL до сих пор работают в банках: по оценке компании Gartner 1997 года, их было около 200 миллиардов строк.

Зал 4. APL, 1962: всё сразу

Кеннет Айверсон преподавал в Гарварде и в 1957 году начал придумывать математическую запись для алгоритмов: обычная доска с формулами казалась ему слишком бедной. В 1962 году он выпустил книгу «Язык программирования» — A Programming Language, отсюда и название, — а в 1966-м в IBM заработала первая полноценная реализация, APL\360. Для неё понадобилась особая головка пишущей машинки IBM Selectric: знаков в APL больше, чем букв на обычной клавиатуре. В 1979 году Айверсон получил премию Тьюринга, а его лекция называлась «Нотация как орудие мысли».

Самый короткий экспонат музея. В современных APL, например в Dyalog APL, знак ∨ для логических значений означает «или», а для целых чисел — наибольший общий делитель: Евклид встроен в один символ. Интереснее вторая строка: ∨ применяется сразу к четырём парам чисел, без всякого цикла. APL работает с массивами, и число для него — массив из одного элемента. В третьей строке ∨/ вставляет ∨ между всеми элементами списка, как reduce из главы 10. Четвёртая всё-таки пишет Евклида вручную: ⍺ и ⍵ — левый и правый аргументы, ⍵|⍺ — остаток от деления ⍺ на ⍵, ∇ — вызов самой себя, а двоеточие отделяет условие от ответа.

Так выглядит программирование массивами: цикл спрятан внутри операции. Тот же почерк есть и в Python — в библиотеке numpy, которая, как мы видели в главе 33, гоняет свои циклы на C.

У массивного почерка есть странность, которая показывает, как по-разному языки понимают знакомые знаки. В APL нет старшинства операций. Функций в нём десятки, и правило для всех одно: выражение вычисляется справа налево.

Чему в APL равно 2×3+4?

10 14 ошибка: без скобок нельзя

Справа налево: сначала 3+4 = 7, потом 2×7 = 14. Чтобы получить школьные 10, в APL пишут (2×3)+4 — или просто 4+2×3.

Запомните эти 14. Знаки 2×3+4 одинаковы для школьника и для APL, а смысл у них разный. К этой разнице между записью и смыслом мы вернёмся в зале синтаксиса, а в следующей главе увидим, как старшинство операций зашивают в грамматику языка.

Зал 5. C, 1972: поближе к железу

Этот зал вы уже видели изнутри. В главе 33 мы просвечивали функцию на C и смотрели, как она превращается в машинные команды. Деннис Ритчи сделал язык в Bell Labs в 1972–1973 годах, чтобы переписать на нём операционную систему Unix, и с тех пор на C написаны ядра почти всех систем, включая ту, на которой работает песочница курса. Экспонат здесь живой: модуль cs.c отдаёт текст компилятору tcc и запускает результат.

Почерк узнаваемый: фигурные скобки вокруг блоков, точка с запятой после каждой команды, while с условием в круглых скобках. Эту одежду потом надели C++, Java, C#, JavaScript, Go и ещё десятки языков, и потому программист на любом из них прочтёт этот экспонат без словаря. Парадигма — снова императивная, как у FORTRAN, только без меток и прыжков: цикл и функция стали словами языка. Новое — объявления. Каждая переменная получает тип заранее: int a обещает, что в a лежит целое число фиксированного размера, обычно 32 бита, и компилятор следит за обещанием ещё до запуска. Что из этого следует, выяснится в зале типов. Тип int в C — это то, что умеет регистр процессора; безразмерных целых, как в Python, здесь нет. C описывает машину лишь чуть-чуть абстрактнее ассемблера, оттого он и быстр.

Зал 6. Smalltalk, 1972: всё — объект

Начало истории Алана Кэя и Smalltalk рассказывала глава 12. Дальше было так: в Xerox PARC в 1972 году Кэй поспорил, что ядро языка, построенного на сообщениях между объектами, уместится на одной странице, а Дэн Ингаллс через несколько дней после того, как страница была готова, показал по ней работающий интерпретатор. Широкой публике язык показали только в 1981 году: о версии Smalltalk-80 журнал Byte напечатал целую серию статей. Программы на Smalltalk пишут не в файле: их вписывают прямо в работающую систему. Метод добавляют к классу Integer, и все целые числа сразу его умеют.

Читается это как переписка. 1071 euclid: 462 — объекту 1071 послали сообщение euclid: с аргументом 462, и число само знает, как на него ответить: в его классе есть такой метод. self — тот, кто получил сообщение, := — присваивание, \\ — остаток, ^ — вернуть ответ. Самое необычное — цикл. В Smalltalk нет оператора while. [b = 0] — это объект-блок, кусок кода в квадратных скобках, и ему посылают сообщение whileFalse: с другим блоком в аргументе: «повторяй вот это, пока ты ложен». Даже b = 0 — сообщение =, посланное объекту b. Условный оператор тоже сообщение: ifTrue: посылают логическому значению.

Это объектно-ориентированное программирование в чистом виде: программа — множество объектов, которые хранят своё состояние и посылают друг другу сообщения. Simula, с которой начиналась глава 12, придумала классы, а Smalltalk довёл идею до конца: объектом стало всё. Python в этом смысле ближе к Smalltalk, чем кажется.

Знак % в Python — вежливая запись сообщения __mod__, посланного числу. У числа есть методы, а число, функция и сам класс int — объекты. Через такие же специальные методы в главе 12 кролик учился печататься.

Зал 7. Пролог, 1972: спросите, а не прикажите

Здесь нет ни функции, которая что-то возвращает, ни цикла. Есть два утверждения об отношении «G — наибольший общий делитель A и B». Первое — факт: НОД числа A и нуля равен A. Второе — правило: :- читается «если», запятые — «и». НОД A и B равен G, если B больше нуля, R — остаток от деления A на B и НОД B и R равен G. Слова с большой буквы — переменные, с маленькой — имена. Последняя строка — запрос: «при каком G верно gcd(1071, 462, G)?». Как искать ответ, программа не говорит. Пролог ищет сам: перебирает правила сверху вниз, подставляет значения переменных и, если зашёл в тупик, возвращается и пробует следующее правило.

Это логическое программирование — ещё одна разновидность декларативного подхода, знакомого по SQL из главы 45: описать, что верно, а поиск оставить машине. Попробуйте сами. Ниже — маленький Пролог, работающий прямо в браузере. В нём две базы: наш НОД и родословная языков музея по данным Википедии о том, кто на кого повлиял.

Интереснее всего запросы с неизвестными. предок(X, python) спрашивает «кто все предки Python?», и Пролог перечисляет их одного за другим: тот же текст программы работает в обе стороны. В запросе повлиял(X, Y), повлиял(Y, python) неизвестных уже два: Пролог ищет, кто повлиял на тех, кто повлиял на Python. А кнопка «Переставить правила» показывает обратную сторону. Правило предок(X, Y) :- предок(X, Z), повлиял(Z, Y) логически верно, но Пролог, доказывая предок, первым делом снова пытается доказать предок — и так без конца, как рекурсия без базы из главы 9. Логика та же, а поведение зависит от порядка правил и целей в них: программисту на Прологе всё-таки приходится помнить, как машина ищет.

Зал 8. Haskell, 1990: функции без последствий

К середине 1980-х функциональных языков развелось так много — ML, Miranda, Hope, SASL, — что исследователи мешали друг другу: каждый писал на своём. В 1987 году на конференции по функциональным языкам в Портленде собрали комитет, чтобы сделать общий открытый язык. Первое описание вышло в 1990 году. Язык назвали в честь логика Хаскелла Карри; его имя носит и приём «каррирование».

Программа выглядит как определение из учебника математики: два равенства, и подходящее выбирается по образцу аргументов. Если второй аргумент — ноль, ответ a; иначе — НОД от новой пары. Первая строка — тип: euclid берёт два целых и возвращает целое. Его можно и не писать — компилятор Haskell выведет типы сам и проверит их до запуска; как он это делает, расскажет глава 53.

Haskell доводит до конца то, что начал Лисп. В Лиспе присваивание всё-таки есть, хоть им и редко пользуются. В Haskell его нет совсем: функция не может ничего изменить, ни переменную, ни файл, ни экран. Даже печать здесь — значение особого типа IO, описание действия, которое выполнит система. С этим связано второе свойство — ленивость: раз вычисление ничего не меняет, его можно отложить до момента, когда результат понадобится. Выражение take 5 (filter even [1..]) берёт первые пять чётных из бесконечного списка всех натуральных чисел и спокойно возвращает [2,4,6,8,10] — так же по требованию работают генераторы Python из главы 10.

Зал 9. Python, 1989: язык для людей

После восьми залов этот экспонат читается иначе. Отступы вместо begin … end и скобок — от ABC. Цикл и присваивание — императивное наследство FORTRAN и C. a, b = b, a % b присваивает обе переменные разом, почти как функциональная запись «новая пара — это $(b, a \bmod b)$». Рядом в этой книге уже были lambda, map и генераторы из функционального зала, классы и сообщения из зала Smalltalk, а numpy принёс массивы APL. Python — язык многопарадигменный: на нём можно писать любым из этих почерков. В списке языков, повлиявших на Python, Википедия называет ABC, ALGOL 68, APL, C, C++, Haskell, Лисп, Standard ML и ещё полдюжины.

Пять почерков

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

Парадигма — скорее способ думать, чем свойство языка, и в многопарадигменном языке видно, как одна и та же задача меняет почерк. Возьмём задачу проще НОДа: сумма квадратов нечётных чисел от 1 до 10.

Четыре раза 165. Первый вариант говорит машине, что делать по шагам, второй — как одни значения получаются из других, третий — что сделать сразу со всем массивом. Четвёртый, включение из главы 10, ближе всего к математической записи $\sum_{x \le 10,\ x \text{ нечётно}} x^2$. Опытный программист на Python выберет последний: он короче и читается как определение. Но полезно уметь все, потому что каждый язык подталкивает к своему. Потренируйтесь узнавать почерк с первого взгляда.

Синтаксис и смысл

В зале APL выражение 2×3+4 дало 14, хотя школьник получит 10. Знаки те же, смысл другой. В языках, как и в естественной речи, различают две вещи. Синтаксис — правила записи: какие слова и знаки где могут стоять. Семантика — смысл записанного: что произойдёт, когда программа выполнится. Все экспонаты музея синтаксически разные, а семантически одинаковые — все вычисляют 21. Бывает и наоборот: одна и та же строка допустима в нескольких языках и значит в них разное. Вот три таких строки в Python и в C.

В C знак / между целыми — деление нацело, и 7 / 2 даёт 3. В Python с третьей версии / — всегда обычное деление, а нацело делит //. Но и деление нацело у них разное: C отбрасывает дробную часть, округляя к нулю (−3,5 → −3), а Python округляет вниз (−3,5 → −4). Остаток подстраивается под частное, чтобы сохранялось равенство $a = (a \mathbin{/\!/} b) \cdot b + a \bmod b$: в C $-7 = (-2) \cdot 3 + (-1)$, в Python $-7 = (-3) \cdot 3 + 2$. Обе семантики разумны. Но программа, перенесённая из одного языка в другой знак в знак, начнёт молча ошибаться на отрицательных числах — например, при вычислении дня недели для дат до начала отсчёта.

С языком JavaScript, на котором работает почти каждый сайт, картина ещё пестрее. Сравните сами.

Особенно коварен знак =. В FORTRAN, C и Python это присваивание: «положи в ячейку». В Haskell — определение: x = x + 1 там не прибавляет единицу, а определяет x через само себя, и вычислить такой x нельзя: программа зациклится или остановится с жалобой на петлю. В Прологе = означает «сделай две стороны одинаковыми, подставив значения переменных». В ALGOL, Pascal и Smalltalk для присваивания завели отдельный знак :=, чтобы его не путали с равенством. В C if (x = 0) — не сравнение, а присваивание нуля, и условие всегда ложно, но программа компилируется. Python закрыл эту ловушку синтаксисом: if x = 0: там — SyntaxError.

Кто проверяет типы и когда

Третье, по чему различаются языки, — отношение к типам. С типами мы встречаемся с главы 2: "5" + 2 в Python — ошибка, потому что строку и число не складывают. Но когда язык замечает ошибку и замечает ли вообще — у языков по-разному. Это два независимых вопроса.

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

Ошибка в функции была всё время, но первые два вызова прошли: выполнение ни разу не заходило в ветку с ней. Третий вызов упал. В большой программе такая ветка может спать годами, пока не придёт редкий вход. Компилятор C, Haskell или Rust нашёл бы её до первого запуска — в этом сила статической проверки. Платить за неё приходится объявлениями и гибкостью. Функции на Python всё равно, какое значение ей дали, лишь бы оно умело то, что с ним делают; это утиная типизация из главы 12.

Второй вопрос — что делать, если типы не сходятся. Python отказывается: сложить строку с числом нельзя. JavaScript превращает число в строку и склеивает: "пионер " + 1957 — это "пионер 1957". Язык, который молча приводит значения к подходящему типу вместо ошибки, называют языком со слабой типизацией, а тот, что отказывается, — со строгой. А C, язык со статическими типами, типизирован слабо.

Компилятор C знал типы всех значений — и всё равно молча обрезал 1071,9 до 1071, уложил 1071 в байт как 47 и прибавил к строке число, сдвинув её начало на две буквы. Компилятор не сломан: правила языка разрешают такие преобразования, и слабость оставлена в C сознательно, ради скорости и близости к железу. Python, проверяющий типы на ходу, отказался. Получается таблица из четырёх клеток.

Клетки нарисованы чётче, чем они есть. «Строгая» и «слабая» — края шкалы, и общепринятых делений на ней нет. Даже в Python True + True равно 2, а 1 + 2.5 молча становится дробью: это маленькие уступки слабости. Зато вопрос «когда проверяют» понятен всегда, и его цену мы измерим в главе 53: там типы будут судить, а проверку типов вы напишете сами.

Компилятор или интерпретатор — не свойство языка

Про языки часто говорят «компилируемый» или «интерпретируемый». Это неточно. В главе 33 мы различали переводчика, который переводит книгу заранее, и толмача, который переводит фразу за фразой. Одну и ту же книгу может перевести и тот и другой. Язык — это синтаксис и семантика из его описания, а компилятор или интерпретатор — реализация, и у одного языка их бывает много. CPython компилирует Python в байт-код и интерпретирует его, PyPy исполняет тот же язык, компилируя горячие места в машинный код на ходу. C обычно компилируют заранее, но tcc в нашей песочнице переводит программу в память и тут же запускает. У Лиспа уже в начале 1960-х были и интерпретатор, и компилятор.

Поэтому полезнее спрашивать, легко ли язык компилировать. Чем больше язык знает о программе до запуска — типы, размеры, какие функции вызываются, — тем лучший машинный код можно построить заранее. C знает почти всё, Python — почти ничего, и это одна из причин разницы в скорости, которую мы измерили в главе 33. А в одном из языков подвала компилятор настолько прост, что его можно написать за вечер. Спустимся.

Подвал: эзотерика

В подвале музея хранят языки, которые писали, чтобы что-то доказать или над чем-то посмеяться; работать на них никто не собирался. Они называются эзотерическими. Старейший — INTERCAL: в 1972 году два студента Принстона, Дон Вудс и Джеймс Лайон, сделали пародию на языки своего времени. Компилятор INTERCAL отказывается собирать программу, если в ней слишком редко встречается слово PLEASE — программа «недостаточно вежлива», — и если слишком часто — «чрезмерно вежлива».

Больше в языке ничего нет. Лента из 30 000 клеток, в каждой — байт от 0 до 255, указатель на одну из них и восемь команд; всё остальное в тексте программы — комментарии. Нет ни переменных, ни чисел, ни функций, ни даже if: условие делают циклом, который выполняется один раз.

Последний экспонат в подвале — наш НОД. Числа больше 255 в клетку не помещаются, поэтому вместо 1071 и 462 программа получает на вход 252 и 105: у них тот же наибольший общий делитель, 21. Программа читает числа цифра за цифрой, делит с остатком повторным вычитанием и печатает ответ десятичными цифрами: 1892 символа и больше двухсот тысяч шагов. Руками такое не пишут: программу собрал генератор на Python из «макросов» вроде «скопировать клетку» и «если в клетке ноль» — маленький компилятор на Brainfuck. О том, как компиляторы переводят с языка на язык, — глава 52.

В музее такой язык стоит потому, что отвечает на вопрос, с которого мы начали. Восьми команд хватает, чтобы записать любое вычисление, которое можно записать на Python или C: Brainfuck, как говорят, полон по Тьюрингу. А ещё в 1964 году итальянский математик Коррадо Бём описал язык P′′ для машины с лентой — крошечный, без ввода-вывода, и три команды Brainfuck повторяют его команды почти дословно. Что именно значит «любое вычисление» и как это доказывают, — тема главы 55. Нам сейчас хватит вывода: языки различаются не тем, что на них можно вычислить, а тем, как это записывать и думать об этом. По вычислительной силе Brainfuck и Python равны, но НОД на Python занимает четыре строки, а на Brainfuck — 1892 символа.

Почему языков тысячи

Теперь видно, почему языков тысячи. Каждый экспонат подогнан сразу под три вещи. Машина: FORTRAN делали для IBM 704, C — чтобы писать операционную систему. Задача и тот, кто её решает: учёный с формулами, бухгалтерия с ведомостями, исследователь искусственного интеллекта с символами, математик с массивами. И идея о том, что такое программа: команды, функции, правила, объекты, массивы. Все три всё время меняются, и языки продолжают рождаться: Go в 2009 году, Rust в 2015-м.

Алан Перлис, первый лауреат премии Тьюринга, написал в 1982 году: «Язык, который не влияет на то, как вы думаете о программировании, не стоит того, чтобы его знать». Перлис не преувеличивал: программист, видевший Лисп, иначе смотрит на рекурсию, видевший APL — на циклы, а после Пролога и поиск выглядит по-другому. А ещё музей учит читать незнакомое.

Задачи

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

Напишите bf(code, inp="") — интерпретатор Brainfuck. Функция исполняет программу code и возвращает всё, что она вывела, одной строкой. Лента — 30 000 клеток с нулями, указатель в начале на клетке 0. Клетка — число от 0 до 255: + на 255 даёт 0, - на нуле — 255. Команда . выводит chr клетки, , кладёт в клетку код следующего символа строки inp, а если ввод кончился — ноль. Символы, кроме восьми команд, — комментарии. Если скобки не парные, поднимите ValueError. В тестах есть программа НОД из главы и цикл на миллион шагов.

Шесть команд из восьми — по строчке, они есть в таблице главы. Для , заведите счётчик прочитанных символов k: если k < len(inp), кладите ord(inp[k]), иначе ноль, и в любом случае увеличивайте k.

Скобки. [ при нуле в клетке прыгает за парную ], ] при не нуле — к парной [. Какая скобка парная, можно искать каждый раз, считая вложенность, но быстрее найти все пары заранее, одним проходом со стеком, как проверку скобок в главе 15, и сложить в словарь «номер скобки → номер пары». Там же обнаружатся и непарные скобки.

После прыжка не забудьте, что в конце цикла стоит pc += 1: если записать в pc номер парной скобки, следующей выполнится команда сразу за ней — так и нужно в обоих случаях.

Сорок строк — и у вас исполнитель языка, на котором, как мы знаем, можно записать любое вычисление. Устроен он так же, как процессор из главы 32 и интерпретатор байт-кода из главы 33: счётчик команд, выборка, исполнение, переход. Таблица скобок, построенная до запуска, — первый шаг к компиляции: мы один раз разобрали программу, чтобы потом не разбирать её на каждом шаге. Следующая задача делает этот шаг до конца.

Интерпретатор из прошлой задачи на каждом шаге заново выясняет, что за команда перед ним. Компилятор делает это один раз. Напишите to_python(code), которая переводит программу на Brainfuck в текст программы на Python. В тексте должна быть функция program(inp), которая делает то же, что bf(code, inp), и возвращает вывод строкой. Каждая команда превращается в строку Python, [ — в while tape[p]: с телом на отступ глубже. Непарные скобки — ValueError. Тесты выполняют полученный текст через exec и гоняют в нём тройной цикл на 16 миллионов оборотов, отводя на это пять секунд; интерпретатору из прошлой задачи такой цикл обходится в несколько раз дороже.

[ добавляет строку while tape[p]: и увеличивает depth, ] уменьшает его. Если depth пытается опуститься ниже единицы — лишняя ]; если в конце он больше единицы — незакрытая [.

У цикла [] пустое тело, а в Python пустое тело запрещено. Если последняя добавленная строка кончается двоеточием, перед закрытием цикла добавьте pass.

Перевод станет короче и быстрее, если сливать повторы: пять плюсов подряд — одна строка tape[p] = (tape[p] + 5) % 256, три > — p += 3. Строка Python стоит одинаково, сколько бы в ней ни прибавлялось. Тесты уложатся во время и без этого, но на программах с длинными цепочками плюсов разница заметна.

Перевод программы НОД занимает около 870 строк Python и работает в несколько раз быстрее интерпретатора: вся работа по разбору текста сделана один раз, до запуска, а оставшееся Python выполняет как обычный код — тот же выигрыш, что у компилятора перед толмачом в главе 33. Это ещё и первый в курсе компилятор, который переводит в другой язык высокого уровня, — так работают, например, переводчики с TypeScript на JavaScript. Следующий шаг — замечать в программе целые идиомы: [-] значит «обнулить клетку», [->+<] — «прибавить клетку к соседней». Так поступают оптимизирующие компиляторы, о них — глава 52.

FizzBuzz — детская игра на деление, ставшая знаменитой задачей с собеседований: числа от 1 до $n$, но вместо кратных трём — "Fizz", вместо кратных пяти — "Buzz", вместо кратных пятнадцати — "FizzBuzz". Напишите три функции, каждая возвращает список строк ["1", "2", "Fizz", "4", "Buzz", …], но своим почерком. fizzbuzz_loop(n) — императивно, с циклом for или while. fizzbuzz_func(n) — функционально: внутри нет ни операторов цикла, ни присваиваний (и := тоже), ни append и других методов, меняющих список. fizzbuzz_noif(n) — без единого if: ни оператора, ни … if … else …, ни условия во включении, ни match. Функции не вызывают друг друга. Проверка читает код через модуль ast — о нём в следующей главе.

Функциональный почерк: map(функция, range(1, n + 1)) применяет функцию к каждому числу, а list(...) собирает результаты. Функцию для одного числа можно написать lambda, а внутри неё условие — выражением … if … else …: присваиванием оно не считается. Подойдёт и включение [... for i in range(1, n + 1)] — это выражение, а не оператор цикла.

Без if — два пути. Арифметика: "Fizz" * True — это "Fizz", а "Fizz" * False — пустая строка; пустая строка ложна, и "" or "7" даёт "7". Или таблица: ответ зависит только от i % 15, а значит, его можно взять из кортежа из пятнадцати элементов по индексу.

Функциональный вариант склеивает «Fizz» и «Buzz», умножая строки на логические значения: True в арифметике Python — это 1: маленькая слабость типизации, о которой шла речь в разделе о типах. Если не вышло ни того ни другого, получилась пустая строка, и or подставляет число. Вариант без if — таблица: на месте 0 стоит «FizzBuzz», на местах 3, 6, 9, 12 — «Fizz», на 5 и 10 — «Buzz». Ветвление превратилось в чтение по индексу — так думают программисты на APL. Впрочем, or — тоже ветвление, спрятанное в логику: выбирать между вариантами программа не перестала, изменилась только запись.

Куда дальше

Каждый экспонат музея — текст. Чтобы что-то вычислить, машина должна понять его строение. В подвале с этим легко: каждый символ Brainfuck — отдельная команда, а всё остальное пропускается, поэтому интерпретатор из задачи читает программу по одной букве. Лисп почти так же прост: скобки уже расставлены, и программа лежит готовым деревом. Но возьмите строку 2 + 3 * (4 - 1), которую поймёт и Python, и C, и JavaScript.

Python скажет 11. Значит, он понял, что 4 - 1 в скобках считается первым, что умножение сильнее сложения и что 3 * (4 - 1) — одно целое, а не «3 умножить на 4, а потом минус 1». APL прочёл бы те же символы справа налево, и ответ случайно совпал бы. Для одной формулы мы уже строили такой разбор в главе 15 — сортировочной станцией Дейкстры с таблицей старшинства. Но в Python есть не только формулы: if внутри for внутри def, вызовы, списки, включения. Как программа понимает строение текста, в котором вложено всё во всё? Чтобы ответить, придётся поработать лингвистом: следующая глава отправляет вас в экспедицию к носителям незнакомого языка.