Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Истолковывание во время компиляции, либо Альтернативное осознавание лямбд в C 11

Anna | 24.06.2014 | нет комментариев

На Прогре незадолго проскочила ещё одна статья про вычисления на образцах C от HurrTheDurr. В комментариях к ней лично я увидел вызов:

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

А так ли трудно будет написать многофункциональный вычислитель на типах, больше комфортный для программирования, чем клеточный автомат? Как оказалось, нетрудно; я в 30 раз огромнее времени потратил на эту статью, чем на написание и отладку собственно кода вычислителя.

Чуть прежде AveNat опубликовала вступление в лямбда-исчисление в 2-х частях, так что воодушевление пришло мигом. Хотелось, Дабы дозволено было (образно) писать так:

#include <iostream>

#include <LC/kernel.h>
#include <LC/church_numerals.h>

int main()
{
    // Представление естественных чисел в виде лямбда-абстракций
    typedef ChurchEncode<2> Two;    // 2 = k!td>абстракция
v — имя переменной, B — терм
(f x)
аппликация
f и x — термы
Все эти конструкции нужно представить с поддержкой образцов C  . Значениями в языке образцов являются типы. Всякий из этих типов должен нести информацию о своих компонентах. Объявляя их, мы вводим аксиому «существуют следующие выражения»:
template <class Var>            struct Ref; // ссылки
template <class Var, class Exp> struct Lam; // абстракции
template <class Fun, class Arg> struct App; // аппликации

 Впрочем, переменные в лямбда-исчислении не являются полновесными значениями. Переменная v не имеет смысла сама по себе, без абстракции, объединяющей её с каким-либо значением. Следственно термом является именно ссылка на переменную, а не сама переменная. Так что определение дозволено немножко упростить, облегчив написание программ:
template <char  Var>            struct Ref;
template <char  Var, class Exp> struct Lam;
template <class Fun, class Arg> struct App;

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

Fun Fact

Имена переменных дозволено составлять из нескольких символов: 'foo'. Впрочем апологеты лямбда-исчисления считают это роскошью. Во-вторых, значение сходственных символьных литералов оставляется на усмотрение компилятора (2.14.3/1), что в редких случаях может привести к коллизии имён.

 Сейчас мы можем записывать с поддержкой образцов всякие лямбда-термы!

typedef Lam<'f', App<Lam<'x', App<Ref<'f'>, App<Ref<'x'>, Ref<'x'>>>>,
                     Lam<'x', App<Ref<'f'>, App<Ref<'x'>, Ref<'x'>>>>>> Y;

Что дальше?

f(x)
 Умея записывать термы, нужно обучиться их вычислять. Вот здесь теснее всё не так легко, следственно применим довольно знаменитый подход к написанию адовой магии на образцах: вначале всё записать на каком-нибудь декларативном языке программирования, после этого только поправить синтаксические отличия. Лично мне ближе Scheme, так что я буду применять его. С равным триумфом дозволено применить и всякий иной функциональный язык как бы Haskell. (А ещё отличнее — Пролог.)

 Не будем изобретать велосипед для записи самих термов, а используем обычные списки:
; Y = mk! exp) (eval-app (first exp) (second exp)))
        (else (error "eval: syntax error" exp)) ) )

 чудесно. Но как реализовать eval-ref? Откуда интерпретатор узнает значение переменной? Для этого существует такое представление как окружение (environment). В окружениях сохраняются связи между переменными и их значениями. Следственно eval на самом деле выглядит так — с дополнительным доводом:
(define (eval exp env)
  (cond ((ref? exp) (eval-ref exp env))
        ((lam? exp) (eval-lam (first (second exp)) (third exp) env))
        ((app? exp) (eval-app (first exp) (second exp) env))
        (else (error "Syntax error" exp)) ) )

 Сейчас вычисление ссылки на переменную определяется легко — это поиск значения переменной в окружении:
(define (eval-ref var env)
  (lookup var env) )

 Значением абстракции должна быть неизвестная функция одного довода. Эту функцию вызовет аппликация, когда придёт время. Толк абстракции состоит в том, Дабы вычислить своё тело exp в окружении, где переменная абстракции var имеет значение переданного довода arg. О создании такого окружения позаботится функция bind.
