Автор | Сообщение |
bokunopico![]()
54 сообщений |
#4082 2011-03-27 20:11 GMT+3 часа(ов) |
Подскажите, пожалуйста, как будет выглядеть следующая конструкция на Racket с использованием racklog:
любит(саша, аниме). любит(саша, racket). любит(маша, X) :- любит(саша, X). С предикатами я вроде разобрался, получилось:
А вот правило никак не получается оформить в коде, поэтому просьба помочь. Заранее спасибо за помощь. |
|
misha![]()
1275 сообщений |
#4087 2011-03-27 23:39 GMT+3 часа(ов) |
#lang datalog #lang racket |
|
bokunopico![]()
54 сообщений |
#4089 2011-03-28 00:34 GMT+3 часа(ов) |
misha, огромное Вам спасибо. Я смотрел описание модуля по первым главам, оказалось, что надо было заглянуть и в "Glossary of Racklog Primitives". Наверное, без Вашей помощи так бы и не догадался.
А можно ещё задать Вам пару вопросов:
В результате:
Собственно вопрос: достаточно ли "грамотно" написана функция fun, преобразующая полученную конструкцию в "обыкновенный" список? И совсем глупый вопрос: как Вы меняете раскладку в Racket 5.1? Потому что, перейдя с версии 5.0.3, я обнаружил, что такая возможность куда-то улетучилась. :-( |
|
misha![]()
1275 сообщений |
#4093 2011-03-28 02:22 GMT+3 часа(ов) |
> достаточно ли "грамотно" написана функция fun, преобразующая полученную конструкцию в "обыкновенный" список?
Две ветки if нужно сократить в одну: (if (or (null? arg) (not (car arg))) ...)Еще необходимо учитывать структуру списка возвращаемого %find-all. Как Вы думаете зачем дополнительные скобки '((what . anime))? > И совсем глупый вопрос: как Вы меняете раскладку в Racket 5.1? Потому что, перейдя с версии 5.0.3, я обнаружил, что такая возможность куда-то улетучилась. :-( Попробуйте изменить шрифт в настройках пользователя. Возможно, установленный по умолчанию, либо выбранный Вами ранее шрифт не поддерживает кириллицу. Я бы Ваш код переписал так: #lang racketЗачем создаю собственное исключение, надеюсь, Вам понятно? Обратите внимание, я использую (exn-continuation-marks e) вместо (current-continuation-marks)! Это необходимо для того, чтобы выявить источник возникновения перехваченного исключения. отредактировал(а) misha: 2011-03-28 02:35 GMT+3 часа(ов) |
|
bokunopico![]()
54 сообщений |
#4094 2011-03-28 02:59 GMT+3 часа(ов) |
Ещё раз спасибо за ответ и потраченное на меня время. Как Вы элегантно включили в такой маленький код столько новых и интересных особенностей (или возможностей, не знаю, как лучше выразиться) - не передать словами! Может, для Вас всё элементарно, но у меня появился повод в них разобраться. :-)
> Еще необходимо учитывать структуру списка возвращаемого %find-all. Как Вы думаете зачем дополнительные скобки '((what . anime))? В приципе, догадываюсь. Могут быть дополнительные пары "переменная-значение", если моя терминология уместна. Например:
Но я не планирую учитывать такие сложности в текущий момент. > Зачем создаю собственное исключение, надеюсь, Вам понятно? Честно говоря, нет, даже сама природа исключений мне не ясна. Но это уже мои проблемы и думаю, что если внимательно(!) прочитаю соответствующий раздел в документации, то разберусь с данным вопросом. Ещё раз хочу поблагодарить за оказанную помощь. |
|
bokunopico![]()
54 сообщений |
#4113 2011-04-01 20:06 GMT+3 часа(ов) |
Здравствуйте. Опять я со своими проблемами по тому же самому модулю. Подскажите, пожалуйста, как будет выглядеть отрицание правила в Racklog?
Я глупо понадеялся, что %not является особой формой, как %and и %or. Оказалось, что он содержит в своём определении cut (!), который не получается перехитрить. В моём примере, наверное, (%repeat) надо использовать, чтобы добиться нужного результата? В общем, просьба помочь. |
|
misha![]()
1275 сообщений |
#4114 2011-04-01 21:41 GMT+3 часа(ов) |
%not возвращает либо %true, либо %false. Поэтому простейший выход без перебора всех фактов:
(define (good who) |
|
bokunopico![]()
54 сообщений |
#4115 2011-04-01 22:23 GMT+3 часа(ов) |
Спасибо, как я понял, ни %and, ни %or не вычисляются и вообще не возвращают ничего, а как-то хитро обрабатываются, поэтому и удаётся вытащить значение переменной в результирующий список. А %not вычисляется, но при этом теряет значение who. Сделал, как Вы предложили, хоть и жаль, что если фактов много, то придётся очень многие из них таким образом перечислять. Ну, раз нет лёгкого способа, то и не надо, все равно не пойму.
![]() |
|
misha![]()
1275 сообщений |
#4135 2011-04-07 00:51 GMT+3 часа(ов) |
> ни %and, ни %or не вычисляются и вообще не возвращают ничего, а как-то хитро обрабатываются, поэтому и удаётся вытащить значение переменной в результирующий список.
Ну, так это же макросы ![]() > Сделал, как Вы предложили, хоть и жаль, что если фактов много, то придётся очень многие из них таким образом перечислять. Извиняюсь за тупость ![]() #lang racket |
|
bokunopico![]()
54 сообщений |
#4136 2011-04-07 01:20 GMT+3 часа(ов) |
> Ну, так это же макросы
Я недавно начал изучать Scheme/Racket, так что многие элементарные вещи для меня становятся настоящим открытием. ![]() > На самом деле все очень просто Большое спасибо. Даже стыдно, что я могу лишь такими заурядными словами выразить благодарность за чуть ли не за меня разобранный Racklog. |
|
misha![]()
1275 сообщений |
#4142 2011-04-08 22:30 GMT+3 часа(ов) |
> Даже стыдно, что я могу лишь такими заурядными словами выразить благодарность за чуть ли не за меня разобранный Racklog.
А Вы можете расписать по шагам как обрабатывается конъюнкция в предикате "хороший"? |
|
bokunopico![]()
54 сообщений |
#4143 2011-04-08 23:58 GMT+3 часа(ов) |
А Вы можете расписать по шагам как обрабатывается конъюнкция в предикате "хороший"?
Наверное, сперва проверяется истинность предположения (goal) (любит кто (_)). Из него нам важно вытащить имя человека, а уж его конкретные предпочтения не особо важны, поэтому можно обойтись _. Потом проверяется второе предположение (%not (плохой кто)). Поскольку %not отличается от макроса %and по своей природе, поэтому приходится хитрить с дополнительным предположением, чтобы запомнить имя. Верно? К сожалению, такую конструкцию:
я пока довольно плохо понимаю, если вопрос как-то касался её. |
|
misha![]()
1275 сообщений |
#4144 2011-04-09 02:06 GMT+3 часа(ов) |
> Поскольку %not отличается от макроса %and по своей природе, поэтому приходится хитрить с дополнительным предположением, чтобы запомнить имя.
Смотрите, вот эквивалентный код на Прологе: любит(петя, racket).Найдите ошибочные предикаты и объясните в чем ошибка. Но перед этим разберитесь с бэктрекингом. Справка: "," эквивалентна %and, а ";" - %or. |
|
bokunopico![]()
54 сообщений |
#4150 2011-04-09 22:51 GMT+3 часа(ов) |
На мой взгляд, ошибочными будут вторая и третья версии предиката "хороший". И ошибка будет в лишних проверках истинности второго subgoal.
Например, для второго предиката "хороший", после того как выполнится первый subgoal, начнётся поиск подходящего второго subgoal, что в принципе ненужно, так как он точно "входит в состав" первого. Кроме того, если мы уже работаем в конце базы фактов и она достаточно объёмна, то разрешение второго subgoal может отнять некоторое время. Аналогичная ситуация и с третьей версией предиката. Например, можно зафиксировать решение первого subgoal, и если второй вернёт ложь, то это значит, что человек из базы является "плохим" (not истина == ложь), т.е. можно останавливаться. Но будет сделан возврат, или backtracking, а поиск продолжится с проверки факта, следующего за сохраненением первого subgoal. Надеюсь, что я всё же не сильно ошибаюсь. ![]() misha, если Вы не против, то можно и на ты. ![]() |
|
misha![]()
1275 сообщений |
#4151 2011-04-10 00:50 GMT+3 часа(ов) |
> misha, если Вы не против, то можно и на ты.
Ok > Надеюсь, что я всё же не сильно ошибаюсь. Трейсинг предикатов: [debug] 16 ?- хороший1(Кто).Racklog создан на основе Пролога, так что не стоит удивляться таким результатам ![]() P.S. Тогда я хотел сократить рассуждения, а в итоге белиберда получилась ![]() хороший1(Кто) :- Ищем "плохиша" и если он найден, тогда предикат not возвращает fail. хороший2(Кто) :- По аналогии с первым. Как ты уже знаешь, предикат может состоять из нескольких правил, выполняющихся по очереди. Кстати, %or - это всего лишь удобная форма записи составного предиката. Если одно из тел предиката вернет fail(неудачу), то в дело вступает следующее тело составного предиката. Отсечение используется чтобы ограничить поиск текущим телом. Например, Если бы мы не использовали отсечение предикат возвращал бы всегда true. отредактировал(а) misha: 2011-04-10 04:28 GMT+3 часа(ов) |
|
bokunopico![]()
54 сообщений |
#4152 2011-04-10 01:27 GMT+3 часа(ов) |
Очень интересный пример, спасибо большое.
> Racklog создан на основе Пролога, так что не стоит удивляться таким результатам Не знаю, как тут можно не удивляться! Вроде бы всё так понятно и легко с %and и %or (ну, и эквивалентами из Пролога), что и от %not ожидаешь "естественного" поведения. А когда первый предикат, не вызывающий подозрений, оказывается ошибочным... P.S. > Тогда я хотел сократить рассуждения, а в итоге белиберда получилась На мой взгляд, сброс переменных и пустой стек из первоначального варианта сообщения лучше объясняли ошибку первых двух предикатов. Наверное, я не совсем внятно выразил своё удивление. ![]() отредактировал(а) bokunopico: 2011-04-10 04:24 GMT+3 часа(ов) |
|
misha![]()
1275 сообщений |
#4153 2011-04-10 04:32 GMT+3 часа(ов) |
> На мой взгляд, сброс переменных и пустой стек из первоначального варианта сообщения лучше объясняли ошибку первых двух предикатов.
Тогда я слил все в одну кучу ![]() |
|
bokunopico![]()
54 сообщений |
#4154 2011-04-10 04:46 GMT+3 часа(ов) |
Я из Пролога знаю лишь название и пару базовых аспектов, поэтому очень удивился, узнав, что и он использует отсечение в отрицании. То есть такая конструкция в Racklog не из головы придумана:
А на самом деле естественно позаимствована (после правки сообщения догадался) и "повторяет" пример выше. Вот и весь смысл моего предыдущего поста. |
|
misha![]()
1275 сообщений |
#4155 2011-04-10 22:15 GMT+3 часа(ов) |
Рассмотрим трэйсинг предиката хороший2, задав системе вопрос
?- хороший2(X). [trace] 10 ?- хороший2(X).Число в круглых скобках означает глубину абстрактного системного стека возвратов. Обозначим его R, а специальный (используемый в поиске) стек возвратов S. Call: (6) хороший2(_G464) Вызов функции(предиката) с неконкретизированной переменной _G464. ^ Call: (7) not(плохой(_G464)) Последовательно задаем вопросы. Exit: (9) любит(паша, anime) Система возвращает первый найденный факт удовлетворяющий условию любит(_G464, anime), поэтому _G464 конкретизирована (_G464 = паша). ^ Fail: (7) not(user:плохой(_G464)) Т.к. предыдущий результат true, поэтому not возвращает fail. Следовательно, система считает, что "паша" ей не подходит, потому значение _G464 сбрасывается, точнее _G464 расконкретизируется. Fail: (6) хороший2(_G464) Т.к. предыдущий результат fail и стек S пуст, и следующее правило отсутствует(предикат хороший2 не является составным), поэтому система считает, что поиск завершен неудачно. Как будет себя "вести" предикат хороший2, если в базе отсутствуют "плохиши"? отредактировал(а) misha: 2011-04-10 23:12 GMT+3 часа(ов) |
|
misha![]()
1275 сообщений |
#4156 2011-04-10 22:43 GMT+3 часа(ов) |
Рассмотрим трэйсинг предиката хороший3
[trace] 11 ?- хороший3(X). Приступим ![]() Call: (6) хороший3(_G464) Система сразу находит факт удовлетворяющий условию любит(_G464, _G533) ![]() _G464 = петя; система кладет в стек S указатель на найденный в базе данных факт любит(петя, racket). ^ Call: (7) not(плохой(петя)) Не удивляйся, ведь теперь _G464 конкретизирована ![]() Call: (8) плохой(петя) Система установила, что "петя" удовлетворяет всем условиям поиска. В данном случае ";" означает продолжение поиска. Redo: (7) любит(_G464, _G533) Система возобновляет поиск беря со стека S указатель (конечно, указатель необходимо инкрементировать) Exit: (7) любит(паша, anime) Система находит факт удовлетворяющий условию любит(_G464, _G533) и т.д. отредактировал(а) misha: 2011-04-10 23:04 GMT+3 часа(ов) |
|
bokunopico![]()
54 сообщений |
#4157 2011-04-11 02:11 GMT+3 часа(ов) |
misha, ты просто КОЛОССАЛЬНУЮ работу проделал, таким образом проиллюстрировав внутренние механизмы Пролога! И чтобы не повторяться, скажу: ОНТОНИ АРИГАТО.
![]() > Как будет себя "вести" предикат хороший2, если в базе отсутствуют "плохиши"? Я думаю, он выдаст список из всех имеющихся в базе фактов людей. Наверное, это единственный случай, когда он вернёт то, что от него ожидают. Чтобы не быть голосословным, попытаюсь показать, как я себе представляю его "поведение" (благо имеются примеры, на которые можно ориентироваться):
Поиск возобновляется с вычисления subgoal любит(Кто, _), поскольку из стека достаётся соответствующий указатель. В случае с предикатом хороший3 поиск повторялся с самого начала составного предиката, т.е. с разрешения любит(Кто, _), так как (not ...) ничего со стеком не сделал. Я всё к тому, что кажется, благодаря вышеизложенным комментариям трейсинга, мне стала ясна суть backtracking'а. Например, есть предикат (%and g1 g2). Первый subgoal разрешился - в стек помещается указатель, переходим ко второму. Он тоже разрешается - в стек опять помещается указатель. Сперва работаем с указателем для второго subgoal, поскольку ничего другого из стека взять нельзя, а уже когда до конца прошлись по базе фактов с его помощью, только тогда достаём и инкрементируем то, что было помещено раньше. |
|
misha![]()
1275 сообщений |
#4161 2011-04-11 15:56 GMT+3 часа(ов) |
> В случае с предикатом хороший3 поиск повторялся с самого начала составного предиката, т.е. с разрешения любит(Кто, _), так как (not ...) ничего со стеком не сделал.
Составным я называю предикат в котором используется дизъюнкция целей, т.е. его можно составить из нескольких предложений. Поэтому "хороший3" не является составным, а вот "плохой" и "not" являются составными. (%and g1 g2 ...) - конъюнкция, а (%or g1 g2 ...) - дизъюнкция. Как можно сделать поиск более эффективным? Твои предложения. |
|
bokunopico![]()
54 сообщений |
#4168 2011-04-11 22:48 GMT+3 часа(ов) |
> Как можно сделать поиск более эффективным?
Используя только уже разобранные примитивы? Не используя всякие %set-of и не создавая новых предикатов, например, любим(язык, кем)? |
|
misha![]()
1275 сообщений |
#4169 2011-04-12 00:15 GMT+3 часа(ов) |
Реализация эффективного поиска процесс творческий. У нас простая база, поэтому мы можем лишь объединить факты относящиеся к Паше.
|
|
bokunopico![]()
54 сообщений |
#4170 2011-04-12 02:09 GMT+3 часа(ов) |
То есть сделать что-то по аналогии с GROUP BY, а потом использовать предикат хороший3? Так ведь получится, что предикат будет применяться к совершенно другой структуре, нежели та, на которую он был рассчитан, значит, надо воспользоваться новым. Кажется, я излагаю такие же рассуждения, как и в ответе на вопрос, какой предикат ошибочен.
![]() |
|
misha![]()
1275 сообщений |
#4173 2011-04-12 23:45 GMT+3 часа(ов) |
> То есть сделать что-то по аналогии с GROUP BY, а потом использовать предикат хороший3?
(define любит > Так ведь получится, что предикат будет применяться к совершенно другой структуре, нежели та, на которую он был рассчитан, значит, надо воспользоваться новым. Так в чем проблема? ![]() |
|
bokunopico![]()
54 сообщений |
#4175 2011-04-13 01:09 GMT+3 часа(ов) |
Я ожидал, что будет какой-нибудь фокус с преобразованием базы фактов, так сказать, "на лету", а тут даже задача упростилась.
Вот что придумал в итоге:
Предикат хороший даже остался без изменений. Единственное - смущает повторение предиката любит, только никаких идей нет, как избежать этого. Хотя бы правильное направление решения выбрал? |
|
misha![]()
1275 сообщений |
#4176 2011-04-13 02:34 GMT+3 часа(ов) |
> Я ожидал, что будет какой-нибудь фокус с преобразованием базы фактов, так сказать, "на лету", а тут даже задача упростилась.
Этот подход предполагает хотя бы один проход по всей базе вне зависимости того требуется ли нам найти первый подходящий факт, или же найти их все. > (%or (%member 'php что) (%member 'anime что))Ты уже должен был заметить, что дизъюнкция имеет дурное свойство: при возобновлении поиска начинать со следующего предложения. Короче, если (%member 'php что) = %true, то поиск возобновится с (%member 'anime что), а не сначала. Тебе необходимо исправить этот недостаток. > Единственное - смущает повторение предиката любит, только никаких идей нет, как избежать этого. Можешь написать функцию конвертирующую старую базу данных в новую. |
|
bokunopico![]()
54 сообщений |
#4178 2011-04-13 03:02 GMT+3 часа(ов) |
> Единственное - смущает повторение предиката любит, только никаких идей нет, как избежать этого.
> Можешь написать функцию конвертирующую старую базу данных в новую. Я имел в виду, что в предикате хороший сперва вычисляется (любит кто (_)), а потом (любит кто что) уже в составе предиката %not. > Короче, если (%member 'php что) = %true, то поиск возобновится с (%member 'anime что), а не сначала. Именно поэтому и дублируется Паша. отредактировал(а) bokunopico: 2011-04-13 03:18 GMT+3 часа(ов) |
|
misha![]()
1275 сообщений |
#4179 2011-04-13 03:24 GMT+3 часа(ов) |
> Я имел в виду, что в предикате хороший сперва вычисляется (любит кто (_)), а потом (любит кто что) уже в составе предиката %not.
Ты всегда можешь создать более эффективный предикат. А написать конвертер все же стоит. |
|