Реализация - функциональный язык
Cтраница 1
Наиболее естественная потоковая реализация дли функциональных языков - это машина, управляемая данными. Она имеет семайтику аппликативного порядка, и именно эту модель вычислений мы рассмотрим в первую очередь. [1]
Общепринятым методом реализации функциональных языков типа LISP является использование четырехстековой машины, за которой закрепилось наименование SECD-машины. [2]
К сожалению, в реализациях расширенных функциональных языков применения неявно определенных функций, таких как split и difference, должны вычисляться с использованием отождествления, как это делается в реализациях логических языков, подобных Прологу, который обычно менее эффективен, чем основанное на реализации вычисление функциональных выражений. Более того, часто известно, что существуют, как и в нашем примере, рекурсивные, чисто функциональные реализации. Если бы можно было компилировать рекурсивно определенное обращение функции, задавая один из видов соответствующего отношения, тогда все его виды можно было бы реализовать, не прибегая к отождествлению во время выполнения. [3]
К настоящему моменту мы рассмотрели множество реализаций функциональных языков, интерпретационный и компиля-ционный подходы, языки со строгой и ленивой семантикой, основанные на вычислительных моделях, которые используют определенный контекст, редукцию графов и комбинаторы различных форм. В каждом случае возникает возможность повышения производительности выполнения программы и по времени выполнения, и по объему занимаемой памяти. Последний вид повышения производительности относится и к вопросу сборки мусора, рассмотренному в предыдущей главе, но подобный способ разрешения проблемы несколько похож на запирание конюшни после побега лошадей, поскольку в действительности хотелось бы прежде всего сократить потребность в какой-либо сборке мусора до минимума. Аналогично можно отметить определенную локальную оптимизацию, которая возникла в некоторых связанных в основном с компилятором МФО-реализациях, таких как компиляция авторекурсии в циклах. [4]
Ленивые мемо-функции были введены для использования их в ленивых реализациях функциональных языков; они упрощают представление в мемо-таблицах тех аргументов, хранение которых в полном вычисленном виде больше не является необходимым. При этом устраняются многие трудности, связанные с рекурсивной проверкой на равенство и хэшированием, так что эта методика также годится и для строгих реализаций. Основная мысль заключается в смягчении тех требований, которым должна удовлетворять мемо-функция; мы скоро увидим, что все мемо-функции могут быть заданы через ленивые мемо-функции; другими словами, использование ленивой методики не приводит к потере общности. Обычные мемо-функции, которые мы будем называть полными мемо-функциями, требуются для повторного использования уже вычисленных результатов, если они применяются к аргументам, равным тем, которые были использованы накануне. [5]
Описанная в этой главе G-машина хотя и является хорошей основой для полноценной реализация функционального языка, но тем не менее существует несколько способов оптимизации, выполнение которой целесообразно. [6]
Из данного обсуждения можно было бы заключить, что во избежание лишних вычислений и зацикливания все реализации функциональных языков должны быть ленивыми. Однако существуют значительные затраты, связанные с передачей параметров по необходимости, что будет показано в гл. В связи с этим некоторые функциональные языки обладают строгой семантикой или энергичной семантикой, означающей, что все функции являются строгими ко всем своим аргументам и все параметры последовательно передаются по значению. Однако имеются и другие языки, с противоположным подходом, обладающие ленивой семантикой; программа на таком языке ведет себя так, будто бы все параметры передаются по необходимости. Это не подразумевает, что все параметры должны на самом деле быть переданы по необходимости, поскольку, как было показано, параметр, который требуется функции всегда, может быть передан любым способом без влияния на поведение программы в целом. Таким образом, ленивая реализация подразумевает просто сохранение ленивой семантики, а не повсеместное использование вызова по необходимости, хотя, конечно, и такое возможно. [7]
Как будет показано в дальнейшем, это является важным моментом, поскольку дает основу для некоторых оптимизаций при реализациях функционального языка. [8]
Первая часть этой книги достаточно полно знакомит читателя с основами функционального программирования, и мы можем сейчас описать различные методы, используемые для реализации функциональных языков. Для того чтобы сохранить общность в наших рассуждениях, мы будем использовать специальную нотацию для функциональных выражений, которая является достаточно мощной, чтобы выразить все черты функционального языка, и в то же время достаточно простой, чтобы легко описать различные методы реализации без рассмотрения специфики исходных языков. Промежуточная нотация, которую мы будем использовать, называется лямбда-нотацией и происходит из области математической логики, называемой лямбда-исчислением, на котором основаны многие теоретические результаты в области функциональных языков. Часть II начинается с введения в лямбда-исчисление, где описывается синтаксис лямбда-выражений, а также правила переписывания, специфицирующие индивидуальные шаги, требуемые для вычисления, или редукции, заданного лямбда-выражения. Самое важное из этих правил, называемое р-редукцией, выражает в лямбда-исчислении применение функции. Неформально роль р-редукции состоит в том, чтобы заменить каждое вхождение формального параметра функции соответствующим параметром. Фактически в основе любой реализации лежит порядок, в котором выполняются последовательные р-редукции, и условия, при которых последовательность редукций завершается. Вообще говоря, существуют два пути выполнения р-редукции: мы можем либо оставить ссылку на формальный параметр без изменений, но запомнить обозначаемую ею величину в отдельной структуре данных, либо выполнить подстановку, которая физически заменяет ссылку на параметр его фактическим значением. Эти два подхода ведут к реализациям, основанным на контексте и копировании соответственно. [9]
 |
