Ну чтобы не бояться не быть полезным - "программирование в стиле подстановки атомов"
June 18th, 2011
09:19 am

[Link]

Previous Entry Add to Memories Tell A Friend Next Entry
"программирование в стиле подстановки атомов"
Если бы я занялся задачей 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).

Задачу ("программирования в стиле подстановки атомов") можно сформулировать так:

Хотим написать программу T. Надо перевести её в вид: I A1 A2 ... An, где Ai -- одна из данного набора карт (S, K, I и пр.).

Может быть, вовсе и не все программы так можно представить.

Точнее, конечно, так (учитывая, что есть left и right applications of cards and slots):

A6 (... (A3 (I A1 A2...) A4 A5...) ...) A7 A8...

Как задуманную программу перевести в такой вид?


Или посмотреть на задачу построения программы как на задачу поиска вывода в системе с 2*15 правилами вывода (по 2 правила на каждую карту -- то что в условии названо "left" и "right" applications), например:

правило S1: из посылки Φ, хранимой в ячейке, получаем (ΦS)
правило S2: из посылки Φ, хранимой в ячейке, получаем (SΦ)

но этих тривиальных правил не достаточно, работают ещё редукции (собственно применения комбинаторов).

Сумеем ли мы искать вывод (желаемой программы) в такой системе автоматически?.. (например, хорошим свойством было бы, если бы мы могли как-то искать только среди посылок, которые проще)


Ну а вторая часть тогда -- когда мы научились строить желаемые программы в ячейках (а ещё эти программы -- помимо совершения действий как побочных эффектов -- в результате должны были бы давать себя или тоже полезные программы, которые бы записывались после хода в ячейку обратно) -- было бы запрограммировать хорошую "атаку". Ну не знаю, например: attack одну чужую ячейку, потом help той своей ячейке, жизнь которой мы использовали для этого, несколько раз для восстановления её жизни, потом ещё раз attack, в итоге в убитой клетке, возможно, создаём зомби, который тоже что-то подобное плохое будет делать. Тут есть ограничение: не больше 1000 function applications за ход, надо нашу программу уложить в это (так что, ячейку за ячейкой убивать все 256 чужих ячеек в один ход, наверное, не удастся).

А в-третьих, надо придумать, что делать, пока ты строишь свою мощную программу -- тут как раз происходит соревнование с противником: кто быстрее построит свою атакующую программу, несмотря на помехи, создаваемые противником... Про это я не думал.



it's like in natural language


"Программу в стиле подстановки атомов" можно словами описать так:

все скобки вложены друг в друга (т.е. нет скобок ещё где-то).

Ха-ха, на самом деле это же то, как обычно выглядят теории естественного языка -- атомы это heads! (А left/right
branching могут меняться.)


Теперь хотя бы стиль программирования более понятен и близок кажется.

Re: it's like in natural language


Т.е. очередное скармливание карты -- это очередной merge.

Re: it's like in natural language


или не совсем так всё же...

очередной merge -- это только когда мы карту к ячейке применяем.

Re: it's like in natural language


Но в теориях ЕЯ мы обычно можем в качестве значений lexical entries сложные программы придумывать -- какие нам надо. А
здесь совсем в другом месте может находить место наша сочинительская мощность.

Здесь карты фиксированы, и значения у них -- просто S, K, I и пр., а не то, что нам может захотеться для нашей теории
семантики и синтаксиса ЕЯ, чтобы всё работало.

(Хотя в общем-то тут и в теориях ЕЯ должны быть жёсткие ограничения, ведь люди выучивают как-то значения лексических
единиц, так что теоретику не должно быть позволено сколь угодно сложную программу придумать в качестве значения в
теории слова X в языке Y. Но это не то, чтобы большая проблема для современных лингв.теорий сейчас, потому что никто и
не предлагает безумно сложные значения для слов обычно. Просто на нынешней стадии, наверное, лингвисты скорее
исследуют этот простор -- что может быть нужно для теорий разных языков, чем стремятся уже наложить на себя
ограничения, когда ещё никто толком не знает, что может быть нужно (какие инструменты).)





Конечно, необязательно придумывать алгоритм трансформации программ в такой стиль. Можно просто программировать в таком
стиле (но для этого каких-то навыков/понимания возможностей и приёмов хочется)

отложенные побочные действия? (без этой цели мой приме


Пример-то у меня, наверное, дурацкий, как я ожидал: λx(get 0) -- т.е. тут я пытаюсь отложить выполнение (get 0) до
момента, когда я вызову всю эту функцию.

Не знаю, можно ли делать такие отложенные вычисления в этой системе (а это хотелось бы для функций с побочными
действиями, такими, как attack там и т.п.). Изначально она представлена как call-by-value.

В моём дурацком примере в системе без состояния можно было бы сразу подставить значение.

И это реализуется тривиально (в указанном виде):

K (I get 0)

т.е. по ходам (в начале наша ячейка -- обозначим её f[i] -- содержит I):

f[i] <- f[i] get
f[i] <- f[i] 0
f[i] <- K f[i]

Ну что ж, а есть ли смысл пытаться запрограммировать отложенные побочные действия?

комбинатор, откладывающий применение


Для подобного простого примера с отложенным действием нам пригодился бы такой комбинатор:

D' f y x = (f y) -- это как-то неубедительно выглядит

или который бы работал так:

D f y c = c (f y)
т.е. дадим ему в качестве последнего аргумента продолжение I -- получим (f y):
D f y I = I (f y) = f y

при этом я имею в виду что (f y) будет выполнено только на последнем шаге. Можно ли такое сделать?

попытка реализовать похожее передавая f как 2-ой арг. S


Хотим, чтобы S f g x = f x (gx) давало (get 0).

Попробуем построить f такую, что f x = get, а g -- такую, что g x = 0.

Чтобы f x = get можно было бы взять f = K get. (Аналогично g = K 0.)

Тогда всё вместе: S (K get) (K 0) = get 0. Но такой структуры программу мы не можем построить.

Ну что ж, может, это не очень важная цель -- отложенные вычисления и сложная запрограммированная атака?..





Can continuation passing style be a useful skill here?


Возникает сразу желание сравнить эту систему с известными штуками.

Вот по структуре, конечно, программы в указанном виде похожи на программы в continuation passing style.

(Например, пример вроде λc(c(get 0)) в c.p.s. как-то так должен быть:

get' λf(0' λyλc(c(fy)))

-- здесь "атомы" нанизываются слева по одному на соответствующие продолжения (которые мы могли бы на каждом шаге иметь в
ячейке).)

Но полезно ли это нам? Ведь в c.p.s. мы пользуемся уже переведёнными (поднятыми для c.p.s.) "атомами" (в моей
терминологии):

get' = λc(c get)
0' = λc(c 0)

А перед тем, как скормить атом в ячейку, у нас нет средств его поднять...

Tags: ,

(Leave a comment)

My Website Powered by LJ.Rossia.org