Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Categories:

О комбинаторе W/join, инкапсулирующем всю нелинейность

Открытие о том, что комбинатор W - единственный нелинейный комбинатор, и этот факт можно использовать для оптимизации, получилось случайно - vag_vagoff  прислал пример, нереализуемый с помощью комбинаторов BCIK (все они - линейные!):
testfun a = a + x where x = sqrt a
До этого момента HN0 прекрасно обходился без W, I и K, голыми BC. В необходимости I и K я до сих пор не уверен, всё еще жду примера, когда они не могут быть устранены оптимизатором. Т.е., я считаю, что \a b -> a всегда может быть заменена на a и  \a -> a (комбинатор I, id) всегда может быть заменена на a.

В BCW на HN0 данный пример выглядит так:
testfun = join i where
	i = j sqrt where
		j = o +
Тут я полагаю, что реализовывать +, sqrt и числа искусственными конструкциями в духе нумералов Чёрча, для которых вполне могут понадобится искусственные же комбинаторы I и K, не нужно.

По причине искусственности комбинатора S я сразу же отверг базис SK. Вы же не оперируете при покупке картошки аксиомами Пеано, и не строите условных операторов исключительно с помощью штриха Шеффера.

Необходимость flip была мне очевидна - привязку второго аргумента member в оригинальном примере без него сделать нельзя было. В процессе разработки библиотеки выяснилось, что о нужен тоже, и o и flip не реализуются друг через друга.

У меня получалось писать довольно сложные программы, несмотря на убогость языка и отсутствие какой-либо поддержки для рекурсии, условных конструкций и разделения данных. В связи с этим Ваг и сконструировал серию примеров, требующих обязательного разделения. Общая рекурсия, судя по Epigram и Martin-Lof Type Theory, мне никогда и не понадобится. А вот с if действительно загвоздка, не хочется вычислять обе ветки. Буду думать, как это впишется в текущий компилятор.
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.
  • 24 comments