Простое преобразование графа, представляющее Х - применение. [10] |
Таким образом, при графовом представлении разделение выражений представляется естественным образом без необходимости введения явного контекста, что делает редукцию графов жизнеспособной моделью для реализации функциональных языков. [11]
Как уже было сказано и в чем можно будет убедиться по ходу дальнейшего изложения, поддержка ленивого вычисления является очень дорогой, и для того, чтобы избежать его при реализациях функционального языка, затрачиваются большие усилия всякий раз, когда это возможно. Например, при анализе ленивой функциональной программы часто определяется, что функция, заданная пользователем, является строгой в одном или нескольких своих аргументах. Эти строгие аргументы затем могут передаваться по значению, давая некоторое увеличение эффективности без изменения поведения программы при ленивой реализации. Подобная форма оптимизации, известная как анализ строгости, более детально обсуждается в гл. [12]
Впервые мысль о применимости абстрактной интерпретации для анализа строгости была высказана в [69], который использовал эту методику также для исследования проблемы установления условной конечности времени вычисления выражения. Основной задачей здесь является повышение эффективности ленивой реализации функционального языка путем поиска возможности доступа к аргументам по значению, а не по необходимости без изменения условий окончания работы программы. Как мы видели в предыдущих главах, это устраняет необходимость в создании задержек для аргументов в SECD-машине и в то же время уменьшает количество структур данных, создаваемых во время прогона программы и обрабатываемых в дальнейшем сборщиком мусора. Более того, если при параллельной редукции графов известна строгость каждой определенной пользователем функций, то это позволяет производить вычисление строгих аргументов параллельно с вычислением функции, увеличивая тем самым степень параллелизма. [13]
В книге английских специалистов рассмотрены проблемы аппликативного программирования, существенно повышающего интеллектуальность разрабатываемых программ по сравнению с традиционным программированием. При этом спецификация предметной области существенно упрощает труд программиста. Особое внимание уделяется вопросам реализации функциональных языков, основанной на Х - нсчнслении Черна. В качестве базового языка рассматривается функциональный язык Норе, имеющий простой и ясный синтаксис. Изложение сопровождается многочисленными примерами конкретных программ. [14]
Основным преимуществом хранения весов внутри указателей, как и в методе однобитовых счетчиков ссылок, является то, что отсутствует необходимость осуществления доступа к ячейке при увеличении числа указателей на нее. Мы должны изменить показания счетчика ссылок ячейки при удалении ссылок на нее, но при этом обычно снимаются ссылки с указывающей ( адресующей) ячейки, так что доступ к адресуемой ячейке будет осуществлен в любом случае. Именно по этой причине метод взвешенных счетчиков ссылок особенно хорошо подходит для распределенных версий реализации функциональных языков, где частота посылок сообщений сильно влияет на эффективность работы. [15]
Страницы: 1 2