Давненько мы не касались темы функционального программирования… успел ли ты соскучиться? Уверен, что нет, но деваться некуда :), ведь сегодня я настроен показать тебе реальную силу функционального подхода. Заодно мы рассмотрим то общее, что объединяет функциональные языки. В этой статье мы попробуем написать простейший интерпретатор сразу на трех языках: 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 код будет выглядеть следующим образом:

Продолжение статьи доступно только подписчикам

Вариант 1. Оформи подписку на «Хакер», чтобы читать все статьи на сайте

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

Вариант 2. Купи одну статью

Заинтересовала статья, но нет возможности оплатить подписку? Тогда этот вариант для тебя! Обрати внимание: этот способ покупки доступен только для статей, опубликованных более двух месяцев назад.


Комментарии

Подпишитесь на ][, чтобы участвовать в обсуждении

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

Check Also

Хакер ищет авторов. Читатель? Хакер? Программист? Безопасник? Мы тебе рады!

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