66465

Повышение эффективности базового обучения информатике за счет предоставления её теоретических образующих

Дипломная

Информатика, кибернетика и программирование

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

Русский

2014-08-21

1.19 MB

0 чел.

58

Оглавление

1.Введение........................................................................................3                                                                                       

1.1Общие аспекты связанные с обучающими системами.

1.2 Позиция в отношении к предмету.

1.3 Особенности и составляющие обучения.

1.4 Развивающее обучение в высшей школе.

1.5 Современный аксиоматический метод.

1.6. Обучающая система FLINT.

1.6.1. Версии системы FLINT.01.95 и FLINT.Р01.96 .

1.6.2. Версия системы FLINT.02.97 .

1.6.2.1 Среда информационного моделирования.

1.6.2.2. Модель обучаемого.

1.6.2.3. Модель предметной области.

1.6.2.4. Модель системы.

2. Постановка задачи...................................................................16

2.1. Учащийся - теоретик.

  2.2.  Общая концепция системы (FLINT.03.98).

2.2.1. Модель теоретической самоорганизации на основе информатики.

  2.2.2. Информатика для базового обучения.

2.3. Экспериментальный прототип системы (FLINT.Р02.98).

   2.3.1. Априорный класс обучаемого - прагматик.

   2.3.2. Концептуальная иерархия учебного материала.

   2.3.3. База данных.

   2.3.4. Обучение в прототипе.  

2.4. Задача дипломной работы......................................................................24

   2.4.1. Согласование стилей программирования.

   2.4.2. Собственная задача...........................................................................25

  1.  Положение дел с Предметной Областью у предшественников.

3. Основная теоретическая часть. .............................................................26

3.1. Введение в аппликативное программирование.

  3.1.1. Идея: понятие функции.

  3.1.2. Основное отличие чистых функций от функций императивных языков.

3.2. Логика обоснования идеи........................................................................29

  3.2.1. Бестиповое -исчисление. Определения.

  3.2.2. Бестиповая комбинаторная логика (на пути к реализации).

     3.2.2.1. Необходимость введения.

     3.2.2.2. Комбинаторная логика. Основные определения.

3.3.  Реализация................................................................................................35

  3.3.1. Энергичные и ленивые вычисления.

  3.3.2. Редукция графов в -исчислении.

  3.3.3. Комбинаторная редукция с помощью графов.

  3.3.4. Неподвижная точка и рекурсия.

    3.3.4.1. Неподвижная точка в -теории.

    3.3.4.2. Теорема о неподвижной точке.

    3.3.4.3. Практическая роль теоремы в программировании.

    3.3.4.4. Пример на неподвижную точку.

  3.3.5. Однородные средства в аппликативном стиле.

  3.3.6. Смешанные вычисления.

3.4. Сравнения реальных языков программирования......................54 

  3.4.1. Норе.

  3.4.2. Миранда.

  3.4.3. Лисп.

   3.4.4. FP.

       3.4.4.1. Некоторые примеры программ на языке FP.

  1.  Резюме сравнения языков.
  2.  Заключение.................................................................................60

Список литературы.....................................................................61

Приложения..................................................................................62


1
.Введение.

      Дипломная работа выполнена в рамках проекта “Компьютерный комплекс обучения основам информатики” (грант 96-01-00306 РФФИ, научный руководитель проф. Трифонов Н.П., ответственный исполнитель н.с. Громыко В.И.) и соглашения о совместной научной работе между факультетами математики и информатики  FSU - Jena (Prof. G.Wechsung), Германия и факультетом ВМиК по теме “Учебные пособия и обучающие системы в области информатики” с консультационным участием Prof. M.Broy, Prof. A.Blaser .

Суть проекта состоит в разработке системы базового обучения информатике студентов ВУЗов, которая должна отличаться от широко распространенных в настоящее время систем :

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

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

1.1. Общие аспекты, связанные с обучающими системами.

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

Первые эксперименты по применению ЭВМ в обучении относятся к началу 60-х годов. Но идея создания и использования  обучающих машин возникла задолго до того, как она получила соответствующую техническую базу для своей реализации. Теоретические основы конструирования и применения обучающих машин были заложены еще в 1920-х годах и связаны с именем С.Пресси (1926 г.). Первые машины представляли собой механические или механо-электрические устройства, предназначенные для контроля знаний и обучения. Расцвет данного направления приходится на 1950-60 гг., затем наступил кризис, выход из которого  планировался в замене обучающих машин универсальным средством  обработки информации - ЭВМ.

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

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

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

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

1) информационно-справочное обслуживание (предъявление учебного материала, которое можно организовать как по желанию ученика, так и по результатам тестирования - система советует, с чего начинать).   

2) решение задач (причем правильный или неправильный вариант ответа сопровождается “живой” реакцией системы);

3) построение моделей объектов.

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

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

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

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

ответ обучаемого сравнивается с эталонным решением и на  основании различий производится диагностика ошибок обучаемого;

по результатам диагностики корректируются  текущие  характеристики обучаемого.

Таким образом, сразу заметно отличие ИОС от традиционных ОС - это наличие обратной связи.

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

ЭС по решению задач в изучаемой ПО;

ЭС по диагностике ошибок обучаемого;

ЭС по планированию процесса управления учением.

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

Классификация ИОС в соответствии с целями функционирования:

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

2) Диагностирующая (демонстрирующая). Предназначена  для  указания  учащемуся  на его неправильные представления о предметной области, в следствие которых он допускает ошибки при решении определенного типа задач.

3) Управляющая. Предназначена  для  управления  познавательной  деятельности обучаемого. Является расширением диагностирующей ИОС знаниями о целях функционирования системы, имеющимися в учебном материале и стратегии обучения.

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

Типы и состав интеллектуальных обучающих систем.

Тип ИОС

Состав

Консультационная

Учебная среда

Объяснение

Диагностирующая

Решатель задач

Диагностика

Модель обучаемого

Управляющая

Решатель задач

Диагностика

Управление учением

Модель обучаемого

Сопровождающая

Инструментальная система

Диагностика

Управление учением

Модель пользователя

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

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

1.2. Позиция в отношении к предмету.

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

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

Конкретизация РО для базового обучения информатике, которое выстраивается на прагматике предмета - программировании, проводится с учетом его современных проблем. На этом пути привлекательны конструктивностью позиции Н. Вирта и Ч. Э. Р. Хоара. Первый призывает осмысливать собственные информационные проблемы посредством моделирования подходящего языка программирования (послужной список созданных им языков впечатляет: Эйлер, Алгол-W, Паскаль, Модула, Модула-2, Оберон). Тем самым он фиксирует внимание на необходимости поднимать прагматические проблемы любой деятельности по конструированию в программировании до высот их обобщенного, абстрактного восприятия. Второй неоднократно демонстрировал конструктивную мощь взаимодополняющих семантик: реализаторской, пользовательской (проблемно-ориентированной) и авторской (выражающей “идеальную”, идейную суть предметной области). Состояние дела обучения уже предлагает нам удачные образцы синтезирующего предъявления семантик. Книга А. Филда, П. Харрисона “Функциональное программирование” (1988г., у нас 1993г.) решает проблему связного изложения семантик для функциональных языков. Конечно же, в новом не все получается с первой попытки. Например, не удалось в качестве авторской семантики предложить модели -исчислений и комбинаторных алгебр. Но вопрос этот ставится и обсуждается на основании доверия к сообщенным математическим фактам. Приведем еще один пример новаторства  - учебник (в четырех частях - 1200 страниц) “Информатика. Основополагающее введение” профессора М. Броя (M. Broy), лауреата премии Лейбница Германской академии наук за 1993г., одного из лидеров немецкой теоретической школы, преемника и ученика Ф. Л. Бауэра (F. L. Bauer). Он продолжает традицию концептуального взгляда на предмет, заложенную в известном учебнике Ф. Л. Бауэра и Д. Гооза (G. Goos) “Информатика”. В первой части предлагается введение в информатику на основе аппликативной среды информационного моделирования. В остальных частях рассмотрены вопросы устройства современных базовых вычислителей, устройства языков программирования, эффективности вычислений. В целом, наша позиция исследования отличается от приведенных двумя моментами: ориентацией на привлечение к обучению разных сред информационного моделирования; еще большим вниманием к  концептуальности (современный аксиоматический метод) в отношении предмета информатики и особой заботой о восприятии обучаемым предлагаемого (логика открытия).

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

1.3. Особенности и составляющие обучения.

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

Авторитет Эдсгера Дейкстра с его книгами “Краткое введение в искусство программирования” /71 г./ и затем “Дисциплина программирования” /76 г./ говорит: “... я чувствую себя сродни преподавателю композиции в консерватории. Он не учит своих подопечных тому, как следует писать конкретную симфонию, но он должен помочь им обрести собственный стиль и объяснить, что под этим подразумевается”. Но время требует в обучении большего - максимального развития творческих особенностей интеллекта. Таким образом, предыдущее обучение - “преподаватель композиции” становится только необходимой составной частью. Теперь нужен “преподаватель сочинительства”.

Противоречие между наукоемкостью теоретических понятий и неподготовленностью обучаемого (студента-первокурсника) решается методом РО. Метод состоит в подключении творческих возможностей интеллекта обучаемого при овладении предметом. Общей целью является развитие у обучаемого умения воспринимать, предъявлять и исследовать знания. Метод РО ориентирует на предъявление предметной области (ПО) как среды развития для логики открытия (ЛО) обучаемым предмета, то есть для его творческой деятельности по самостоятельному переоткрытию предмета, и на этом основании формированию универсального качества интеллекта - теоретической адаптивности. Общая цель конкретизируется посредством РО при её разработке в отношении базового обучения информатике. Этому служат: учет системологического подхода к развитию научной культуры от века машин к веку систем; восприятие информатики как дальнейшего азвития математического механизма по своевременному приобщению нашего интеллекта к познающему научному разуму века машин и к созидающему разуму века систем; понимание предмета при базовом обучении широко, как симбиоза программирования, математики (логики) и информатики. Таким образом, конкретной целью обучения является приобщение обучаемого на предмете к интеллектуальному состоянию, которое свойственно системному аналитику. То есть комплекс должен обеспечить учащегося понятийными средствами об инструментах информационного моделирования для предъявления знания для его исследования, причем сократовским методом обучения (посредством логики открытия).

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

учебник, выстроенный традиционно на основе логики обоснования предмета, который послужит основой для курса лекций; но выбранные темы соответствуют цели - теоретическому кругозору;

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

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

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

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

Комплекс является сложной системой, архитектура которой фиксирует иерархию проблем обучения, связанных с «восхождением» интеллекта к Теоретическому Мышлению.

              1.4. Развивающее обучение в высшей школе.

Сегодня РО чаще всего используется в среднем образовании. Мы применяем его в высшей школе, создавая курс информатики для студентов университетов и технических ВУЗ’ов первых двух годов обучения. Все базовые курсы отличаются высокими запросами к творческим способностям, т.к. имеют широкую область определения предмета. Увеличение трудности РО в высшей школе обязано сложностью (наукоемкостью) для начинающего понятий, используемых для обеспечения целеполагания. Кроме того, чем старше контингент обучаемых, тем труднее его приобщить к умению адаптироваться. Наконец, в информатике приходится сталкиваться также с ранним профессионализмом, связанным с полнотой узкого круга понятий.

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

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

   1.5.  Современный аксиоматический метод.

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

Историческое движение в направлении современного аксиоматического метода мы видим в следующих двигающихся навстречу друг другу тенденциях:

от программирования:

 Алгоритмы + Структуры данных = Программа;

от информатики:

 Универсальная алгебра + Логика = Теория моделей  АТД.

Движение соответствует прагматическому сближению программирования с предметной областью, т.е. от “как делать” к ”что делать”, причем с большим вниманием к тому “как это делается”. Результатом является

САМ = АМ(аксиоматический метод, алгебраическая система, по Б. ван дер Вардену)  +                 Язык предъявления АМ(формальная теория, по Д.Гильберту) +    Конструктивная модель (эрбрановская), фиксирующая ИСТИННОСТЬ

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

                    1.6. Обучающая система FLINT.

Перейдем теперь к системе FLINT и рассмотрим, что нового несет в себе этот проект и какие принципы в него заложены.

Система обучения информатике FLINT (Friendly  Intelligent Tutor) основана на учебнике и компьютерном практикуме. Общее направление работы состоит в развитии творческих возможностей человека при обучении предмету. Применен подход теории развивающего обучения (РО), который определяющую роль отводит необходимому атрибуту творчества - теоретическому мышлению.

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

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

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

Развивающее обучение - максимально мировоззренческое видение мира. Учим человека делать открытия на основе познавательной инверсии.

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

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

Таким образом,  целью  обучения  (и компьютерной системы) является - способствовать саморазвитию  обучаемого  (развитие саморазвития).  Компьтерная система обучения FLINT как раз и нацелена на конкретизацию принципов Развивающего Обучения  (РО)  для базового обучения информатике.

  1.  Версия системы FLINT.01.95 и FLINT.Р01.96 .