(define (eval-lam var exp env)
  (lambda (arg)
    (eval exp (bind var arg env)) ) )
Значения остальных переменных могут варьироваться, но реально в лямбда-исчислении принято, Дабы они оставались такими же, как и в месте определения абстракции (то есть брались из окружения env). Из-за свойства сохранения начального окружения сходственные функции именуются замыканиями.

 Наконец, аппликация — использование значения абстракции fun к значению довода arg.
(define (eval-app fun arg env)
  ((eval fun env) (eval arg env)) )
Тут вначале вычисляется абстракция и её довод, а потом теснее происходит вызов. Соответственно, eval исполняет редукцию лямбда-термов в аппликативном порядке (с вызовом по значению).

 Осталось только определить пару функций для работы с окружениями. lookup для поиска значения переменной в окружении и bind для создания новых окружений:
(define (bind var val env)       ; Для окружений применяются ассоциативные списки:
  (cons (cons var val) env) )    ;   (bind 'x 1 '((y . 2)))  ===>  ((x . 1) (y . 1))
                                 ;   (lookup 'x '((x . 1) (y . 2)))  ===>  1
(define (lookup var env)         ;   (lookup 'y '((x . 1) (y . 2)))  ===>  2
  (let ((cell (assq var env)))   ;   (lookup 'z '((x . 1) (y . 2)))  ===>  #<ERROR>
    (if cell (cdr cell)
        (error "lookup: unbound variable" var) ) ) )

 Супер! У нас есть интерпретатор лямбда-исчисления, написанный в чистом функциональном жанре. (Каждый исходник.) И он даже работает:
(eval '((lambda (x) x) B)
       (bind 'B 42 '()) ) ; ===> 42

Но что за скобки? И при чём тут C ?


I'm two pages in an still have no idea what are you sayingГлядя на начальный код интерпретатора на Scheme, дозволено касательно легко додуматься, как писать интерпретатор лямбда-термов на образцах C . Напомню, что сами термы записываются следующими образцами:
template <char  Var>            struct Ref;
template <char  Var, class Exp> struct Lam;
template <class Fun, class Arg> struct App;
 

Шаблонные функции (не те)

Функция-интерпретатор именуется Eval. Так как в образцах нет функций, то нам придётся обойтись одними образцами:

template <class Exp, class Env> struct Eval;

 Вызовом такой функции является инстанциирование образца: Eval<Exp, Env>. Возвращаемое значение этого вызова должно быть типом C . Условимся, что Eval определяет внутри себя тип value, если её значение определено для переданных доводов:
typename Eval<Exp, Env>::value
Сходственный код разрешает получить значение вызова Eval с доводами Exp и Env (в виде типа value). Если определенный вызов ложен (не имеет смысла), то тип value не будет определён и мы получим ошибку времени компиляции. Сходственным образом определяются и другие «шаблонные функции».

Eval и Apply

Сейчас с поддержкой частичной специализации образцов мы можем декларативно описать поведение Eval. Скажем, вычисление ссылки на переменную — это поиск значения переменной в окружении с поддержкой функции Lookup (она возвращает значение через result):
template <char Var, class Env>
struct Eval<Ref<Var>, Env>
{
    typedef typename Lookup<Var, Env>::result value;
};

 Итог вычисления абстракции — это замыкание, представляемое шаблонным типом Closure. Замыкание сберегает в себе (неизвестную) функцию и окружение определения этой функции:
template <char Var, class Exp, class Env>
struct Eval<Lam<Var, Exp>, Env>
{
    typedef Closure<Lam<Var, Exp>, Env> value;
};

 Итог вычисления аппликации — это использование вычисленного замыкания к вычисленному доводу (исполняемое функцией Apply):
