[Recent Entries][Archive][Friends][User Info]
| June 18th, 2011 | |
|---|---|
| 09:19 am [Link] |     Если бы я занялся задачей ICFPC ("Lambda. The Gathering"), я бы попробовал двигаться в таком направлении (может, по моим записям кто-то заметит интересное в задаче; я вчера утром некоторое время подумал; правда, участвовать я не собрался, хотя бы потому что одному это не весело): Во-первых, в ячейках мы можем составлять (постепенно) хитрые программы (т.е. программировать с помощью комбинаторов S, K, I, что по выразительности то же, что и программировать с помощью λ -- там в тексте условия задачи даже есть схема перевода из более привычных многим из нас λ-термов в комбинаторы; для нашего удобства можно писать свои задумки в виде λ-термов и давать их автоматическому переводчику; правда, можно захотеть оптимизировать перевод вручную, потому что нас заботит количество function applications, которое ограничено 1000 за 1 ход). (Упражнение: реализовать такой перевод из λ-термов -- скажем, на Lisp-е.) Задуманную программу мы должны будем составлять в ячейке постепенно на протяжении нескольких ходов. (Ведь на одном ходе мы можем скормить туда только одну простую карту из данного набора, а не что-то составленное сложно.) Общий приём составления программы кажется таким: когда за предыдущие ходы мы подготовили в ячейке программу вида (точнее, это у меня запись вида её значения) λx(Φ[x]), то желаемую программу мы получаем подстановкой вместо x какой-то карты A на очередном ходе: Φ[A]. Т.е. сначала в ячейке строится "скелет" задуманной программы, в который мы потом подставляем внутренние части (атомарные, = карты). Например, данное нам начальное состояние ячейки -- I (т.е. λx x) -- это самый верхний уровень программы, в него мы можем подставить специализированный кусочек, а в результате желательно опять получить программу, которая при подаче на вход новых кусочков будет давать программу, служащую для порождения задуманной программы (при подаче всё новых кусочков). В общем, надо продумать схему перевода программы в такой стиль постепенного порождения. (Может быть, тем, кто занимается комбинаторами или реализацией функ.языков программирования, это понятно как делать, но мне пока что не очень.) Попробуем на каком-нибудь простом примере. Хотим построить программу λx(get 0) (это простой пример function application внутри нашей построенной программы; на этом примере я хочу проверить, что мы можем строить function application). Она будет на самом деле (в переводе на язык комбинаторов) иметь вид K (get 0). λx(get 0) = K (get 0) Начнём с конца; допустим, на последнем шаге построения мы подадим 0 -- разложим (λ-abstraction по нужному месту): K (get 0) = λx(K (get x)) 0 λx(K (get x)) -- это значение того, что должно быть в ячейке на предпоследнем шаге построения. Как можно перевести это в комбинаторы, упрощая (т.е. избавляясь от function application внутри, которое мы не умеем делать сами и подавать туда) -- придумываем: λx(K (get x)) = S (K K) get Т.е. на предпоследнем шаге можно было бы хотеть получить S (K K) get. (Как-то это по-дурацки выходит; похоже, мне ничего не удалось! Тут ведь опять внутри сложности -- function application. Но доведу-ка до конца эту наивную попытку.) Это можно было бы получить, подав на предпоследнем шаге get -- раскладываем: S (K K) get = λx(S (K K) x) get λx(S (K K) x) = S (K K) (S (K K)) В общем, ничего хорошего не вышло, потому что такую сложную штуку тоже надо уметь строить. (Но я пока что не очень и старался придумывать упрощающие приёмы, обратные направлению построения программы -- написал первый попавшийся перевод с использованием S (K K), который оказался-таки не упрощающим.) Нужно придумать более основательный подход к этой задаче. Может, взгляд на всё как на композицию функций пригодится -- ведь явно ссылаться на аргумент с помощью связанной переменной мы в этом языке не можем, т.е. надо программировать в variable-free стиле (point-free, function-level, concatenative programming). Задачу ("программирования в стиле подстановки атомов") можно сформулировать так: Или посмотреть на задачу построения программы как на задачу поиска вывода в системе с 2*15 правилами вывода (по 2 правила на каждую карту -- то что в условии названо "left" и "right" applications), например: правило S1: из посылки Φ, хранимой в ячейке, получаем (ΦS) правило S2: из посылки Φ, хранимой в ячейке, получаем (SΦ) но этих тривиальных правил не достаточно, работают ещё редукции (собственно применения комбинаторов). Сумеем ли мы искать вывод (желаемой программы) в такой системе автоматически?.. (например, хорошим свойством было бы, если бы мы могли как-то искать только среди посылок, которые проще) Ну а вторая часть тогда -- когда мы научились строить желаемые программы в ячейках (а ещё эти программы -- помимо совершения действий как побочных эффектов -- в результате должны были бы давать себя или тоже полезные программы, которые бы записывались после хода в ячейку обратно) -- было бы запрограммировать хорошую "атаку". Ну не знаю, например: attack одну чужую ячейку, потом help той своей ячейке, жизнь которой мы использовали для этого, несколько раз для восстановления её жизни, потом ещё раз attack, в итоге в убитой клетке, возможно, создаём зомби, который тоже что-то подобное плохое будет делать. Тут есть ограничение: не больше 1000 function applications за ход, надо нашу программу уложить в это (так что, ячейку за ячейкой убивать все 256 чужих ячеек в один ход, наверное, не удастся). А в-третьих, надо придумать, что делать, пока ты строишь свою мощную программу -- тут как раз происходит соревнование с противником: кто быстрее построит свою атакующую программу, несмотря на помехи, создаваемые противником... Про это я не думал.
|