программирование и логика

[a_shen]

Полное помеченное двоичное дерево (то есть отображение множества 01-слов в 01, каждому слову, то есть вершине, соответствует метка) может быть задано по-разному:

(1) как программа, которая по слову указывает метку соответствующей вершины

(2) как программа, которая в применении к 0 даёт метку корня, а в применении к 1 и 2 выдаёт текст программ, задающих (в том же смысле) левое и правое поддеревья

От (2) к (1) переход очевиден, надо рекурсивно вызывать интерпретатор - а обратный переход не совсем очевиден (и может быть хорошей задачей по логике для программистов)

Comments

[a-kruglov.livejournal.com]

Я почему-то как прочитал, сразу догадался. Если есть (1), и надо сделать (2), надо к (1) дописать "оболочку", в которой текущий корень был бы задан константой. При обработке входов 1 и 2 -- выводить себя, дописывая 0 или 1 к константе. При обработке 0 -- запускать (1) на константе. Может быть, я чего-то не понял и сложность должна была быть в выводе прогой самой себя. Для языков, где нельзя читать собственный исходник, (включая машину Тьюринга, как мне кажется) это обходится стандартным образом записыванием текста исходника в константу и выводом её фактически дважды. Исходная идея: если обработать слово можно только целиком, а послупает оно по символам, значит его надо сохранять в буфер по мере поступления.

[chaource.livejournal.com]

Функцiональный языкъ программированiя позволитъ перейти отъ 1 къ 2 безъ большихъ проблемъ. Думаю, достаточно, если результатомъ будетъ не текстъ программы, а сама программа какъ функцiя?

[a-shen.livejournal.com]

ну, тогда придётся определять, какого рода математическим объектом является "программа как функция", что создаст множество проблем - так что лучше бы текст...

[deni-ok.livejournal.com]

Лямбда-термом, какие проблемы?

[a-shen.livejournal.com]

я в этом мало понимаю, но если это не текст, то элемент какого множества? тут, боюсь, дело тонкое...

[deni-ok.livejournal.com]

Да, можно смотреть на любую программу или функцию, как на текст. Но в чистых функциональных языках значение любого выражения однозначно определяется этим выражением и только им; поэтому текст "2+2" и текст "4" это одно и то же. То есть текст программы, генерирующей дерево, и <<текст>> самого дерева --- одно и то же.

С точки зрения функционального языка можно сказать, что определение (1) описывает сборку дерева, а (2) --- его разборку. Индукция и коиндукция.

data Tree = Node Bool Tree Tree

prg1 :: ([Bool] -> Bool) -> Tree
prg1 f = prg1' f []
  where prg1' f xs  = Node (f xs) (prg1' f (False:xs)) (prg1' f (True:xs))

prg2 :: Tree -> (Bool,Tree,Tree)
prg2 (Node b l r) = (b, l, r)

[a-shen.livejournal.com]

я в этом совсем не разбираюсь - говоря о тексте, я имел в виду просто последовательность символов, так что в этом смысле "2+2" и "4" это разные тексты. Видимо, они в каком-то смысле эквивалентны, но я не знаю, как это определяется.

[chaource.livejournal.com]

Что же, въ постановку вопроса (2) входитъ задача вывода текста программы въ текстовый файл? На Паскале, или требуется ассемблеръ??

[a-shen.livejournal.com]

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

[a-kruglov.livejournal.com]

Ещё, кроме того, что у программы есть вход и выход, обычно подразумевается, что любую программу можно закодировать в виде, который можно подать на вход или получить с выхода.

[bigturtle.livejournal.com]

Не называется ли это "partial application"?

[bigturtle.livejournal.com]

Теория.

Нужно написать лямбда-выражение, сотсоящее из функцию и поддерева данных. Функция должна возвращать лямбда-выражение в символьном виде. Функция примает два аргумента: дерево данных и 0/1/2 селектор. Дерево данных уже присутвует в лямбда-выражении, то есть имеется partial application: f a b = (f a) b.

Практика:

Лямбда-выражение можно закодировать в самой вульгароной скобочной форме, вроде:
execute (data (data ("a", "b"), 'c"), argument)
Это должно быть завернутов некий интерпретатор, что тоже тривиально.