Главная страница « Информация « 4 курс « курс ФПScheme «

Учебное пособие по выполнению задания «Доктор»


Набор упражнений в рамках общего задания «Доктор» первоначально был составлен канд. физ.-мат. наук Черновым А. В. более десяти лет тому назад. Предложенный им текст доступен онлайн [pdf]. Затем в течение ряда лет задание обновлялось канд. физ.-мат. наук Малышко В. В.. Результаты этих обновлений перед Вами.

Оглавление


Введение
1-й блок. Упражнения с 1 по 4
1.1. Упражнение 1. Заготовка doctor.rkt
1.2. Упражнение 2. Рекурсивные и итеративные процессы
1.3. Упражнение 3. Функции высших порядков и списки
1.4. Упражнение 4. 3-я стратегия генерации ответов
2-й блок. Упражнения с 5 по 6
2.1. Упражнение 5. Многопользовательский «Доктор»
2.2. Упражнение 6. 4-я стратегия генерации ответов
3-й блок. Упражнение 7. Обобщённый reply
4-й блок. Дополнительное упражнение 8 ("творческое")


Введение


      «Доктор» (или ELIZA) -- это название программы, созданной Джозефом Вейценбаумом. Эта программа имитирует (или пародирует) психоаналитика, ведущего диалог с пациентом. Программа принимает реплики пациента (в виде списков символов) и генерирует ответные реплики (также в виде списков). Для простоты сокращена пунктуация в записи реплик. Исходный код ELIZA на языках LISP-семейства можно найти в Сети: [html], [html].

      В рамках выполнения практического задания Вы создадите собственную версию «Доктора», которая основана на некоторых (но не всех!) идеях, лежащих в основе исходной программы.

      Упражнения по «Доктору» делятся на 4 блока:
