Вырашэнне таямніцы магічных аптымізацый абстрактнага алгарытму

Учора я паведаміў пра дзіўнае назіранне, што пэўныя функцыі могуць паводзіць сябе так, як быццам яны маюць негатыўную складанасць. Вам не трэба чытаць гэты артыкул перад гэтым. Карацей кажучы, λ-тэрмін f (біты) = копія (comp (inc, n, bits)) асімптатычна хутчэй, чым g (bits) = comp (inc, n, bits); гэта значыць, аперацыя copy (a (1) для фіксаванага памеру) паводзіць сябе так, як калі б яна мела складанасць O (1 / n), прымушаючы праграму працаваць хутчэй, выконваючы больш рэчаў (!?).

Гэта не адзіны мудрагелісты вынік складанасці, які я меў пры эксперыменце з абстрактным алгарытмам. Гады таму я заўважыў, што ён здольны вылічыць праграмы, якія не ўпісваюцца ў камп'ютэрны памер Сусвету. Нядаўна я апублікаваў, як гэта можа прымяніць аперацыю O (1) N разоў у часе O (log (N)) (!?). Нягледзячы на ​​прадстаўленыя праніклівыя адказы, цяжка было асэнсаваць такое неінтэнтыўнае паводзіны.

Пасля шматлікіх даследаванняў і некаторых нядаўніх уяўленняў гэта нарэшце мяне ўразіла. Атрымліваецца тлумачэнне ўсяго гэтага даволі простае, і ў гэтым артыкуле я растлумачу, што адбываецца асцярожна (на гэты раз не жартам). Калі вы спяшаецеся, не саромейцеся пераходзіць да tl; dr ў канцы.

1. Аптымізацыйныя функцыі - гэта тыя функцыі, якія зліваюцца, калі складаюцца самастойна

Для пачатку пачнем з найпростага прыкладу, на якім здараецца нешта цікавае: не паўтараецца. Давайце рэалізаваць яго двума рознымі спосабамі:

Праўда = λt. λf. t False = λt. λf. f not_a = λb. (b False True) not_b = λb. λt. λf. (Bft)

Калі вы не разумееце гэтых вызначэнняў, вы можаце прачытаць пра кадаванне лямбда, але гэта не занадта важна. Цяпер, як паслядоўныя прыкладанні not_a і not_b працуюць у Absal (рэалізацыя абстрактнага алгарытму)? Вось графік:

Складанасць (агульная перапісванне) ужывання

Тут складанасць вымяраецца як перапісвае графік. Не хвалюйцеся з гэтай нагоды, хаця проста выказаць здагадку, што час, неабходны для запуску λ-тэрміна, прапарцыйна колькасці перапісаных графікаў. Як бачыце, not_a выконвае лінейна, а not_b выконвае лагарыфмічна. Гэта велізарная розніца для такой невялікай змены! Акрамя таго, гэта вельмі неінтуітыўна, таму што вы не павінны мець магчымасць ужываць N nots у O (log (N)). Тады чаму гэта адбываецца? Перш чым адказаць, давайце спачатку зробім эксперымент. Давайце складзем абедзве функцыі з сабой і правяраем іх нармальныя формы.

  • норма (not_a.not_a): λb. (b (λt.λf.f) (λt.λf.t) (λt.λf.f) (λt.λf.t))
  • норма (not_b.not_b): λb. λt. λf. (btf)

Цікава: калі самастойна складаецца, not_a расце больш, але not_b застаецца аднолькавага памеру. Чаму? Таму што больш познія функцыі зрасталіся. Гэта той самы эфект, які дазваляе Haskell за адзін праход некалькі разоў перайсці спіс па спісе, выключаючы прамежкавыя структуры. Гэта прыводзіць нас да гіпотэзы, што магічнае паскарэнне можа мець нейкае дачыненне да гэтай уласцівасці. Давайце правяраем гэтую гіпотэзу, правяраючы працу карты на спісах:

