Практическая часть диплома нацелена на обеспечение обучающей системы FLINT материалом для компьютерного учебника-задачника:
· реализовать задание практикума для аппликативного стиля с предъявлением спецификаций на основании теоретической части диплома (задача 1).
3 Аппликативный стиль. Денотационная семантика. (класс Прагматика).
В пункте 1.1 было декларировано, что связывание прагматики программирования с теорией информатики мы проводим на основании взаимодополняющих семантик в ракурсе современного аксиоматического метода. В пункте 1.2. была представлена походящая модель ПО в компьютерном учебнике-задачнике и были зафиксированы опорные моменты, которые обеспечат нужную связь. Цель этого пункта - показать, насколько близка прагматическая сторона предмета к его теоретическим основам, насколько легче её восприятие через теорию предмета. Поэтому здесь проводится анализ стиля по определенным в пункте 2 требованиям.
3.1 Проблемная ориентированность (программистский аспект).
Как отмечалось в пункте 2 выявлению связи теоретического материала с прагматическим служит подход по разработке учебного материала на основании общих принципов, выраженных в следующих понятиях: главные ориентиры обучения, идеи, наследуемые ориентиры обучения, среда информационного моделирования, современный аксиоматический метод, взаимодополняющие семантики, системный аналитик. Применим подход к аппликативному стилю, чтобы выделить ключевые понятия, которые необходимо будет предъявить в учебнике-задачнике.
В первую очередь исследуем общее в проблемной ориентированности конкретных языков стиля. Вспомним, что идеей среды саморазвития аппликативного стиля является функция, а наследуемыми ориентирами - смешанные вычисления, комбинаторные вычисления, языковые расширения в направлении приближения свойств стиля к выражению в нем “что делать”.
3.1.1 Сравнение языков программирования стиля.
Во всех языках функционального программирования способы описания функций базируются на тех или иных формализмах, созданных в математической логике: лямбда-исчислении (Лисп), комбинаторной логике (Миранда), нормальных алгоритмах Маркова (Рефал), рекурсивных уравнениях Эрбрана-Гёделя (KRC). В более современных языках, таких, как Миранда, используются и некоторые другие достижения математики, например, теоретико-множественная нотация. В чистых языках функционального программирования обычно имеется одна главная операция - применение функции к аргументу, или аппликация, из-за чего их часто называют аппликативными. Прозрачная математическая семантика этой операции позволила Д. Тернеру (автору Миранды) говорить о ”семантической элегантности” аппликативных языков (см. пункт 3.4). Не случайно поэтому процесс написания программ на этих языках в чем-то сродни математической деятельности. Обсуждение самих этих языков позволяет легко перейти на теорию предмета, тогда возникает связь теории и практики, необходимая для целей РО.
Для рассмотрения выберем следующие языки: Норе, Миранда, Лисп и FP. Проблемная ориентированность языков определяется функционалами или функциями высшего порядка. Концепция функций высшего порядка возникает из идеи о том, что функции должны иметь тот же статус, что и любой объект данных, так чтобы они сами могли быть входными и выходными данными других функций.
Так, например, в Норе, как и в большинстве функциональных языков, не существует ограничений на количество и сложность подобных функций. Однако в языке FP нет средств для определения пользователем функций высшего порядка. Вместо этого язык обеспечен небольшим набором встроенных функций высшего порядка, которые рассматриваются как программно-встроенные блоки. В языке Миранда осуществлен совершенно иной подход к функциям высшего порядка: там нет механизма для явного определения лямбда-выражения, функциональные объекты в нем генерируются частичным применением существующих функций.
Язык Норе.
Рассмотрим следующие функции языка Норе:
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 : (alpha®beta)#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).
Язык Миранда.
Общий подход, принятый в языке Миранда, очень похож на подход языка Норе. но значительно отличается от него подходом к рассмотрению функций. Миранда - это строго типизированный язык высокого уровня, поддерживающий типы данных пользователя и полиморфизм, но он значительно отличается от Норе подходом к рассмотрению функций. Главное отличие в том, что Миранда - ”карринговый” язык, то есть в нем объекты, значениями которых является функция, строятся путем частичного применения существующих функций, а не с помощью явных лямбда-выражений, как это делается в Норе.
Каждая функция в языке Миранда является по существу функцией высшего порядка. Когда мы на этом языке записываем определение вида
f x y z = ¼
мы можем обычным образом интерпретировать f как функцию от трех аргументов x, y, z или, как в Норе, в качестве функции от одной тройки аргументов (кортеж). Однако в языке Миранда в действительности f является функцией высшего порядка только от одного аргумента x. Результатом применения f к аргументу E1, который мы запишем в виде fE1, является другая функция, снова только от одного аргумента y. Применение этой функции к следующему аргументу E2 снова дает функцию от оного аргумента z. Полное применение f записывается в виде fE1E2E3. Итак, мы пришли к понятию карринг.
Карринг - обработка функций от n аргументов как конкатенации n функций от одного аргумента.
Посмотрим, как будет выглядеть функция 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=y+x*x
прибавляет 25 к каждому элементу L. Заметим, что введенная функция может быть рекурсивной благодаря тому, что имеет имя.
Заметим также, что нет необходимости в том, чтобы все функции были карринговыми, поскольку Миранда предоставляет также механизм для построения кортежей и для декомпозиции этих кортежей с помощью сопоставления с образцом.
Язык Лисп.
Лисп является нетипизированным языком обработки списков, в котором программы и данные имеют одинаковое представление.
В языке Норе мы можем непосредственно записать обозначающее функцию выражение с помощью лямбда-выражения. В Лиспе существует идентичный механизм, только функция вводится с помощью специального атома 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)) ).