Давненько мы не касались темы функционального программирования... успел ли ты соскучиться? Уверен, что нет, но деваться некуда :), ведь сегодня я настроен показать тебе реальную силу функционального подхода. Заодно мы рассмотрим то общее, что объединяет функциональные языки. В этой статье мы попробуем написать простейший интерпретатор сразу на трех языках: Haskell, OCaml и Scala.

 

Введение

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


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

По устройству компиляторов существует масса книг («Книга с драконом» и многие другие), которые очень подробно описывают процесс синтаксического анализа, оптимизации и кодогенерации.
Есть много классических инструментов, разработанных так давно, что если в качестве аналогии рассмотреть оружие, то утилиты lex и yacc сродни первобытным копьям и каменным топорам. В этом смысле инструменты, которые предоставляют Haskell и другие функциональные языки, может быть, и не выглядят как огнестрельное оружие, но представляют собой аналоги по меньшей мере катаны и вакидзаси в мире проектирования языков программирования.

В этой статье весь код будет написан на трех языках, чтобы увидеть сходства и различия в использовании тех или иных инструментов программирования. Если про Haskell и Scala слышали, наверное, все, то OCaml на данный момент кажется довольно экзотическим языком. Но это совершенно не значит, что он чем-то плох. Это очень мощное расширение языка ML, который был придуман еще очень давно (в начале семидесятых). Сейчас лямбда-функции уже мейнстрим, а вот вывод типов только начинает набирать популярность — но если подумать, что он уже был в ML, то становится немного страшно. Даже компания Microsoft выпустила язык F#, который очень похож на OCaml, только работает он в окружении .NET. На самом деле довольно много языков программирования были изначально реализованы на OCaml. Список можно найти здесь, тем более что это просто прекрасный источник знаний о данном языке. Следует отметить, что на OCaml (и на ML вообще) написано несколько систем автоматического доказательства теорем.

На язык OCaml можно посмотреть немного шире, чем на просто функциональный язык, потому что он, в отличие от Haskell, также поддерживает императивный и объектно ориентированный стили программирования. Несмотря на то что OCaml куда менее популярен по сравнению с остальными нашими испытуемыми, он имеет очень продвинутый интерактивный интерпретатор utop, собственную систему пакетов и довольно развитую инфраструктуру. Единственный существенный недостаток — это отсутствие нормальной поддержки со стороны популярных IDE.

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


По некоторым бенчмаркам, веб-сервер, написанный на Haskell, много быстрее Node и других популярных аналогов

Язык программирования Scala был придуман сравнительно недавно и уже очень популярен среди разработчиков для JVM. Этот язык сочетает в себе многие прекрасные особенности функциональных и объектно ориентированных языков. На Scala написано множество библиотек и интернет-сервисов. Надо сказать, что богатые возможности этого языка также ведут и к проблемам. В каком-то смысле Scala напоминает C++, где одно и то же можно сделать двадцатью различными способами и в результате код, который написан просто для того, чтобы он работал, совершенно невозможно читать или тем более повторно использовать.


На Scala написано множество библиотек и интернет-сервисов

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

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

 

Сложные типы данных

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

  • декартово произведение;
  • размеченное объединение.

В функциональных языках декартово произведение обычно представлено с помощью кортежа, в ООП это классы. Размеченное объединение в функциональных языках играет существенную роль, так как позволяет различать объекты в рамках одного типа, но с разной структурой. В объектно ориентированных языках это реализовано с помощью наследования. В некоторых функциональных языках, таких как OCaml и Haskell, — при помощи так называемых алгебраических типов. На самом деле такое название не должно пугать. Вот как это выглядит в OCaml:

type shape =
  | Circle of float
  | Rect of float * float

let area s = match s with
  | Circle radius -> 3.14159 *. radius *. radius
  | Rect (width, height) -> width *. height

