Проблемно-ориентированные знания в системе обучения функциональному программированию тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Груздева, Надежда Валерьевна

• Груздева, Надежда Валерьевна
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Груздева, Надежда Валерьевна

Оглавление

Введение

Глава 1. Компьютерные системы обучения программированию

Глава 2. Представление знаний о классах задач и вариантах программ

2.1 Классификация типичных задач

2.2 Спецификации задач и шаблоны программ

2.3 Процедуры анализа и синтеза программ

Глава 3. Процедуры проверки правильности рефал-программ

3.1 Проверка правильности решений задач первого класса

3.2 Проверка правильности решений задач второго класса

3.3 Вспомогательные процедуры

3.3.1 Установление соответствия

нетерминал -> тип рефал-переменной

3.3.2 Эквивалентные трансформации БНФ

3.3.3 Построение левой части рефал-правила

по альтернативе БНФ

3.3.4 Построение правой части рефал-правила

по альтернативе БНФ

3.3.5 Разбиение образцов на группы

Глава 4. Экспериментальная система обучения языку Рефал

4.1 Основные функции и структура системы

4.2 Учебник языка Рефал

4.3 Библиотека спецификаций задач и шаблонов программ

4.4 Модуль проверки правильности рефал-программ

4.5 Модуль трассировки рефал-программ

Заключение

Литература

Приложение 1. Синтаксис языка Рефал-2

Приложение 2. Шаблоны рефал-программ

Введение диссертации (часть автореферата) на тему «Проблемно-ориентированные знания в системе обучения функциональному программированию»

Введение

Первые компьютерные или автоматизированные обучающие системы (КОС или АОС) появились еще в 60-х годах [7]. Они широко применялись в обучении разным предметам - например, географии, электротехнике, медицине. В то же время возник термин "автоматизированное обучение", обозначающий новую область информатики, связанную с применением ЭВМ в качестве посредника между преподавателем и учеником при обучении какому-либо предмету.

В обучение программированию КОС внедрялись очень медленно, поскольку программирование долгое время считалось профессией избранных. Но бурный рост парка ЭВМ, а тем самым и потребностей в программном обеспечении изменил взгляды на создание программ. Характерной чертой программного обеспечения является быстрый темп старения, поэтому всем, кто связан с созданием и использованием программного обеспечения, постоянно приходиться обновлять свои знания. Для этого создается большое количество учебников по программированию, организуются курсы, лекции, практикумы, создаются видеосредства для обучения. КОС в этом ряду предлагают эффективный способ обучения, обеспечивая индивидуализацию курса обучения по отношению к конкретному обучаемому.

Основной характеристикой, определяющей КОС, является способ представления материала обучения. В зависимости от этого все системы разделяют на два класса: традиционные КОС и интеллектуальные КОС.

Традиционные КОС основываются на так называемой парадигме программированного обучения [7]: вначале обучаемому предоставляется текст, содержащий учебную информацию, и затем задается вопрос, проверяющий усвоение им этой информации и требующий краткого ответа. После анализа ответа обучаемому сообщается, правильно или ошибочно он ответил. Правильные и ошибочные варианты ответа

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

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

Распространение персональных ЭВМ и успехи в области искусственного интеллекта (ИИ) оказали революционное влияние на исследования в области применения ЭВМ в обучении. На смену традиционным компьютерным обучающим системам приходят учебные системы нового поколения - интеллектуальные обучающие системы (ИОС) [3, 12]. Создание ИОС стало результатом применения методов и средств ИИ в области автоматизированного обучения.

Первые попытки создания ИОС относятся к началу 70-х годов и вызваны разочарованием ряда разработчиков обучающих систем в традиционной технологии программированного обучения, а именно, в слабой адаптивности традиционных КОС к конкретному обучаемому. С помощью этой технологии невозможно создать КОС, которые выполняли бы функции контроля и помощи в процессе практической работы обучаемого с учетом его индивидуальных характеристик. В течение 70-х и 80-х годов был разработан ряд экспериментальных ИОС [1, 2, 5, 25-28, 3032], которые продемонстрировали плодотворность нового подхода и стимулировали дальнейшие исследования [4, 6, 8-11, 29, 33-37].

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

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

Модуль-эксперт проблемной (предметной) области содержит проблемно-ориентированные знания, т.е. знания об изучаемом при помощи данной КОС предмете - о геологии, геометрии, языке программирования и т.д.

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

Модуль анализа действий обучаемого содержит и постоянно обновляет необходимые системе знания о конкретном обучаемом. Для отображения этих знаний используется динамическая модель обучаемого.

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

Модуль интерфейса объединяет в себе знания, необходимые для поддержания наиболее удобного для обучаемого взаимодействия с системой.

Что касается обучения программированию, то актуальность применения методов ИИ в этой области обусловлена спецификой изучаемого предмета:

• составление программ - это задача, сопоставимая по сложности, например, с доказательством теорем;

• выразительные средства любого языка программирования являются избыточными, позволяющими создавать различные программы для решения одной и той же задачи, отличающиеся заложенными в них алгоритмами, а также эффективностью, размером и т.п.;

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

Ясно, что наиболее эффективным и предпочтительным является индивидуальный подход к обучаемому, который можно реализовать в КОС.

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

ошибочных решений. Именно реализация в системе хотя бы одной из перечисленных возможностей позволяет отнести ее к интеллектуальным обучающим системам.

Модуль-эксперт проблемной области в системе обучения программированию должен включать не только знания о синтаксисе и семантике языка программирования, но и знания, которыми владеет эксперт-программист в своей работе (способы алгоритмизации задачи, знания о стиле программирования и пр.). В идеале эти процедурные и декларативные знания позволяют модулю-эксперту самому решать задачи, которые ИОС предлагает обучаемому, помогать обучаемому в процессе решения задач, проверять его решение.

Очевидно, что одной из основных проблем разработки интеллектуальных систем обучения программированию является проблема проверки правильности программ, написанных обучаемым в процессе решения задач. Методы формального доказательства правильности программ [13, 23 ,38] трудно реализуемы и малопригодны для использования в КОС.

В существующих системах обучения программированию [1, 2, 5, 25-28, 30-32] проверка правильности программы понимается как установление ее соответствия (эквивалентности) одной из известных системе эталонных программ, являющихся решениями соответствующей задачи. Сложность проверки правильности программ связана с тем, что даже для несложных задач число различных решений одной и той же задачи (вариантов программ) достаточно велико. Причем эта вариативность резко увеличивается с ростом сложности задач.

В области автоматизированного обучения программированию наименее изученным является обучение функциональным языкам, к которым относятся Лисп [17, 24], Рефал [16, 19, 20, 41], Плэнер [18]. Большинство разработанных к настоящему времени систем предназначалось для обучения языку Лисп, из них известны лишь три

ИОС- система Lisp Tutor [1, 27], система ELM-ART [30] и отечественная система ЛУЧ [2].

В то же время на протяжении последних лет наблюдался растущий интерес к функциональному программированию [23] как в академических, так и в промышленных организациях. Привлекательность функциональных языков вызвана тремя главными, присущими им особенностями. Во-первых, функциональные программы неизменно оказываются намного короче, с более высокой степенью абстракции и часто понятнее, чем соответствующие аналоги, написанные на процедурных языках. Во-вторых, функциональные программы пригодны для формального анализа и манипулирования. И, в-третьих, они естественно поддаются реализации на параллельных ЭВМ.

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

Исторически первая система обучения функциональному программированию - Lisp Tutor - относится к системам поддержки процесса решения задач. Lisp Tutor осуществляет пошаговое управление и контроль хода решения обучаемым простой лисп-задачи (например, программирование функции APPEND), и в ней не возникает проблема проверки правильности законченной программы. В отличие от Lisp-Tutor системы ЛУЧ и ELM-ART обладают возможностью анализа различных законченных программ - решений одной задачи. Система ЛУЧ проверяла правильность программы путем тестирования на некотором наборе тестов. В системе ELM-ART проверка правильности программы обучаемого проводится путем сопоставления с эталонными программами-

решениями данной задачи. Так как ELM-ART предлагает для решения ограниченный набор типичных лисп-задач, каждая из которых имеет несколько возможных решений, проблема поиска нужного эталона, возникающая при проверке правильности программы, не встает особо остро. Однако с ростом сложности задач указанный метод представления знаний о вариантах программ становится все более неадекватным. Кроме того, он имеет такой недостаток, как сложность изменения и пополнения набора задач, решения которых система может проверять.

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

Данная диссертационная работа посвящена исследованию и разработке методов проверки правильности функциональных программ для КОС и организации необходимых для этого проблемно-ориентированных знаний. Исследование проводилось для функционального языка программирования Рефал.

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

На базе предложенного подхода для функционального языка программирования Рефал разработаны способы спецификации

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

Данная диссертационная работа состоит из введения и четырех

глав.

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

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

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Груздева, Надежда Валерьевна

Заключение

В работе получены следующие основные результаты:

1. Предложен подход к проверке правильности программ в системах обучения функциональному программированию, основанный на представлении знаний о классах задач в виде спецификаций задач, шаблонов программ и процедур синтеза таких шаблонов, что позволяет сравнительно просто расширять множество предлагаемых при обучении задач.

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

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

Построенная экспериментальная система может быть полезна при самостоятельном изучении языка Рефал, а также - как дополнительное средство — и при обучении студентов преподавателем.

Предложенный подход к проверке правильности программы обучаемого может быть применен при создании КОС, предназначенных для обучения другим функциональным языкам программирования.

Разработанные процедуры синтеза шаблонов рефал-программ и используемые ими вспомогательные алгоритмы и процедуры могут быть использованы в системах автоматического синтеза рефал-программ.

Список литературы диссертационного исследования кандидат физико-математических наук Груздева, Надежда Валерьевна, 1998 год

Литература:

1. Андерсон Дж.Р., Рейзер Б.Дж. Учитель Лиспа // Реальность и прогнозы искусственного интеллекта - М.: Мир, 1987,стр. 27-47.

2. Большакова Е.И., Мальковский М.Г., Пильщиков В.Н. Обучающая система ЛУЧ // Сб. научно-метод. статей по математике, Вып. 13, М.: Высш. Школа, 1986, стр.96-114.

3. Брусиловский П.Л. Интеллектуальные обучающие системы // Информатика, н.-т. сборник, Вып. 2, 1990, стр. 3-22.

4. Гецко Л.Н., Колос В.В. Сетевая модель предметной области в обучении Прологу // Проблемы разработки и внедрения программного обеспечения ЭВМ и систем - Киев: ИК АН УССР, 1988, стр. 51-55.

5. Джонсон У.Л., Солоуэй Э. PROUST // Реальность и прогнозы искусственного интеллекта — М.: Мир, 1987, стр. 48-70.

6. Зайцева Г.В. Организация обучающего диалога на основе фреймов БЗ // Автоматика и вычислительная техника, № 5, 1991, стр. 91-95.

7. Кибернетика и проблемы обучения: Сб. переводов под ред. А.И. Берга -М.: Прогресс, 1970.

8. Колос В.В., Кудрявцева С.П., Сахно A.A. Разработка и реализация семейства интеллектуальных обучающих систем на основе учебных структур знаний // Известия РАН, Техническая кибернетика, 1993, № 2, стр. 190-201.

9. Мельников И.А., Монкус В.В., Тамм Б.Г. Обзор и анализ зарубежных компьютерных обучающих систем в области программирования // Прикладная информатика, Сб. статей под ред. В.М. Савинкова - М.: Финансы и статистика, 1989, стр. 131-153.

Ю.Озолинь М.Э. Способ представления знаний в автоматизированной обучающей системе // Диалоговые системы и представление знаний. Труды по искусственному интеллекту IV - Тарту: 1981, стр. 89-101.

П.Петрушин В.А. Экспертно-обучающие системы - Киев: Наукова Думка, 1992.

П.Петрушин В.А. Интеллектуальные обучающие системы: архитектура и методы реализации (обзор) // Известия РАН, Техническая Кибернетика, №2, 1993, стр. 164-189.

13 Андерсон Р. Доказательство правильности программ - М.: Мир, 1982.

14.Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции, Том 1 -М.: Мир, 1979.

15. Дарлингтон Дж. Синтез нескольких алгоритмов сортировки // Кибернетический сборник, Вып. 18 -М.: Мир, 1981, стр. 141-176.

16.Климов A.B., Романенко С.А. Метавычислитель для языка Рефал. Основные понятия и примеры, препринт Ин. прикл. матем. им. М.В. Келдыша АН СССР, 1987, № 71.

17.Лавров С.С., Сигаладзе Г.С. Автоматическая обработка данных. Язык Лисп и его реализация - М.: Наука, 1978.

18-Пилыциков В.Н. Язык Плэнер - М.: Наука, 1983.

19.Базисный Рефал и его реализация на вычислительных машинах - М.: ЦНИПИАСС, 1977.

20.Романенко С.А. Метаалгоритмический язык Рефал и тенденции его развития // Искусственный интеллект: в 3-х кн., Кн. 3, Программные и аппаратные средства: Справочник -М.: Радио и связь, 1990, стр. 47-55.

21.Турчин В.Ф. Эквивалентные преобразования программ на Рефале // Автоматизированная система управления строительством - М.: ЦНИПИАСС, 1974, вып. 4, стр. 36-68.

22.Турчин В.Ф. Эквивалентные преобразования рекурсивных функций, описанных на языке Рефал // Теория языков и методы построения систем программирования. Труды Симпозиума, Киев-Алушта: 1972, стр.31-42.

23.Филд А., Харрисон П. Функциональное программирование - М.: Мир, 1993.

24.Хювенен Э., Сеппянен Й. Мир Лиспа: в 2 томах. Том 1. - М.: Мир, 1990.

25.Adam A., Gloess P., Laurent J.P. An Interactive Tool For Program Manipulation // Automatic Program Construction Techniques - Colier Macmillan Publishers: London, стр. 123-138.

26.Adam A., Laurent J.P. LAURA: a system to debug programs // Artificial Intelligence, V. 14, 1980, стр. 75-122.

27.Anderson J.R., Skwareski E. The automated tutoring of introductory computer programming // Communications of ACM 29(9), 1986, стр. 842849.

28.Barr A., Beard M., Atkinson R.C. The computer as tutorial laboratory: the Stanford BIP project // Intern. Journal on the Man-Machine Stud., V.8, N5, 1976, стр. 567-596.

29.Back R.J. Invariant Based Programs And Their Correctness // Automatic Program Construction Techniques - Colier Macmillan Publishers: London, стр. 223-242.

30.Brusilovsky P., Schwarz E., Weber G. ELM-ART: An intelligent tutoring system on World Wide Web // Third International Conference on Intelligent Tutoring Systems, ITS-96, Monreal, 1996.

31.Detienne F., Soloway E. An empirically-derived control structure for the process of program understanding // Intern. Journal Man-Machine Stud., 33(3), 1990, стр. 323-342.

32.Koffman E.B., Blount S.E. Artificial intelligence and automatic programming in CAI // Artificial Intelligence, V. 6, 1975, стр. 215-234.

33.Linn M.V., Clancy M.J. Can experts' explanations help students develop program design skills? // Intern. Journal on the Man-Machine Stud., 36(4), 1992, стр. 511-551.

34.Nwana H. Intelligent Tutoring systems: an overview // Artificial Intelligence Review, 4(4), 1990, стр. 251-277.

35.Rist R.S. Variability in program design: The interaction of process with knowledge // Intern. Journal Man-Machine Stud., 33(3), 1990, стр. 305-322.

36.Sokolinicki T. Towards knowledge-based tutors: a survey and appraisal of intelligent tutoring systems // Knowledge Engineering Review, 6(2), 1991, стр. 59-95.

37.Trafton J.G., Reiser B.J. Proving natural representation to facilitate novices' understanding in a new domain: forward and backward reasoning in programming // Proc. 13th Annual Conf. Cognitive Science Soc., Chicago, 7-10 Aug., 1991, стр 923-927.

38.Boyer R.S., Moore J.S. Proving Theorems About LISP Functions // Journal of the ACM, V. 22, N 1, 1975, стр. 129-144.

39.Burstall R.M., Darligton J. A transformation System for Developing Recursive Programs // Journal of the Association for Computing Machinery, V. 24, 1977, № 1, стр. 44-67.

40.Murray W.R. Heuristic and Formal Methods in Automatic Program Debugging // 9-th International Joint Conference on Artificial Intelligence, Los Angelos, 1985, стр. 15-19.

41.Turchin V. REFAL-5, Programming Guide and Reference Manual - New England Publishing Co.: Holyoke, 1989.

42.Gruzdeva N.V. Programming knowledge in ITS for learning functional programming // Proc. of the 10-th Annual Meeting of the PPIG, 5Л-7Л January 1998, Kmi, Open University, стр. 115-116.

43.Груздева H.B., Юськаева P.P. Система обучения функциональному программированию // Тезисы докладов конференции "Ломоносов-98", М: МГУ, 1998 (в печати).

44.Болыпакова Е.И., Груздева Н.В. Проверка правильности программ в системе обучения функциональному программированию // Вестник Моск. Ун-та, Сер. 15, Вычисл. матем. и киберн., 1999, № 2 (в печати).

Приложение 1 Синтаксис языка Рефал-2

<программа> ::= <определение функций> <определение функций> : := <определение функции> |

<определение функции> <определение функций>

Определение функции> ::= <имя функции> <тело функции> <имя функции> ::= <идентификатор> <тело функции> ::= последовательность правил> <последовательность правил> ::= <правило> |

<правило> <последовательность правил>

<правило> ::= <левая часть> = <правая часть> |

Я <левая часть>=<правая часть> Каждое правило (предложение) в теле функции располагается на отдельной строке, а если правило очень длинное - не помещается на одной строке - оно может быть продолжено на следующую, для чего в конце продолжаемой строки ставится символ '+'.

<левая часть> ::= <образец>

<образец> ::= <выражение без функциональных скобок>

<правая часть> ::= <выражение>

<выражение> : := <пусто> | <терм> <выражение>

<терм> ::= <символ> | <переменная> | <структурный терм> |

<функциональный терм>

<структурный терм> ::= (<выражение>)

функциональный терм> ::= < <идентификатор> <выражение> >

<символ> ::= <символ-литера> | <составной символ> <символ-литера> ::= '<литера>'

<составной символ> ::= <символ-метка> | <символ-цифра> <символ-метка> ::= /<идентификатор>/ <символ-цифра> ::= /<целое без знака>/ <переменная> ::= <признак типа> <спецификатор> <индекс> <признак типа> ::= Б | W | Е | V <спецификатор> ::= <пусто> | (<спецификация>) <спецификация> ::= последовательность элементов> <последовательность элементов> ::= <элемент> |

<последовательность элементов> <элемент>

<элемент> ::= <одноэлементное множество> | <стандартное множество> <одноэлементное множество> ::= <символ> <стандартное множество> ::= Е ( В | Б | N | О <индекс> ::= <буква> | <цифра>

Е - множество прописных букв О - множество десятичных цифр Б - множество символ-меток N - множество символ-цифр О - множество символ-литер

В приведенных металингвистических формулах жирным шрифтом выделены специальные внутренние символы Рефала, в том числе и два вида скобок - структурные скобки: ( и ), и функциональные скобки: < и >. Структурные скобки используются для задания структуры во внутреннем представлении выражения, а функциональные - для вызова функции. Любой открывающейся скобке (структурной или функциональной) в

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

8-переменная (переменная типа Б) сопоставляется с одним символом, \¥-переменная - с одним символом или одним структурным термом, У-переменная - с любой непустой последовательностью символов и структурных термов, Е-переменная - с любой (в том числе пустой) последовательностью символов и структурных термов. Разные рефал-переменные должны иметь разные индексы.

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

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

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

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

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

Приложение 2 Шаблоны рефал-программ

1. Шаблоны программ для задач первого типа (задачи обработки неструктурированного текста)

Для всех трех подтипов (удаление, замена и вставка элементов текста) данного типа задач возможны два основных варианта решения: первое основано на алгоритме последовательного выделения элементов слева направо, второе - справа налево.

Первый вариант решения:

БШ Е1 $оЬу$ Е2 = Е1 $new$ <РШ Е2> Е1 = Е1

Второй вариант решения:

БШ Я Е1 $оЬл*$ Е2 = <ПМ Е1>$пе\у$Е2 Е1 =Е1

В этих шаблонах программ - элемент текста, над которым

производится действие, $пе\¥$ - в зависимости от подтипа задачи либо пусто (в случае удаления), либо новый элемент текста (в случае замены), либо $оЬ]$ и вставляемый элементы текста (в случае вставки).

Если элементов текста, над которыми производится какое-либо из перечисленных действий (замена или вставка), больше одного, то шаблоны соответствующих вариантов решения имеют вид:

1) РШ Е1 $оЬ]$ Е2 = Е1 $пе\у$ <БШ Е2>

Е1 = Е1 Р1 $екех1$ = $е1гер1$

2) БШ Я Е1 $о1у$ Е2 = <РШ Е1> $пе\у$ Е2

Е1 =Е1 Р1 $екех!$ = $е1гер1$

Вместо $о1у$ подставляется некоторая рефал-переменная, а вместо $пе\у$ - вызов функции (только для подтипов 2 и 3), в качестве аргумента которой задана эта рефал-переменная. Левая часть единственного правила функции Р1 $еИех1$ - выделяемый элемент текста, а правая часть $е1гер1$ - выражение, на которое он заменяется.

Для задач подтипа 2 - задачи замены символов текста - возможны еще два варианта решения:

1) БШ Е1 $оЬ]$ Е2 = Е1 <БШ $new$ Е2>

Е1 =Е1 $екех1$ = $е1гер1$

2)РШ Я Е1 $оЬу$ Е2 = <РШ El$new$>E2

Е1 = Е1 $екех1$ = $е1гер1$ Для задач подтипов 1 и 2 - удаление и замена элементов текста -возможен еще один вариант решения:

РШ [Я] Е1 $оЬу$ Е2 = <РШ El$new$E2> Е1 =Е1 $еИех1$ = $е1гер1$ В этом решении в первом правиле признак правого отождествления Я может как стоять, так и отсутствовать.

Если в задаче удаляемых или заменяемых элементов текста несколько, возможен вариант решения, шаблон программы которого: БШ [Я] Е1 $оЬ|$ Е2 = <БШ Е1 $new$ Е2> Е1 =Е1

В рефал-программе, построенной из этого шаблона, происходит размножение первого правила этого шаблона: подстановкой вместо $оЬ^$ одного из возможных выделяемых элементов, а вместо $пе\у$ - пусто (для задач подтипа 1) или выражения, на которое должен быть заменен этот элемент (для задач подтипов 2 и 3). Во всех правилах, кроме последнего,

должны либо везде стоять, либо везде отсутствовать признаки Я правого отождествления.

2. Шаблоны программ для задач второго типа (задачи расстановки структурных скобок)

Если в задаче выделяются символы-скобки только одного вида, то шаблон программы:

Е1 $б2$ ЕЗ = <Б1 <¥2 Е1> Е3> Е1 $з1$ ЕЗ = <ЕШ1(Ж> Е1 =Е1

¥2 Я Е1 $з11$ЕЗ =Е1 (ЕЗ ) Е1 =<ЕЮиЖ>

где $в2$ - символ закрывающейся скобки, а $81$ - символ открывающейся скобки.

Если символов-скобок несколько видов, то шаблон программы: Е1 $М2$ )2 ЕЗ = <Б1 <¥2 Е1 82>ЕЗ> Е1 8( $М1$ )2 ЕЗ = <ЕМ1(Ж> Е1 = Е1

¥2 К Е1 8($М1$)2ЕЗ = Е1 <БЗ 82 Е3> Е1= <ЕШ1(Ж>

¥3 $81$ Е2 $82$ = Е1 ($в11$ Е2 $э12$) Е1 =<ЕЯЯОЯ>

где $М1$ и $М2$ - множества, состоящие соответственно из символов открывающихся и символов закрывающихся скобок и получаемые из спецификации задачи. В рефал-программе, построенной из этого шаблона, происходит размножение первого правила функции БЗ: вместо $э1$ подставляется очередной символ открывающейся скобки, а вместо $з2$ - соответствующий ему (парный) символ закрывающейся скобки.

3. Шаблоны программ для задач первого подтипа третьего типа

(задачи подсчета символов текста)

В задачах этого типа возможно 2 способа решения - с использованием накопителя и без.

Во всех шаблонах программ с использованием накопителя специальный параметр $зит$ обозначает одно из двух выражений:

(Е1)/1/> или <АБВ(/1/) Е1>. Выделение элементов слева направо, накопитель перед выражением: БШ Е1 = <Б1 (/О/) Е1> Б1 (Е1) Е2 $оЬЗ$ ЕЗ = <Б1 ($8ит$) Е3> (Е1) Е2 = Е1

Выделение элементов справа налево, накопитель перед выражением: БШ Е1 =<Б1 (/0/)Е1>

Я (Е1) Е2 ЕЗ = <Б1 ($зит$) Е2> (Е1)Е2 = Е1

Выделение элементов слева направо, накопитель после выражения: БШ Е1 = <Б1 Е1(/0/)>

Е2$о^$ЕЗ (Е1) = <Р1 Е3($зшп$)> Е2(Е1) = Е1

Выделение элементов справа налево, накопитель после выражения: БШ Е1 =<Б1 Е1(/0/)>

Я Е2 $оЬ]$ ЕЗ (Е1) = <Б1 Е2 ($зиш$)> Е2 (Е1) = Е1

Варианты программ с накопителем и с удалением из текста $оЬ]$ -объекта подсчета:

1)РШ Е1 = <Б1 (/О/) Е1>

Б1 [Я] (Е1) Е2 $оЪз$ ЕЗ = <Б 1 ($8ит$) Е2 Е3> (Е1)Е2 = Е1

2)БШ Е1=<Б1 Е1(/0/)>

[Я] Е2 $о^$ ЕЗ (Е1) = <Б1 Е2 ЕЗ ($зит$)> Е2 (Е1) = Е1

Если объектов подсчета $оЬ]$ несколько, то применимы следующие два шаблона программ:

1)РШ Е1 =<Б1 (/0/)Е1>

¥1 [К] (Е1) Е2 $ ЕЗ = 1 ($зит$) Е2 Е3> (Е1)Е2 = Е1

2)БШ Е1 = <Б1 Е1(/0/)>

П [Я] Е2 $о1у$ ЕЗ (Е1) = <¥\ Е2 ЕЗ ($зит$)> Е2(Е1) = Е1

Шаблоны программ рекурсивного решения, без использования накопителя:

Выделение элементов слева направо:

1) БШ Е1 $оЬ]$ Е2 = (/1/) <БШ Е2»

Е1 = /0/

2) БШ Е1 $оЬ]$ Е2 = <ADD (<РШ Е2>) /1 />

Е1 = /0/

Выделение элементов справа налево:

1) БШ Я Е1 $оЬ)$ Е2 = (/1/) <БШ Е1»

Е1 = /0/

2) БШ Я Е1 Е2 = <АОО (<РШ Е1>) /1/>

Е1 =/0/

Варианты рекурсивных решений с удалением из текста $оЬ]$ - объекта подсчета:

1) БШ [Ы] Е1 $оЬ)$ Е2 - <АББ (/1/) <БШ Е1 Е2»

Е1 = /О/

2) БШ [Я] Е1 Е2 = <АББ (<БШ Е1 Е2>) /1/>

Е1 = /0/

Если элементов подсчета несколько, то для каждого из последних двух шаблонов могут быть получены две рефал-программы: первая программа - подстановкой вместо рефал-переменной (сопоставляемой со всеми

объектами подсчета), вторая программа - размножением первой строки шаблона.

4. Шаблоны фрагментов программ (функций) для задач пятого типа (задачи вычисления арифметических выражений)

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

В качестве правой части может быть задан один из трех вариантов:

1)<ОР БЗ (<Б1 У1>) <¥2 V2» Для этого варианта шаблон функции: ОР $ор$ $ехрг$ = <$8ТРЩ $ехрг$>

Все правила синтезируемой функции ОР получаются размножением данного правила заменой $ор$ на символ-знак операции, $8ТРЫ$ - на соответствующую этому символу стандартную (встроенную) рефал-функцию ('+' соответствует функция АЭО, соответствует 811В и т.д.), $ехрг$ - на одно из двух выражений VI или (VI) У2.

2) <ОР (<Р1 У1>) 83 <Р2 У2» Для этого варианта шаблон:

ОР $ехрг 1 $ $ор$ $ехрг2$ = <$8ТРШ ($ехрг 1 $) $ехрг2$>

Где $ехрг1$ и $ехрг2$ разные (т.е. с разными индексами) рефал-

переменные любого типа, а $ор$ и $STFN$ заменяются соответственно на

символ-знак операции и соответствующую этому символу встроенную

функцию.

3)<ОР (<Б1 У1>) <Р2 У2> 83> Для третьего варианта шаблон:

ОР $ехрг$ $ор$ = <$81ТШ $ехрг$>

где $ор$ - символ-знак операции, $8ТРЫ$ - соответствующая этому символу стандартная (встроенная) функция, $ехрг$ - одно из двух выражений: VI или (VI) У2.