Система FLINT уже имеет свою историю. Первой теоретической версией системы, явно сформулированной, является модель системы, описанная в публикации в журнале “Педагогика и Информатика” №2 за 95 год.  Дадим ей идентификатор FLINT.01.95. Она характеризуется “разорванностью”. Эта система состояла из пяти независимых, не связанных между собой блоков, с каждым из которых можно было работать независимо от других, и которые не образовывали единого, связного представления информации. Этой модели соответствовал демонстрационный вариант, которому присвоим идентификатор FLINT.Р01.96 (Р - означает реализация). Данная модель была реализована в виде интерактивной системы и базы данных. Работа с информационной средой осуществлялась в форме диалога, реализованного в Windows 3.1. Диалог состоял из двух основных этапов. На первом этапе система предлагала пользователю ознакомится с учебной задачей, т.е. узнать информацию о том, что она собой представляет, кем создана, какие задачи решает, и перейти непосредственно ко второму этапу - обучению. Диалог с информационной средой готовился с помощью редактора базы данных, предназначенного для внутреннего использования в системе. С помощью него осуществлялось также необходимое наполнение и редактирование понятий и задач предметной области, для каждого из которых существовал отдельный файл. Весь материал в системе находился в одном файле в виде внутреннего представления базы данных системы, который создавался компилятором после обработки множества файлов с понятиями и задачами. Таким образом, существовала жестко фиксированная схема представления предметной области, изменить которую можно было только перекомпилировав всю базу.

1.6.2. Версия системы FLINT.02.97 .

Вторая теоретическая версия системы (FLINT.02.97) описана в дипломе 97г. Маханько И. и в статье “Модели для базового обучения информатике в высшей школе”, опубликованной в журнале “Математика. Компьютеры. Образование”. Она описывается также ниже.

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

Третья теоретическая версия системы FLINT.03.98 (пункт 2.1) является следствием уточнений, вызванных реализацией FLINT.Р02.98. Это естественно - конструирование тотчас же меняет (уточняет) представление о задаче (принцип неопределенности Мартина).

1.6.2.1 Среда информационного моделирования.

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

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

Вообще говоря, модель имеет отношение к ответу на вопрос Как _Учить?, но естественно через фиксирование ключевых моментов по вопросу Чему _Учить?.

  1.  Модель обучаемого.

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

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

                                   

Модель обучаемого

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

Модель отвечает на вопрос Кого _Учить?. Общий ответ (относительно рационального мышления) - творческую личность системно- информационного состояния науки. Конкретный ответ (в рамках предмета ) - системного аналитика предъявлению знания для исследования.

1.6.2.3. Модель предметной области.

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

материал для НАЧИНАЮЩЕГО -  строится с пониманием начального состояния обучаемого в современной рациональной культуре; строится также с использованием познавательной инверсии посредством сред раннего целеполагания; здесь закладывается понимание абстракций через логику открытия.

материал для ПРОФЕССИОНАЛА, УНИВЕРСАЛА - строится на взаимодействии  Логики Обоснования и Логики Открытия, т.к. выстраивается, с одной стороны, на материале НАЧИНАЮЩЕГО , с другой стороны , его доводим до элементов соответствующей теории;

материал для ЛИЧНОСТИ - строится на Логике Обоснования необходимых теорий, т.е. связан с  Теоретическим Мышлением.

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

Модель ПО отвечает на вопрос Чему _Учить? - согласованному использованию Логики Обоснования и Логики Открытия для переоткрытия (творческого ) свойств предмета.


1.6.2.4. Модель системы.

Модель системы предполагается как сложная система, архитектура которой фиксирует иерархию проблем обучения , связанных с “восхождением” интеллекта к Теоретическому Мышлению. Функционально также фиксируется связь блоков иерархий через взаимодействие на основе Динамической Модели Обучаемого. Это связано с тем, что предполагается работа системы на интерактивном взаимодействии с ней обучаемого, т.е. исключаются детерминированные схемы действий. Это естественное требование на систему,  поддерживающую РО . Поэтому столь высоки требования на подготовку материала ПО.

Где: БУ - Блок Учителя, БО - Блок Обучаемого, БПО - Блок Предметной Области, ДМО - Динамическая Модель Обучаемого.

Тактика 1. Познавательная инверсия для ассимиляции идей теоретических вычислителей.

Тактика 2. Аккомодация теоретического мышления в отношении главных ориентиров среды информационного моделирования на основе наследуемых ориентиров (теории, являющиеся основой программирования).

Тактика 3. Логика открытия на основе планов по самоорганизации рефлексирующего эпистемолога (повторение в онтогенезе мышления филогенеза культуры).

2. Постановка задачи.

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

2.1. Учащийся теоретик.

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

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

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

  1.  способности к познанию посредством зоны ближайшего развития (ЗБР) (ПО готовится, как среда развития; в соответствии с ней работает система);

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

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

2. Системологическая самоорганизация (самоорганизация в век систем). Этому соответствует деятельность учащегося на основе системологического существа среды информационного моделирования. Конкретно, обеспечивается деятельность, направленная на создание продукта на компьютере. Эта проблема разрешается в системе в полном объеме посредством заданий практикума, которые предполагают получение законченного продукта.

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

3. Познавательная инверсия для восприятия идеи САМ, конструктивности (более узко - здесь работает БПО). Эта задача естественным образом распадается на следующие:

3.1. Элементы теорий: ПИ для идей различных стилей программирования. Обеспечивается деятельность по активному включению целеполагания учащегося в точках "роста". Это значит, что идею надо развивать с той точки зрения, что любой человек повторяет развитие культуры, в которой он существует (генотип повторяет фенотип).

3.2. Логика обоснования теории. Обеспечивается формальная логическая деятельность учащегося для его понимания теоретического существа предмета. Тогда возникает ассимиляция рационального, исходя из его существа - рациональное служит в первую очередь обоснованию (а не открытию). Конкретно, обеспечивается деятельность, связанная с доказательством в рамках теорий различных стилей программирования.

3.3. Логика открытия логик обоснования теории, с помощью которой обеспечивается восприятие целого. Понимание элементов теории становится естественным на основании нового уровня целеполагания. Этому служит сравнение теорий между собой, представление их в целом и в сопоставлении к общему рациональному, т. е. САМ.

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

5. Теоретическое системологическое мышление: логика открытия логик обоснования конструктивности САМ (более узко - в системе этому служит специальный блок - БУ, это максимальная теоретическая самоорганизация, которая обеспечивается системой).

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

Педагогика сотрудничества, в которой субъект и объект объединены и оба являются субъектами творчества, представляется неотъемлемой частью не только будущего комплекса обучения, но и его ранних "неполных" реализаций. Т. е. необходима интерактивная среда обучения, "наблюдение" за текущим состоянием обучаемого (в том числе и самонаблюдение), его ближайшей областью развития, чему служит динамическая модель обучаемого (ДМО). Еще раз повторимся, что главная проблема - обеспечение самоорганизации учащегося - решается на функциональном уровне.

2.2. Общая концепция системы (FLINT.03.98).

Реализация системы уточняет позицию в отношении теоретических концепций системы. Ниже фиксируется соответствующие изменения по отношению к предыдущей версии системы FLINT.02.97 (пункт 1.4.2).

Система обучения информатике FLINT (FriendLy INtellegent Tutor - “дружественный интеллектуальный учитель”) должна использовать способность человека к познанию для его теоретической самоорганизации на основании предмета и тем самым для овладения этим предметом. Система предназначена для обучения студентов первого курса Высших Учебных Заведений основам информатики на базе конструктивных продвижений математики XX века, что в прагматическом (программистском) плане соответствует разнообразию сред информационного моделирования (стили программирования), с применением соответствующего задаче метода обучения - Развивающего обучения. Для обучаемого создается среда саморазвития, которая должна поднять его конструирующий уровень (в программировании) на основании его концептуального саморазвития в отношении конструктивных достижений информатики.

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

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

2.2.1. Модель теоретической самоорганизации на основе информатики.

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

Классам обучаемого соответствует следующие стратегические понятия (концепции):

Соответствие предметов классам, категориям обучаемого и теоретической самоорганизации, следующее:

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

2.2.2. Информатика для базового обучения.

Новое понимание предметов в ракурсе информатики для базового обучения, следующее:

а) Программирование осталось без изменений.

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

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

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

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

2.3. Эксперементальный прототип системы (FLINT.Р02.98).

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

На данный момент система FLINT представлена эксперементальным прототипом. Этот прототип состоит из двух частей: редактора базы и визуализатора. Редактор предназначен для наполнения и редактирования предметной области, а визуализатор - для предъявления информации обучаемому в удобном для него виде, в соответствии с Динамической Моделью Обучаемого.

2.3.1. Апприорный класс обучаемого - прагматик.

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

Соответствие атрибутов формируемого целеполагания обучаемого, следующие:

2.3.2. Концептуальная иерархия предъявления материала.

Рассотрим концептуальную иерархию предъявления материала в Предметной Области. Она имеет следующий вид:

Стратегия

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

2.3.3. База данных.

Материал для предметной области состоит из понятий, примеров и задач, принадлежащих соответствующему стилю (в данный момент в системе существует пять стилей: Императивный, Объектно-ориентированыый, Логический, Аппликативный и Марковский). Каждое понятие имеет окрестность “вширь” (глобальную, соответствующую стратегии системы по обеспечению концептуального саморазвития обучаемого), окрестность “вглубь” (локальную, соответствующую тактике системы по обеспечению оснований для деятельности обучаемого в его ближайшем незнаемом (зона ближайшего развития)), окрестность задач и окрестность примеров. В глобальной окрестности находятся общие для всех стилей, фундаментальные понятия (например информатика, программирование),  в локальной - понятия, тесно связанные с данным стилем, в окрестности задач и примеров - соответственно задачи и примеры, относящиеся к данному стилю.

2.3.4. Обучение в прототипе.

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

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

Схема Базы Данных FLINT:

Схему эксперементального прототипа системы FLINT (см. приложение D).

2.4. Задача дипломной работы.

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

2.4.1. Согласование стилей программирования.

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

Выбранный принцип позволяет дифференцировать стили программирования по значению для САМ и разработать их в соответствии с такой дифференциацией:

  1.  Императивный стиль. Демонстрирует основы вычислимости, основываясь на согласованном предъявлении данных и исполнения, уровне спецификаций (преобразователи предикатов, аксиоматический метод).

Объектно-ориентированное программирование. Демонстрирует основы вычислимости, основываясь на классическом предъявлении систем. Здесь особенно интересны два направления: наследуемость и параллельность.

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

Аппликативный стиль. Рассматривается как альтернатива САМ (т. к. в нем нет иерархии носителя и его свойств). Этот стиль представляет новые возможности в рамках собственных средств в программировании.

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

2.4.2. Собственная задача.

В данной дипломной работе рассматривается аппликативный стиль в контексте описанных выше принципов.

Работа должна состоять из двух частей - теоретической и практической.

Теоретическая часть: необходимо рассмотреть аппликативный стиль программирования в двух аспектах: его значение для понимания САМ и внутренние проблемы стиля. Главной идеей для этого стиля является понятие функции, т.е. необходимо разработать среду саморазвития посредством ПИ для этой идеи.

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

  1.  Положение дел с Предметной Областью у предшественников.

  

 В дипломе [] была разработана ИС для абстракции исполнение аппликативного стиля. В дипломе была рассмотрена среда развития для аппликативного стиля и, частично, задание практикума.

  1.  Основная теоретическая часть.

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

  1.  Введение в аппликативное программирование. 

В последнее время появилось довольно большое число языков, преуспевших в отходе от формы традиционного программирования; примером такого рода могут служить аппликативные, или функциональные, языки. Функциональные программы строятся из “чистых” математических функций, которые по сравнению с функциями многих императивных программ свободны от побочных эффектов (т.е. их вычисление не может изменить среду вычислений). Из-за этого нет возможности программировать “с помощью эффекта”, так что сама величина, которая должна быть вычислена программой, и сама программа редуцируются к одному и тому же результату. Выполнение программы тогда становится процессом изменения формы требуемой итоговой величины так, что “8+1” можно заменить на “9”; при этом обе они будут обозначать одну и ту же величину.

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

                                 3.1.1 Идея: понятие функции.

Алгоритмика начинается с понятия функции, точнее, понятия вычислимой функции

(“Функция f называется вычислимой, если существует алгоритм, который для любого аргумента x (в качестве входа для алгоритма) вычисляет значение f(x) (как выход алгоритма). В частности высказывание о вычислимости функции зависит от нашего выбора понятия алгоритма” ).

В математике функция есть отображение из множества величин, названного областью определения функции, в объекты из множества, именуемого областью значений функции. Простейший пример функции - функция знак, осуществляющая отображение любого заданного целого числа в одно из значений плюс, минус или нуль в зависимости от того, является ли данное число положительным, отрицательным или равным нулю. Областью  определения функции знак является множество целых чисел, а множеством значений - множество {плюс,минус,нуль}: ... знак(-1)=минус, знак(0)=нуль, знак(1)=плюс... Эта функция отображает каждый элемент из области определения в единственный элемент из области значений функции (т.е не существует неодназначности). Все такие функции называют детерминированным.

Существует много способов задания функций: например графиком, сведение функции к понятию множества (по Дирихле : функция F: AB - это подмножество F A x B, обладающее свойством xA  yB (<x,y>F) ) или используя множество уравнений - по одному уравнению на каждый элемент определения :

...

знак(-2)=минус

знак(-1)=минус

знак(0)=нуль

знак(1)=плюс

знак(2)=плюс

...

Однако, такие представления неудобны. Например  в третьем способе для полной характеристики функции (у нас знак) требуется бесконечное число уравнений .

Т.к мы имеем дело с вычислимостью, то необходимо использовать другие методы .

Например, знак можно опредилить, используя лишь одно правило:

 

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

   плюс, если х>0              

знак(х)= 

              минус, если x<0 - теперь эта функция не определена при х=0.

Традиционное (школьное) представление о функции таково, что если задана формула, то функция тут-же считается. Однако, существуют более сложные функции, например функция Улама, которая задаётся следующим образом:

                 1, если n1                     n/2, если n чётно 

ulam(n)=   , где g(n)=

               ulam(g(n)) иначе         3*n+1 иначе

С первого взгляда на внешний вид этой функции довольно сложно определить, является ли эта функция вычислимой. В действительности эта функция является частично вычислимой, например для чётных значений n значение ulam(n)=1, а для некоторых нечётных n, таких как n=5 получим зацикленную и следовательно незавершимую цепочку вызовов: ulam(5)=ulam(16)=ulam(8)=...ещё 14 вызовов...=ulam(13)=ulam(40)=ulam(20)= ulam(10)=ulam(5)=...  или например ulam(3)=ulam(10)=ulam(5)=... т.е для функции Улама существует целый ряд параметров, для которых завершение вычисления этой функции невозможно.

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

 

В настоящее время не известно алгоритма для вычисления f . Более того, может оказаться, что такого алгоритма нет. В отличии от положения с функцией f мы знаем, что g примитивнорекурсивна. Действительно, или g должна быть константой x.1, или найдется такое k, что

g (x) = 1 для x k ;

g (x) = 0 для k x.

В обоих случаях существует примитивнорекурсивная схема, но никто не знает в настоящее время, как выявить верную схему.

Для построения более простого примера возьмем проблему, не решенную математиками, например проблему Гольдбаха о том, что всякое четное число, большее двух, есть сумма двух простых чисел, и определим функцию h так:

h (x) =

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

Таким образом мы приходим к рассмотрению функции как вычислительного предписания через понятие функции, которая в применении к аргументу выдает вполне определенное значение. В школе вычислительные предписания принимают главным образом вид выражений. Например, f1=(x+2)(x-2) или f2=x2-4. Таким образом, f1 f2, хотя f1(x) = f2(x). Таким образом, смысл функционального выражения в алгоритмике состоит в его сущности как предписания для исполнения одной или нескольких вычислительных операций.

Такие функции как знак можно рассмотреть как объект с входом и выходом, где вход - параметр функции, а выход - результат вычислений:  -4[знак]минус где -4 является фактическим параметром функции, а процесс подачи на вход функции фактического параметра называется применением функции (такой подход называется абстракцией). В математическом виде это можно записать как знак(-4)=минус. Идея того, что функция является механически зафиксированным правилом преобразования входов в выходы - одно из фундаментальных положений функционального программирования. Функция (как объект) является конструктивным блоком для функциональной программы, и с помощью объединения таких блоков можно порождать операции любой сложности - такой процесс называется функциональной композицией.

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

   3.1.2 Основное отличие чистых функций от функций императивных языков программирования

           (денотационная семантика и недостатки императивной семантики).

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

program example(output);

var flag : boolean;

function f (n : integer) : integer;

begin

if flag then f:=n

 else f:=2n;

flag:=not flag

end;

begin

flag:=true;

writeln(f(1)+f(2));

writeln(f(2)+f(1))

end.

После выполнения этой программы на терминал будет выведены два числа: 5 и 4. Однако, это довольно странно, поскольку с математической точки зрения коммутативность сложения позволяет заменять x+y на y+x для любых x и y.

Однако, дело здесь не в изменении самой функции ‘+’. Проблема состоит в том, что функция f сильно отличается от математических функций. Следует обратить внимание на то, что величина  глобальной переменной flag в нашей программе на языке Паскаль имеет возможность изменяться, и именно это уничтожает свойство функциональности языка. Значение же элементарной функции ‘+’ не изменяется. Источником таких проблем в программах на языке Паскаль является операция присваивания flag:=not flag, изменяющая величину flag.

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

   3.2 Логика обоснования идеи.

 3.2.1. Бестиповое лямбда-исчисление. Определения.

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

Остановимся на таком основополагающем понятии, как абстракция (о нём уже упоминалось в пункте 3.1.1) более подробно.

Лямбда-исчисление было разработано в начале 30-х годов А.Чёрчем с целью формализации математического понятия функции, трактуемой как вычислительное предписание (Как заметил Черч, запись  f(х) можно понимать двояко: как функции f, зависящей от аргумента х и как значение f  в точке х. В случае функции нескольких переменных также возникают проблемы: х+у - это функция от х или от у или от х и у? Чтобы избежать двусмысленности, он ввёл новую форму записи). Лямбда-исчисление даёт язык для такого представления функций и выражения некоторых их свойств.

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

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

ЛАМБДА-ПЕРЕМЕННЫЕ предназначены для обозначения произвольных операторов, записываются малыми латинскими буквами x, y, x1, y1, x2, y2,... и т.д.

ЛАМБДА-ТЕРМ 

1.любая переменная => -терм;

2.любые Л-термы M,N => -терм (M N) - применение M к аргументу N;

3.любая переменная x, любой -терм M => -терм (Лx.M) - функция от x, определяемая -термом M; при записи объемлющие скобки можно опускать. Например x.(Mx)(( y.Ny)z) - -терм.

АППЛИКАЦИЯ - (M N) - применение M к аргументу N (в математике аппликацию М к N обычно обозначают через M(N) ). Например ((х.у +х у)1)2).

АБСТРАКЦИЯ - (x.M) - задание функции от аргумента x, определяемой -термом M. Например х.у.*(+ху)2

СВЯЗАННЫМ посредством x называют любое ВХОЖДЕНИЕ переменной x в терм (x.M).

СВОБОДНЫМ называется любое вхождение переменной в терм, не являющееся связанным.Например в терме (v.x)( y.yx(x.yvx)) левое вхождение v является связанным, а правое - свободным; два самых левых вхождения х свободные, а два других - связанные; все три вхождения у - связанные.

Множество всех переменных, имеющих свободные вхождения в М, обозначается через FV(M).

ПОДСТАНОВКА - Для любых -термов M и N и переменной x через [N/x]M обозначается результат подстановки N вместо любого свободного вхождения x в терм M и замены всех y в M так, чтобы свободные переменные из N не стали связанными в [N/x]M (если не производить такой замены, то возможен конфликт имён и результат подстановки может получиться не эквивалентным исходному терму. Например [v/x](x.(v.x))= v.v и [v/x](x.(y.x))= y.v - термы, которые до подстановки были -конвертируемыми (см.далее), а результаты не являются таковыми. Это получилось из-за того, что в первой подстановке переменная v стала связанной в (v.x) чего не возникает при замене).

Пример подстановки: если My.yx, Nvx [(vx)/x](y.yx)y.[(vx)/x](yx) y.y(vx) или если My.yx, Nуx [(уx)/x](y.yx)z.[(yx)/x](zx) z.z(yx), где z - любая переменная (не х и не у).

АЛЬФА-КОНВЕРСИЯ - -терм x.M альфа-конвертируется в -терм y.[y/x]M, если y не является свободной переменной для M: (x).My.[y/x]M если yFV(M) (*).

Если P сводится к Q посредством конечной (возможно пустой) последовательности преобразований вида (*), то говорится, что Q получается из Р заменой связанных переменных или Р -конвертируемо к Q:  PQ. Например z.z и х.х

Терм вида (x.M)N называется БЕТА-РЕДЕКСОМ (он обозначает применение оператора к входному значению).

Если бета-редекс содержится в терме T, и одно из его вхождений заменяется термом [N/x]M, то говорим, что происходит БЕТА-СВЕРТЫВАНИЕ этого вхождения.

Конечная последовательность бета-свертываний и замена всех связанных переменных называется БЕТА-РЕДУКЦИЕЙ. Если такая последовательность конечна и переводит P в Q, то мы говорим, что P -редуцируется к Q, и пишем PQ. Например

а). (x.((y.xy)u))(v.v)  (y.y(v.v)y)u (v.v)u  u

b). (x.((y.xy)u))(v.v)  (x.xu)(v.v) (v.v)u   u

(более подробно принципиальное различие между пунктами a и b будет рассмотрено далее см.пункт 5.1.). Внимательно присмотревшись к этому примеру, можно заметить эквивалентность полученных результатов  несмотря на разный порядок проведения редукций. Это является одним из фундаментальных свойств -исчисления и подтверждается следующей теоремой, которая гарантирует, что стратегия проведения -редукций - безразлична. Теорема Черча-Россера для -редукции: Если P  М и P  N, то существует такой терм T, что M  T, N  T.

КАРРИНГОМ - называется соглашение об аппликации -термов, позволяющее ограничиться исследованием -функций только от одной переменной. Функция от n переменных рассматривается как конкатенация n функций от одной переменной: f x1x2...xn = ((...(fx1)x2)...xn). Скобками задан порядок аппликации: сначала -терм, обозначенный для краткости формулы символом f, применяется к -терму, обозначенному символом х1; затем  результат аппликации применяется к -терму х2 и т.д. Поясняющий пример:

  1.  x.y.(x+y) - функция от двух аргументов.

x.(y.(x+y)) - функция от одного аргумента х, дающая в результате функцию от одного аргумента у (а переменная х в этой функции является свободной). Применим -терм 2) к -термам t и z: (((x.(y.(x+y))) z) t) = ((y.(z+y)) t) = z+t

Итак, более формально

Исчисление лямбда-конверсии.

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

Формулы: равенства термов.

Аксиомы:  t = t для атомарных термов.

(x).M  y.[y/x]M (переименование)

(x.t1)t2 [t2/x]t1 (-редукция)

Правила вывода:

   

Доказуемость: последовательность равенств 1, 2,, n называется доказательством n, если i - аксиома, либо имеются j, k < i такие, что i получается из j и k по правилу вывода.

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

      3.2.2 Бестиповая комбинаторная логика (на пути к реализации).

           3.2.2.1 Необходимость введения.

Рассмотрим лямбда-абстракцию x. (у. - x y). При применении ее к некоторому аргументу, например 3, мы наполняем ее тело, создавая тем самым новую лямбда-абстракцию (x. - y 3). Каждое применение x-абстракции к новым аргументам создает новые и различные y-абстракции, тем самым лишая нас надежды скомпилировать единственный фиксированный код для каждой лямбда-абстракции.

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

Рассмотрим формализацию вычислительных предписаний, которые представляются КОМБИНАТОРАМИ. В аппликативном программировании их роль значительна и в прагматическом плане (т.к. они могут послужить реализацией аппликативного интерпретатора), и в теоретическом плане (т.к. они являются теми функциями, которые порождают функции).

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

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

3.2.2.2 Комбинаторная логика. Основные определения.

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

Переменные вводятся аналогично переменным лямбда-исчисления с добавлением двух дополнительных символов S и K, называемах базисными комбинаторами.

Комбинатором называется -выражение, не содержащее свободных переменных. Например, функция тождества x. x является комбинатором и обозначается обычно буквой I. Другим примером является комбинатор фиксированной точки Y = h. (x. h(xx))( x. h(xx)), но более подробно этот комбинатор будет описан позже (см пункт 5.4). Двумя следующими примерами являются вычеркиватель K, задаваемый в виде K=x.y.x, и распределитель S, задаваемый S=f.g.x. fx (gx).

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

Комбинаторная логика (КЛ). Созидается теория, в которой фиксируется, что значит равенство термов. Равенство фиксируется посредством доказательства.

Подразумеваемая структура: A = <A, , c1,,cm> - алгебраическая структура с непустым носителем А; выделенными в нем элементами c1, c2,, cm, m0; двуместной операцией . {А - множество имен}

Язык: термы, построенные из переменных, K, S посредством операции .

Формулы: равенства термов.

Аксиомы: t = t для атомарных термов.

St1t2t3 = t1t3(t2t3)