template <class Fun, class Arg, class Env>
struct Eval<App<Fun, Arg>, Env>
{
    typedef typename Apply<typename Eval<Fun, Env>::value,
                           typename Eval<Arg, Env>::value>::result value;
};

 Таким образом, Eval определена только для Ref, Lam, App (и окружений вторым доводом). Вызовы Eval с другими доводами легко не скомпилируются.

 Идём дальше. Замыкания — это легко конструкции данных интерпретатора, хранящие два значения (функцию и окружение её определения). Реализуются, безусловно, ещё одним образцом:
template <class Abs, class Env> struct Closure;

 Каждая суть лямбда-исчисления сосредоточена в определении функции Apply. Замыкания вычисляются в окружении своего определения, которое Bind расширяет привязкой довода вычисляемой функции к его фактическому значению:
template <class Fun, class Arg> struct Apply;

template <char Var, class Exp, class Env, class Arg>
struct Apply<Closure<Lam<Var, Exp>, Env>, Arg>
{
    typedef typename Eval<Exp, Bind<Var, Arg, Env>>::value result;
};
(Подметьте, что Apply в тезисе дозволено определить вообще для чего желательно, не только для использования абстракций.)

Lookup и Bind

Осталось разобраться с окружениями. Для начала, хорошо было бы иметь пустое окружение:
struct NullEnv;

 Дальше, нужно реализовать механизм растяжения окружений с поддержкой Bind. Данный тип данных определяет новое окружение, в котором переменная Var связана со значением Val, а значения остальных переменных определяются окружением Env:
template <char Var, class Val, class Env> struct Bind;
Получили неповторимый связный список на образцах.

 Наконец, нам нужно уметь находить в этом списке значение требуемой переменной — оно будет в первом элементе списка с совпадающим именем. Поиск исполняет функция Lookup:
template <char Var, class Env> struct Lookup;

 В пустом окружении ничего нет. Если желанное значение есть в нынешнем окружении, то возвращаем его. Напротив рекурсивно просматриваем остальные окружения:
template <char Var>
struct Lookup<Var, NullEnv>;

template <char Var, class Val, class Env>
struct Lookup<Var, Bind<Var, Val, Env>>
{
    typedef Val result;
};

template <char Var, char OtherVar, class Val, class Env>
struct Lookup<Var, Bind<OtherVar, Val, Env>>
{
    typedef typename Lookup<Var, Env>::result result;
};
 

Конец

Вот так в 50 строках мы всецело определили синтаксис и семантику лямбда-исчисления с поддержкой образцов C , что доказывает Тьюринг-полноту механизма раскрытия образцов C (при условии неограниченного объёма доступной памяти).

Определение машины Тьюринга (англ.) дозволено втиснуть в приблизительно такой же объём строк, но оно всё равно будет больше многословным из-за больше трудной конструкции. Определение мю-рекурсивных функций (англ.) будет наверно короче, но ненамного. Увлекательно было бы ещё посмотреть на реализацию цепей Маркова, но её я не нашёл, оценить размеры начального кода трудно, а писать самому лень.

 Окей, испробуем провести простейшее вычисление, применяя полученные вероятности (полный код):
/* Определения, показанные выше */

#include <iostream>

