Специализни шаблонца! (udpn) wrote,
Специализни шаблонца!
udpn

Category:

Обобщённые стрелки

Предупреждение: дальше по тексту зачастую будет утверждаться какое-нибудь X, однако никаких исследований по этому поводу не проводилось никем и никогда. Поэтому вопросы вроде "c чего ты взял, что Х -- обобщённая стрелка", скорее всего, останутся с ответом "потому что попой чую" или вовсе без оного.

У вас есть некоторый язык программирования.
Вы хотите в нём воспользоваться имеющимся синтаксисом для некоторой хитрой цели.
К примеру, вы кодогенерируете джаваскрипт.
Вам нужен, таким образом, способ перегрузки оригинального синтаксиса.
Существуют языки, где вы можете получить AST некоторого фрагмента кода, поменять его и сделать обратно кодом. Например, Лисп, Хаскелл и Скала.
Такую возможность называют "макросы", саму дисциплину -- метапрограммирование.
Писать AST вручную, если мы что-нибудь генерируем, неприятно.
Нам хотелось бы иметь возможности из почти исходного синтаксиса генерировать неполные AST (c дырками).
Такая возможность называется квазиквотированием.
Но что-либо серьёзное в этом ключе написать всё равно сложно.
Не вполне понятно, в каком именно месте здесь включается типизация, например.
Удостовериться, что данный фрагмент кода генерирует AST с корректными типами всегда, невозможно.
Для этого придётся проводить что-то вроде статического анализа над генерирующим AST кодом.
Учитывая, что используется оригинальный язык, а он обычно Тьюринг-полон, получаем неразрешимую задачу.
Доказывать корректность таких кодогенераторов в общем случае сложно.
Это "вжжж" неспроста.
Рассмотренный ранее подход к метапрограммированию называется интенсиональным.
Существуют ещё и не-интенсиональные подходы, и я знаю из них только один.
Обобщённые стрелки.
Для них в общем случае нужна поддержка интерпретатором или компилятором.
Программа при трансляции переводится в язык из небольшого набора комбинаторов.
Пользователю предоставляется возможность эти комбинаторы переопределять на некотором фрагменте кода.
Чтобы всё было в порядке, комбинаторы поставляются с набором аксиом, которым они должны удовлетворять.
Теперь к подробностям.
Разные программы требуют различного набора комбинаторов.
Если в программе есть несколько переменных, её представление требует комбинаторов, которые работают с парами (типами-произведениями), например, first : (a -(x)> b) -> ((a, c) -(x)> (b, c)). Этот first должен удовлетворять кое-каким аксиомам.
Если одна переменная может использоваться дважды, нужен dup : a -(x)> (a, a).
Если в языке есть литералы целых, нужно что-то вроде int : () -(x)> Int.
Чтобы появился этот (), нужен ещё набор примитивов типа uncancel_l : a -(x)-> ((), a), uncancel_r : a -(x)> (a, ()).
Ну вы поняли идею, да? Шинкуем язык на комбинаторы и типа всё.
На самом деле, мы можем нашинковать исходный язык на комбинаторы многими способами.
Например, если в языке мы можем объявлять рекурсивные функции, то мы можем добавить комбинатор fix, он же loop.
В то же время, если бы в нашем языке была возможна только "хорошая" убывающая рекурсия по натуральным числам, мы могли бы объявить в качестве примитива natrec.
Но ничто нам не мешает иметь и то, и другое одновременно.
Просто данный код будет транслироваться в потенциально разные наборы комбинаторов в зависимости от того, акие комбинаторы мы перегрузили в данном фрагменте кода.
Например, факториал будет иметь возможность транслироваться в natrec, если мы запускаем его в доказанно завершимом контексте, или fix, если мы запускаем его в контексте трансляции в JS.
И ещё: наборы комбинаторов это type class'ы.
Ознакомиться с классическими можно, изучив (необобщённые) стрелки: Arrow, ArrowChoice, ArrowApply, ArrowLoop
Этих наборов целая решётка.

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

Стрелки (необобщённые) были разработаны, в том числе, для создания эффективных парсеров (Swierstra & Duponchel). Дело в том, что стрелка a ~> b это что-то вроде функции a -> b или около того, но она дополнительно может хранить какие-нибудь данные.
data Something a b = Something AdditionalData (a -> [b])
Это, кстати, позволяет решить одну очень больную проблему для других языков.
Представьте себе, что вы можете произвести некоторые затратные вычисления при запуске программы, а потом пользоваться результатами. Например, посчитать таблицы синусов для дальнейшего использования в генерации объёмных сферических объектов или меш нужной детализации по функции, как это делают в демо-сценах
Вы затем хотите вынести этот функционал в библиотеку и обнаруживаете, что не знаете, стоит ли вам вызывать эти вычисления (обычно в конструкторе соотв. класса), так как вы не знаете, будут ли они использованы в пользовательском коде.
Можно сделать это в стиле синглетона, но это породит +1 if (и лишние +5% прочистки конвеера), а также в исполнимый файл может попасть код, который никогда не будет вызван (оптимизатор может его и удалить, но он не тотальный, задача поиска мёртвого кода неразрешимая же).

Самое главное: обобщённые стрелки позволяют создать действительно универсальный язык.
Обычно когда в языке X не хватает Y, кто-нибудь берёт и делает X+Y.
Например, с чего бы от С++ ответвляться всяким PHP?
Нужна была весьма специфическая среда для кода (хорошие встроенные строки, например).
В то же время, несмотря на почти идентичность синтаксиса, в язык были внесены изменения.
Теперь библиотеки для С++ нельзя просто так взять и использовать в PHP и наоборот.
В случае языка со встроенными обобщёнными стрелками нужно было бы просто создать подходящую стрелку, которая работает с server state, session state и чем-нибудь там ещё.
Скорее всего, для такой стрелки не понадобилось бы даже менять компилятор.
Вся кодовая база была бы доступна. Весь старый синтаксис бы работал.

Впрочем, если такой язык написать, то можно будет решить проблему вавилонской башни посредством кодогенерирующих инстансов соответствующих стрелок.
Собственно, ваш покорный слуга шёл к этому 7 лет (из них 6.5 вокруг да около сабжа; нельзя просто так взять и самому придумать обобщённые стрелки, их должен придумать кто-то другой, а кто-то третий -- рассказать), и собирается это таки сделать :)
Интуиции в таком подходе к разработке ЯП мне сильно не хватает, и достать её, в общем-то, особо негде.

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

Инстансы:
хост-язык (этот инстанс неявно скармливается функции main)
парсеры
кодогенераторы (fix генерирует рекурсивные вызовы, let генерирует заголовки функций, ...)
    CUDA
    шейдеры
    JS, CSS, HTML, PHP
    С++
    заголовки .h для dll сразу из определения функций
    VHDL и Verilog
    электрические схемы (цифровые и аналоговые)
    изображения (векторная графика, генеративное моделирование, SVG)
специализатор (упрощает pow(x, 2) до \x -> x * x)
инлайнер
оптимизаторы
неявное распараллеливание
трансляторы

Хотелось бы поблагодарить ребе akuklev за разъяснение мне этого дела, камрада tomotom за то, что не устаёт слушать мой больной бред и гуру sharpc за лучи ненависти к ФП и стратегию "заткнись и пиши" :)
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 114 comments