Бывают столь совершенные виды красоты и столь блестящего достоинства, что люди, тронутые ею, ограничиваются тем, что смотрят на нее и говорят о ней. Ж. Лабрюйер
APL – самое, пожалуй, экзотическое растение в мире языков программирования. Некоторые воспринимают его просто как курьез, другие видят в нем серьезный прикладной язык для реальных задач (хотя они и в меньшинстве), но у каждого, кто впервые видит программу, написанную на APL, она вызывает легкий шок.
Программы эти больше напоминают магические формулы, заклинания шаманов или древние зашифрованные письмена, но никак не воплощение алгоритма, способного решать поставленную задачу.
Чтобы сразу ошарашить читателя, приведём без всякого объяснения программу, которая находит индексы всех элементов вектора X в векторе Y:
(((1,A)/B)⌊1+⍴Y)[(⍴Y)↓(+\1,A←(1↓A)≠¯1↓A←A[B])[⍋B←⍋A←Y,X]]
APL обладает двумя замечательными (от слова «замечать») свойствами:
В языке используется огромное число разнообразных, не встречающихся на клавиатуре ни одного из существующих в наше время компьютеров, символов[1];
Многие программы на APL занимают только одну строчку.
Эти два свойства несомненно связаны между собой. Чтобы понять, каким образом, мы должны сначала разобраться с этими "странными символами" - зачем они нужны и с чем их едят.
В самом начале 60-х, Кеннет Айверсон, который в то время был профессором Гарвардского университета, разработал математическую нотацию с целью облегчить преподавание прикладной математики. Нотация оказалась настолько эффективной, что Айверсон почувствовал возможность применить её как интерактивную систему для математических вычислений. А отсюда уже был один шаг до создания языка программирования на основе созданной нотации. В 1962 году Айверсон выпустил книгу под названием A Programming Language (проще этого названия трудно было придумать - "Язык программирования"), которая и дала имя будущему языку - APL. Так, по иронии судьбы, один из самых непохожих на "нормальные" языки программирования, APL носит гордое название - "язык программирования". Забегая вперёд, скажем, что в 1980 году за создание APL Кен Айверсон получил Премию Тьюринга.
В 1965 году Ларри Брид и Фил Абрамс из IBM Research Center в Йорктаун Хайтс построили первую экспериментальную систему APL. А в 68-м появился первый коммерческий транслятор APL\360, который, как ясно из названия, работал на компьютере IBM 360. Система была достаточно революционна для того времени - она была интерактивна, то есть позволяла набирать программы на терминале, подсоединённом к IBM 360, а не вводить их с помощью перфокарт. Кроме того, система APL/360 была интерпретатором, а не компилятором, а это значит, что, набрав на клавиатуре выражение языка, пользователь тут же получал ответ системы на экране - не было необходимости компилировать программу (то есть переводить её на машинный язык низкого уровня), а затем запускать.
Так выглядела клавиатура терминала, работающего с интерактивной системой APL, соединённого с IBM/360:
Конечно, эта клавиатура больше напоминает пульт управления инопланетного космического корабля, так как его любят изображать в фильмах низкого пошиба, и тем не менее каждый из символов обладает глубоким и чаще всего не единственным смыслом.
Здесь хочется привести интересную аналогию. Хорхе Луис Борхес в своей лекции "Каббала" пишет, что разница между священным текстом и обычной книгой заключается в различных подходах к рассмотрению текста. Если какой-либо филолог, пишет Борхес, начнёт подсчитывать количество букв и слов в "Дон Кихоте" его сочтут сумасшедшим, но священные тексты (такие как Ветхий Завет) рассматриваются именно таким образом (по крайней мере, каббалистами). В той же мере мы не придаём большого значения ключевым словам какого-либо языка программирования: например, в языке С можно с помощью препроцессора заменить все открывающие фигурные скобки на слово begin, а закрывающие на end, и смысл программы от этого не изменится. Кроме того, в С и подобных ему языках мы можем произвольно разбивать текст на строчки и вставлять лишние пробелы и табуляцию (ничто, кроме стиля, при этом не пострадает). В APL же, учитывая плотность информации на символ программы и тот факт, что множество программ APL занимают всего одну строчку, мы волей-неволей должны относиться к тексту программы, как к "священному писанию": каждый символ выполняет уникальную задачу на своём, единственно правильном месте. У читателя может возникнуть резонный вопрос: а зачем вообще нужен такой язык программирования, программы которого надо расшифровывать подобно египетским иероглифам ? Вместо ответа я предлагаю вам ещё раз взглянуть на эпиграф к этой главе.
Однако, довольно философии.
Основным предназначением APL является работа с многомерными массивами чисел - их создание, преобразование и произведение математических операций. В общих чертах некую "генеральную" программу на APL можно было бы представить такой формулой:
fn(fn-1(...(f3(f2(f1(array))))...))
Эта формула только на первый взгляд выглядит страшновато, но на самом деле она означает вот что: над данным массивом array производится некая операция (которая скорее всего будет выражена одним из символов APL) f1, над результатом которой производится операция f2, над результатом которой производится операция f3, и так далее.
Программа заканчивается выполнением операции fn, результат которой и будет результатом всего алгоритма.
Когда APL работает с массивами, это производит впечатление магии - как будто джинн из "Тысячи и одной ночи" в одно мгновение ока создаёт и разрушает дворцы. Возьмём, например, выражение ⍳0
Обычно функция ⍳ (читается iota) возвращает вектор всех натуральных чисел от 1 до заданного, но в виде ⍳0 она возвращает пустой вектор[2], попросту говоря ничего (не в том смысле, что ничего не возвращает, а в самом прямом, льюис-кэрролловском смысле возвращает ничто).
Так вот, возьмём это самое ничто и применим к нему операцию ⍴ (ro), которая создаёт массив заданной размерности:
(⍳ 1000)⍴ ⍳0 Здесь iota 1000 создаёт вектор от (1, 2, ..., 1000) и задаёт его в виде левого аргумента функции ro, которая в свою очередь создаёт тысячемерный массив из своего правого аргумента, то есть из ничего. В итоге мы получаем замок из песка - тысячемерный массив пустоты! Попробуйте-ка это осознать. А хотите создать всё из ничего? Возможно, но придётся применить магию посильней.
Начнём всё с того же ничего (⍳0) и применим к нему оператор / (reduce), который вставляет между всеми элементами вектора правого аргумента функцию, являющуюся левым аргументом. В качестве функции левого аргумента возьмём ⌊ (minimum), которая находит наименьшее число в векторе: ⌊ / ⍳0
Таким образом, мы пытаемся найти минимальное число среди несуществующих чисел. Результатом этого запрещённого в физической, но разрешённого в магической реальности APL действия будет число, которое единственное может устоять против невозможности операции нахождения минимума - это максимально возможное число APL, которое именно так и обозначается: ⌊ / ⍳0. Соответственно, минимально возможное число, которое единственное не подвержено несбыточности определения максимума среди пустоты обозначается ⌈ / ⍳0.
Уже знакомая нам функция ⍴ (ro), будучи применена к единственному аргументу справа, обладает другим свойством: она возвращает вектор измерений данного ей массива[3]. Например, если М - матрица 10 20 30 40 50 60 то выражение ⍴M вернёт вектор 2 3. А что будет, если мы применим функцию ro ещё раз к результату её выполнения:
⍴ ⍴ M Второй вызов ro возвращает вектор измерений вектора измерений M, то есть 2, и это... верно, размерность М!
Можно ещё долго упражняться в магии, но мы оставим самое интересное для второй части, в которой вас ждёт увлекательное приключение - задача по расшифровке "Жизни".
[1] В 1978 году компания IBM выпустила модель IBM 5110 со встроенным интерпретатором APL и соответствующей клавиатурой:
[2] В буквальном смысле "множество всех натуральных чисел от единицы до нуля".
[3] Необходимо заметить, что большинство встроенных функций APL обладают такой дуальностью: они работают по разному в зависимости от того, один или два у них аргумента. Более того, "Тао APL" проявляется ещё и в том, что почти каждая функция имеет своего двойника с противоположным значением. Так, например, scan (\) и reduce (/), минимум (⌊) и максимум (⌈), encode (⊤) и decode (⊥) и т.д.