Здесь у нас есть один тип данных, для которого существуют два конструктора с принципиально разным набором параметров. Причем против конструктора можно использовать сопоставление с образцом, как это сделано в функции area, которая вычисляет площадь соответствующей фигуры. Из особенностей языка здесь следует отметить явное указание на то, что мы имеем дело с декартовым произведением в конструкторе Rect. OCaml также интересен тем, что для целых чисел и чисел с плавающей запятой он имеет синтаксически различные наборы операций, для вещественных чисел соответствующая операция заканчивается точкой: *.

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

data Shape = Circle Double | Rect Double Double

area :: Shape -> Double
area (Circle radius) = 3.14159 * radius * radius
area (Rect width height) = width * height

Код на Haskell поразительно схож с кодом на OCaml, и это связано с тем, что язык ML, по сути, их общий предок. В Haskell довольно много синтаксического сахара: к примеру, с помощью data можно создавать декартово произведение, не используя кортеж напрямую. Еще одна особенность в том, что в Haskell можно выносить тип функции в виде аннотации за пределы определения самой функции (точнее, строчкой выше). Это очень удобно. Здесь сказано, что функция area является функцией из Shape в Double.

По правде говоря, это можно сделать и в OCaml, однако для этого придется создать заголовочный файл, что не всегда удобно. Несмотря на то что OCaml и Haskell сами выводят тип функции, рекомендую указывать тип в аннотации в случае Haskell и напрямую в OCaml let area (s: shape): float = ..., чтобы облегчить чтение и отладку кода.

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

abstract class Shape { def area(): Double }
class Circle(val radius: Double) extends Shape {
  @Override
  def area(): Double = 3.14159 * radius * radius
}
class Rect(val width: Double, val height: Double) extends Shape {
  @Override
  def area(): Double = width * height
}

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

sealed trait Shape
case class Circle(radius: Double) extends Shape
case class Rect(width: Double, height: Double) extends Shape

def area(shape: Shape): Double = shape match {
  case Circle(radius) => 3.14159 * radius * radius
  case Rect(width, height) => width * height
}

Здесь также используется сопоставление с образцом. Трейты (trait) в Scala очень напоминают интерфейсы в Java (можно было использовать и абстрактные классы, как в предыдущем примере, — это, скорее, дело вкуса), а в нашем конкретном случае обеспечивают имитацию алгебраического типа, так как классы Circle и Rect, с одной стороны, будут иметь тип Shape, с другой — ключевое слово sealed делает наше размеченное объединение «закрытым справа».

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

 

Абстрактные синтаксические деревья

Теперь, когда с функциональным подходом к сложным типам данных все понятно, попробуем разобраться с такой полезной штукой, как абстрактное синтаксическое дерево (AST). Начнем с совсем тривиального примера: положим, что нам нужно написать простейший интерпретатор математических выражений. Чтобы еще упростить пример, будем считать, что нам хватит простейших операций, таких как сложение, вычитание и умножение. Суть абстрактного синтаксического дерева очень проста — это абстракция S-выражения (из языка Lisp) для соответствующей части программы (в нашем случае просто математического выражения). Таким образом, абстрактное синтаксическое дерево для выражения 10 + 2 * 5 можно записать как (+ 10 (* 2 5)). На языке OCaml код будет выглядеть следующим образом:

type expr =
  | Num of int
  | Plus of expr * expr
  | Minus of expr * expr
  | Mul of expr * expr

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

let rec eval expr = match expr with
  | Num x -> x
  | Plus (x, y) -> eval x + eval y
  | Minus (x, y) -> eval x - eval y
  | Mul (x, y) -> eval x * eval y

Теперь, если мы захотим что-нибудь вычислить, это будет совсем легко. К примеру, выражение Mul (Num 2, Plus (Num 3, Minus (Num 2, Num 1))) соответствует математическому выражению 2 * (3 + 2 - 1).

На Haskell ситуация будет очень похожей:

data Expr =
    Num Int
  | Plus Expr Expr
  | Minus Expr Expr
  | Mul Expr Expr

eval :: Expr -> Int
eval (Num x) = x
eval (Plus x y) = eval x + eval y
eval (Minus x y) = eval x - eval y
eval (Mul x y) = eval x * eval y

Для меня лично код на Haskell выглядит немного более лаконично по сравнению с OCaml. Здесь нам не нужно использовать кортежи, зато появляются лишние скобки взамен исчезнувших запятых: Mul (Num 2) (Plus (Num 3) (Minus (Num 2) (Num 1))).

Вот теперь можно сравнить то, что получилось, с кодом на Scala. Несмотря на то что набор из case-классов с sealed трейтом скорее похож на костыль в языке, все кажется довольно неплохо:

sealed trait Expr
case class Num(n: Int) extends Expr
case class Plus(x: Expr, y: Expr) extends Expr
case class Minus(x: Expr, y: Expr) extends Expr
case class Mul(x: Expr, y: Expr) extends Expr

def eval(expr: Expr): Int = expr match {
  case Num(n) => n
  case Plus(x, y) => eval(x) + eval(y)
  case Minus(x, y) => eval(x) - eval(y)
  case Mul(x, y) => eval(x) * eval(y)
}

Для Scala выражение выглядит очень привычно, поэтому я его здесь не выписываю.

Перейдем к более сложному примеру.

 

Императивный язык FlowChart

Когда я учился в школе, нас заставляли рисовать алгоритмы в форме диаграмм из прямоугольников, ромбов и всяких там стрелок. То, что мы здесь сейчас разберем, — то же самое, только выраженное в программной форме явным образом (сам термин FlowChart как бы намекает). Пример для этой статьи я позаимствовал из книги Нила Джонса (Niel Jones) с соавторами, ссылку на которую я обязательно дам в конце статьи, но уже в связи с куда более интересным сюжетом, чем просто написание интерпретатора. Но для начала, как полагается в серьезных случаях, опишем грамматику языка:

<Program>     ::= read <Var>, ..., <Var>; <BasicBlock>+
<BasicBlock>  ::= <Label>: <Assignment>* <Jump>
<Assignment>  ::= <Var> := <Expr>;
<Jump>        ::= goto <Label>;
                  if <Expr> goto <Label> else <Label>;
                  return <Expr>;
<Expr>        ::= <Constant>
                  <Op> <Expr>, ..., <Expr>
<Label>       ::= любой идентификатор или число

Для тех, кто незнаком с формой Бэкуса — Наура (BNF): здесь слева от знака ::= находится элемент программы, а справа от знака - то, из чего этот элемент может состоять. Знак * означает «0 и более», а знак + — «1 и более». Таким образом, здесь мы задаем язык, определяя правила выражения более сложных элементов через более простые.

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

В качестве примера рабочей программы можно рассмотреть реализацию алгоритма Евклида для вычисления наибольшего общего делителя:

read x, y;
1: if x = y goto 7 else 2;
2: if x < y goto 5 else 3;
3: x := x - y;
   goto 1;
5: y := y - x;
   goto 1;
7: return x;

Конечно, здесь мы не будем учинять синтаксический анализ, а пойдем по тому же пути, что и в случае с интерпретатором формул. Для начала нужно понять, что нам нужно, чтобы сделать такой интерпретатор. В отличие от предыдущего примера, у нас здесь есть переменные, а значит, их нужно где-то хранить. Для этого мы будем использовать хранилище (store), которое реализовано через список пар. Можно было бы взять какую-то более продвинутую структуру данных, например таблицу (map), однако мы будем придерживаться стратегии «ничего лишнего» и в учебных целях обойдемся тем, что есть. Структура абстрактного синтаксического дерева для программы на языке FlowChart следующая (вариант OCaml):

type expr =
  | Int of int
  | Var of string
  | Op of string * expr list

