Функциональное программирование 1.4

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

Под трансляцией программы обычно подразумевается преобразование её из некоторого исходного языка в некоторый целевой язык.

И исходный, и целевой языки могут быть языками высокого уровня, например, существуют трансляторы с Паскаля на С.

Обычно же перевод выполняется с языка более высокого уровня на язык более низкого уровня.

Компилятор – это транслятор, который преобразует программу с языка высокого уровня в некоторое низкоуровневое представление, обычно в машинный код.

Как правило, компилятор читает программу целиком из файла с исходным текстом, выполняя лексический анализ, затем синтаксический анализ, строит в памяти некоторое промежуточное представление программы (его называют абстрактным синтаксическим деревом), после чего проходит по этому дереву и конвертирует промежуточное представление в нужный целевой формат, например, инструкции для процессоров архитектуры Intel x86.

Результат записывается в файл на диске.

Файл имеет особый формат, понятный операционной системе, и называется исполняемым модулем.

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

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

Понятно, что компиляция занимает значительное время по сравнению с запуском скомпилированной программы.

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

Интерпретаторы работают несколько иначе.

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

Будучи считанной, очередная инструкция программы анализируется, и, если не возникло ошибок, исполняется.

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

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

Понятно, что интерпретируемая программа будет работать медленнее заранее скомпилированного исполняемого модуля.

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

Сделаем несколько замечаний.

Во-первых, интерпретация и компиляция – в определенном смысле равнозначные подходы, каждый обладает своими преимуществами.

Во-вторых, есть языки, которые допускают и компиляцию, и интерпретацию.

Примерами преимущественно компилируемых языков могут служить Паскаль, С, С++, Ада.

Примерами преимущественно интерпретируемых языков могут служить bash, ранние версии Lisp и ранние версии Basic.

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

При последующем запуске скрипта этап компиляции повторяется.

Типичными примерами таких языков могут служить Perl и Ruby.

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

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

В результате компиляции получается файл с байт-кодом, т. е. инструкциями не процессора целевой платформы, а инструкциями некоторой виртуальной машины.

Позднее байт-код передается на вход этой машине (иногда называемой средой исполнения) и переводится ей в инструкции целевой платформы, т. е. того процессора, на котором работает виртуальная машина.

Компилировать программу в байт-код можно на одной платформе, а исполнять – совсем на другой.

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

А как же выполняются программы, написанные на Lisp?

Если мы говорим о какой-либо реализации стандарта Common Lisp, то можно сказать, что поддерживаются оба подхода к выполнению программ.

Во-первых, программы на Lisp могут интерпретироваться.

Это наиболее традиционный вариант исполнения, в этом отношении Lisp похож на скриптовые языки.

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

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

К сожалению, у каждого компилятора свой формат файлов с промежуточным представлением, поэтому байт-код, скомпилированный, например, CLISP, не получится выполнить с помощью SBCL.

Наконец, можно сохранить программу и в виде исполняемого модуля, однако эта возможность предусматривается не всеми компиляторами Common Lisp.

Отдельный вопрос, который сейчас мы не будем обсуждать, касается принципов построения больших проектов на Lisp, включающих множество файлов с исходным кодом.

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

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

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

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

Такой режим известен как Read-Eval-Print Loop, или REPL.

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

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

Если строка, которую мы передаем интерпретатору, содержит ошибки, как это случилось со второй командой, Lisp напечатает сообщение об ошибке (в данном случае сообщение о том, что 40 – не имя функции) и предложит варианты устранения ошибки.

Если ввести :r1, то далее Lisp предложит заменить ошибочное значение на другое и повторит разбор команды.

Если ввести :r2, то Lisp прекратит выполнение команды с ошибкой.

Сравните вторую и четвертую команды.

Чтобы сложить два числа, нам нужно записать выражение немного по-другому.

Для того чтобы выйти из интерпретатора, достаточно ввести команду (quit) или (exit), а в Linux и OS X можно нажать комбинацию клавиш Ctrl-D.

Любая программа на Lisp является последовательностью так называемых форм.

Формы – это s-выражения, которые считываются интерпретатором и исполняются.

А s-выражение, в свою очередь, может быть представлено либо в виде отдельного значения, иногда называемого атомом, либо в виде списка, содержащего другие s-выражения, то есть другие списки и атомы.

Значения в списке разделяются пробелами, а сам список берется в круглые скобки.

S-выражения могут использоваться и для записи данных, и для записи команд.

Собственно, когда-то давно предполагалось, что s-выражения будут использоваться для данных, а для команд Маккарти предполагал использовать m-выражения, но первые реализации компиляторов подтвердили, что списки одинаково хорошо годятся и для данных, и для команд.

В результате Lisp стал первым языком, обладающим интересным свойством: код и данные в нем представляются одинаково.

Работу со списками как структурами данных мы рассмотрим немного позже.

А m-выражения в Lisp так и не понадобились.

Следует отметить, что любая правильная программа на Lisp является совокупностью s-выражений, однако не любое s-выражение является правильной программой на Lisp, в чем мы могли убедиться, обсуждая предыдущий пример.

В чем же дело?

Дело в том, что правильные формы в Lisp должны быть записаны с помощью префиксной нотации.

Префиксная нотация (польская запись) предполагает, что сначала записывается знак операции, а за ним следуют операнды.

Правильная форма в Lisp представляет собой или атом, или список, первый элемент которого указывает, какие действия необходимо выполнить с остальными элементами.

Сравните выражение проверки на равенство, записанное на С, и то же самое по смыслу выражение, записанное на Lisp: первым в списке идет знак операции, за ним – операнды.

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

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

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

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

В Lisp же нет нужды в самом понятии ранга операции.

К настоящему моменту вы уже обладаете достаточными знаниями, чтобы написать свою первую программу на Lisp.

Для простоты воспользуемся обычным текстовым редактором и компилятором Lisp.

Создадим в некотором каталоге текстовый файл, в который запишем одну единственную форму.

Это вызов функции print, выводящей в стандартный поток вывода строку "Hello, Lisp!".

Файлам с исходным кодом на Lisp обычно дают расширение .lisp или .lsp.

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

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

Если все прошло успешно, то интерпретатор считает команду из файла, и в результате мы увидим в консоли строку с приветствием.

Для того чтобы скомпилировать файл в байт-код, можем воспользоваться функцией compile-file.

Ей в качестве аргумента также передается путь к файлу с исходным кодом.

В том же каталоге, где мы сохранили файл hello.lisp, появится файл hello.fas.

После этого мы можем снова загрузить нашу программу, передав функции load путь к файлу с байт-кодом.

Мы можем проделать все те же операции и из командной строки.

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

Для компиляции в байт-код нужно запустить компилятор с параметром –c.

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

Итак, наша лекция подошла к концу.

Что нового мы узнали о функциональном программировании и языке Lisp?

Во-первых, мы очень кратко обсудили историю развития языков программирования и вычислительной техники и показали роль различных подходов (парадигм) в этом развитии.

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

Мы выбрали Lisp в качестве языка, который позволит нам познакомиться с приемами и базовыми концепциями функционального программирования.

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

Наконец, мы изучили основы синтаксиса Lisp и написали простейшую программу на Lisp, после чего выяснили, как её компилировать и запускать на выполнение.