Самоприменимость или Three Futamura Projections
Не, ну просто все шутят о всяких самоприменимостях и надстройках, но все-таки немного не дотягивают до нужного уровня мозговскрыва. Просто вчера перед отходом ко сну вспоминали с товарищем эту статейку, вот, решил поделиться с общественностью 
Фигня там написана. Засунуть интерпретируемый код в ресурсы программы-интерпретатора - это не значит написать компилятор.
никто не предлагает так писать компилятор =]
скажите, PHP таки порвало Java ?
Точно не знаю, но вот Development — замечательный раздел 
какой-нибудь язык умеет записывать в декларативном виде частичные вычисления?
например, что:
items.OrderBy(f).Take(k) == items.Min(k, f)
например, что:
items.OrderBy(f).Take(k) == items.Min(k, f)
С++ (boost::bind)
С++ (boost::bind)приведи, пожалуйста, примерчик.
зы
помню, что в boost-е можно было записать только какие-то простые варианты.
ну смотря в каком смысле частичные. Если как связь функции и переменной - то хаскель справляется нативно, python через funtools.partial. Но ни тот, ни другой не делает полной оптимизации как описано в статье, например не выкидывает пустые ветвления кода и прочее. Хотя часть оптимизаций в хаскеле возможно есть, но только как часть более общих оптимизаций, присущих функциональным языкам.
Если как связь функции и переменной - то хаскель справляется нативно, python через funtools.partialно запись в них императивная, а не декларативная.
или я ошибаюсь?
но запись в них императивная, а не декларативная.поясни, что ты имел в виду?
или я ошибаюсь?
хаскел:
plusone = (+1)
питон:
plusone = functools.partial(int.__add__,1)
из твоих примеров не понял как записать мой вариант, поэтому мне сложно будет продемонстрировать отличия декларации от императива
можешь расшифровать словами что делает твой пример. А то я не вполне понял
можешь расшифровать словами что делает твой пример. А то я не вполне понялон говорит, что взять первых k элементов от коллекции items, отсортированной по критерию f - это тоже самое, что взять k минимальных(по критерию f) элементов из коллекции items
то есть позволяет сравнивать функции? Как ты это себе представляешь (функции одинаковы если на любом наборе входных данных дают одинаковый результат? Эта задача алгоритмически не разрешима, вряд ли какой компилятор сможет помочь.
Хаскель скажет, что не может сравнивать функции, потому что они не являются членами класса Eq, и для них не реализован оператор (==)
Питон просто сравнит указатели (для питона все объекты сравниваются одинаково - по указателям)
Хаскель скажет, что не может сравнивать функции, потому что они не являются членами класса Eq, и для них не реализован оператор (==)
Питон просто сравнит указатели (для питона все объекты сравниваются одинаково - по указателям)
то есть позволяет сравнивать функции?позволяет записывать, что вот такая-то последовательность вызовов равна вот такой более простой.
хаскель ровно это и делает.
Питон - нет. Просто создаёт новую функцию, которая получена из старой частичным применением аргументов. Таким образом новая функция равна старой, а старая не равна новой, она про неё ничего не знает.
У хаскеля полное равноправие. Потом можешь посмотреть как там определён класс Eq.
Программист должен определить либо оператор (==) либо оператор (/=) либо оба. В первых двух случаях хаскель доопределит всё необходимое сам. Потому что у него записано (==) = not (/=)
Питон - нет. Просто создаёт новую функцию, которая получена из старой частичным применением аргументов. Таким образом новая функция равна старой, а старая не равна новой, она про неё ничего не знает.
У хаскеля полное равноправие. Потом можешь посмотреть как там определён класс Eq.
Программист должен определить либо оператор (==) либо оператор (/=) либо оба. В первых двух случаях хаскель доопределит всё необходимое сам. Потому что у него записано (==) = not (/=)
похоже, это не то что я хочу, то что ты говоришь можно и в C записать, только толку с этого будет 0.
В GHC есть прагма RULES, она позволяет такие замены делать.
http://www.haskell.org/ghc/docs/6.12.1/html/users_guide/rewr...
http://www.haskell.org/ghc/docs/6.12.1/html/users_guide/rewr...
Хаскель скажет, что не может сравнивать функции, потому что они не являются членами класса Eq, и для них не реализован оператор (==)
instance (Eq b, Num a) => Eq (a -> b) where
f == g = let sample h = map (h . fromInteger) [1, 2 .. 10] in sample f == sample g
В GHC есть прагма RULES, она позволяет такие замены делать.спасибо, близко, но не то.
это запись в императивном виде.
спасибо, близко, но не то.Что ьы понимаешь под "императивным видом"?
это запись в императивном виде.
Что ьы понимаешь под "императивным видом"?в данном случае, насколько я понимаю - эти правила применяются жадным образом одно за другим.
соответственно, применить, например, другую стратегию наложения правил будет проблематично.
или, например, задать вопрос - какие из уже записанных правил противоречат друг другу?
в данном случае, насколько я понимаю - эти правила применяются жадным образом одно за другим.Понял. Да, там ограниченные средства контроля их применения.
соответственно, применить, например, другую стратегию наложения правил будет проблематично.
или, например, задать вопрос - какие из уже записанных правил противоречат друг другу?
У тебя настолько ограниченый кругозор, что ты не можешь толком
объяснить, что же ты хочешь. Тебя трудно понять.
Насколько я понял, ты хочешь записывать правила упрощения
(в общем случае --- преобразования) функций общего вида.
Да, такие языки есть.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
объяснить, что же ты хочешь. Тебя трудно понять.
Насколько я понял, ты хочешь записывать правила упрощения
(в общем случае --- преобразования) функций общего вида.
Да, такие языки есть.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
f == g = let sample h = map (h . fromInteger) [1, 2 .. 10] in sample f == sample gфизик?
>> f == g = let sample h = map (h . fromInteger) [1, 2 .. 10] in sample f == sample g
> физик?
А в чём, собственно, проблема?
Или ты хочешь сказать, что это не является отношением эквивалентности?
---
...Я работаю антинаучным аферистом...
> физик?
А в чём, собственно, проблема?
Или ты хочешь сказать, что это не является отношением эквивалентности?
---
...Я работаю антинаучным аферистом...
отношения эквивалентности можно задавать произвольно, только вот наличие здравого смысла за этими определениями тоже необходимо, иначе мы получим нечто пусть и существующее, но бессмысленное.
А физик при том, что я вспомнил анекдот про делителей числа 60.
А физик при том, что я вспомнил анекдот про делителей числа 60.
> отношения эквивалентности можно задавать произвольно,
> только вот наличие здравого смысла за этими определениями тоже необходимо,
> иначе мы получим нечто пусть и существующее, но бессмысленное.
Ты согласен с тем, что в программировании мы работаем с конструктивными объектами?
---
...Я работаю антинаучным аферистом...
> только вот наличие здравого смысла за этими определениями тоже необходимо,
> иначе мы получим нечто пусть и существующее, но бессмысленное.
Ты согласен с тем, что в программировании мы работаем с конструктивными объектами?
---
...Я работаю антинаучным аферистом...
Ты согласен с тем, что в программировании мы работаем с конструктивными объектами?и что? Даже если забыть о математики и смотреть только с точки зрения программиста подобная операция сравнения бессмысленна в силу своей исключительно узкой применимости (многочлены степени не выше 9)
Да, такие языки есть.какие, например?
>> Ты согласен с тем, что в программировании мы работаем с
>> конструктивными объектами?
> и что? Даже если забыть о математики и смотреть только с точки
> зрения программиста подобная операция сравнения бессмысленна в
> силу своей исключительно узкой применимости (многочлены
> степени не выше 9)
Математики не могут мыслить дальше одного шага?
Или ты считаешь, что раз операция сравнения может быть дорогой,
то её и быть не может?
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
>> конструктивными объектами?
> и что? Даже если забыть о математики и смотреть только с точки
> зрения программиста подобная операция сравнения бессмысленна в
> силу своей исключительно узкой применимости (многочлены
> степени не выше 9)
Математики не могут мыслить дальше одного шага?
Или ты считаешь, что раз операция сравнения может быть дорогой,
то её и быть не может?
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
> какие, например?
А что толку тебе отвечать, если ты опять придумаешь что-нибудь
в роде "то да не то?"
Этими вещами занимаются в системах доказательства теорем.
Ты даже классической логики не осилил, а там всё ещё сложнее.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
А что толку тебе отвечать, если ты опять придумаешь что-нибудь
в роде "то да не то?"
Этими вещами занимаются в системах доказательства теорем.
Ты даже классической логики не осилил, а там всё ещё сложнее.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
Или ты считаешь, что раз операция сравнения может быть дорогой,тебе бы следовало знать, что бывают не просто дорогие операции, а алгоритмически неразрешимые.
то её и быть не может?
тебе бы следовало знать, что бывают не просто дорогие операции, а алгоритмически неразрешимые.вообще-то, в понятии алгоритмическая неразрешимость заложена жаба. Вот, к примеру, то же сравнение двух алгоритмов — да, задача алгоритмически неразрешимая. Однако, если мы ограничиваем длину алгоритмов (например, гигабайтом то оказывается, что задачу можно решить алгоритмически.
Соответственно, вполне можно написать практически применимую систему, которая будет работать в 95% случаях (правильно выдавать ответ а на остальные 5% просить помочь человека.
Однако, если мы ограничиваем длину алгоритмов (например, гигабайтом то оказывается, что задачу можно решить алгоритмически.ну это правда. Тогда можно ещё вспомнить про NP-полноту и практическую неразрешимость задачи для модели Неймана.
Тут же можно вспомнить, что кучу np-полных задач можно решать быстро, но не полно. В нашем случае — будет хорошо работать набор эвристик, особенно, если их получится вывести автоматически из большого количества алгоритмов, про которые заранее известно, что они эквивалентны.
> тебе бы следовало знать, что бывают не просто дорогие операции,
> а алгоритмически неразрешимые.
Есть такой неочевидный факт, что множество целых чисел конечно.
---
...Я работаю антинаучным аферистом...
> а алгоритмически неразрешимые.
Есть такой неочевидный факт, что множество целых чисел конечно.
---
...Я работаю антинаучным аферистом...
ну как бы да. Продвинутые эвристики, банк алгоритмов ( в каком-то обобщённо-деревянном виде) и так далее. В общем это проект на долгое развитие и серебряной пулей не является. И вообще проект долгосрочный получается. А первая часть сейчас худо-бедно развивается вместе с прочими инструментами автоматической верификации программ.
Кстати вторую часть (банк алгоритмов) хорошо набирать, если 1) создать язык с хинтами, либо дополнить хинтами какой-нибудь диалект имеющихся языков, того же питона например 2) сделать web-ide для сабжа 3) автоматически извлекать из юзверских программ пополнение для своего дерева алгоритмов.
Кстати вторую часть (банк алгоритмов) хорошо набирать, если 1) создать язык с хинтами, либо дополнить хинтами какой-нибудь диалект имеющихся языков, того же питона например 2) сделать web-ide для сабжа 3) автоматически извлекать из юзверских программ пополнение для своего дерева алгоритмов.
Есть такой неочевидный факт, что множество целых чисел конечно.а я думал, что счётно.
>> Есть такой неочевидный факт, что множество целых чисел конечно.
> а я думал, что счётно.
Мы не в "Study."
Кроме того, если очень хочется, то есть чем заморочиться.
---
...Я работаю антинаучным аферистом...
> а я думал, что счётно.
Мы не в "Study."
Кроме того, если очень хочется, то есть чем заморочиться.
---
...Я работаю антинаучным аферистом...
2) сделать web-ide для сабжа 3) автоматически извлекать из юзверских программ пополнение для своего дерева алгоритмов.чем тексты open-source программ, доступные в инете не подходят? т.е. чем тексты внутри этой ide будут лучше?
тем что их там больше будет.
тем что их там больше будет.спорно. Потому что секретные проекты в web ide писать не станут, да и пока ею начнут активно пользоваться, пройдут годы.
А индекс open source существует уже сейчас.
множество целых чисел конечно.
Про разницу Int и Integer в хаскеле слышал? Число последних, конечно, тоже ограничено, но перебрать до конца вселенной не успеешь.
Для таких как ты приведена ссылка на немонотонную логику.
---
"I have a clock on my office wall that runs backwards.
It forces visitors to think. They hate me for that."
---
"I have a clock on my office wall that runs backwards.
It forces visitors to think. They hate me for that."
Однако, если мы ограничиваем длину алгоритмов (например, гигабайтом то оказывается, что задачу можно решить алгоритмически.Либо ты подразумевал длину трассы или объём памяти, либо ты не прав и ограничив длину записи самого алгоритма мы ничего не добьёмся.
ограничив длину записи самого алгоритма мы ничего не добьёмся.количество алгоритмов конечной длины — конечно. Соответственно, существует алгоритм в виде большой такой булевой таблицы, который отвечает, эквивалентны ли два алгоритма.
количество алгоритмов конечной длины — конечно. Соответственно, существует алгоритм в виде большой такой булевой таблицы, который отвечает, эквивалентны ли два алгоритма.А как ты собираешься заполнять эту таблицу?
А как ты собираешься заполнять эту таблицу?true - если алгоритмы эквивалентны
false - если нет
или ты имеешь ввиду, что мое доказательство неконструктивно (т.е. мы знаем, что алгоритм существует, но написать мы с тобой не знаем как?) ну дак и пофиг. Вопрос алгоритмической разрешимости/неразрешимости тем не менее мы выяснили.
> (т.е. мы знаем, что алгоритм существует, но написать мы с тобой не знаем как?)
Если для области определения существует нумерация, а она существует,
то она, как правило, разумна. Если величины из области значений можно
сравнивать, что является разумным допущением, то мы имеем алгоритм
сравнения функций. Это и есть то, что хотел сказать .
---
"Математик может говорить, что ему хочется,
но физик должен, хотя бы в какой-то мере, быть в здравом рассудке."
Если для области определения существует нумерация, а она существует,
то она, как правило, разумна. Если величины из области значений можно
сравнивать, что является разумным допущением, то мы имеем алгоритм
сравнения функций. Это и есть то, что хотел сказать .
---
"Математик может говорить, что ему хочется,
но физик должен, хотя бы в какой-то мере, быть в здравом рассудке."
немонотонную логику.И как она поможет в решении данной задачи? Позволит быстро дать неправильный ответ?
> или ты имеешь ввиду, что мое доказательство неконструктивно (т.е. мы знаем, что алгоритм существует, но написать мы с тобой не знаем как?)
У тебя нет доказательства. А при попытке его всё-таки написать ты мгновенно наткнёшься на halting problem. Потому что проблема эквивалентности алгоритмов тоже неразрешима. Причём Гёделевское утверждение для любого вменяемого языка значительно меньше гигабайта, например.
Вообще фраза про гигабайт смешная — ты в курсе, что для приблизительно тридцати машин Тьюринга с пятью состояниями и двоичным алфавитом проблема остановки не решена? Тыц! Так вот, машина Тьюринга с пятью состояниями и двоичным алфавитом описывается приблизительно тремя байтами. Какие гигабайты, ты что.
У тебя нет доказательства. А при попытке его всё-таки написать ты мгновенно наткнёшься на halting problem. Потому что проблема эквивалентности алгоритмов тоже неразрешима. Причём Гёделевское утверждение для любого вменяемого языка значительно меньше гигабайта, например.
Вообще фраза про гигабайт смешная — ты в курсе, что для приблизительно тридцати машин Тьюринга с пятью состояниями и двоичным алфавитом проблема остановки не решена? Тыц! Так вот, машина Тьюринга с пятью состояниями и двоичным алфавитом описывается приблизительно тремя байтами. Какие гигабайты, ты что.
У тебя нет доказательства.Ну я с такими заявами могу смело говорить: есть и отсылать к предыдущему сообщению.
Потому что ты его прочитал не включая мозг, извини. Если там не понятно, могу еще раз объяснить специально для тебя.
Даже по ссылке есть то, что я в этом треде говорю:
Although there is no single algorithm A that outputs the number Σ(n) for each input n (i.e., the function Σ is not computable there is, for each input n, an algorithm An that outputs the number Σ(n)Собственно, это означает, что действительно просто не прочитал мое сообщение, а среагировал по ключевым словам.
Извини, действительно читал невнимательно.
Ок, тогда у меня претензии только к
Конечно, можно за "100%" брать не количество всех алгоритмов, а только тех, которые мы встретим на практике, но всё равно, заранее понятно, что определять даже хотя бы определённость каждого на всех входных данных будет очень непросто.
Ок, тогда у меня претензии только к
Соответственно, вполне можно написать практически применимую систему, которая будет работать в 95% случаях (правильно выдавать ответ а на остальные 5% просить помочь человека."Ну вот из 1200 возможных МТ с пятью состояниями и бинарным алфавитом в 40 (а не тридцати) случаях даже "попросить помочь человека" не работает. Это 3.3%. В случае шести состояний всё ещё гораздо хуже, потому что например текущий победитель останавливается за ~2.6e2879 шагов, то есть даже проверить непосредственно, что он действительно останавливается, мы не можем.
Конечно, можно за "100%" брать не количество всех алгоритмов, а только тех, которые мы встретим на практике, но всё равно, заранее понятно, что определять даже хотя бы определённость каждого на всех входных данных будет очень непросто.
Я готов заменить слово 95%, на "наверное, довольно большую часть практически значимых алгоритмов". Поскольку, с одной стороны, есть сложные случаи, с другой — на практике я встречался с проблемами такого рода только в специальных случаях, типа обфусцированных программ.
Например, небезызвестный на ВМК Чернов в своей проге-обфускаторе (C, Java, Verilog) делает эквивалентные замены (несколько классов). Причем, даже если пишем алгоритм для конкретного класса замен, оказывается, что задача NP-трудная (или NP-полная — ща уже не помню).
А вот в текстах, которые пройдут code review в каком-нить проекте типа Chromium (проекте, где работают сотни людей и следят за тем, чтобы непонятного кода было поменьше разберется и не очень продвинутый алгоритм. В малом количестве случаев можно просить человека о помощи и он поможет, ведь текст понятен.
Например, небезызвестный на ВМК Чернов в своей проге-обфускаторе (C, Java, Verilog) делает эквивалентные замены (несколько классов). Причем, даже если пишем алгоритм для конкретного класса замен, оказывается, что задача NP-трудная (или NP-полная — ща уже не помню).
А вот в текстах, которые пройдут code review в каком-нить проекте типа Chromium (проекте, где работают сотни людей и следят за тем, чтобы непонятного кода было поменьше разберется и не очень продвинутый алгоритм. В малом количестве случаев можно просить человека о помощи и он поможет, ведь текст понятен.
нате вам неплохое введение в тему
http://metacomputation-ru.blogspot.com/
чтобы вы глупостей тут не писали
http://metacomputation-ru.blogspot.com/
чтобы вы глупостей тут не писали
Оставить комментарий
Serab
Ладно, это все-таки development, а не h&s, так что пусть это будет здесь: http://habrahabr.ru/blogs/crazydev/47418/