Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Category:

Просьбы и обещания

В связи с нижеизложенными фантазиями у меня такие вопросы к общественности:
  1. Плохо ли то, что просьбы передаются неявно? Можно, например, передавать просьбу дополнительным параметром.
  2. Можно ли придумать более эффективную кодировку для просьб?
  3. Смасштабируется ли метафора передачи просьбы скрытым аргументом на случай сложных выражений? Очевидно, например, что map передает просьбу как есть вниз по стеку вызовов.
  4. Связана ли моя идея просьбы с понятием data shape (shapely types etc)?
  5. Есть ли работы по выводу просьб и оптимизации программ с их учетом?
Возьмем простую функцию
foo::Bool -> Bool -> Bool -> (Bool, Bool, Bool)
foo a b c = (a, b, c)
Допустим, мы хотим протестировать все возможные control flow. В чистом жадном тотальном языке control flow полностью определяется аргументами. Иначе говоря, 8 тестов полностью покроют функцию.
assert(foo False False False == (False, False, False))
assert(foo False False True == (False, False, True ))
...
assert(foo True True False == (True, True, False))
assert(foo True True True == (True, True, True ))
В ленивом языке поведение этой функции гораздо сложнее.

Её могут "попросить" конструировать не весь тапл, а только его часть. Считаем, что в нашем языке (a, b, c) == (a, (b, c)) == (,) a ((,) b c). Возможно 11 вариантов просьб:
_
(,) _ _
(,) a _
(,) _ ((,) _ _)
(,) a ((,) _ _)
(,) _ ((,) b _)
(,) a ((,) b _)
(,) _ ((,) _ c)
(,) a ((,) _ c)
(,) _ ((,) b c)
(,) a ((,) b c)
Итого пространство control flow выросло в 11 раз, и если мы захотим его протестировать, нам понадобится 88 тестов - 8 вариантов аргументов и 8 вариантов просьб.

Нетотальные (частичные) языки отличаются непринципиально - просто будет не 8 возможных комбинаций, а 27 (Bool = True | False | _|_ вместо True | False). Также стоит заметить, что данный пример годится не только для call by need, но и для более простой стратегии редукции call by name.
Subscribe

  • Продолжение эпопеи с переездом

    С подключением ADSL в результате Кларо так и не приехал, так что я подключился помимо говнопровайдера ещё и к основному конкуренту Кларо - Альтису.…

  • Наше кино

    http://www.imdb.com/title/tt4263270/ Я тут периодически из мазохистских соображений хожу в кинотеатр за компанию. В результате посмотрел две сказки…

  • Ещё одна поговорка

    el que madruga dios lo ayuda - кто рано встаёт тому бог подаёт A caballo dado no de le ve el colmillo - дарёному коню в зубы не смотрят

  • 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.
  • 14 comments

  • Продолжение эпопеи с переездом

    С подключением ADSL в результате Кларо так и не приехал, так что я подключился помимо говнопровайдера ещё и к основному конкуренту Кларо - Альтису.…

  • Наше кино

    http://www.imdb.com/title/tt4263270/ Я тут периодически из мазохистских соображений хожу в кинотеатр за компанию. В результате посмотрел две сказки…

  • Ещё одна поговорка

    el que madruga dios lo ayuda - кто рано встаёт тому бог подаёт A caballo dado no de le ve el colmillo - дарёному коню в зубы не смотрят