Nil = λc. λn. мінусы = λh. λt. λc. λn. ch (tcn) map_a = λf. λl. l (λh. λt. мінусы (fh) t) Nil map_b = λf. λl. λc. λn. l (λh. λt. c (fh) t) n спісу = Мінусы праўдзівыя (мінусы ілжывыя (мінусы ілжывыя (мінусы ілжывыя).

Тут мы зноў вызначылі гэта двума рознымі спосабамі: map_b злучаецца, а map_a не. Давайце вымераем складанасць прымянення карты некалькі разоў да спісу:

Складанасць (усяго перапісанняў) прымянення

Як бачыце, тут назіраецца аднолькавае паводзіны: версія, якая зліваецца, выконвае лагарыфміку, а версія, якая не працуе лінейна, падтрымліваючы нашу гіпотэзу. Воа! Але чаму гэта адбудзецца?

(Вось код для прайгравання гэтага эксперыменту і генерацыі графікаў.)

2. Экспаненцыя шляхам квадрацыі = склад дзялення

Каб зразумець гэта, давайце спачатку пагаворым пра цэлыя экспаненцыі. Калі вы распрацоўшчык, хутчэй за ўсё, вы чулі пра вытрымку шляхам квадрацыі. Гэта старажытны просты алгарытм, здольны вылічыць A ^ B значна менш крокаў, чым трэба, каб памножыць A некалькі разоў, B раз. Каб абнавіць розум, давайце візуалізуем, як гэта працуе:

# Вылічэнні 13 ^ 8 з паўторным множаннем
13 ^ 2 = 13 * 13 = 169 13 ^ 3 = 13 * 169 = 2197 13 ^ 4 = 13 * 2197 = 28561 13 ^ 5 = 13 * 28561 = 371293 13 ^ 6 = 13 * 371293 = 4826809 13 ^ 7 = 13 4826809 = 62748517 13 ^ 8 = 13 * 62748517 = 815730721
# Вылічэнні 13 ^ 8 з экспаненцыяй на квадраты
13 ^ 2 = 13 * 13 = 169 13 ^ 4 = 169 * 169 = 28561, 13 ^ 8 = 28561 * 28561 = 815730721

Як бачым, першы падыход памнажае 13 адзін на адзін, патрабуючы N множання, каб дасягнуць 13 ^ N (лінейны час), а другі некалькі разоў замест першага ліку праводзіць квадраты, што дазваляе скакаць з 13 ^ 1 да 13 ^ 2 да 13 ^ 4 да 13 ^ 8 у адным множанні на кожны скачок (лагарыфмічны час). Каб вылічыць значэнні, якія не з'яўляюцца дасканалымі квадратамі, трэба проста памножыць падпарадкі, то ёсць 13 ^ 11 = 13 ^ 8 * 13 ^ 2 * 13 ^ 1.

Акуратна, так? Але наколькі гэта актуальна? З-за менш вядомых фактаў, для любой функцыі, якую можна зліць па кампазіцыі, мы можам таксама вылічыць яе паўторнае прымяненне ў кроках O (log (N)), выкарыстоўваючы той самы трук! Давайце візуалізаваць яго таксама:

# Вылічэнні не ^ 8 (т) пры паўторным ужыванні
не ^ 2 (t) = (λb.λf.λt. bft). (λb.λf.λt. bft) = (λb.λf.λt. btf) не ^ 3 (t) = (λb.λf.λt. bft). (λb.λf.λt. btf) = (λb.λf.λt. bft) не ^ 4 (t) = (λb.λf.λt. bft). (λb.λf.λt. bft) = (λb.λf.λt. btf) не ^ 5 (t) = (λb.λf.λt. bft). (λb.λf.λt. btf) = (λb.λf.λt. bft) не ^ 6 (t) = (λb.λf.λt. bft). (λb.λf.λt. bft) = (λb.λf.λt. btf) не ^ 7 (t) = (λb.λf.λt. bft). (λb.λf.λt. btf) = (λb.λf.λt. bft) не ^ 8 (t) = (λb.λf.λt. bft). (λb.λf.λt. bft) = (λb.λf.λt. btf)
# Вылічэнні не ^ 8 (т) з кампазіцыяй шляхам сумеснага выкарыстання
не ^ 2 (t) = (λb.λf.λt. bft). (λb.λf.λt. bft) = (λb.λf.λt. btf) не ^ 4 (t) = (λb.λf.λt. btf). (λb.λf.λt. btf) = (λb.λf.λt. btf) не ^ 8 (t) = (λb.λf.λt. btf). (λb.λf.λt. btf) = (λb.λf.λt. btf)

Добра, гэта занадта цяжка чытаць. Давайце заменім лямбды на іх імёны:

# Вылічэнні не ^ 8 (х) пры паўторным ужыванні
не ^ 2 (х) = не. не = ідэнтыфікатар не ^ 3 (х) = не. id = не ^ 4 (x) = не. не = ідэнтыфікатар не ^ 5 (х) = не. id = не ^ 6 (x) = не. не = ідэнтыфікатар не ^ 7 (х) = не. id = не ^ 8 (x) = не. не = ідэнтыфікатар
# Вылічэнні не ^ 8 (х) з кампазіцыяй шляхам сумеснага выкарыстання
не ^ 2 (х) = не. не = ідэнтыфікатар не ^ 4 (х) = ідэнтыфікатар. id = id не ^ 8 (x) = id. id = ідэнтыфікатар

Вы бачыце? Першы падыход прымяняецца не па адным, а для дасягнення канчатковага выніку патрабуецца N прыкладанняў (лінейнае час), а другі некалькі разоў самастойна складае пачатковую функцыю, пераскокваючы з не ^ 2 не ^ 4 не ^ 8 толькі з адной кампазіцыя для кожнага скачка (лагарыфмічны час). Іншымі словамі, да таго часу, пакуль самаскладанне f-засцерагальнікаў, мы можам ажыццявіць паўторнае прымяненне ў лагарыфмічны час, выкарыстоўваючы тую ж хітрасць, якая адстае ад экспаненцыі, шляхам квадрацыі!

3. Абсал ажыццяўляе зліццё падчас выканання

На жаль, ведаючы, што гэты трук недастаткова для паскарэння лёгкаплаўкіх алгарытмаў: нам таксама патрэбны функцыянальны мову, здольны выконваць кароткачасовае зліццё падчас выканання. Сам Haskell, наадварот, не здольны зрабіць гэта для родных функцый. Для ілюстрацыі давайце рэалізаваць у ім кампазіцыю:

Гэтая функцыя прымае лік n, функцыю f, і вяртае новую функцыю, якая паўтарае f неаднаразова да x, n разоў, выкарыстоўваючы метад "склад дзялення". У якасці прыкладу (comp (не, 10, x)) ацэньваецца ў эквіваленце:

Звярніце ўвагу, як гэтая функцыя да яе ўводу прымяняецца не 10 разоў, хоць кампазіцыя выкарыстоўвае толькі 3 разы? Менавіта таму яна павінна быць эфектыўнай. Такім чынам, у чым складанасць comp (не, N, x) у Haskell? Не лагарыфмічны, як мы чакалі, але лінейны! Вы можаце праверыць гэты факт, запусціўшы гэты Gist. Калі вы змяніце 2 ^ 20 на нешта вышэйшае, напрыклад, 2 ^ 40, у яго не застанецца памяці. Чаму? Таму што ён лянівы і ніколі не ацэньвае ўнутры лямбдаў, якія былі б неабходныя для зліцця гэтых прамежкавых выразаў. І нават калі б гэта было, усё адно не атрымаецца. У гэтым асобным допісе высвятляецца, чаму, вывучаючы мадэль ацэнкі Haskell і JavaScript, і чаму яны не з'яўляюцца аптымальнымі.

Цяпер мы сапраўды блізкія да вырашэння нашай галаваломкі. Але, па-першае, нам трэба пагаварыць пра паралельныя сусветы; Я маю на ўвазе паралельныя скарачэнні. Галоўнае ўяўленне аб Absal - выкарыстанне сетак узаемадзеяння, а не больш простых тэкставых уяўленняў. Сеткі ўзаемадзеяння - гэта мадэль вылічэння на аснове графікаў з маркіраванымі партамі (адзін - "галоўны порт") і вельмі своеасаблівы нюанс: калі сустракаюцца два "асноўных порта", вузлы, злучаныя імі, перапісваюцца.

Перапісаць правілы ўзаемадзеяння камбінатараў, тып сеткі ўзаемадзеяння

Гэта выклікае вельмі цікавы эфект: незалежна ад таго, якім парадкам вы перапісваеце свае вузлы, агульная колькасць крокаў застаецца нязменнай. Калі, такім чынам, вы кампілюеце λ-тэрміны ў сеткі для ўзаемадзеяння, то вы можаце памяншаць выразы ў любым парадку: спачатку функцыі, спачатку аргументы, нават паралельна. У рэшце рэшт, выкананая праца будзе аднолькавай!

Хітрасць, вядома, у тым, як правільна перакласці λ-тэрміны ў сеткі для ўзаемадзеяння. На жаль, няма рашэння, якое б эфектыўна ахоплівала ўсе λ-тэрміны. Але для велізарнага іх класа (напэўна, усё, што вы напісалі б на практыцы) ёсць просты і элегантны спосаб зрабіць гэта: гэта абстрактны алгарытм. Каб растлумачыць гэта ў бліжэйшы час, кожная лямбда і кожнае прыкладанне λ-тэрміна становіцца патройным вузлом у сетцы, і кожнае паўторнае знаходжанне зменнай становіцца "вентылятарным вузлом". Акрамя таго, галоўны порт вузла прыкладання паказвае на порт функцыі, і таму паўторнае вырашэнне файлаў ніколі нельга дубляваць.

Калі вы разбіты, не хвалюйцеся. Галоўнае ўяўленне заключаецца ў тым, што, будучы свабодным скарачаць тэрміны ў любым парадку, які ён захоча, Абсал можа быць максімальна прагным без штрафу за выкананне, што, у сваю чаргу, дазваляе яму распальваць прамежкавыя кампазіцыі. Гэта менавіта тое, што трэба для таго, каб выкарыстоўваць трук "кампазіцыя, падзяліўшыся". Калі вы сапраўды хочаце палепшыць разуменне абстрактнага алгарытму, рэкамендую прачытаць гэтую кнігу, яна вельмі педагагічная. Акрамя таго, вы можаце проста разгледзець малюнак ніжэй:

Ён адлюстроўвае ацэнку тэрміна (λg. G (g λx. X)) (λh. (Λf. F (f λz. Z)) (h λy. Y)) тэрміна па абстрактным алгарытме. Звярніце ўвагу на тое, як падвыразы можна падзяліць некалькімі тэрмінамі, як мы можам ацаніць унутры лямбда, не рызыкуючы дубляваць працу (і, пакуль яшчэ лянота), і як адна бэта-скарачэнне пастаяннага часу ў гэтым фармаце эквівалентна некалькі бэта-скарачэнняў на больш традыцыйныя ўяўленні. Прыгожа, не?

А як жа рэчы з негатыўнай складанасцю?

Давайце перабярэм усё, што мы даведаліся да гэтага часу. Па-першае, некаторыя функцыі λ-вылічэння зліваюцца, калі яны самастойна складаюцца. Пад "засцерагальнікам" я маю на ўвазе памер іх нармальных формаў, якія застаюцца пастаяннымі. Па-другое, гэтыя функцыі можна ўжываць N разоў з складанасцю O (log (N)) пры дапамозе стратэгіі "склад дзялення", пакуль мова гаспадара можа імкліва нармалізаваць падвыразы ў лямбдах. Па-трэцяе, Absal здольны даваць ацэнку ўнутры лямбдаў, што дазваляе яму рабіць менавіта гэта, зліваючы ўнутраныя кампазіцыі падчас выканання. Гэта прыводзіць нас да адной лагічнай высновы: копія павінна неяк выклікаць узрывальнік! Нічога сабе! Ці можа быць? Давайце правяраем гэтую гіпотэзу, шукаючы нармальныя формы!

- Звычайная форма `inc`: λa. λb. λc. λd. (((ac) λe. (b λf. λg. λh. (((напрыклад) λi. (f λj. λk. λl. (((ik) λm. (jm)) l))) h))) d )
- Звычайная форма `укл. ўкл`: λa. λb. λc. λd. (((a λe. (b λf. λg. λh. (((напрыклад) λi. (f λj. λk. λl. (((ik) λm. (jm)) l))) h))) λe. (c λf. λg. λh. (((напрыклад, λi. (f λj. λk. λl. (((ik) λm. (jm)) l))) h))) d)
- Звычайная форма `укл. укл. ўкл`: λa. λb. λc. λd. (((a λe. (c λf. λg. λh. (((напрыклад) λi. (f λj. λk. λl. (((ik) λm. (jm)) l))) h))) λe. (b λf. λg. λh. (((e λi. (f λj. λk. λl. (((ik) λm. (jm)) l))) λi. (g λj. λk. λl. ((( ik) λm. (jm)) l))) h))) d)
-------------------------------------------------- -----------
- Звычайная форма `копіі. ўкл`: λa. ((((λb. λc. λd. λe. (d (((b λf. λg. λh. λi. (g (((f λj. λk. λl. λm. (kj)) λj. λk. λl. λm. (lj)) λj. λk. λl. l))) λf. λg. λh. λi. (h (((f λj. λk. λl. λm. (kj)) λj. λk. λl. λm. (lj)) λj. λk. λl. l))) λf. λg. λh. h))) λb. λc. λd. λe. (c (((λf. λg. λh. λi. (h (( (f λj. λk. λl. λm. (kj)) λj. λk. λl. λm. (lj)) λj. λk. λl. l))) λf. λg. λh. λi. (g (((f λj. λk. λl. λm. (lj)) λj. λk. λl. λm. (kj)) λj. λk. λl. l))) λf. λg. λh. h))) λb. λc. λd. d)
- Звычайная форма `копіі. укл. ўкл`: λa. (((a λb. λc. λd. λe. (c (((b λf. λg. λh. λi. (h (((f λj. λk. λl. λm. (kj)) λj. λk. λl. λm. (lj)) λj. λk. λl. l))) λf. λg. λh. λi. (g (((f λj. λk. λl. λm. (lj)) λj. λk. λl. λm. (kj)) λj. λk. λl. l))) λf. λg. λh. h))) λb. λc. λd. λe. (d (((λf. λg. λh. λi. (h (( (f λj. λk. λl. λm. (kj)) λj. λk. λl. λm. (lj)) λj. λk. λl. l))) λf. λg. λh. λi. (g (((f λj. λk. λl. λm. (lj)) λj. λk. λl. λm. (kj)) λj. λk. λl. l))) λf. λg. λh. h))) λb. λc. λd. d)
- Звычайная форма `копіі. укл. укл. ўкл`: λa. ((((λb. λc. λd. λe. (d (((b λf. λg. λh. λi. (h (((f λj. λk. λl. λm. (kj)) λj. λk. λl. λm. (lj)) λj. λk. λl. l))) λf. λg. λh. λi. (g (((f λj. λk. λl. λm. (lj)) λj. λk. λl. λm. (kj)) λj. λk. λl. l))) λf. λg. λh. h))) λb. λc. λd. λe. (c ((b λf. λg. λh. λi. (g (( (f λj. λk. λl. λm. (lj)) λj. λk. λl. λm. (kj)) λj. λk. λl. l))) λf. λg. λh. λi. (h (((f λj. λk. λl. λm. (lj)) λj. λk. λl. λm. (kj)) λj. λk. λl. l))) λf. λg. λh. h))) λb. λc. λd. d)
- Заўвага: выкарыстанне фіксаванай глыбіні 3 для лепшай візуалізацыі

Вось яно! Менавіта так і адбываецца. Не хвалюйцеся змест гэтых тэрмінаў, мы проста ўлічваем іх памеры. Тут склад самога інка невялікі, але, паколькі мы працягваем дадаваць усё больш цалі, нармальная форма павялічваецца лінейна. Іншымі словамі, inc не зліваецца з сабой. Калі мы проста дадаем копію. да паслядоўнасці inc.s, то нармальная форма атрыманай функцыі большая, але застаецца пастаяннай, незалежна ад колькасці кампазіцый. Іншымі словамі, яго самаскладанне проста перастаўляе зменныя і, такім чынам, зліваецца. Гэта, у сваю чаргу, дазваляе ўзнікнуць эфект "кампазіцыя дзяленням", што абумоўлівае лагатып складанасці N-га складу. Адчувае сябе добра, у т.л.!

І ўсё. Загадка вырашана. Вось код для рэплікацыі гэтага эксперыменту з Absal (гл інструкцый па ўстаноўцы ў папярэднім паведамленні).

Апошняе нявырашанае пытанне было б: чаму капіяванне выклікае, уключаючы засцерагальнік? Але гэта не цяжка зразумець. Спачатку давайце візуалізуем азначэнні copy and inc:

Зараз давайце выправім глыбіню d = 2 і візуалізуем, што адбываецца пры складанні копіі:

Атрымліваецца ўцягнутая ў сябе копія, падаючы яе кучу канструктараў, якія пераўтвараюць яе ў функцыю, якая вычарпальна ўзгадвае ўсе галіны яе ўводу на максімальную глыбіню, замест таго, каб дачасна вяртацца, калі больш не трэба працаваць, як гэта было зроблена раней. Звярніце ўвагу, як радок 16 на першым фрагменце была заменена радкамі 8-21 на другім. Іншымі словамі, inc у асноўным стала вялікай табліцай перастаноўкі / пошуку замест звычайнай рэкурсіўнай функцыі. Гэта гучыць як дрэнная ідэя, але аказваецца, што гэта поўнае асвятленне менавіта тое, што было неабходна для функцыі, каб можна было злучыцца з самой сабой. Без гэтага сімвалічныя зменныя, якія дачасна вяртаюцца ў пэўных галінах, не змаглі б знізіцца дадаткова, назапашваючыся ў самастойна складзеных умовах, прымушаючы іх расці ўсё больш і больш. Ці, у якасці альтэрнатывы, дадатковы ўзор адпавядае самазнішчэнню пад самаскладаннем, захоўваючы цела функцыі маленькім.

Выснова

Ну, гэта была даволі паездка. Аказваецца, абстрактны алгарытм меў простыя тлумачэнні, якія ляжалі ў яго магічных выніках. Я рады, што я нарэшце высветліў усе гэтыя рэчы і ўдзячны Redditors, якія пракаментавалі ідэі і здагадкі; спецыяльна, / u / matt-noonan, які згадаў кампазіцыю, падзяліўшыся хітрасцю, якая сабрала ўсе творы ў маёй галаве.

тл; д-р

У абсалютнай аптымальнай рэалізацыі функцыянальных моў паўторнае ўжыванне выконваецца з царкоўнымі нумарамі, якія прадстаўлены функцыямі з вялікім аб'ёмам унутранага абмену. Напрыклад, 21 прадстаўлены як:

λf1. λx. няхай f2 = f1. f1 няхай f4 = f2. f2, няхай f8 = f4. f4, хай f16 = f8. f8 ў f16 (f4 (f1 x))

Гэты фармат вельмі падобны на "экспанецыя пры дапамозе квадрацікаў", класічны алгарытм, здольны вылічыць экспаненцыю A ^ B у O (log (N)) замест O (N). Гэта само па сабе недастаткова для растлумачэння з'яў; Напрыклад, у Haskell, выкарыстанне гэтай функцыі не дае паскарэнняў. Абсал, праўда, надзвычай прагне (нягледзячы на ​​пакуты, ніякіх запаволенняў для гэтага), што робіць яго здольным вылічыць нармальную форму прамежкавага f. f кампазіцыі, якія па сутнасці выконваюць зліццё падчас выканання. Гэта карысна толькі тады, калі f засцерагаецца, калі самастойна складаецца, інакш рост яго нармальнай формы выкліча экспанентнае запаволенне з-за кошту капіравання ўсё больш вялікіх умоў.

Калі f зліваецца пад самаскладаннем, то абсалют выяўляе эфект "кампазіцыі дзяленнем", які падобны на "экспаненцыя шляхам квадрацыі", за выключэннем функцый і кампазіцый замест цэлых лікаў і множання. Менавіта гэта дазваляе вылічыць N паўторных прыкладанняў f за час O (log (N)). Нарэшце, атрымліваецца копія. inc ператварае inc у функцыю, якая самастойна зліваецца, замяняючы сімвалы, якія назапашваюцца лямбдамі, якія самазнішчаюцца пад самаскладаннем, і таму гэта асімптатычна хутчэй, чым інк.

tl; dr tl; dr

Магія.