Реализация на Scala графической среды для языка Unlambda
Для тех, кто меня знает, не секрет, что в свободное от изготовления спектроскопов и телескопов время я занимаюсь программированием. Собственно, сейчас это и есть моя основная деятельность. На этом поприще, конечно, тоже немало всего интересного, о чём можно написать пост. Некоторое время я раздумывал, организовать ли мне два разных блога: в одном из которых я бы иногда писал про всяческие поделки/опыты/явления, а в другом - о программировании, информационных технологиях и.т.п. Я решил писать обо всём в одном месте: во-первых мне так проще; во-вторых я и так пишу достаточно редко: пусть лучше будет один полуживой блог чем два неживых; ну а в третьих - нередко самое интересное именно "на стыке" областей: непонятно, куда постить, скажем, про кофейник, управляемый через веб-интерфейс :)
В этом посте речь пойдёт о комбинаторной логике, основанном на ней языке программирования Unlambda, который может сломать вам мозг, и реализации "среды" для Unlambda на языке Scala, который, напротив, очень приятен.
Представим, что у нас есть язык, в котором существует единственный тип объектов: функции одного аргумента. И этот самый аргумент функций, и возвращаемое значение - тоже ничто иное, как функции одного аргумента. То есть вообще нет ничего другого - ни чисел, ни переменных, соответственно, нет и присваиваний. Есть, правда, один оператор: применить функцию взяв в качестве аргумента другую функцию. Запись (a b) означает "применить к a аргумент b". Будем считать применение левоассоциативным, то есть
a b c = ((a b) c).
Для того, чтобы начать что-то конструировать из этого "материала", нам потребуются элементарные кирпичики: базовые функции, через которые мы будем выражать всё остальное. Вот они, K и S:
K x y = x
S x y z = x z (y z)
Минуточку! У нас же функции одного аргумента, что же означает запись K x y = x ? Очень просто: результат применения (K x) - функция, которая при применении к любому y вернёт x. В таком же ключе следует понимать и S x y z.
Всё! Этого достаточно, чтобы наша система была полной по Тьюрингу.
Грубо говоря, это значит, что оператор применения и комбинаторы S и K можно положить в основу языка программирования, на котором можно выразить все те же самые вычисления, что и на других, более привычных языках.
Чтобы понять, как с помощью комбинаторов S и K выразить такие вещи, как числа, ветвления, рекурсию и списки - рекомендую обратиться к популярной статье.
Всё это и положил в основу Unlambda изобретатель данного языка - Дэвид Мэдор (David Madore). Синтаксис языка очень простой, похожий на то, что я уже писал, только операция применения записывается не скобками, а обратным апострофом: Так, выражение ((ab)c) запишется как ``abc, выражение a(bc), соответственно, как `a`bc.
В Unlambda встроены уже знакомые нам функции s и k. Кроме них есть функция i, "тождественный комбинатор":
I x = x
или, в синтаксисе Unlambda `ix = x. Её существование удобно, но необязательно, так как она может быть выражена чере S и K. Один из способов:
S K K x = K x (K x) = x
Для печати результатов служит функция .c, которая, будучи применённой к любому x вернёт x и напечатает символ c. Есть ещё с пяток функций, о которых можно прочесть, например, в статье в википедии.
Я хочу рассказать о созданной мной "графической среде", в которой можно исследовать и отлаживать программы на Unlambda. Интерфейс программы очень простой: там, где написано "Source code" пишем или вставляем из буфера обмена ваш исходный код. Например, на скриншоте ```s`kiii . Затем, для того, чтобы провести разбор вашей программы и построение дерева вычислений (которое можно видеть в области "Evaluation tree"), нажимаем F2. Затем, если ваша программа читает какие-то данные (см. Википедию про чтение данных в Unlambda), то вводим данные для чтения программой в поле "Input". Теперь, для того, чтобы ваша программа выполнялась шаг за шагом, нажимаем F7. При этом будет видно, как шаг за шагом преобразуется дерево "Evaluation tree".
Где взять саму Unlambda-среду? Можно собрать из исходников, которые выложены на гитхабе.
Всё написано на языке Scala. Сборка осуществляется с помощью Simple Build Tool (SBT). Simple Build Tool - конечно же оксюморон, поэтому ниже приведу последовательность действий (в основном это команды в консоли), которые нужно выполнить, чтобы собрать и запустить мою Unlambda-среду.
Для тех, кто не хочет заморачиваться и доверяет собранным чужими руками бинарникам, я положил на Dropbox архив, в котором всё лежит уже в скомпилированном виде, и можно запустить среду, выплонив файл run.bat (в Windows) или run.sh (в Linux).
А вот инструкция для сборки из исходников:
Я уже давно присматривался к языку программирования Scala. Уже несколько лет назад я вдоволь написался стандартных примеров в духе "здравствуй мир", вычисления факториала и.т.п. Недавно на сайте coursera.org проходил онлайн-курс по Функциональному программированию на Scala за авторством самого Мартина Одерски (Martin Odersky), создателя Scala. Ознакомившись с материалами курса, я решил, что неплохо было бы более близко познакомится с "экосистемой" Scala, сварганив пусть "маленький и несерьёзный", но "настоящий" проектик, в котором бы использовалась система сборки (в мире Scala стандарт де-факто SBT), автотесты и.т.п. Кроме того, я между делом интересуюсь теоретическими основами функционального программирования. Поэтому
ещё одна реализация Unlambda'ы - идеальный вариант: написать на Scala интерпретатор Unlambda крайне просто, других реализаций именно на Scala я не нашёл (хотя вообще реализаций Unlambda довольно много). Кроме того, мало таких реализаций, в котором можно было бы не только просто выполнять программы на Unlambda, а в интерактивном режиме смотреть, что и как происходит "внутри" вашей программы. Эти обстоятельства и смотивировали меня создать описанную Unlambda-среду используя Scala.
В этом посте речь пойдёт о комбинаторной логике, основанном на ней языке программирования Unlambda, который может сломать вам мозг, и реализации "среды" для Unlambda на языке Scala, который, напротив, очень приятен.
Представим, что у нас есть язык, в котором существует единственный тип объектов: функции одного аргумента. И этот самый аргумент функций, и возвращаемое значение - тоже ничто иное, как функции одного аргумента. То есть вообще нет ничего другого - ни чисел, ни переменных, соответственно, нет и присваиваний. Есть, правда, один оператор: применить функцию взяв в качестве аргумента другую функцию. Запись (a b) означает "применить к a аргумент b". Будем считать применение левоассоциативным, то есть
a b c = ((a b) c).
Для того, чтобы начать что-то конструировать из этого "материала", нам потребуются элементарные кирпичики: базовые функции, через которые мы будем выражать всё остальное. Вот они, K и S:
K x y = x
S x y z = x z (y z)
Минуточку! У нас же функции одного аргумента, что же означает запись K x y = x ? Очень просто: результат применения (K x) - функция, которая при применении к любому y вернёт x. В таком же ключе следует понимать и S x y z.
Всё! Этого достаточно, чтобы наша система была полной по Тьюрингу.
Грубо говоря, это значит, что оператор применения и комбинаторы S и K можно положить в основу языка программирования, на котором можно выразить все те же самые вычисления, что и на других, более привычных языках.
Чтобы понять, как с помощью комбинаторов S и K выразить такие вещи, как числа, ветвления, рекурсию и списки - рекомендую обратиться к популярной статье.
Всё это и положил в основу Unlambda изобретатель данного языка - Дэвид Мэдор (David Madore). Синтаксис языка очень простой, похожий на то, что я уже писал, только операция применения записывается не скобками, а обратным апострофом: Так, выражение ((ab)c) запишется как ``abc, выражение a(bc), соответственно, как `a`bc.
В Unlambda встроены уже знакомые нам функции s и k. Кроме них есть функция i, "тождественный комбинатор":
I x = x
или, в синтаксисе Unlambda `ix = x. Её существование удобно, но необязательно, так как она может быть выражена чере S и K. Один из способов:
S K K x = K x (K x) = x
Для печати результатов служит функция .c, которая, будучи применённой к любому x вернёт x и напечатает символ c. Есть ещё с пяток функций, о которых можно прочесть, например, в статье в википедии.
Я хочу рассказать о созданной мной "графической среде", в которой можно исследовать и отлаживать программы на Unlambda. Интерфейс программы очень простой: там, где написано "Source code" пишем или вставляем из буфера обмена ваш исходный код. Например, на скриншоте ```s`kiii . Затем, для того, чтобы провести разбор вашей программы и построение дерева вычислений (которое можно видеть в области "Evaluation tree"), нажимаем F2. Затем, если ваша программа читает какие-то данные (см. Википедию про чтение данных в Unlambda), то вводим данные для чтения программой в поле "Input". Теперь, для того, чтобы ваша программа выполнялась шаг за шагом, нажимаем F7. При этом будет видно, как шаг за шагом преобразуется дерево "Evaluation tree".
Где взять саму Unlambda-среду? Можно собрать из исходников, которые выложены на гитхабе.
Всё написано на языке Scala. Сборка осуществляется с помощью Simple Build Tool (SBT). Simple Build Tool - конечно же оксюморон, поэтому ниже приведу последовательность действий (в основном это команды в консоли), которые нужно выполнить, чтобы собрать и запустить мою Unlambda-среду.
Для тех, кто не хочет заморачиваться и доверяет собранным чужими руками бинарникам, я положил на Dropbox архив, в котором всё лежит уже в скомпилированном виде, и можно запустить среду, выплонив файл run.bat (в Windows) или run.sh (в Linux).
А вот инструкция для сборки из исходников:
- Ставим SBT. Скачать можно отсюда. Я заметил, что SBT плоховато работает в Windows, если имя пользователя Windows написано кириллицей.
- Качаем исходники ScalaSwingTreeWrapper. Можно так же воспользоваться git-ом и склонировать репозиторий. Например, у меня ScalaSwingTreeWrapper распаковался в директорию ScalaSwingTreeWrapper-master.
- Собираем ScalaSwingTreeWrapper. В оболочке командной строки переходим туда
cd ScalaSwingTreeWrapper-master
и выполняем команду
sbt
если sbt не прописана в переменной окружения PATH, то вместо этого
ПОЛНЫЙ_ПУТЬ_К_SBT/sbt
В оболочке sbt выполняем команды
update
package
В результате в директории появится файл ScalaSwingTreeWrapper-master/target/scala_2.9.1/scalaswingtreewrapper_2.9.1-1.2.jar.Возможно цифры, обозначающие версии компилдятора Scala и ScalaSwingTreeWrapper'а будут отличаться. - Качаем исходники среды Unlambda, о которой я здесь пишу. Как и в случае с ScalaSwingTreeWrapper'ом можно так же воспользоваться git-ом и склонировать репозиторий. Распаковываем архив, получаем директорию UnlambdaSimpleEnvironment-master .
- Копируем файл scalaswingtreewrapper_xxx.jar, полученный на шаге 3 в поддиректорию проекта UnlambdaSimpleEnvironment-master/Unlambda-GUI/lib.
- Собираем и запускаем среду Unlambda. Для этого переходим в директорию UnlambdaSimpleEnvironment-master, и запускаем sbt, выполнив команду
sbt
В оболочке sbt выполняем команду
gui/run
Я уже давно присматривался к языку программирования Scala. Уже несколько лет назад я вдоволь написался стандартных примеров в духе "здравствуй мир", вычисления факториала и.т.п. Недавно на сайте coursera.org проходил онлайн-курс по Функциональному программированию на Scala за авторством самого Мартина Одерски (Martin Odersky), создателя Scala. Ознакомившись с материалами курса, я решил, что неплохо было бы более близко познакомится с "экосистемой" Scala, сварганив пусть "маленький и несерьёзный", но "настоящий" проектик, в котором бы использовалась система сборки (в мире Scala стандарт де-факто SBT), автотесты и.т.п. Кроме того, я между делом интересуюсь теоретическими основами функционального программирования. Поэтому
ещё одна реализация Unlambda'ы - идеальный вариант: написать на Scala интерпретатор Unlambda крайне просто, других реализаций именно на Scala я не нашёл (хотя вообще реализаций Unlambda довольно много). Кроме того, мало таких реализаций, в котором можно было бы не только просто выполнять программы на Unlambda, а в интерактивном режиме смотреть, что и как происходит "внутри" вашей программы. Эти обстоятельства и смотивировали меня создать описанную Unlambda-среду используя Scala.
Ссылки
- Комбинаторы — это просто! (wikibooks.org) - пожалуй, самое лучшее из того, что подходит для первого знакомства с комбинаторной логикой.
- Домашняя страничка языка Unlambda. В "стандартную поставку", которую можно скачать с этого сайта входят несколько реализаций интерпретатора на разных языках. Хотелось бы отметить реализацию на Perl, которая позволяет выполнять программы пошагово, в режиме отладчика с помощью интерфейса командной строки (как в GDB), и очень выразительные реализации на двух диалектах ML.
- Unlambda (ru.wikipedia.org) - статья в википедии
- Unlambda - мозги навыворот - похожий пост об Unlambda. Реализация на языке Go.
- Бестиповое лямбда-исчисление, комбинаторы, Unlambda и числа Фибоначчи - пост про Unlambda на habrahabr.ru.
- Unlambda.NET - реализация Unlambda на C#
- Домашняя страничка и документация SBT.
- Getting started with Scala using SBT