type statement =
  | Goto of string
  | Assign of string * expr
  | If of expr * string * string
  | Return of expr

Здесь мы немного расширили наше выражение за счет переменных и «обобщенной» операции, которая представляет собой пару, состоящую из имени операции и списка операндов. Список нужен, чтобы мы могли использовать как бинарные, так и унарные операции, например логическое НЕ. Здесь также описана структура для представления различных операторов. Все операторы имеют один и тот же тип. Это таит в себе некоторые трудности: положим, что остальные элементы программы определены так:

type block = string * statement list
type program = string list * block list
type bind = string * int
type store = bind list

let vars = fst
let blocks = snd

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

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

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

let rec lookup n s = match s with
        | [] -> raise (Failure n)
        | (n', v) :: bs -> if n = n' then v else lookup n bs

let rec update ((n, v): bind) (s: store): store = match s with
          | [] -> [(n, v)]
          | (n', v') :: bs ->
              if n = n' then (n, v) :: bs
              else (n', v') :: update (n, v) bs

Язык OCaml довольно занимателен тем, что там операция сравнения — это просто символ =. Здесь я включил в описание параметров функции также тип, что было не обязательно: система вывода типов справилась бы, но информация о типе очень полезна, когда кода много. Здесь я использовал новые названия для типов данных (bind и store), это намного удобнее для чтения и обслуживания кода, чем знания о том, что первый параметр — это кортеж из двух элементов, а второй — список кортежей.

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

let mul x y =  x * y
let int2bool x = x != 0
let comp c x y = if c x y then 1 else 0

let logic c x y = let x' = int2bool x in
  let y' = int2bool y in
    if c x' y' then 1 else 0

let prim = [("+", (+)); ("-", (-)); ("*", mul); ("/", (/));
        ("=", comp (=)); ("<", comp (<)); (">", comp (>));
        (">=", comp (>=)); ("<=", comp (<=));
        ("&&", logic (&&)); ("||", logic (||))]

Данный кусок кода требует некоторых пояснений касательно активного применения каррирования. Для максимального удобства нам хочется использовать уже существующие функции сравнения и логические функции так же легко, как и операции сложения и умножения (из-за особенностей комментариев в OCaml операция умножения обернута в функцию mul). Функции сравнения возвращают булев тип, которого нет в нашем языке, и нам нужно преобразовать функции сравнения в понятную для нас форму. Это делается с помощью обертки comp. Таким образом, каррированный вариант (без двух последних аргументов) функции даст нам функцию сравнения, которая возвращает 1 вместо true и 0 вместо false.

Для тех, кто не в курсе деталей вопроса, каррирование — это очень удобный инструмент функционального программирования, который позволяет использовать функции лишь с частью аргументов. Можно просто считать, что функции с несколькими аргументами — это синтаксический сахар. Рассмотрим простой пример на Haskell:

foo :: Int -> Int -> Int
foo x = \ y -> x + y

На самом деле это то же самое, что написать foo x y = x + y, поэтому тип функции можно записать как Int -> (Int -> Int), а расстановка скобок при применении функции к аргументам обратная (foo 3) 5. Наша обертка для логических операций работает точно так же.

let rec eval e s = match e with
  | Int n -> n
  | Var x -> lookup x s
  | Op (f, [x; y]) -> let f' = lookup f prim in
    f' (eval x s) (eval y s)
  | Op ("~", [x]) -> let x' = int2bool (eval x s) in
    if x' then 0 else 1
  | _ -> raise (Failure "Unknown operation")

Здесь все очень похоже на eval с математическими функциями, с некоторыми необходимыми расширениями. Так как мы используем здесь переменные, то передаем хранилище s в качестве второго аргумента. Теперь нужно написать функцию для последовательного выполнения блоков программы:

let rec run stmts p s = match stmts with
  | Goto l :: _ -> let b = lookup l (blocks p) in run b p s
  | Assign (x, e) :: cs -> let v = eval e s in run cs p (update (x, v) s)
  | Return e :: _ -> eval e s
  | If (e, m, n) :: _ -> let cond = eval e s in
                     let l = if cond = 0 then n else m in
                     let b = lookup l (blocks p) in run b p s
  | _ (* [] *) -> raise (Failure "Premature end of program")

В функцию run передается набор операторов (блок без метки) stmts, программа p и хранилище s. Далее все довольно просто, происходит последовательное выполнение операторов и переходы между блоками по необходимости.

В качестве финального аккорда напишем функцию для запуска программы с заданными входными переменными:

let interpret prog args = match prog with
  | (vs, (_, stmts):: _) -> let s = zip vs args in run stmts prog s

Таким образом, при запуске управление передается первому блоку. Реализацию функции zip, которая из двух списков делает список соответствующих пар, оставим читателю в качестве простого упражнения.

 

Так как же писать программы на нашем языке?

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

let _if op args m n = If (Op (op, args), m, n)
let (<~) (Var v) e = Assign (v, e)
let op f args = Op (f, args)

Теперь наша программа, которая вычисляет наибольший общий делитель, выглядит совсем просто:

let prog_gcd: program = let x = Var "x" in let y = Var "y" in
  (["x"; "y"],
  [("1", [_if "=" [x; y] "7" "2"]);
  ("2", [_if "<" [x; y] "5" "3"]);
  ("3", [x <~ op "-" [x; y];
        Goto "1"]);
  ("5", [y <~ op "-" [y; x];
        Goto "1"]);
  ("7", [Return y])])
 

Особенности реализации на Haskell и Scala

Структуры данных для представления программ на Haskell выглядят практически полностью идентично, и это останется читателю в качестве упражнения. В случае Scala есть несколько особенностей. Синтаксический сахар (в виде функции <~) для введения короткой формы присваивания нужно поместить прямо в определение типов, входящих в абстрактное синтаксическое дерево.

case class Var(name: String) extends Expr {
  def <~(rhs: Expr): Statement =
    Assign(name, rhs)
}

В Scala есть одна особенность, которая многим нравится, а мне вот совсем нет, — это использование символа wildcard _ в очень разных контекстах. Это часто приводит к путанице, особенно при использовании этого символа при каррировании. Посмотрим на код для примитивных функций:

class FCL(val prog: Program, args: Seq[Int]) {
  var store: Map[String, Int] = prog.vars.zip(args).toMap
  var blockMap = prog.blocks.toMap

  type Func2 = (Int, Int) => Int

  val prim: Map[String, Func2] = Map("+" -> (_ + _),
    "-" -> (_ - _), "*" -> (_ * _), "/" -> (_ / _),
    "=" -> (comp(_ == _) _), "<" -> (comp (_ < _) _),
    ">" -> (comp (_ > _) _), ">=" -> (comp (_ >= _) _),
    "<=" -> (comp (_ <= _) _), "&&" -> (logic (_ && _) _),
    "||" -> (logic (_ || _) _))

Последний символ wildcard используется для обеспечения каррирования соответствующих функций, которые также должны быть уже объявлены в специальной форме:

def int2bool(z: Int): Boolean = z != 0

def comp(op: (Int, Int) => Boolean)(x: Int, y: Int): Int =
  if (op(x, y)) 1 else 0

def logic(op: (Boolean, Boolean) => Boolean)(x: Int, y: Int): Int =
  if (op(int2bool(x), int2bool(y))) 1 else 0

В Scala для удобства мы пользовались структурой Map там, где в OCaml и Haskell мы ради простоты использовали список пар. Но это дело вкуса. Для полноты картины приведем функцию run, потому что ее структура вполне отражает особенности гибридного подхода, в отличие от чисто функциональных вариантов в OCaml и Haskell:

def run(stmts: Seq[Statement]): Int = stmts match {
  case Goto(label) :: _ => run(blockMap(label))
  case Assign(name, expr) :: ss => {
    store = store + (name -> eval(expr))
    run(ss)
  }
  case Return(expr) :: _ => eval(expr)
  case If(cond, thenLabel, elseLabel) :: _ => {
    val r = eval(cond)
    if (r == 0)
      run(blockMap(elseLabel))
    else
      run(blockMap(thenLabel))
  }
}

def interpret(): Int = {
  run(prog.blocks(0)._2)
}

Вот, собственно, и все, что касается реализации простейшего интерпретатора.

Разница и схожие черты функциональных языков хорошо видны на этом примере. Он не настолько сложен, чтобы показать на нем какие-нибудь хитрые особенности Haskell, но тем не менее. Из этих примеров видно, насколько хорошо функциональное программирование подходит для решения подобных задач. Другой вопрос в том, зачем вообще нужен интерпретатор, почему не сразу компилятор? На самом деле между интерпретаторами и компиляторами существует очень нетривиальная связь, о которой хотелось бы рассказать в последнем разделе этой статьи.

 

Частичные вычисления

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

Интуиция подсказывает, что, может быть, есть еще что-то. Что же собой представляет интерпретатор с формальной точки зрения (с практической все понятно — он позволяет пошагово выполнять программу)? Ясно, что для предъявления формальной семантики языка вполне достаточно просто предъявить интерпретатор, однако непонятно, что из этого можно извлечь. Интерпретатор — это некоторая программа, написанная на языке L и способная выполнять программу на языке S, то есть intL(pS, d) — это то же самое, как если мы бы запустили программу прямо на машине, для которой язык S родной, с данными d.

Теперь представим, что у нас есть программа — назовем ее специализатор spec, — которая для любой программы (для простоты с двумя входными параметрами) p(x, y) и некоторого x0 позволяет получить остаточную программу p'(y), для любого y совпадающую с p(x0, y). Причем специализатор использует знания о значении x0 и пытается вычислить все, что можно, и удалять ненужные ветви выполнения и прочее.

Теперь посмотрим, что будет, если мы применим специализатор к нашему интерпретатору (здесь полагаем, что наш специализатор работает для языка L):

intL(pS, d) = spec(intL, pS)(d)

Так как специализатор работает из L в L, то spec(intL, pS) — это программа на L, которая делает то же самое, что и pS, то есть просто pL или скомпилированная программа! Можно зайти еще дальше и применить специализатор к интерпретатору еще раз. Тогда мы получим:

spec(spec, intL)(pS)(d)

где spec(spec, intL) — это просто компилятор (!!!) из S в L. Таким образом, мы нашли способ автоматически из интерпретатора получать компилятор.

Если подумать, то ничто не мешает провернуть тот же трюк еще раз:

spec(spec, spec)(intL)(pS)(d)

Здесь spec(spec, spec) — это так называемый генератор компиляторов, который для любого интерпретатора, написанного на языке L, даст соответствующий компилятор.

Три соответствующих уравнения называются проекциями Футамуры, или, более точно, проекциями Футамуры — Турчина, в честь авторов идеи. Насколько бы невероятным это ни казалось, но это работает, хотя практические результаты были получены лишь через много лет после открытия таких соотношений. К сожалению, из-за технических трудностей это не очень распространенная техника, однако если ты интересуешься языками программирования, то это очень интересная область для экспериментов. Узнать больше можно в книге Niel Jones, Carsten Gomard, Peter Sestoft «Partial Evaluation and Automatic Program Generation» (Prentice Hall International, 1993).

  • Подпишись на наc в Telegram!

    Только важные новости и лучшие статьи

    Подписаться

    • Открыть комментарии
    Подписаться
    Уведомить о
    0 комментариев
    Межтекстовые Отзывы
    Посмотреть все комментарии