Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Есть ли работы по "сублинейным" типам?

Вадлер (он же Уодлер) пишет, что линейные типы возникли в том числе и как решение задачи о вычислительно эффективном чисто функциональном обновлении массива:

foo = array_update bar 2 3

В этом чисто функциональном коде, эквивалентном императивному bar[2] := 3, у нас есть 2 версии одного и того же массива - одна названа foo, а другая bar.

Идея в том, что если старая версия bar на момент создания foo никому не нужна, то мы можем просто императивно обновить массив bar и назначить ему имя foo, вместо того чтобы создавать копию. Снаружи это будет выглядеть одинаково, а производительность вырастет.

Линейные типы решают задачу определения того, что "версия не нужна", весьма приблизительно: считается, что версия bar не нужна, если bar упоминается в программе всего 2 раза - в месте определения и в месте использования.

Но, скажем, если мы докажем, что bar[2] нигде не используется, то оптимизацию всё равно можно выполнить.

Есть и более реалистичные сценарии. Вот такой (снова чисто функциональный) код:

x = bar[2] + bar[3]
foo = array_update bar 2 3

Если язык "энергичный", то нашу оптимизацию всё равно можно выполнить, несмотря на то что bar имеет нелинейный тип.

Вопрос к залу: есть ли работы по ослаблению условия линейности для обновлений на месте в чисто функциональном коде? (не обязательно для обновлений массивов)
Tags: fp, programming
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 17 comments