1-й блок -- упражнения с 1 по 4. Максимальный балл -- 5.
2-й блок -- упражнения 5 и 6. Максимальный балл -- 7.
3-й блок -- упражнение 7. Максимальный балл -- 8.
4-й блок -- упражнение 8. Максимальный балл -- 10.

      Рекомендуется сдавать упражнения блоками. Выполнив упражнения блока, отправьте код через форму на Moodle-площадке. После ревью Вашего кода Вам может быть предложено оценить эффективность фрагмента Вашего кода и улучшить её, переписав фрагмент. Для отправки обновлённого кода через ту же форму будет предоставлена новая попытка. Точно также новые попытки будут предоставлены для сдачи последующих блоков.

      Версии программы 1-3 блоков следует составлять на подмножестве языка scheme/base (начинайте свой код с директивы #lang scheme/base). В них использование мутаторов (присваиваний и т. п.), мутируемых структур данных Racket, запрещено. При переходе от начальных упражнений к последующим код следует дописывать так, чтобы функциональность программы расширялась (то, что было раньше, не портить, сохранять прежние версии кода функций, дописывая к их именам постфиксы с номером упражнения и т. п.). Не следует сдавать несколько разных версий программы, каждая из которых решает только одно из упражнений.

      Предполагается, что прошлые годы учёбы привили Вам навык оформления кода. Сдаваемый код должен быть оформлен должным образом: быть читаемым, сопровождаться содержательными и актуальными комментариями на русском языке. Комментарии, размещённые в заготовке кода могу стать неактуальными по ходу выполнения упражнений. Их также следует править.

Блок 1. Упражнения с 1 по 4


      Упражнение 1. Заготовка doctor.rkt + замена лица

      В документах ВК-группы [html] найдите заготовку кода «Доктора» и скачайте её. На сайте [html] найдите дистрибутив среды Racket и установите её себе на компьютер. Запустите IDE Racket и откройте заготовку кода «Доктора». Запустите код в интерпретаторе (Ctrl+R или кнопкой Run). Проверьте, как он работает. Например, вводите реплики пациента из листинга (реплики отмечены **, но ** не являются частью реплик):

> (visit-doctor 'ivan)
Hello, ivan!
(what seems to be the trouble?)
**(everyone hates me)
(you feel that everyone hates you)
**(whenever i enter a room no one will look me in the eye)
(please go on)
**(they laugh at me behind my back)
(you seem to think they laugh at you behind your back)
**(they get together and talk about how they hate me)
(please continue)
**(even my mother hates me)
( that even your mother hates you)
**(even when i was a baby she said i was ugly and stupid)
(many people have the same sorts of feelings)
**(she hit me all the time)
(please continue)
...

      «Доктор» отвечает на реплики пациента двумя способами, реализованными в нём. Первый способ заключается в замене в реплике пользователя всех местоимений первого лица (i, me, my, ...) на соответствующие местоимения второго лица (you, you, are, ...). Местоимения второго лица в реплике пользователя заменяются на местоимения первого. К полученной таким образом фразе спереди дописывается некоторое общее замечание, вроде why do you say that или you seem to think that.

      Второй метод проще первого. Реплика пациента при построении ответа не используется. В качестве ответа «Доктор» выдаёт одну из заготовленных общих фраз, выбранную случайно: please continue или many people have the same sorts of feelings.

      Какой из двух методов будет использован, решает случай. С равной вероятностью выбирается один из двух.

      «Доктор» запускается вызовом его основной функции -- visit-doctor с указанием имени пациента в качестве значения параметра. В этой функции сначала выводится приветствие пациента, задаётся вопрос, приглашающий к обмену репликами, а затем вызывается функция doctor-driver-loop, реализующая цикл приёма реплик пациента и генерации ответов «Доктора».

(define (visit-doctor name)
  (printf "Hello, ~a!\n" name)
  (print '(what seems to be the trouble?))
  (doctor-driver-loop name)
)

       В цикле происходит печать приглашения -- ** -- и чтение реплик пациента, каждая из которых является списком символов (пользователю следует вводить их в скобках). Если пациент говорит (goodbye), происходит выход из цикла и завершение работы «Доктора». В противном случае, порождается ответная реплика в соответствии с одной из двух стратегий, описанных выше.

(define (doctor-driver-loop name)
    (newline)
    (print '**) ; доктор ждёт ввода реплики пациента, приглашением к которому является **
    (let ((user-response (read)))
      (cond 
	    ((equal? user-response '(goodbye)) ; реплика '(goodbye) служит для выхода из цикла
             (printf "Goodbye, ~a!\n" name)
             (print '(see you next week)))
            (else (print (reply user-response)) ; иначе Доктор генерирует ответ, печатает его и продолжает цикл
                  (doctor-driver-loop name)
             )
       )
     )
)

      Генерацию ответной реплики осуществляет функция reply, принимающая реплику пациента в качестве значения параметра.

(define (reply user-response)
      (case (random 2)  ; с равной вероятностью выбирается один из двух способов построения ответа
          ((0) (qualifier-answer user-response)) ; 1й способ
          ((1) (hedge))  ; 2й способ
      )
)

      Вторая стратегия построения ответов реализована функцией hedge. Она случайно выбирает из списка заготовленных реплик один элемент.

(define (hedge)
       (pick-random '((please go on)
                       (many people have the same sorts of feelings)
                       (many of my patients have told me the same thing)
                       (please continue)
                       )
         )
)

      Случайный выбор одного из элементов списка реализует функция pick-random.

(define (pick-random lst)
  (list-ref lst (random (length lst)))
)

      Первая стратегия построения ответов реализована функцией qualifier-answer, получающей реплику пациента в качестве значения параметра. В ней случайно выбирается одно из заготовленных начал ответа. Окончанием ответа является реплика пользователя, в которой заменены лица.

define (qualifier-answer user-response)
        (append (pick-random '((you seem to think that)
                               (you feel that)
                               (why do you believe that)
                               (why do you say that))
                )
                (change-person user-response)
        )
)

      Замену лиц осуществляет функция change-person. Она вызывает более универсальную функцию many-replace, получающую список замен и список, в котором следует произвести замены. Она проверяет каждый элемент изменяемого списка, на возможность его замены. Если замена возможна (элемент найден в списке замен, то она производится, а окончание ответа находится при помощи рекурсивного вызова. Список замен является ассоциативным списком. Он составлен из подсписков, каждый из которых начинается с элемента-ключа и продолжается элементом-значением. Поиск подсписка по ключу выполняет стандартная функция assoc. Обратите внимание, что в if используется результат вызова assoc, который не всегда будет логическим значением. Убедитесь, что Вы верно понимаете как работают if и assoc.

(define (many-replace replacement-pairs lst)
        (cond ((null? lst) lst)
              (else (let ((pat-rep (assoc (car lst) replacement-pairs))) ; Доктор ищет первый элемент списка в ассоциативном списке замен
                      (cons (if pat-rep (cadr pat-rep) ; если поиск был удачен, то в начало ответа Доктор пишет замену
                                (car lst) ; иначе в начале ответа помещается начало списка без изменений
                            )
                            (many-replace replacement-pairs (cdr lst)) ; рекурсивно производятся замены в хвосте списка
                        )
                     )
               )
         )
)

      Выполняя упражнение 1, измените функции qualifier-answer и hedge, добавив в каждую не менее трёх новых заготовленных фраз-реплик и/или фраз, с которых начинается ответ с заменой лица. Повысьте уровень абстракции у структуры данных, представляющей данные о заменяемых местоимениях и глаголах в списке замен внутри change-person. Заведите дополнительные функции: конструктор, селекторы, чеккер и перепишите с их помощью many-replace. Можно заметить, что довольно многое заменяется на you, на your, на yours. Предложите, как это можно учесть на уровне внутреннего представления, чтобы сократить дублирование в хранимых данных.

      Упражнение 2. Рекурсивные и итеративные процессы

      Рассмотрим код функции many-replace. В ней с рекурсивным вызовом связаны остаточные вычисления. Следовательно, процесс, порождаемый при вычислении вызова этой функции, -- рекурсивный. Можно переписать many-replace так, чтобы процесс стал итеративным и вычисления занимали меньше памяти за счёт хвостовой рекурсии.

      Выполняя упражнение 2, напишите новую версию функции many-replace с хвостовой рекурсией и вызовите её в теле change-person. Составьте код нового many-replace без определения локальной вспомогательной функции, а с использованием "именованного" let. Далее всякий раз, когда для реализации итеративного процесса понадобится локальная вспомогательная функция, используйте вместо неё "именованный" let. Новая версия функции должна быть эффективной. Если Вы планируете использовать append для "сборки" результата, то оцените сложность решения. Как получить ответ без append?

      Упражнение 3. Функции высших порядков и списки

      Рассмотрим ещё раз реализацию many-replace. Она осуществляет отображение списка lst в список-результат. Общую схему подобной обработки списка реализует функция map.

      Выполняя упражнение 3, напишите ещё одну версию функции many-replace и замените вызов в теле change-person. Сделайте так, чтобы тело новой версии состояло только из вызова map. Дополнительную функцию не определяйте отдельно, а заведите как анонимную -- результат вычисления спецформы lambda. Переписанная функция должна быть столь же эффективной, как результат выполнения упражнения 2. В ходе дальнейшей работы над «Доктором» всякий раз, когда описываете обработку списка, сделайте это с помощью подходящей функции высшего порядка (map, foldl, foldr, filter, andmap, ormap ...). В модуле, подключаемом директивой (require racket/list) есть дополнительные функции высшего порядка для работы со списками (filter-map, count, append-map, filter-not, argmin, argmax, remf, remf*, ...), имейте это в виду.

      Упражнение 4. 3-я стратегия генерации ответов

      Двух способов генерации ответов мало. Добавим третий. «Доктор» может запоминать все реплики пациента и в ходе беседы возвращаться к сказанному пациентом ранее. В этом случае реплика «Доктора» будет начинаться со слов earlier you said that, а затем будет следовать одна из предыдущих реплик пациента, в которой выполнена замена лица. Например, если из предыдущих реплик пациента выбрана реплика (you are not being very helpful to me), то по ней будет построен ответ (earlier you said that i am not being very helpful to you).

      Выполняя упражнение 4, измените программу таким образом, чтобы doctor-driver-loop сохранял список всех реплик пользователя. Замечание: не используйте присваивания (мутаторы вроде set!). В этом нет необходимости. Новая версия функции reply будет выбирать одну стратегию из трёх. Новую стратегию реализуйте как отдельную функцию history-answer. Обратите внимание, что hedge и qualifier-answer можно применять всегда, а history-answer -- только при наличии предыдущих реплик. Когда пациент вводит первую реплику, эта стратегия не применима. Учтите это в реализации. Для случайного выбора из трёх альтернатив следует взять случайное число от 0 до 2: (random 3), и использовать его как номер выбранной стратегии, считая, что они нумеруются с нуля. Для вызова стратегии по выбранному номеру подходит спецформа case.

Блок 2. Упражнения 5 и 6


      Упражнение 5. Многопользовательский «Доктор»

      Текущая версия программы умеет работать только с одним пациентом, имя которого задаётся в вызове функции visit-doctor. Когда пациент говорит goodbye, visit-doctor возвращает управление интерпретатору. Выполняя упражнение 5, измените программу таким образом, чтобы «Доктор» автоматически переходил к приёму следующего пациента после прощания с предыдущим. Предусмотрите способ завершения работы многопользовательского «Доктора» или после использования стоп-слова в качестве имени очередного пациента, или при исчерпании количества принимаемых пациентов. Стоп-слово и максимальное количество пациентов передаются в обновлённый visit-doctor как значения его параметров. Например, (visit-doctor 'suppertime 3) может завершиться либо если трое пациентов обслужено, либо если введено имя пациента suppertime. Для ввода имени очередного пациента можете воспользоваться функцией ask-patient-name (заметьте, что именем пациента считается первый элемент списка, введённого пользователем):

(define (ask-patient-name)
 (begin
  (println '(next!))
  (println '(who are you?))
  (print '**)
  (car (read))
 ) 
)

      Теперь сессия работы «Доктора» может выглядеть следующим образом:

> (visit-doctor 'suppertime 3)
(next!)
(who are you?) 
**(hal abelson)
(hello, hal)
(what seems to be the trouble?)
**(everyone taking 6.001 hates me)
(why do you say everyone taking 6.001 hates you)
...
**(goodbye)
(goodbye, hal)
(see you next week)
(next!)
(who are you?)
**(eric grimson)
(hello, eric)
(what seems to be the trouble?)
...
**(goodbye)
(goodbye, eric)
(see you next week)
(next!)
(who are you?)
**(suppertime)
(time to go home)

      Упражнение 6. 4-я стратегия генерации ответов

      Реализуйте ещё одну стратегию генерации ответных реплик, зависящую от ключевых слов в реплике пациента. Например, на фразу i am often depressed «Доктор» может ответить when you feel depressed, go out for ice cream. Здесь «Доктор» увидел в реплике пациента ключевое слово depressed и выдал в ответ одну из заготовок, связанную с этим словом. На низком уровне структура данных, хранящая группы ключевых слов и привязанных к ним шаблонов для составления ответных реплик может выглядеть так:

( 
  ( ; начало данных 1й группы
    (depressed suicide exams university) ; список ключевых слов 1й группы
    ( ; список шаблонов для составления ответных реплик 1й группы 
	  (when you feel depressed, go out for ice cream)
      (depression is a disease that can be treated)
	)
  ) ; завершение данных 1й группы
  ( ; начало данных 2й группы ...
    (mother father parents brother sister uncle ant grandma grandpa)
    (
	  (tell me more about your * , i want to know all about your *)
      (why do you feel that way about your * ?)
	)
  )
  (
    (university scheme lections)
	(
	  (your education is important)
	  (how many time do you spend to learning ?)
	)
  )
)

      Можно видеть, что в разные группы ключевых слов могут входить одни и те же слова. Если в варианте ответной реплики есть звёздочка, это значит, что в ответе вместо * «Доктор» укажет ключевое слово, по которому он построил реплику. Например, на фразу пользователя, содержащую слово father может быть дан ответ tell me more about your father , i want to know all about your father.

      Выполняя упражнение 6, реализуйте в программе стратегию построения ответов по ключевым словам. Оформите необходимую структуру данных должным образом, составив конструктор, селекторы, чеккеры. Реализованная структура не должна быть мутируемой. Она должна быть эффективной по памяти (дублирования не должно быть больше, чем в примере, данном выше). Пополните набор групп ключевых слов (не менее чем двумя новыми группами). Пополните варианты ответов для каждой группы (не менее чем двумя вариантами). Построение реплик по ключевым словам должно быть реализовано так, чтобы можно было изменять варианты и/или группы, не исправляя код функции, составляющей реплику по ключевым словам.

      Стратегия построения реплики по ключевым словам применима только в том случае, когда в реплике есть хотя бы одно ключевое слово. Следует описать отдельную функцию-предикат, проверяющую это. Функция-предикат должна быть эффективной. Она не должна делать лишних действий, после того как становится ясно, что стратегия применима. Если для работы функции-предиката не нужна вся структура данных, хранящая группы ключевых слов и привязанных к ним шаблонов, то следует однократно предобработать эту структуру, получив необходимые данные, и затем использовать результат однократной предобработки в вызовах функции-предиката.

      Функция построения реплики по ключевым словам должна работать так. Сначала происходит поиск всех ключевых слов в реплике пациента. Среди найденных слов случайно выбирается то ключевое слово, которое будет использовано для построения реплики. Этот выбор должен учитывать количество вхождений слова в реплику пациента (вероятность выбора слова, входящего несколько раз, должна быть выше). Когда выбор ключевого слова сделан, по нему следует выбрать один из подходящих шаблонов для составления ответной реплики. Предусмотрите учёт ситуации, когда одно и то же ключевое слово относится к разным группам. Для таких слов следует выбирать шаблон из объединённого перечня всех шаблонов, относящихся к каждой группе, куда входит ключевое слово. В выбранном шаблоне следует заменить * на ключевое слово. При этом следует использовать ту реализацию замен, которая уже есть в коде «Доктора». Поскольку построение реплики является обработкой списка, напишите код с использованием уместных функций высшего порядка (map, foldl, foldr, filter, andmap, ormap ...).

Блок 3. Упражнение 7. Обобщённый reply


      Каждый раз при добавлении новой стратегии приходилось переписывать reply. Можно переписать его, создав обобщённую версию, которая будет работать с любым подаваемым ему на вход перечнем стратегий. Удобство обобщённого reply состоит в том, что при изменении стратегий построения ответных реплик будет достаточно менять сами данные о стратегиях, но не управляющий механизм. Этот универсальный механизм состоит в следующем: во-первых, строится набор стратегий, применимых в текущей ситуации; во-вторых, если в построенном наборе больше одной стратегии, то выбирается одна из них; в-третьих, выбранная стратегия применяется и её результат будет ответной репликой. На вход механизма подаётся структура данных со сведениями обо всех стратегиях «Доктора». Про каждую стратегию в этой структуре хранится: а) функция-предикат от реплики пользователя, от истории реплик пользователя, от, возможно, других параметров, которая возвращает #f, только если стратегия не применима, и не #f -- иначе (Внимание! В структуре данных должна храниться именно функция!); б) вес стратегии -- натуральное число, которое будет использовано при выборе одной из применимых стратегий (чем больше вес, тем выше вероятность применения стратегии, например, если есть применимые стратегии с весами 2, 3, 1, то первая будет выбрана с вероятностью 1/3, вторая -- с вероятностью 1/2, третья -- с вероятностью 1/6); тело стратегии -- функция, которая по реплике пользователя, по истории реплик пользователя, по, возможно, другим параметрам строит ответную реплику (Внимание! В структуре данных должна храниться именно функция!). Например, для стратегии "hedge" функция-предикат -- это функция никогда не возвращающая #f; вес этой стратегии = 1 (самый малый); тело этой стратегии -- функция hedge.

      Выполняя упражнение 7, следует реализовать структуру данных (конструктор, селекторы и проч.); переписать reply, добавив ему параметр -- структуру данных о стратегиях построения реплик. Все стратегии ответов, имеющиеся в программе должны быть представлены в этой структуре данных. Каких-либо способов построения ответов вне структуры данных о стратегиях быть не должно. Структура данных о стратегиях не зависит от реплик пользователей и её значение не должно вычисляться более чем один раз. Так как речь снова идёт об обработке списков, пишите код с использованием уместных функций высшего порядка (map, foldl, foldr, filter, andmap, ormap ...). Назначая веса стратегиям, используйте разные значения веса, чтобы взвешенный поиск не превращался в случайный -- pick-random. Рекомендуется реализовать аналог pick-random -- pick-random-with-weight, который получает список взвешенных элементов, и выбирает случайный элемент с учётом весов. Рекомендуется перед реализацией «геометрически» решить задачу, т. е. рассмотреть случайный выбор части из составного отрезка (длина части отрезка = весу соответствующего элемента списка).

Блок 4. Дополнительное упражнение ("творческое")


      4й дополнительный блок можно сдать тем, кто желает заработать ещё больше добавочных баллов. Сделать это можно до начала мая 2021 года. Позднее Ваш задел по 4му блоку рассматриваться не будет. Блок посвящён дальнейшему совершенствованию «Доктора». Одним из путей совершенствования является добавление, так называемого, метауровня. Выполняя блок 3, мы реализовали один из способов выбора стратегии построения ответов. Этот способ заключался в том, что среди всех применимых стратегий с учётом их весов случайно применяется одна. Обозначим этот способ выбора как управляющую стратегию №1. Мы могли бы использовать другой способ выбора (другую управляющую стратегию). Например, можно упорядочить стратегии по весу, проверять сначала применимость более тяжёлых и, как только какая-то стратегия применима, останавливать проверку и использовать её (т. н. управляющая cond-стратегия с весами). Другие управляющие стратегии могли бы учитывать историю стратегий (предыдущие использования стратегий построения ответов), сложность выполняемых проверок и др.. На метауровне «Доктор» перед тем как выбирать стратегию построения ответа, анализирует, какие управляющие стратегии применимы в текущий момент. Из применимых управляющих стратегий «Доктор» выбирает одну (случайно, с учётом веса). Далее он запускает выбранную управляющую стратегию для выбора стратегии построения ответа. У всех управляющих стратегий должны быть нетривиальные условия их применения. Решения с тривиальными условиями, тождественными #t или всегда возвращающими #t, не принимаются.

      Второй путь совершенствования «Доктора» -- это учёт истории в стратегии ответов по ключевым словам. «Доктор» мог бы запоминать, какое ключевое слово было использовано и к какой группе ключевых слов относилась выбранная реплика (ведь одно слово может входить в несколько групп). В последующем «Доктор» мог бы, с одной стороны поддерживать тему, выбирая реплики-ответы из предыдущей группы, если есть такая возможность, с другой стороны, избегать повторов, заменяя * в заготовке реплики не на использованное ранее ключевое слово, а на родственные ключевые слова из одной группы с ним. Например, если предыдущий обмен репликами, касался матери пациента, «Доктор» мог бы поддержать тему семьи, но переключить разговор на других родственников пациента.

      Вы можете придумывать собственные стратегии построения ответных реплик, использовать идеи исходной программы ELIZA и т. п..

Предупреждение


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

  

© Кафедра системного программирования ВМК МГУ.

Обновлено: 16.II.2021