Kt1t2 = t1  для произвольных термов.

Правила вывода:

Доказуемость: последовательность равенств 1, 2,, n называется доказательством n, если i - аксиома, либо имеются j, k < i такие, что i получается из j и k по правилу вывода.

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

Тогда, если E и EКЛ представляют одно и то же выражение в этих двух логиках, то можно показать, что

MКЛ =КЛ NКЛ   M = N 

(если выполняется правило экстенсиональности Mx=NxM=N или правило -конверсии x. Mx=M).

В этом смысле комбинаторная логика может рассматриваться как модель -исчисления (Все приведённые результаты показывают, что КЛ во многом аналогична -исчислению. Однако эта анология не является полной. Существует важное свойство, которым обладает -исчисление, но не обладает КЛ, а именно свойство, обозначенное Карри через (): Х = Y  x.X = y.Y - очевидно, поскольку любые свёртывания или расширения, которые можно выполнить в Х, можно аналогично выполнить в x.X. Но для КЛ-термов аналогом () является: Х =КЛY  x.X =КЛ y.Y которое ложно при X=Kxx и Y=x). Можно определить следующую абстракцию, позволяющую формально прейти от КЛ-логики к -исчислению: для каждого х и каждого терма Z построим из базисных комбинаторов и частей Z новый терм, обозначаемый х.Z. Он определяется индукцией по числу символов в Z следующим образом:

  1.  x.U KU , если х не входит в U   
  2.  x.x   I
  3.  x.Ux  U , если х не входит в U
  4.  x.UV  S(x.U)( x.V) UV если х входит в UV и c) неприменимо.

Например x. y. yx  x. (y. yx) (d) x. (S(y. y)(y. x)) (b,a)x. (SI(Kx)) (d) 

                  S (x. SI)(x. Kx) (d,c) S(S(x. S)(x. I))K (a) S (S (KS) (KI)) K,

В нашем представлении мы будем также использовать тождественный комбинатор I (его можно выразить через K и S). Заметим, что единственным механизмом сочетания выражений является применение функций - отсюда термин “аппликативное выражение”.

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

Сначала заметим, что -выражения можно транслировать в комбинаторную форму путем последовательного абстрагирования (выделения) переменных из подвыражения. Функция comb, осуществляющая отображение -выражений в комбинаторную форму, подробно описана в книге “Функциональное программирование” [24, стр. 294-295]. Так, например, применяя функцию трансляции comb к выражению x.(y. + x y), мы получим ее комбинаторную форму S (S(KS)(S (S(KS)(S(KK)(K+)) )(S(KK) I) )) (KI). В данном случае мы приходим к “программированию без переменных”. Так как переменные отсутствуют, то нет необходимости рассматривать вопрос об их именах и контексте. Таким образом, проблема свободных переменных оказывается решенной.

Основная привлекательность комбинаторного подхода заключается  в его математической элегантности и простоте вычислений, вытекающей из наличия только трех правил преобразования графов (исключая те, что связаны с примитивными функциями). Итак, все, что нам нужно сделать - это определить правила преобразования графов, соответствующее применениям S, K и I, и объединить их с правилами применения примитивных функций. Но, к сожалению, даже очень простое -выражение имеет очень сложный эквивалент в КЛ (это видно на предыдущем примере с функцией +). Эта проблема решается путем расширения набора примитивных комбинаторов S, K и I (см. Пункт 3.3.3).

                   

3.3. Реализация.

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

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

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

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

            3.3.1. Энергичные и ленивые интерпретаторы.

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

При таком порядке вычислений обработка некоторых условных выражений может привести к неопределённому результату. Например, определённое при всех целых значениях a (кроме а<>0) выражение if a<>0 then 1/a else a приведет к аварийному завершению программы при а=0, так как при аппликативном порядке вычислений выражения обеих ветвей будут вычисляться независимо от результата вычисления предиката (a<>0), и при вычислении выражения 1/а произойдет деление на 0. Это не единственный случай, когда возникают проблемы. Вычисление некоторых обычным образом определённых рекурсивных функций также может привести к аварии или зацикливанию. Например, вычисление выражения факториала, определённого в виде fac(n)= if n=0 then 1 else n*fac(n-1), приведёт к зацикливанию, так как ветвь else будет вычисляться каждый раз независимо от значения предиката (n=0).

Одним из решений этой проблемы является преобразование условных -выражений с использованием пустых функций с одним пустым аргументом (dummy). Приведённое выше условное выражение после преобразования имеет форму

(if a<>0 then dummy (/ 1 a) else dummy a) any,

где any может быть любым объектом. Данный эквивалент условного выражения уже не может привести к аварии.

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

3.3.2 Редукция графов в -исчислении.

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

Дадим краткое описание редукции графов.  Нам необходимы три типа выражений:

  1.  Константы появляются в графовом представлении в качестве листьев.
  2.  Аппликации вида Е1Е2 представляются специальным типом вершин

@-вершинами, которые помечаются символом @:  @

          

            E1          E2

  1.  Лямбда-абстракции вида x.В представляются с помощью -вершин, при этом связанная переменная х представляется левым листом, а тело В - правым:          

                     

 

  х       В

Рассмотрим функциональную программу (x. AND x x) (NOT TRUE). Представим эту программу деревом ее грамматического разбора:

        Отметим, что карринг отражен в поддереве для (AND x x).

Это дерево содержит два так называемых редуцируемых выражения (или редекса), которые состоят из применения (аппликации) функции к своему аргументу (аргументам): применение NOT к TRUE и применение x-абстракции к (NOT TRUE). Чтобы применить x-абстракцию к ее аргументу (NOT TRUE), мы заменяем верхний узел @ некоторой конкретизацией тела x-абстракции, в которой вместо каждого вхождения x подставляется указатель на аргумент:

Заметим, что дерево превратилось в граф. Теперь мы можем применить NOT к его аргументу TRUE, получив

Наконец, выполнив операцию AND, получим FALSE.

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

  1.  Исполнение функциональной программы заключается в вычислении некоторого выражения.

Функциональная программа допускает естественное представление в виде дерева (или, в более общем случае, графа).

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

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

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

Порядок редуцирования редексов не влияет на ответ(смотри  теорему Черча-Россера пункт 2.1).

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

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

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

Но, к сожалению, не все лямбда-абстракции поддаются такой компиляции. Возникает проблема свободных переменных.

3.3.3 Комбинаторная редукция с помощью графов.

О необходимости введения дополнительных комбинаторов уже говорилось в пункте 4.2.2. Не смотря на то, что комбинаторов S и K достаточно для преобразования любого лямбда-выражения в аппликативное выражение, полученное выражение получается достаточно сложным и для решения этой задачи появляется потребность в дополнительных комбинаторх B, C (композитор, перестановщик)

B f x y f (x y) или В=f. x. y.f(x y)

C f x y f y x или С=f. x. y.f y х.

Тогда в КЛ, имеющей примитивные комбинаторы K, S, I, C, B, выполняются следующие равенства:

S (K t1)(K t2) =КЛ K (t1 t2)

S (K t1) I =КЛ t1

S (K t1) t2 =КЛ B t1 t2

S t1(K t2) =КЛ C t1 t2.

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

S(K E1)(K E2) = .K E1 x(K E2 x)  x.E1 (K E2 x)  x.E1 E2 = K(E1 E2)

Тогда применение функции comb приводит к оптимизированной форме:

comb (x.(+ 2 (- x 3))) = B (+ 2) (C - 3) вместо  S(K(+2))(S(S(K-)I)(K3))={2}=S(K(+2))(S-(K3))={4}=S(K(+2))(C-3)={3}=B(+2)(C-3).

Теперь рассмотрим представление комбинаторных функций графами (оно аналогично представлению -выражений). Существует 2 правила.

1) Константу мы представляем в виде дерева с одной вершиной соответствующей самой константе.

2) Применения функций вида A B в виде:

Пример: + 1 3 = (+ 1) 3

Пример: B (+ 2) (C - 3) 4

Для каждого комбинатора существует правило редукции, которое можно отобразить с помощью графов.

1) Редукция тождественного комбинатора

 

2) Редукция вычеркивателя

3) Редукция распределителя

4) Редукция перестановщика

5) Редукция композитора

Пример комбинаторной редукции:

B (+ 2) (C - 3) 4

B-редукция:

2.Построение графов для взаимно-рекурсивных функций:

Пусть имеется система функций

f1 = E1

f2 = E2

  ...

fn = En

Причем Е1...Еn могут зависеть от f1...fn, так что надо нарисовать граф для каждой функции и соединить дугами обращения к другим функциям с входами в них.

Пример: f = comb( x.cons x ( g x)) = S cons g

g = comb( x.cons( * x x) ( f x)) = S ( B cons square) f

Обращение f 2 выдаст последовательность 2 4 2 4 2 4...

Граф выглядит следующим образом:

Последнее, что мы рассмотрим, это представление рекурсивных функций с помощью графов на примере функции factorial.

Функция factorial в комбинаторном представление имеет вид

factorial = S ( C ( B cond ( = 2)) 2) ( S * ( B factorial ( C - 1))).

Граф выглядит следующим образом.

Определим преобразование графа для представления применения Y-комбинатора (этот комбинатор будет подробно описан в следующем пункте). Это нетрудно сделать. Такое определение вытекает из определения фиксированной точки, то есть для любого -выражения  X имеем YX = X (YX) = X (X (X...X (YX)...)). Таким образом, граф обеспечивает корректное представление:

3.3.4. Неподвижная точка и рекурсия.

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

В языках программирования высокого уровня необходимо иметь возможность записывать определение рекурсивных функций. Мы можем это сделать, так как имеем возможность дать имя любой функции f, а затем ссылаться на это имя где угодно в программе (при определённых ограничениях, обусловленных языком), даже в теле функции, названной этим именем, например, f(f(x)). Однако в -исчислении функции не имеют имён. Они представляются -выражениями (впрочем, это единственный объект -теории). Поэтому для представления рекурсии необходимо придумать какой-то метод, который позволит функциям вызывать себя не по имени, а каким-то другим образом. Этим способом может быть механизм копирования аппликаций: то есть вид -выражения остаётся неизменным, а рекурсия будет осуществляться уже при выполнении, посредством копирования тела функции. Для этого и используется неподвижная точка.

3.3.4.1. Неподвижная точка в лямбда-теории.

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

Обобщим выражение E(F) посредством -абстракции

 f. x. (x=0 | 1 | x (f (- x 1))).

Обозначим эту абстракцию через G. Возникает уравнение для оператора G:       z=Gy.

Чтобы смоделировать рекурсию, необходимо иметь оператор Y со следующим свойством

YG = G(YG) = x. (x=0 | 1 | x (YG (x-1))).

Тогда оператор Y для операторного уравнения z=Gy отыскивает неподвижную точку 

YG = G(YG).

Тогда рекурсивная функция F с телом Е(F) записывается в -исчислении в виде:

Y (F. E(F)).

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

Теорема.  f x (f x = x).

Доказательство:

Возьмём w = x. f(xx). Тогда искомым x является ww. Проверим утверждение теоремы: x = ww= (x.f(xx)) w=f(ww)=f x.

Как видно из доказательства, оператором Y является:

Y = h. (x. h(xx))(x. h(xx)).

Убедимся, что именно это выражение и есть оператор неподвижной точки Y. Применим его к произвольной функции f:

 Y f = (h. (x. h(xx))(x. h(xx))) f =

 = (x.f(x x)) (x.f(x x)) = f ((x.f(x x)) (x.f(x x))) = f (Yf)

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

Y f f(Y f) f(f(Y f))   

Однако можно модифицировать определение Y так, чтобы обойти эту проблему, определив альтернативный Y-комбинатор как:

 Y1 = h. (x. h(y. xxy))(x. h(y. xxy)) 

Y и Y1 -эквивалентны, поскольку один можно получить из другого с помощью -преобразования (y. xxy = xx1)). Если теперь вместо Y использовать Y1, самоприменение вычисляется, только когда оно применяется к аргументу, соответствующему переменной y, например, к целому аргументу функции факториал F.

Пример энергичного(по значению) вычисления F=f. x. (x=0|1|x(f(- x 1))).

Y1F 3 (x. F (y. xxy))(x. F (y. xxy)) 3  

F (z. (x. F (y. xxy))(x. F (y. xxy)) z ) 3

( 3 ((z. (x. F (y. xxy))(x. F (y. xxy)) z ) 2))

( 3 ((x. F (y. xxy))(x. F (y. xxy)) 2)) /* ( 3 (Y1 F 2)) */

   ( 3 ( 2 ( 1 (x. F (y. xxy))(x. F (y. xxy)) 0)))

( 3 ( 2 ( 1 1)))6.

Так как w1w10 F (y. w1w1y) 0 1, где w1=(x. F (y. xxy)).

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

Реализовать комбинатор Y можно двумя способами: в виде лямбда-выражения или, если все лямбда-выражения представлены в графовой форме, Y просто реализуется  установкой циклического указателя (см. Пункт 5.3).

         3.3.4.2. Теорема о неподвижной точке

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

Определение: Точка f называется неподвижной (фиксированной) точкой функции (функционала) , если (f)=f. Такая точка называется наименьшей, если е: (e)=e => fe (где  - отношение порядка (возможно частичного) на множестве определения ). 

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

Возьмём : PP - монотонное отображение на полной структуре P. Применим к произвольному элементу из P. К результату снова применим и так далее. Вследствие полноты P будет существовать точная верхняя грань последовательности. Если полученная последовательность значений будет монотонной, то её и стоит подозревать на неподвижность, т.е. supk{ (a)} = a?

Следовательно,

Теорема о неподвижной точке. Если - монотонное отображение полной структуры P в себя, то (а) = а для некоторого аОP.

Доказательство:

Рассмотрим множество Х = {х | (x) х, xОP}. Минимальный элемент (основание) существует в силу полноты Р и Х, таким образом, множество Х не пусто. Следовательно, существует а = sup Х. При этом для любого x Х, так как а х  и - монотонно, то (а)  (х)  х, следовательно (а) а. Аналогично, т.к.  - монотонно, то ((а))  (а), что влечет (а) Х и, значит, а  (а), так как а = sup Х.

Таким образом, а  ) a => а = (а).

Рекурсию можно воспринимать двояко: индуктивно и через решение функционального уравнения. Эти толкования рекурсии совпадают при определенных условиях на функционал.

Монотонный функционал называется (цепочно) непрерывным, если для монотонно возрастающей последовательности x0= и xi+1=(xi)=i()  справедливо:

suрxi: iN=suрxi: iN.

Теорема о совпадении наименьшей неподвижной точки с супремумом цепочки.

Если непрерывен, то Y совпадает с супремумом цепочки {xi: iN} (x0=, xi+1=(xi)).

Доказательство: Из непрерывности следует, что супремум цепочки является неподвижной точкой для :

suрxi: iN=suрxi: iN=suрxi+1: iN=suрxi: iN.

Осталось доказать, что точка b=supxi: iN будет наименьшей неподвижной точкой (по индукции). Предположим, что a - также фиксированная точка . Докажем, что b  a. В базовом случае   a, так как - основание (минимальный элемент). Предположим, что k()  a, тогда k+1()  (a) = a, так как - монотонно, а a - фиксированная точка по предположению. Так как a  k() для любого k, то х является верхней границей монотонной последовательности. По определению наименьшей верхней границы и b a.

3.3.4.3. Практическая роль теоремы в программировании.

Надо позаботиться о простоте восприятия монотонности и непрерывности оператора при толковании рекурсивных объектов посредством теоретико-множественного решения подходящего уравнения. Во многих случаях подходит плоский (дискретный) порядок. Введем порядок на произвольных элементах: xy, если (x=)(x=y). Например, для N мы, тем самым,  определили дискретную решетку:

Она является полной.

Рекурсивные функции могут трактоваться как решения функциональных уравнений. Рассмотрим для простоты f: NN. Индуцируем порядок на функциях на основании плоского порядка на N.

f g Df x [f(x) g(x)].

Таким образом, fg, если g является продолжением (расширением) функции f (то есть на области определения f эти функции совпадают, и g может быть “шире”). В каком-то смысле g уточняет функцию f. В таблице изображены примеры функций, находящихся в таком порядке. Эти функции монотонны по определению порядка.

F0

F1

F2

F3

F

T

Т

T

T

T

0

0

0

0

0

1

1

1

1

2

4

4

4

N

N2

Пример (индуктивное толкование рекурсивного соглашения о функции факториала). Рассматривается рекурсивное объявление

fсt fас = (nаt х)nаt:

 if х0 then 1 else хfас(х-1) fi,

при этом получают следующий функционал :

В соответствии с нашим определением справедливо для хN, i=0,1,:

fас 0(х)=, т.е. fас 0=.

Тем самым для функции fас i получается не рекурсивное равенство:

Это можно доказать индукцией по iN, i=0,1,:

(1) i=0, тогда утверждение тривиально.

(2) Пусть утверждение правильно для fас i

fас i+1(х)=fасi(х)

Пример (наименьшая неподвижная точка для функционала функции факториала). Функция

fас: NN

с fас(n)=n! есть наименьшая неподвижная точка , т.е. наименьшее решение функционального уравнения f=f с

Индуктивное толкование suрi: i=0,1, и толкование неподвижной точки fiх  полностью идентичны, если функционал обладает так называемым свойством непрерывности.

Проверим на непрерывность

supfi: i=0,1,...(x) = supfi(x-1): i=0,1,... =

sup[fi]: i=0,1,...(x) = sup[fi(x)]: i=0,1,... = sup{faci+1(x): i=0,1,...}=x!

Для сравнения с хорошими функционалами рекурсивных определений приведем пример немонотонного функционала. Пусть функционал , действуя на функцию f: NN, выглядит следующим образом:

Пусть fg, gf, x0 - наибольшая точка (обычный порядок на N) области определения f. Для xx0 области определения f [f]=[g]=.

Для x=x0 [f](x0) = 1, а [g](x0) = .

Таким образом, мы получили [f](x0)  [g](x0). Значит, построенный нами функционал не является монотонным.

Рекурсивные типы могут трактоваться  как решения уравнений для множеств.

Пример (индуктивное толкование рекурсивного объявления типа). Пусть дано следующее объявление типа двоичных деревьев

sоrt m = еmрtу(еmрtу)соns(m lеft, nаt rооt, m right).

Если записывать для единственного элемента типа еmрtу, то для любого множества данных М получим:

(М)=(l,х,r): lМ\  хN rМ\.

Это приводит к следующим множествам данных:

М0=,

Мi+1=(l,х,r): lМi\  хN rМi\,

т.е.

М1=, ,

М2=, , (,0,), (,1,), ...,

М3=, , (,0,), ((,0,), 0, ), ....

Итак, получаем множество, эквивалентное множеству двоичных деревьев.

Пример (трактовка неподвижной точки для двоичных деревьев в рекурсивном объявлении типов). Пусть имеют место определения предыдущего примера. Для множества М с

М=Мi

имеет место

М=(l,х,r): lМ\  хN rМ\, ()

т.е. М есть решение уравнения М=(М). М является также наименьшей неподвижной точкой оператора .

Действительно, оператор является монотонным и непрерывным по теоретико-множественному включению.

Монотонность очевидна. Если M1M2, то (M1)(M2).

Проверим непрерывность: M0=, Mi+1=(Mi), тогда MiMi+1.

U(Mi)=UMi+1=(UMi).

Формальные языки могут трактоваться как решения уравнений для множеств. Рассмотрим язык, определяемый БНФ (см. п. 3.4).

<x>::=1|2<x>

Зафиксируем решетку множеств по включению. Язык можем воспринимать как решение уравнения

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

Решением уравнения является регулярное множество 2*1.

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

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

                3.3.4.4 Пример на неподвижную точку.

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

Y=h.x.hx xx.hx x

Приспособим нашу функцию к действию функционала Y.

=f.n.

Развернем рекурсию

Y3x.x xx.x xx.x xx.x x

Чтобы выделить существо дальнейших преобразований, изучим действие Y.

YY

Если предположить аппликативный (энергичный, вызов по значению) порядок вычислений, тогда зациклимся. Это произойдет из-за невозможности посчитать аргумент Y.

Y

Если будут действовать отложенные вычисления (ленивые, вызов по имени), то есть будет нормальный порядок вычислений, тогда развернется рекурсия.

Перепишем наш пример.

Y33+3 +- 3 13 +- 3 1

Обозначив через S=n.

+S- 3 13

++- 2 123

++1 2 3

+ 3 36

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

  1.  Однородные средства в аппликативном стиле.

Итак, описана теория лямбда-исчисления и комбинаторной логики и показаны средства реализации этих систем. Поведем разговор о построении на этом основании практической системы аппликативного программирования. При этом выделим основные вопросы.

1) Минимальные возможности. возникают после введения УСЛОВНЫХ ВЫРАЖЕНИЙ при задании тела функций, ОПРЕДЕЛЕНИЯ ФУНКЦИЙ и использования их имени при собственном определении (РЕКУРСИЯ).

Можно записать функцию факториал в виде:  Q = n. ( n=1| 1| n*Q(n-1))            (1)

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

Q = n. ((= n 1)| 1| (* n (Q (- n 1)))) (1*)

Тогда рекурсивная часть преобразования выражений проходит как обычно:

(Q 3) = (* 3 (Q (- 3 1))) =...

Неплохо было бы иметь такую же запись для if.. Тогда придется (и это очень хорошо для последующего) ввести ВЫРАЖЕНИЕ НАД ФУНКЦИОНАЛЬНОЙ (операциональной) ЧАСТЬЮ. Итак, перепишем (1*):

Q = n. ( (if (= n 1)). 1 (* n (Q (- n 1))) (1**)

Подчеркнутое операциональное выражение является операцией, по которой считается первый или второй аргументы операции. Поэтому запись (1**) следует лучше представлять в виде

Q = n. ((if (= n 1)) (). 1 (). (* n Q (- n 1)))

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

(Q 3) = ((IF (= 3 1)) # #) = (* 3 (Q (- 3 1))) =

= (* 3 (Q 2)) = (* 3 ((IF (= 2 1)) # #)) =

= (* 3 (* 2 (Q (- 2 1)))) = (* 3 (* 2 (Q 1))) =

= (* 3 (* 2 ((IF (= 1 1)) # #))) = (* 3 (* 2 1)) =...

Тогда наш пример запишется  в виде:

Q = N. n. ((IF (= n N)) N (* n (Q N (+ n 1))))

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

(def Q (n) ((if (= n 1)) 1 (* n (Q (- n 1)))))

А -выражения приобретают вид: из n. m. (n+m) в  ( (n m) (+ n m)).

Как уже отмечалось в пунктах 4.1 и 4.2 для упрощения реализации удобно всё представлять комбинаторами.

2) -выражениями вводятся неименованные функции. Естественно, что они могут быть фактическими аргументами. Это традиционно:

(f. (f 5) x. (+ x 1)), тогда значением будут

(x. (+ x 1) 5) = (+ 5 1) = 6

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

(def Ф (n) ((in (= n 1)) x. x x. (+ x 1))).

Тогда (Ф 1) = x. x ((Ф 1) 2) = 2

(Ф 2) = x. (+ x 1) ((Ф 2) 2) = 3

Более интересным случаем является получение разных функций в качестве результата:

(def Ф1 (n) ( (m) (+ n m)))

Тогда (Ф1 2) = m. (+ 2 m).

3) Комбинаторы  уже были описаны в пункте 4.2.

Рассмотрим пример. Пусть Ф = f. x. ((f(fx)). Тогда Ф(x. (x+1)) = y. (x. (x+1)(x. (x+1) y)) = y. (x. (x+1)(y+1)) = y. ((y+1)+1) = y. (y+2).

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

ФФ = (f. x. (f(fx))) (f. x. (f(fx))) =

y. (f. x. (f(fx)). (f. x. (f(fx)). y))) = y. (f. x. (f(fx)) (x. (y(yx)))) =

= y. (z. (x. (y(yx)). (x. (y(yx)). z))) = y. (z. (x. (y(yx)) (y(yz))) =

= y. z. (y(y(y(yz))))

Тогда понятно, что результат Ф Ф f x = f(f(f(fx)))).

Конечно же, соответствующие преобразования можно произвести. Но "охватить" их сложно. Считать выражение (ФФ)Ф еще труднее. Здесь нас выручает техника комбинаторов. Пусть Фxy = x(xy). Тогда

Ф Ф f x = Ф(Фf)x = Фf(Фfx) = f(f(Фfx)) = f(f(f(fx)))) (*)

Значительно легче, чем с Л-преобразованиями. Посчитаем ФФФfx = Ф(ФФ)fx = ФФ(ФФf)x = Ф(Ф(ФФf))x = Ф(ФФf)x) =

  = ФФf(ФФf(Ф(ФФf)x)) = (*) = f^4 (ФФf(Ф(ФФf)x)) =

  = f^4 (f^4 (Ф(ФФf)x)) = f^4 (f^4 (ФФf(ФФfx)) =

= f^4 (f^4 (f^4 (ФФfx))) = f^4 (f^4 (f^4 (f^4 x))) = = f^16 x, где f^n x = f(.. (fx)) /n раз/.

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

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

(1) (def П ( n)  (if n=1 then ( 1) else (* ( n) (П (- n 1)))))

Тогда (П i. (i+1) 3) = (* (i. (i+1) 3) (П i. (i+1) 2)) =... Перепишем (1) к виду, по которому готовилось бы выражение, приспособленное для счета:

(2) (def П ( n)

    (if n=1 then (). ( 1)

        else (Expr * (). ( n) (П (- n 1))))) Теперь уже при обращении (П i. (i+1) 3) получим

(* (i. (i+1) 3) (* (i. (i+1) 2) (i. (i+1) 1))).

Напомним, что семантикой () является - отложить вычисления. Если обратиться (eval (П i. (i+1) 3)), то полученное выражение свернется.

Но программа  (2), которая естественно получилась из (1) (в отличие от подобного преобразования в процедурном стиле, где  используется метод Йенсена передачи параметров по наименованию) допускает и естественное обращение, чтобы посчитать

     

Найдем это обращение к программе. Если обратиться

x. (П y. (x+y) 2) 3), то получим:

(* (П y. (3+y) 2) (* (П y. (2+y) 2) (П y. (1+y) 2))). Если обратиться (eval (П x. (П y. (x+y) 2) 3)), то получим:

(eval (* (* (+ 3 2)(+ 3 1)) (* (* (+ 2 2)(+ 2 1)) (* (+ 1 2)(+ 1 1)). )).

Подчеркнутые выражения не могут посчитаться при действии eval,т. к. операция * неприменима к аргументам вида (+ 3 2), т. е. к выражениям. Правильным обращением является

(eval (П x. (eval (П y. (x+y) 2)) 3)).

Теперь посчитается нужное выражение, т. к. порождается выражение вида:

(eval (*

(eval (* (+ 3 2) (+ 3 1)))

   (* (eval (* (+ 2 2) (+ 2 1)))

    (eval (* (+ 1 2) (+ 1 1))))))

Еще раз отметим, что сплошное моделирование смешанного вычисления в процедурном стиле заменилось обозримыми рациональными действиями в аппликативном стиле. Программируя (2) воспользовались отложенными вычислениями, а при обращении посредством eval их "пустили в работу".

 

                    3.3.6 Смешанные вычисления.

 

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

Пусть задана примитивная функция +1=x.x+1.

Тогда можем посчитать +15x.x+156.

Нарастим возможности за счет обобщения примитива до

+x.y.x+y

и введения функции высшего порядка

Ff.x.f x

Тогда, используя карринг, можем посчитать требуемое обращение F+ 1 5. Действительно

F+15x.+1x5+15y.1+y56

Введем двойную суперпозицию

К +1 вернулись для простоты записи. Попробуем посчитать +45 с помощью +1 и F2. Можем действовать двумя способами. Обычный способ, соответствующий императивному стилю, представляется таким образом:

+1+17+189

Второй способ соответствует технике смешанных вычислений. Конструкцию предыдущего обращения F2+1 +1+15 можем получить в виде F2+1F2+15 посредством простого обращения F2F2+15. Это обращение ближе находится к формулировке “Что делать”. Действительно F2F2x.F2F2x то есть имеем выражение, которое двойную суперпозицию функции х, именно F2x, применит посредством двойной суперпозиции F2 F2x.

F2 F2+1 F2 F2+1x.F2+1F2+1 x

F2 F2+15 F2+1F2+15

Получили обещанное ранее обращение императивного случая. В пункте 3.3.5 было показано, что пониманию “Что делать” также начинает помогать техника алгебры комбинаторов. Данный пункт позволяет нам перейти от 4 к 5 уровню концептуальности предъявления материала.

 3.4 Сравнения реальных языков программирования.

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

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

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

Функциональное программирование как раздел теоретического программирования сформировался через добрых два десятка лет после появления Лиспа, когда стали актавно развиваться другие языки и формализмы, основанные на математическом понятии функции. Наиболее известными языками являются Рефал  [Турчин 68], ML [Milner 84], а также серия языков, разработанных Д.Тёрнером и его коллегами: KRC, Sasl и Миранда [Turner 82,83,85,86]. Большую роль в развитии функционального программирования сыграла Тьюринговская лекция Дж.Бэкуса [Backus 78].

Во всех языках функционального программирования способы описания функций базируются на тех или иных формализмах, созданных в математической логике: лямбда-исчислении (Лисп), комбинаторной логике (Миранда), нормальных алгоритмах Маркова (Рефал), рекурсивных уравнениях Эрбрана-Гёделя (KRC). В более современных языках, таких, как Миранда, используются и некоторые другие достижения математики, например, теоретико-множественная нотация.

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

Для рассмотрения выберем следующие языки: Норе, Миранда, Лисп и FP. Проблемная ориентированность языков определяется функционалами или функциями высшего порядка. Концепция функций высшего порядка возникает из идеи о том, что функции должны иметь тот же статус, что и любой объект данных, так чтобы они сами могли быть входными и выходными данными других функций.

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

3.4.1 Язык Норе.

Рассмотрим следующие функции языка Норе:

IncList - увеличивает на 1 каждый элемент списка (функция определяется на родовом (полиморфном) типе данных).

dec IncList : list(num)list(num);

---IncList(nil)<=nil;

---IncList(x::l)<=(x+1)::IncList(l); имеется возможность сопоставления с образцом (::)

MakeStr - отображает каждый элемент списка в список из одного элемента.

dec MakeStr : list(char)list(list(char));

---MakeStr(nil)<=nil;

---MakeStr(c::l)<=[c]::MakeStr(l);

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

---Inc(n)<=n+1;

во втором -

---Listify(c)<=[c];
(c соответствующими определениями типа). Можно выявить общую структуру, определив функцию высшего порядка, которая, используя функции типа Listify и Inc в качестве аргумента, применяет их к каждому элементу заданного списка, выступающему в роли второго аргумента. Подобная функция высшего порядка широко используется и часто называется map. Поскольку мы не знаем наперед тип применяемой функции или тип обрабатываемых элементов списка, то map должна быть объявлена полиморфной функцией (alpha - динамическое определение типа для функций, beta - для элементов списка). Итак,

dec map : (alphabeta)#list(alpha)list(beta); функция от одной двойки

      аргументов (кортеж).

---map(f, nil)<=nil;

---IncList(F, x::l)<=f(x)::map(f, l);
Теперь, используя map и вспомогательные функции Inc и Listify, можно выразить IncList и MakeStr:

IncList(L) map(Inc, L)

MakeStr(L)  map(Listify, L).
Удобство такого подхода очевидно, однако явное определение подобных функций может быть довольно неудобным. Язык Норе дает нам возможность записывать выражения (лямбда-выражения), значением которого является функция. Например, Inc будет описана так:

lambda x=>x+1.

Тогда IncList(L) map(lambda x=>x+1, L).

3.4.2. Язык Миранда.

Язык Миранда был разработан Д.Тёрнером и его коллегами в университете г.Кента.

Этот язык имеет ряд интересных черт, связанных с математической логикой.

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

Каждая функция в языке Миранда является по существу функцией высшего порядка. Когда мы на этом языке записываем определение вида
f x y z = 
мы можем обычным образом интерпретировать f как функцию от трех аргументов x, y, z или, как в Норе, в качестве функции от одной тройки аргументов (кортеж). Однако в языке Миранда в действительности f является функцией высшего порядка только от одного аргумента x. Результатом применения f к аргументу E1, который мы запишем в виде fE1, является другая функция, снова только от одного аргумента y. Применение этой функции к следующему аргументу E2 снова дает функцию от оного аргумента z. Полное применение f записывается в виде fE1E2E3 (Смотри поняте карринг из пункта про лямбда-исчисление) .

Посмотрим, как будет выглядеть функция Inc прибавления единицы к некоторому целому. На языке Миранда она может быть записана в виде частичного применения примитивной функции + к аргументу 1: (+) 1 (скобки превращают инфиксную функцию + в префиксную). Рассмотрим функцию map. Она имеет следующее определение на языке Миранда:

map f []=[]

map f (x : l)=(f x) : (map f l)
Тогда выражение

map((+) 1) L
увеличивает на единицу каждый элемент списка L.

В языке Миранда все функции должны иметь имена. В языке Норе мы вводим вложенные функции, используя lambda-выражения, в Миранде это достигается с помощью определения функции внутри where-выражения. Например, функция
map(f 5) L 
where f x y=yxx прибавляет 25 к каждому элементу L. Заметим, что введенная функция может быть рекурсивной благодаря тому, что имеет имя.

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

3.4.3 Язык Лисп.

(Синтаксис языка смотри в приложении B).

Лисп является нетипизированным языком обработки списков, в котором программы и данные имеют одинаковое представление.

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

(LAMBDA (x) (ADD x (QUOTE 1))).

Используя QUOTE и LAMBDA совместно, мы можем передавать функции (лямбда-выражения) как параметры другим функциям. Рассмотрим применение map, где в качестве функции f используется функция, увеличивающая свой аргумент на единицу. Для того, чтобы эту функцию можно было передать в качестве параметра, определяющее ее лямбда-выражение заключается в кавычки.
Опишем map:

(defun map (lambda (f L)

(cond ((eq L nil) nil) 

         t (cons (f (car L)) (map f (cdr L))]

Тогда увеличение каждого элемента списка (1 2 3) на единицу можно описать так:
(map (QUOTE (LAMBDA (x) (ADD x (QUOTE 1)))) (QUOTE (1 2 3)) ).

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

Рассмотрим функционал Ф2 = f. x. f (f x) композиции функции. Так, применение этого функционала к функции g и числу 3 дает нам Ф2 g 3  g(g 3).
Посмотрим вычисление выражения (Ф
2Ф2) g 3.

2Ф2) g 3  (x. Фx) g 3  Фg) 3.
Далее вычисления могут идти двумя путями. Могут использоваться ленивые вычисления (вычисления параметров откладывается до их использования) или энергичные вычисления (сначала вычисляются все параметры, затем только - применение функции. Более подробно об энергичных и ленивых вычислениях смотри пункт 3.1.).

Итак, при ленивых вычислениях:

2 g) 2 g 3)  (x. g (g x)) (g (g 3)) (g (g (g (g 3)))) = g4 3;

при энергичных:

Ф2 (x. g (g x)) 3 (x. g2 (g2 x)) 3 = g4 3.

Первоначально при описании функционала предполагалось применение его к двум аргументам: функции и объекту. Но при вычислениях в качестве x выступает также функция g. Бестиповость языка позволяет нам сделать это.

Отметим, что все объекты Лиспа - это S-выражения. Более того, программа на Лиспе сама является S-выражением, то есть не существует явных ключевых слов. Это приводит к одинаковому представлению программ и данных.

 3.4.4. Язык FP.

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

Отличительной особенностью FP является то, что в нем нельзя выражать функции высшего порядка, определенные пользователем. Все функции высшего порядка являются встроенными - это комбинирующие формы “применить-ко-всем”, левая вставка и правая вставка. Так, в FP существует аналог функции map, работающей со списками: f обозначает функцию, которая применяет f к каждому элементу в заданной последовательности аргументов.

( f) : <x1,,xn>=<f : x1,, f : xn>
Например,
tl применяет функцию выделения хвоста последовательности к заданной последовательности последовательностей (tl - примитив языка):

( tl) : <<1 2 3>,<4 5 6>>=<tl : <1 2 3>, tl : <4 5 6>>=<<2 3><5 6>>.
Функционалы правая и левая вставка определяются следующим образом:

(/f) : <x>  = x базовый случай

(/f) : <x1,,xn> = f : <x1, /f : <x2,,xn>> - правая

и

(\f) : <x>  = x базовый случай

(\f) : <x1,,xn> = f : <\f : <x1,,x-1>, xn> - левая.

Существуют также варианты вставок, имеющие связанные с ними базовые случаи. Они указываются индексами у символов \ и /.

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

Функция факториал - рекурсивная

def   fac=eq01,                             /   n=0

              [id, fac(-[id, 1])]         / (n, fac(n-1))

где - функционал суперпозиции. Фактически запись передает посредством суперпозиции известное рекурсивное определение.

Заметим, что в этом определении нет ссылок на объекты, и поэтому нет символов применения функции. Тело состоит целиком из функций  и функционалов. При применении fac к конкретному числу выражения становятся более привычным:

fac : 3 eq 0 : 3 1; : <3, fac : (- : <3, 1>)> = : <3, fac : (- : <3, 1>)>.

Любая рекурсивная функция может быть выражена в FP с помощью комбинирующих форм и примитивов языка. Однако многие такие функции имеют альтернативное нерекурсивное определение, использующее функции ,/,\ для удаления рекурсии. Нерекурсивный эквивалент:

def fac = /1   ,

где /1 - функция вставки (со значением в базовом случае, равном 1),

  - примитив, при применении к n этот генератор дает последовательность целых от 1 до n.  Например, : 5<1,2,3,4,5> (см. приложение С).

Тогда fac : 3 = /1  : <1, 2, 3> = : <1, /1 : <2, 3>> =  

= : <1,  : <2, </1 : 3>>> = : <1,  : <2, : <1, 3>>>> =

= : <1,  : <2, 3>>> = : <1, 6> = 6.

     3.4.4.1  Некоторые примеры программ на языке FP.

За счет функционалов аппликативный стиль достигает хорошего уровня для формулировок “Что делать”. Приведем примеры на языке FP.

Функция вычисления длины последовательности, рекурсивный вариант:

def  len=null                   / nil

                +[1, len tl]       /  +(1, len(tl(l)))

Нерекурсивная функция:

def  len_n=/+1

Означает, а) заменить члены последовательности 1; в) суммировать их со значением, равным нулю в базовом случае. Например,

len_n:[a,b,c]/+:[1,1,1]+(1,+(1,+(1,0)))3

Знаменитая функция member, проверяющая, входит ли элемент в последовательность

def  mem=null2F;

                  eq[1, hd2]T;

                            mem[1, tl2]

Нерекурсивная функция поинтересней.

def  mem_n=/or   eq distl

Конечно, без знания обращения к ней трудно догадаться, что происходит. Итак

mem_n:<1, <3,2,1>>

/or   eq:<<1,3>, <1,2>, <1,1>>

/or <eq:<1,3>, eq:<1,2>, eq:<1,1>>

or(F, or(F,T))T

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

              3.4.5 Резюме сравнения языков.

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

Функции в Miranda являются карринговыми, т.е. они могут быть применены частично, давая в результате новые функции.

 Miranda имеет средства абстракции списков и множеств.

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

Программы и данные в Лиспе представляются одинакововым образом с помощью S-выражений.

FP является нетипизированным функциональным языком, который предписывает программирование на функциональном, а не на объектном уровне.

 FP-система состоит из объектов, примитивных функций и комбинирующих форм.

Все структуры данных в FP строятся с помощью последовательностей, которые являются симметричными списками.

Все функции высшего порядка в FP являются встроенными.

Многие рекурсивные функции могут быть выражены нерекурсивно с поиощью одной или комбинирующих форм.

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

Рассмотренная в пункте 6 сравнительная семантика нескольких аппликативных языков программирования, позволяет перейти с 3 концептуального уровня на 4.

  1.  Заключение.

Подитоживая проделанную работу, хотелось бы высказать некоторую неудовлетворённость тем, что не удалось предъявить такое важное понятие, как модели Д.Скотта, которые являются по сути моделью лямбда-исчисления.

Результаты работа следующие:

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

Практическая часть: в реализованный в рамках семинара демонстрационный прототип системы FLINT помещён учебный материал по первым трём пунктам в заданной иерархии.

Переспективы работы:

Дальнейшее развитие концептуальных возможностей системы FLINT.

Наполнение предметной области.

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

  Благодарности

В заключение хочу выразить глубокую признательность своему научному руководителю Владимиру Ивановичу Громыко за неоценимую помощь и постоянную поддержку в работе и Николаю Павловичу Трифонову за ценные критические замечания при редактировании диплома. Также хочу поблагодарить однокурсников  Мигачёва Павла, Захарову Наталью, Ванькову Алену и Тагера Дмитрия, с которыми было тесное и плодотворное сотрудничество на протяжении всей работы. Приношу благодарность аспирантам Маханько Илье и Мисуркину Павлу за огромную помощь в реализации демонстрационного прототипа системы, а также  весь коллектив семинара «Обучающие системы» за постоянную помощь.

  1.  Список литературы.

  1.  Ãðîìûêî Â.È., Êó÷åâñêèé Þ.Â., Ïàí÷óê Î.À. Ðàçâèâàþùåå îáó÷åíèå â êîìïëåêñå îáó÷åíèÿ îñíîâàì èíôîðìàòèêè. Ïåäàãîãè÷åñêàÿ èíôîðìàòèêà, 95, ¹2.
  2.  Кнут Д.Е. “Программирование как искусство”. Лекции лауреатов премии Тьюринга за первые 20 лет. Москва, “Мир”, 1993
  3.  Громыко В.И. Базовое обучение информатике. Вестник МГУ. Серия 15. Вычислительная математика и кибернетика, 95, №2.
  4.  Громыко В.И., Колядко М.В., Трифонов Н.П. Компьютерная система в комплексе обучения основам информатики. Педагогическая информатика, 95, №2.
  5.  Минский “Форма и содержание в информатике”.
  6.  Моисеев Н. Н. “Алгоритмы развития”
  7.  Математическая логика в программировании. Сборник статей под ред. М.В. Захарьящева и Ю.И. Янова, Москва, “Мир” 1991.
  8.  Роджерс Х.“Теория рекурсивных функций и эффективная вычислимость”, Москва, “Мир” 1972
  9.  Буллос Дж., Джеффри Р.“Вычислимость и логика”, Москва, “Мир” 1994
  10.  Грис Д.“Наука программирования”,Москва, “Мир” 1984
  11.  Дал У., Дейкстра Э., Хоор К. “Структурное программирование”
    Москва, “Мир” 1975
  12.  “Данные в языках программирования”. Сборник статей под ред. В.Н.Агафонова, Москва, “Мир” 1982
  13.  “Семантика языков программирования”. Сборник статей под ред В.М.Курочкина, Москва,”Мир” 1980
  14.  Энгелер “Метаматематика элементарной математики”, Москва “Мир”, 1987
  15.  Гэри,Джонсон “Вычислительные машины и труднорешаемые задачи”
  16.  Ахо А., Хопкрофт Дж., Ульман Дж.“Построение и анализ вычислительных алгоритмов”,Москва, “Мир”  1979
  17.  Х. Барендрегт “Лямбда - исчисление: его синтаксис и семантика“
  18.  А. Филд, П. Харрисон “Функциональное программирование“
  19.  Колядко М. В.  Развивающее обучение информатике в системе FLINT. Дипломная работа. Кафедра Алгоритмических Языков, ВМК МГУ, Москва - 93, научный руководитель Громыко В. И.
  20.  Панчук О. А. Развивающее обучение в системе FLINT. Аппликативный стиль. Дипломная работа. Кафедра Алгоритмических Языков, ВМК МГУ, Москва - 94, научный руководитель Громыко В. И.

  [21] Сафонова Л.А. Развивающее обучение в системе FLINT. Аппликативный        cтиль - среда развития. Среда саморазвития на основе теоремы компактности.  Дипломная работа. Кафедра Алгоритмических Языков, ВМК МГУ, Москва - 96, научный руководитель Громыко В.И.

  [22] Маханько И.А. Формирование теоретического мышления обучаемого в системе FLINT. Дипломная работа. Кафедра Алгоритмических Языков, ВМК МГУ, Москва - 97, научный руководитель - Громыко В.И.

  

                                 6. Приложения.

Приложение A. SECD-машина.

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

SECD-машина интерпретирует выражения -исчисления.

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

Замыкание представляет собой замкнутое выражение. Будем записывать замыкания в виде:

[ id, exp, env], где

id  - идентификатор связанной переменной в Л-выражении,

exp - тело Л-выражения,

env - контекст, содержащий связи свободных переменных тела.

Элемент env - это пара вида (id, value).

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

Работа SECD-машины заключается в осуществлении переходов из одного состояния в другое.

Состояние SECD-машины это 4-х элементный кортеж (S, E, C, D), где

S - стек объектов, используется при вычислении рекурсивных выражений; стек будем рассматривать как список, причем голова списка слева,

E - контекст, то есть список пар вида (id, value),

C - управляющая строка, то есть оставшаяся часть вычисляемого выражения,

D - дамп, то есть предыдущее состояние, используется для возврата из вызова функций.

Переходы определим с помощью функции переходов из одного состояния в другое.

1 Функция переходов.

Для текущего состояния (S, E, C, D) следующее состояние определяется стеком С.

Обозначения: 

value(X,E) - значение X в данном контексте E, причем value(K,E)=K для любого E, если K константа.

head(S) - голова списка S (самый левый элемент),

var(Лx.E)=x,

body(Лx.E)=E,

tail(S) - “хвост” списка S (список S без первого элемента),

:S - добавить элемент X в начало списка S.

Итак, приступим к описанию функции переходов:

1) Если управляющая строка непустая и первым её элементом является X=head(C), то мы имеем следующие 4 варианта:

(a) X - это константа или идентификатор. Величина, связанная с X в текущем контексте проталкивается в стек S, и объект X удаляется из управляющей строки C. Таким образом, следующее состояние определяется в виде: (value(X,E)::S, E, tail(C), D).

(b) X - это -абстракция. В этом случае мы формируем замыкание, добавляем его в стек S, и следующее состояние имеет вид ([var(X), body(X), E]::S, E, tail(C), D).

(c) X=FA, то есть X - это применение выражения F (функции) к выражению A (аргументу). При энергичной реализации (см п.4.2.1) выражения А и F вначале вычисляются, а затем величина F применяется к величине А. Это выполняется с помощью замены элемента FA в управляющей строке на 3 элемента F, A, @, где @ - это специальный символ применения, который (как увидим далее) при своём появлении в начале управляющей строки вызывает применения верхнего элемента стека к элементу, находящемуся непосредственно под ним. Таким образом, следующее состояние имеет вид: (S, E, (A::(F::(@::tail(C)))), D).

(d) X=@, где @ - специальный признак применения. Выражение в вершине стека должно быть или примитивной функцией, или замыканием в соответствии с ранее определёнными преобразованиями состояний. Если стек S=f::a::S’, то мы имеем следующие 2 подслучая:

(i) Если f - это примитивная функция, она применяется к a. Результат этого применения заменяет f и a в стеке S, а символ @ удаляется из управляющей строки. Следующее состояния имеет вид: (f(a)::S’, E, tail(C), D).

(ii) Если f - это замыкание [V, B, E’], то выражение тела (B) вычисляется в контексте E, дополненном связью V с a. Однако, перед тем, как сделать это, состояние машины нужно запомнить, чтобы можно было продолжить работу после того, как вычисление В закончится. Это состояние представляет собой текущее состояние машины (кортеж из 4-х элементов) с удалёнными верхним элементом управляющей строки и двумя верхними элементами стека. Новый стек пуст, новый контекст представляет собой контекст применяемого замыкания, дополненный связью идентификатора связанной переменной с выражением аргумента, а новая управляющая строка состоит из единственного элемента. Поэтому следующее состояние имеет вид: ((),(V,a)::E’, B, (S’, E, tail(C), D)).

2) Управляющая строка С - пуста. Вычисление текущего (под)выражения считается законченным, и его результатом является единственный элемент стека S (для синтаксически корректных выражений). Состояние, хранящееся в вершине дампа D, восстанавливается, а только что полученный результат проталкивается в новый стек. Если D=(S’, E’, C’, D’), то следующее состояние имеет вид (head(S)::S’, E’, C’, D’).

     Приложение B. Язык программирования Лисп.  ОПРЕДЕЛЕНИЯ:

АТОМ - число или идентификатор.  [1,  c.5],  [2, c.64]

NIL - "пустой" атом. Эквивалентная запись: ()

Т - " истина".

S-ВЫРАЖЕНИЕ:

1) любой атом => S-выражение;

2) S-выражения A, B => S-выражение (A.B)  [2, c.65-66]

СПИСОК - заключенная в круглые  скобки  последовательность лисповских

S-выражений  ,  разделенных пробелами.  [1,c.5],[2,c.65]

ВЫЧИСЛИМОЕ ВЫРАЖЕНИЕ  -  выражение,  имеющее значение. Значения В.В.  могут быть получены в результате вычислений. При этом  число - вычислимое выражение, значение - оно само.  Атомы Т (истина) и NIL (ложь) имеют значение, совпадающее с  ними самими.  Идентификаторы  имеют значения, если являются  именами переменных.  Список  вида (f a1 a2 ...  an) или (g)  имеет значение,  если f  или  g,  соответственно,  является  обозначением функции, а a1, a2, ... an являются аргументами  функции f,  а g не имеет аргументов. Значением списка является  список из  значений  его  элементов.

[1, c.6]

БАЗОВЫЕ ФУНКЦИИ: [2, c.79-94], [1, c.8-14]

- обработки списков:

 (CAR x) ==>  1-й эл-т списка x;

 (CDR x) ==> список из эл-тов x без 1-го;

 (CONS x,  y) ==> список-конкатенация:  (car (cons x y)) = x; (cdr (cons x y) = y;

 (LIST x1,... xn) = ( x1 ... xn);

 (ATOM x) ==> T если x - атом, иначе NIL;

 (EQ x y) ==> T если x и y совпадают, иначе NIL;

 (NULL x) ==> T если список x не пуст, иначе NIL;

- управления ходом вычислений:

 (QUOTE x) ==> x; блокирует вычисление своего параметра;

 (EVAL x) ==> вычисляет x, затем вычисляет значение  полученного  выражения;

 - цикл: (DO x (p s1 s2 ... sn) e1 e2 ... ek)  - Особая функция.  Список x пустой либо вида (v1 .. vt),  где vi - либо идентификатор,  либо  (идентификатор  начальное_значение [шаг]), где начач_знач и шаг -- вычислимые выражения, причем  шаг  может  отсутствовать.       Выполнение -- вначале объявляются локальные для DO переменные ( из x),  при этом им присваиваются начальные значения (если  не указано - NIL).После этого проверяется пре- дикат p.  Если истинно, то вычисляются s1,...sn, а значение sn становится значением DO. Выполнение завершается. Если же значение p ложно,  то вычисляются последовательно e1,...ek. После этого  вычисляются шаги и присваиваются локальным переменным. Так продолжается до тех пор,  пока значение p  не станет истинным.  Порядок описания vi в списке не влияет на результат.  [1, c.38-39]

  - условие: (COND (p1 e11 ... e1n1)    [1, c.12]

                    (p2 e21 ... e2n2)

                             ...

                    (pk ek1 ... eknk)) - Функция последовательно  вычисляет значения предикатов  pi до тех пор,  пока не встретится pj,  значение которого отлично от  NIL;  в  этом  случае функция вычычисляет  последовательно все ej1,...ejnj, а ее значением становится значение ejnj.

ФАКТИЧЕСКИЙ ПАРАМЕТР - аргумент функции. [1, c.7]

ОБЫЧНАЯ ФУНКЦИЯ - функция, при выполнении которой сначала вычисляются фактические параметры, а затем выполняются действия,  предписанные данной функцией. [1, c.7]

ОСОБАЯ ФУНКЦИЯ  - функция,  при выполнении которой вычисляются лишь некоторые фактические  параметры, либо  параметры вовсе не вычисляются. [1, c.7]

ЛАМБДА-ВЫРАЖЕНИЕ - специальное выражение, используемое в качестве обозначения функции : (LAMBDA a e1 e2 ... en), список а может быть пустым;

обращение к -выражению:  ((LAMBDA (a1 ... ak) e1 e2 ... en) p1 ... pk)

1)  последовательно  вычисляются  фактические параметры  p1, ... , pk;

2) значение  каждого  pi  (i=1..k) присваивается соответствующему формальному параметру,  который внутри -выражения  служит локальной переменной (a1 ... ak);

3) последовательно вычисляются e1, e2 ,..., en а значение en становится значением обращения к -выражению. [1, c.14], [2, c.105]

ОПРЕДЕЛЕНИЕ ФУНКЦИЙ  -  имя  вместе с поставленным ему -выражением:      (DEFUN f a e1 e2 ... en), где f - имя определяемой функции, а - список идентификаторов  формальных  параметров,  а e1, e2, ..., en - выражения,  вычисляемые при выполнении функции и  составляющие ее тело. [1, c.15]

РЕКУРСИВНАЯ ФУНКЦИЯ - функция, во время выполнения тела  которой  встречается обращение к ней самой. [1, c.15]

РАЗРУШАЮЩАЯ ФУНКЦИЯ - функция,  изменяющая  внутреннюю структуру списков:

(RPLACA X Y) - обычная функция, заменяет левую ссылку  -(car X)- в первом звене непустого списка X  ссылкой  на  выражение Y. Значение функции - измененный X.

(RPLACD X Y) -- обычная функция, заменяет правую ссылку -(cdr x)- в первом звене непустого списка X на выражение Y. Значение функции - измененный X.

(NCONC X Y) -- заменяет ссылку в последнем звене списка X  ссылкой  на Y,  значением функции при этом становится  измененный список X.  Если X - пустой, то значением становится Y.    [1, c.29]

ФУНКЦИОНАЛЫ - функции,  имеющие  в  своих  аргументах другие  функции; имеющие  функцию  как  результат.  [1, c.33-36], [2, c.249-257], *[2, c.259-269]

МАКРОСРЕДСТВА -- функции,  вычисляющие свое тело перед выполнением.

[1, c.42-43]

                        ЛИТЕРАТУРА:

     1. Семенов М. Ю.  Язык Лисп для персональных ЭВМ. М.:

     МГУ, 89.

     2. Хювенен Э. Сеппянен И. Мир Лиспа. М.: Мир, 90.

      Приложение C. Язык программирования FP.  Основные определения:

FP-система состоит из трёх компонентов: объектов, примитивов и комбинирующих форм.

ОБЪЕКТЫ в FP-системе существуют трёх типов:

- Основание - является неопределённым объектом и представляет ошибочное состояние, т.е. если при вычислении выражения получается то вычисления завершаются  и выдаётся сообщение об ошибке.

Атомоы в FP-системе аналогичны атомам в Лиспе (см. Приложение В).

Последовательность - это симметричный (в том смасле, что для каждой операции, работающей с головой списка, существует симметричная операция, работающая с хвостом) список, не имеющий типа. Последовательность записывается как набор объектов через запятую, заключённый в угловые скобки ( < > - пустая последовательность - аналог NIL Лиспа). Последовательность сохраняет основание, т.е. последовательность не определена, если не определён хоть один её член. Последовательность имеет очевидное сходство со списком Лиспа (см. Приложение  В).

Примитивы - предварительно определённые функции, которые поддерживаются непосредственно реализацией (см. Базовые функции Лиспа). В FP применение функции f к аргументу х обозначается f : x, а если f - функция от к аргументов, то её применение к x1, ... , xk записывается как f : < x1, ... , xk >. Некоторые важные примитивы:

id - Тождественная функция id: x = x

1,2,... - Функции селекторы: применение ‘i’ к последовательности даёт i-й элемент,

например 3:<a,b,c,d>=c.

1r,2r,... - аналогично предыдущему, но с конца, например 2r:<a,b,...,y,z>=y.

hd - (аналог CAR Лиспа) - 1-й эл-т последовательности;

tl - (аналог CDR Лиспа) - входная последовательность без 1-го элемента.

hr,tr - аналогочно hd,tl соответственно, но с конца.

null - проверка входной последовательности на пустоту (аналог NULL Лиспа).

- функция йота - имея целый аргумент n0, возвращает последовательность первых n положительных целых, например: :5=<1,2,3,4,5>; :0=< >.

distl - формирует из заданных объекта и последовательности последовательность пар: distl:<y, < x1, x2, ..., xn >>=< <y,x1>, <y,x2>, ..., <y,xn>>

distr - аналогично distl, но справа: distr:<< x1, x2, ..., xn >,y>=< <x1,y>, <x2,y>, ..., <xn,y>>

Все примитивы являются строгими, т.е. они возвращают , если применяются к  .

Комбинирующая форма - програмная конструкция, т.е. строительный блок, с помощью которого конструируются новые функции. Функции пользователя вводятся с помощью слова def: def f = ..., тело f определяется с помощью комбинирующих форм.

В FP существуют шесть комбинирующих форм:

  1.  Константа - функция, которая при применении к любому определённому объекту всегда даёт один и тот же результат - обозначается подчёркиванием.
  2.  Условное выражение - имеет следующий синтаксис: pq;r где p,q,r функции. В применении к х: (pq;r):x = q:x, если p:x=T; = r:x, если p:x=F; = иначе. Например

(eq1 ; 2) : <5,6> при вычислении даст 6 т.к. eq:<5,6>=F и 2:<5,6>=6. Функцию максимума двух объектов можно описать так: def max= >1;2 тогда max:<2,3>= =(>1;2):<2,3>={т.к. >:<2,3>=F}=2:<2,3> =3

  1.  Композиция функций f и g записывается в виде fg и означает (fg):x=f:(g:x).

С помощью конструкций строятся последовательности. Конструкция и n функций записывается в виде [f1, f2, ..., fn] и означает [f1, f2, ..., fn]:x=<f1:x, f2:x, ..., fn:x>. Например (+[id,id]):x=+:([id,id]:x)=+:<x,x>=x+x.

В FP нельзя выражать функции высшего порядка, определённые пользователем. Однако существуют встроенные функции высшего порядка:

         - присенить-ко-всем - применяет входную функцию к каждому элементу в заданной последовательности аргументов: ( f):< x1, x2, ..., xn >=< f:x1, f:x2, ..., f:xn >

        / - правая вставка - определяется следующим образом:

    (/f):<x>=x; (/f):< x1, x2, ..., xn >=f:< x1, (/f):<x2, ..., xn >>. Например  (/+):< x1, x2, ..., xn >=

= x1+x2+ ...+ xn.

       \ - левая вставка - аналогична правой вставке, но действует с другой стороны:

    (\f):<x>=x; (\f):< x1, x2, ..., xn >=f:< (\f):<x1, x2, ..., xn-1 >, xn >.


      
Приложение D. Схема FLINT.

 Приложение Е. Схема БД FLINT.

Понятия, задачи и примеры для общности хранятся в одной таблице:

NOTIONS

NID | NAME | STATUS | HINT | TYPE | DEFINED | RESERVED

NID (NUMBER 5) - óíèêàëüíûé èäåíòèôèêàòîð ïîíÿòèÿ, çàäà÷è, ïðèìåðà (ïðîñòðàíñòâî èäåíòèôèêàòîðîâ îäíî äëÿ âñåõ)

NAME (CHAR 128) - символьное имя понятия (задачи / примера)

STATUS (NUMBER 1) - идея, опорное (целевое) понятие, промежуточное понятие (впоследствии можно добавить статусов)

HINT (CHAR 128) - к какому стилю/категории относится (пока в основном включено для удобства ввода)

TYPE (NUMBER 1) - определяет, понятие это, задача или пример

DEFINED (LOGICAL) - определено понятие или нет (т.к. пока будет много неопределенных понятий)

RESERVED (NUMBER 10) - зарезервировано для служебных целей

Окрестности хранятся в таблицах:

AREA_A, AREA_B, AREA_P, AREA_E

NID | NID1

AREA_A - окрестность «вширь»

AREA_B - окрестность «вглубь»

AREA_P - окрестность задач

AREA_E - окрестность примеров

Динамическая модель обучаемого ведется в двух таблицах:

DMO

UID | NAME | HINT | LAST_NID | RESERVED

DMO_HIST

UID | NID | FROM_NID | DIALOG_RES

UID (NUMBER 5) - уникальный идентификатор учащегося

NAME (CHAR 128) - имя учащегося

HINT (CHAR 128) - в каком состоянии сейчас находится

LAST_NID (NUMBER 5) - последний просмотренный документ

RESERVED (NUMBER 10) - зарезервировано

каждая запись в таблице DMO_HIST соответствует просмотренному понятию/задаче/примеру

UID (NUMBER 5) - к какому учащемуся относится запись

NID (NUMBER 5) - идентификатор понятия/задачи/примера

FROM_NID (NUMBER 5) - откуда пришел на документ с номером NID

DIALOG_RES (NUMBER 1) - результаты диалога-опроса

 

1) Правило -преобразования основано на том, что выражения (x. Ex) и E обозначают одну и ту же функцию при условии, что x не является свободной переменной в Е, тогда (x. Ex) А = E А для любого выражения А.


 

А также другие работы, которые могут Вас заинтересовать

63956. Информационная система управления проектами в сбласти клинической лабораторной диагностики 3.29 MB
  Объектом исследования дипломного проекта является компания специализирующаяся в области лабораторной медицины в частности в области клинической лабораторной диагностики. Предметом исследования в дипломном проекте является деятельность данной компании в области управления проектами.
63958. Характеристика института соучастия в уголовном праве Российской Федерации 139.13 KB
  Достаточно большое количество фикций и презумпций при квалификации преступления совершенного несколькими лицами распространенность общественно опасных деяний которые совершаются их объединенными усилиями а также неисчислимое количество условностей при обосновании их ответственности обусловливают...
63959. Проект процесса оказания услуг по изготовлению женской верхней одежды в ателье первого разряда. Основное изделие – женское полупальто 11.86 MB
  Целью выпускной квалификационной работы является разработка процесса оказания услуг по изготовлению женской верхней одежды. Для проектирования процессов предприятия сервиса выбрано женское демисезонное полупальто.
63961. Объединение парка маломощных компьютеров в сеть 162.97 KB
  Цель моей работы организовать работу офисной сети, рассредоточить пользователей и организовать распределенное хранение данных между несколькими компьютерами. В рамках моей работы мне нужно выбрать ОС моим требованиям. В организации есть 4 компьютера, на базе процессора Core i5, и нужно объединить их в сеть.
63963. Електропостачання та електрообладнання цеху з дослідженням енергетичних режимів роботи асинхронного електроприводу 1.1 MB
  Метою даної бакалаврської роботи є: систематизація, закріплення і поглиблення теоретичних знань та практичних навичок і здатність застосування цих навичок і знань під час вирішення конкретних електротехнічних задач за напрямом підготовки...
63964. Повышение надежности вычислительных комплексов в отделе кадров ОАО «Агрофирма «Птицефабрика Сеймовская» 577.5 KB
  Сейчас агрофирма является лидером в производстве куриных яиц в Приволжском федеральном округе и входит в десятку крупнейших птицефабрик яичного направления России. Достижение таких успехов не обошлось без внедрений новых технологий и модернизации старых.