int main()
{
    // 1 = редать в 1-й вызов Eval какое-то окружение, то оно будет играть роль глобального для вычисляемого терма: именно оно задаёт значения свободных переменных — тех, которые ни с чем не связаны лямбда-абстракциями.

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

#include <iostream>

int main()
{
    /* Определения One, Two, Plus пропущены */

    // Unchurch = ;typename Expand<Exp>::result, Env>::value value;
};

Expand принимает только один довод. Будем считать, что это чёрный ящик: на входе программа с макросами, на выходе — без них. В нашем простом случае не необходимы какие-либо макроокружения.

Реализация макросов

Сейчас макросы, видимо, нужно реализовать внутри Expand. Нам необходимы некие Lam_ и App_, которые раскрываются дальнейшим образом:
До Позже
Lam_<'x', 'y', ..., 'z', B> Lam<'x', Lam<'y', ..., Lam<'z', B>...>>
App_<A, B, C, ..., Z> App<...App<App<A, B>, C>, ..., Z>
App_<'a', ...> App_<Ref<'a'>, ...>
В C 11 возникли образцы произвольной арности, что порядком облегчает задачу. Владельцам компиляторов C 03 остаётся только страдать и писать 1000 и одну специализацию: Lam_2 для 2-х доводов, Lam_3 для трёх, App_4 для четырёх, и т. д. Ну, либо извращаться ещё мощнее и повторить всё, что показано ниже, с поддержкой родного препроцессора C .

Lam_
Правда, даже у образцов С 11 есть свои ограничения, следственно синтаксис придётся ещё чуть-чуть подпилить. Пачка доводов может быть только последним доводом образца, следственно для Lam_ нужно ввести особую «держалку доводов»:
template <char... Vars> struct Args;
template <class Args, class Exp> struct Lam_;

template <char Var, class Exp>
struct Expand<Lam_<Args<Var>, Exp>>
{
    typedef typename Expand<Lam<Var, Exp>>::result result;
};

template <char Var, char... Vars, class Exp>
struct Expand<Lam_<Args<Var, Vars...>, Exp>>
{
    typedef Lam<Var, typename Expand<Lam_<Args<Vars...>, Exp>>::result> result;
};

 Обратите внимание на повторные вызовы Expand в процессе раскрытия. Они нужны, так как Expand<...>::result неизменно должен быть чистым лямбда-термом без макросов.

App_
А ещё образцы C 11 не разрешают смешивать в пачке доводы-числа и доводы-типы, следственно у App_ будет два соответствующих варианта. Печалька.

 Реализации App_s (для символов) и App_i (для типов) больше объёмные, следственно объяснения и код спрятаны под спойлер.

Спрятанный текст

Для начала нужно унифицировать доводы аппликации. Они могут быть либо пачкой имён переменных, либо пачкой лямбда-термов. Имена нужно превратить в термы. Если бы образцы C 11 разрешали написать map для пачек, то было бы проще, а так мы возведем ещё один связный список. (А может, map реально написать? Anyone?)

struct Nil;
template <class First, class Rest> struct RefList;

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

template <char... Vars> struct ToRefList_s;

template <char Var>
struct ToRefList_s<Var>
{
    typedef RefList<Ref<Var>, Nil> result;
};

template <char Var, char... Vars>
struct ToRefList_s<Var, Vars...>
{
    typedef RefList<Ref<Var>, typename ToRefList_s<Vars...>::result> result;
};

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

template <class... Exps> struct ToRefList_i;

template <class Exp>
struct ToRefList_i<Exp>
{
    typedef RefList<Exp, Nil> result;
};

template <class Exp, class... Exps>
struct ToRefList_i<Exp, Exps...>
{
    typedef RefList<Exp, typename ToRefList_i<Exps...>::result> result;
};

Сейчас полученный список доводов вызова нужно обработать. Функция App_wrap реализует жгуче любимый всеми алгорифм — переворачивание списка на Прологе! Только в процессе список RefList преобразуется в «список» App. Её 1-й довод — это собираемый «список» App, а 2-й — ещё не перевёрнутая часть RefList.

1-й элемент списка RefList нужно применить ко второму. После этого к этому итогу ступенчато используются остальные элементы. Останавливаемся, когда элементы закончатся (дойдём до Nil).

template <class Apps, class RefList> struct App_wrap;

template <class A, class D, class R>
struct App_wrap<Nil, RefList<A, RefList<D, R>>>
{
    typedef typename App_wrap<App<A, D>, R>::result result;
};

template <class Apps, class A>
struct App_wrap<Apps, RefList<A, Nil>>
{
    typedef typename App_wrap<App<Apps, A>, Nil>::result result;
};

template <class Apps, class A, class D>
struct App_wrap<Apps, RefList<A, D>>
{
    typedef typename App_wrap<App<Apps, A>, D>::result result;
};

template <class Apps>
struct App_wrap<Apps, Nil>
{
    typedef Apps result;
};

Подметили её? Да, это хвостовая рекурсия.

В финальном результате мы пишем следующие примитивные определения. Они вызывают рассмотренные под спойлером функции, которые исполняют всё чёрную работу, позже чего сами ещё раз прогоняют итог через Expand, Дабы на выходе не осталось нераскрытых макросов.
template <char...  Exps> struct App_s;
template <class... Exps> struct App_i;

template <char... Exps>
struct Expand<App_s<Exps...>>
{
    typedef typename Expand<
                typename App_wrap<Nil,
                    typename ToRefList_s<Exps...>::result
            >::result
        >::result result;
};

template <class... Exps>
struct Expand<App_i<Exps...>>
{
    typedef typename Expand<
                typename App_wrap<Nil,
                    typename ToRefList_i<Exps...>::result
            >::result
        >::result result;
};
 
Остальное
И последнее, но значимое дополнение. Экспандер должен верно обрабатывать встроенные конструкции языка, раскрывая макросы там, где они могут встретиться:
template <char Var>
struct Expand<Ref<Var>>
{
    typedef Ref<Var> result;
};

template <char Var, class Exp>
struct Expand<Lam<Var, Exp>>
{
    typedef Lam<Var, typename Expand<Exp>::result> result;
};

template <class Fun, class Arg>
struct Expand<App<Fun, Arg>>
{
    typedef App<typename Expand<Fun>::result,
                typename Expand<Arg>::result> result;
};

 Кто подметил в работе Expand параллели с Eval и Apply, тот молодец.
 (Полный код с помощью макросов.)

Рекурсия

Self description
 Сказав про полноту по Тьюрингу полученного вычислителя, мы как-то обошли стороной один момент, удовлетворившись примитивный арифметикой. чай Тьюринг-полная система разрешает выразить циклы! Разглядим циклические вычисления на примере (барабанная дробь) факториала.

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

 Впрочем, хитроумные математики обнаружили метод обойти это лимитация: так называемый Y-комбинатор разрешает выражать рекурсивные функции как решения функциональных уравнений о стационарных точках. Что это такое и как расшифровывается предыдущее предложение, можете прочитать в ином месте, а теперь значимо, что Y-комбинатор записывается вот так:
// Y = ds_andmk!lt;Fact_gen, StandardLibrary>,
            StandardLibrary > > >
не определяет типа result, то есть данный вызов не имеет смысла. Компилятор увидел и разорвал безграничный цикл подстановки образцов, тот, что по эталону является неопределённым (14.7.1/15).

 Образцы C тоже проводят вычисления в аппликативном порядке, потому что вызовом функции typename Eval<Exp, Env>::value является инстанциирование образца. Инстанциирование Eval видимо требует инстанциирования Exp и Env.

 В языках с аппликативным порядком вычислений следует использовать Z-комбинатор — модификацию Y-комбинатора, в которой выражение (x x) завёрнуто в абстракцию, что предотвращает его несвоевременное вычисление:
// Z = center;">


Завершение


Утилитарной инженерной пользы от этого интерпретатора, вероятно, никакой нет, но сама по себе идея замечательна. Образцы C — это она из «невольно Тьюринг-полных» пророческой в теоретической информатике. Аналогичное чувство у меня появилось разве что тогда, когда я узнал, что подсистема управления страничной памятью x86-процессоров тоже полна по Тьюрингу. Если данный интерпретатор разрешает исполнять вычисления, не исполняя ни одного оператора C , то MMU разрешает исполнять вычисления, не исполняя ни одной машинной инструкции программы.

К сожалению, DCPL я дочитал пока только до восьмой главы, следственно написание интерпретатора типизированноголямбда-исчисления оставляется читателям в качестве упражнения. У меня пока ещё слишком слабая математическая подготовка для этого.

P.S. Всё время, пока я писал пост, меня не покидала мысль: «Это либо теснее есть в Бусте, либо пишется там в три строки».

 

Источник: programmingmaster.ru

 

Оставить комментарий
БАЗА ЗНАНИЙ
СЛУЧАЙНАЯ СТАТЬЯ
СЛУЧАЙНЫЙ БЛОГ
СЛУЧАЙНЫЙ МОД
СЛУЧАЙНЫЙ СКИН
НОВЫЕ МОДЫ
НОВЫЕ СКИНЫ
НАКОПЛЕННЫЙ ОПЫТ
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB