Форум: Проблемы искусственного интеллекта

Регистрация | Вход

Все темы | Новая тема  Стр.1 (2) След. > >>    Поиск:
Автор	Тема: Абстрактная интерпретация
NO. Сообщений: 10700	Абстрактная интерпретация Добавлено: 17 июл 09 5:22 В процедурных языках функции описываются через функции, а при выполнении программы используется стек, в котором хранится путь по этому дереву. Стек делится на фреймы, содержащие уже вычисленные данные. И в некоторых языках заявки на еще не вычисленные значения. В Sсheme стек можно сохранить в специальный тип данных continuation, хрянящий частично вычисленную функцию, которую можно вызывать с другими параметрами. При "ленивом" вычислении дерево хранится явно, а вместо вызова функции в дерево добавляется сама процедура. Потом дерево можно оптимизировать и выполнить "энергично". Например f(x,y) = g(x)+h(x,y) При вычислении a=f(1,2)+f(1,3) энергичное вычисление считает g(1) два раза, ленивое только 1 раз. Теперь, по определению f можно автоматически получить "теоремы" вроде если h(x,y)>0 то f(x,y)>g(x), и вместо вычисления выполнять абстрактную интерпретацию, например сразу получать a=(>g(1)). Если этого факта не хватит для дальнейшей работы то следует использовать другие теоремы или в конце концов вычислить само значение. Таким образом вместо каждого вызова и получения значения получается целая цепочка признаков, а вместо стека будет стек стеков. Для простых вычислений над целыми числами во всем этом нет необходимости т.к. дешевле просто запустить и посчитать. А например если функции это сложные запросы к базе данных хранящейся на другом компьютере, то значительно дешевле будет сначала "подумать". Или когда вместо вычисления у нас рассуждение, каждая функция это килобайтное выражение и энергичным не оптимизированным вычислением мы скорее всего даже не доберемся поинтересоваться последними утверждениями определения. То есть это способ оптимизации алгоритмов. Дополнительно можно мемоизировать функции. Можно этот кеш результататов еще раз анализировать и строить признаки уже и данных, а не только функций. Можно запоминать откуда функцию вызывали и какой ответ в конце концов устроил вызвающего. Получается такое интеллектуальное выполнение, развитие managed из .NET Соответственно программирование под такое вычисление будет другое. Программа обычно останавливается когда дойдет до конца или когда выдает ошибку. Сдесь эти случаи одинаковы и не критичны. При программировании мы уже не строим программу, а настраиваем отладчик. Он будет перехватывать такие события и давать следующую инструкцию или другой вариант вычислений. Программа будет просто инструкцией "поехали", при попытке ее выполнения начнут возникать вопросы и проблемы, а программа-база-знаний будет отвечать. [Ответ][Цитата]
shuklin Сообщений: 2053	На: Абстрактная интерпретация Добавлено: 17 июл 09 11:09 какие приемущества, кроме экономии числа строк и часов человка, дает этот подход по сравнению с программированием, скажем, на ASM? [Ответ][Цитата]
NO. Сообщений: 10700	На: Абстрактная интерпретация Добавлено: 17 июл 09 12:21 Вполне можно использовать ассемблер и вместо html. А кроликов резать в ванной. Может быть Айседора Дункан так и делает. Но я - не Айседора Дункан. Тут про оптимизацию, ей занимается сама система. А оптимизировать предполагается знания, они обычно представляют из себя страшную свалку. [Ответ][Цитата]
shuklin Сообщений: 2053	На: Абстрактная интерпретация Добавлено: 17 июл 09 15:59 Цитата: Автор: NO. Тут про оптимизацию, ей занимается сама система. А оптимизировать предполагается знания, они обычно представляют из себя страшную свалку. тогда может начать с модели представления этих знаний? если это знания, а не очередной новый ЯП для ИИ. [Ответ][Цитата]
daner Сообщений: 4593	На: Абстрактная интерпретация Добавлено: 17 июл 09 16:02 Ну... вообще-то относительно процедурного программирования -- это не правильно. Это верно относительно функционального программирования. Или я что-то не совсем правильно понял, то о чем вы написали. В процедурном программировании, НЕЛЬЗЯ не вычислять функцию, так как ее значение зависит не только от ее параметров, но и от состояния системы в целом и кстати состояние системы может зависит от вызова. если скажем есть функция add(pointer_to_queue_of_ints, int_element)->index_of_new_element_in_the_queue , то последовательные вызовы add(A,1); add(A,1); add(A,1); add(A,1); ВСЕ вернут разные значения. Тоже будет и если функция обращается к глобальным переменным, файлам и т.д. Вот в функциональном программирование, это совсем другое дело. Но опять таки, если мы будем говорить об удаленной BD, то я лично не очень представляю себе, как функциональный язык, может работать с этой самой BD, при этом не нарушая чистоты функциональной парадигмы. Просто интересно, как с этим например Haskell справляется? Может кто знает? Но по любому... для функ.языков такой анализ где-нибудь (о задачах можно подумать...) наверняка был бы очень даже полезен. Своего рода pruning дерева вычислений и/или своеобразная аналитическая добавка к динамическому программированию. [Ответ][Цитата]
NO. Сообщений: 10700	На: Абстрактная интерпретация Добавлено: 17 июл 09 16:36 Процедурную программу тоже можно интерпретировать. Глобальные переменные не являются параметрами функций только синтаксически, чтобы не таскать указатели на статику и кучу, тем более они в памяти никуда и не двигаются. В хаскеле вроде бы управление идет снизу, декларациями описываются все возможные параллельные миры, а реален только один, он себя идентифицирует и отслеживает. [Ответ][Цитата]
NO. Сообщений: 10700	На: Абстрактная интерпретация Добавлено: 17 июл 09 16:43 Собственно идея была заменить в лиспе символы путями по какому-то дереву символов. Тогда обрезанный путь обозначает какое-то обобщение. Это как бы старшие биты числа, для некоторых вычислений быват достаточно знать вообще только знак. У чисел один приоритет старшинства бит, а про выражения может быть множество точек зрения как их классифицировать и множество путей-кодов. Получается множество обобщений, намного больше работы, но ее теперь можно оптимизировать, я думаю в итоге станет меньше. [Ответ][Цитата]
daner Сообщений: 4593	На: Абстрактная интерпретация Добавлено: 17 июл 09 17:05 Цитата: Автор: NO. Процедурную программу тоже можно интерпретировать. Глобальные переменные не являются параметрами функций только синтаксически, чтобы не таскать указатели на статику и кучу, тем более они в памяти никуда и не двигаются. В хаскеле вроде бы управление идет снизу, декларациями описываются все возможные параллельные миры, а реален только один, он себя идентифицирует и отслеживает. Ждал такого ответа. Но вообще-то в стеке они по любому не хранятся, так что в выше описанном виде уже не верно. Но дело даже не в них. А как на счет файлов? их тоже в стек? А сеть? А систему ввода? Это все тоже в стек? про хаскель не совсем понял. перефразировать/объяснить подробнее можете? Только просьба: если сами уверенны. если нет, то лучше уже в док.ах почитать. [Ответ][Цитата]
lfa Сообщений: 10	На: Абстрактная интерпретация Добавлено: 17 июл 09 20:37 Цитата: Автор: daner ...А как на счет файлов? их тоже в стек? А сеть? А систему ввода? Это все тоже в стек? Простите, а КОМУ и КОГДА всё #это# может понадобиться?!! (ну прям какая-то назойливая виртуализация по типу модных ныне в серверных применниях... ) [Ответ][Цитата]
NO. Сообщений: 10700	На: Абстрактная интерпретация Добавлено: 18 июл 09 4:51 про монады лучше почитать Я вообще рассуждаю об оптимизации кода, типа вместо a*b+a*c считать только a*(b+c). Это НЕ выполнение программы. Предполагается что есть и код и есть интерпретатор, все в исходниках. Просто специфика такова что изучение этих данных напоминает их выполнение. Но нужно как раз НЕ выполняя программу определить свойства результата. В конце наверно будет что если мы пришли к тому, что программу таки придется выполнить чтобы что-то про нее понять, значит она зависающая. И еще раз, это знания, а не обязательно программы, хотя "в общем виде" их использование это выполнение т.к. алгоритмы тоже знания. [Ответ][Цитата]
NO. Сообщений: 10700	На: Абстрактная интерпретация Добавлено: 18 июл 09 6:57 В параллельном программировании кто-нибудь разбирается? Среди абстракций очень важны про зависимость-независимость. Независимость как процесс моделируется параллельностью. Например в конечном автомате машины Тьюринга на каждой развилке может быть указано с которой ленты брать символ. Хотя и эта инфрмация тоже может получаться с третьей ленты, возможно из живущего на ней автомата. Три ленты необходимы, если не ограничивать ни сложность объектов ни зависимость между ними. Есть еще сети Петри, недетерминированные автоматы, мю-исчисление. Недетерминированный вместо ленты живет на дереве. Мю это алгебра, должно быть самая мощная из этих. Еще любопытно если МТ-автомат будет ползать не по ленте, а по графу другого МТ-автомата. Два таких могли бы редактировать связи. А новые вершины можно получать разделением существующей на последовательные или параллельные, я в explain так делал. При разделении на параллельные может выполняться и fork автомата, будет недетерминированный мета-автомат. Селекция вариантов в нем может обучать подчиненный граф-автомат. Паразиты какие-то, баги ползучие. [Ответ][Цитата]
3d6 Сообщений: 325	На: Абстрактная интерпретация Добавлено: 18 июл 09 10:33 Присоединюсь к вопросу Ктулху - для чего это все? Для какой категории задач? Потому как я, как мне кажется, вовсе не пишу программ, где подобное может пригодиться. Мне нужно сделать определенные операции над входными данными (в которых никаких существенных повторений нет, а если где и есть - это уже давно использовано в логике программы) и сказать, в каком они сейчас состоянии. Есть ли тут место такому языку? Даст ли он выигрыш по времени? [Ответ][Цитата]
NO. Сообщений: 10700	На: Абстрактная интерпретация Добавлено: 18 июл 09 11:31 Это для экспертных систем и баз знаний. Там нужно всего пару шагов "вычислений" сделать зато формулы и данные по мегабайту. Да и в обычных БД всегда есть оптимизатор запросов и его устройство очень сильно и часто непредсказуемо влияет на время выполнения запроса. Опять же это не для примеров из "sql за пять минут" и не для бухгалтерии, а про серьезные базы из сотен и тысяч таблиц. Только в отличие от БД в базе знаний значительная часть в виде выражений, типа вычислимых полей, логически каждое такое отдельная таблица свернутая в формулу. В хорошей базе знаний таких десятки-сотни тысяч. Вот и получается, небольшой запрос сначала понимается, что превращает его в мегабайты смысла, потом этот смысл служит запросом в базу. Даже если там все значения по 1 биту, миллион условий это фильтр к базе в 2^миллион записей. Представляете что такое 2^32? Представьте 2^1000000. Оно не решается ни перебором ни даже индексами. А если все-таки как-то посчиталось, то по сравнению с этой бесконечностью выигрыш почти такой же, например в 2^999990 раз если считало целые сутки. В бухгалтерии таксопарка номер три г.Бобруйс этому языку не место. И мне не место и даже Айседоре Дункан. [Ответ][Цитата]
shuklin Сообщений: 2053	На: Абстрактная интерпретация Добавлено: 18 июл 09 12:46 Цитата: Автор: NO. Я вообще рассуждаю об оптимизации кода ... Ершов, Теоретическое программирование. [Ответ][Цитата]
NO. Сообщений: 10700	На: Абстрактная интерпретация Добавлено: 18 июл 09 13:48 Ершова не нашел, а рукописное не распознаецца [Ответ][Цитата]
Стр.1 (2): [1]  2 След. > >>