2 Постановка задачи: о связном предъявлении теории информатики и практики программирования в теме исполнения для теоретического мышления. 13 (стр. 21 из 25)
Запишем это представление посредством рекурсии, тогда в обращении к функции должно передаться базовое значение и аргумент n. Итак, обращение -1(1,n,0). Схема рекурсии с учетом -1(0,0), будет
-1(i,n,r)=
Сравнение реализации с реализацией Клини показывает, что получили эквивалентные схемы с точностью до обращения. Верификация на частном случае:
-1(1,3,0)®-1(2,3,1)®(3,3,2)®2
Рассмотрим пример с числами Фибоначчи. Порождающая схема будет выглядеть следующим образом:
Обращением к рекурсивной функции может быть F(1,1,n+r). Тогда схема рекурсии имеет вид
Fib(p,q,n,r)=
Так как параметр р не несет информационной нагрузки, то упростим схему, допустив обращение F(1,1,n,1). Схема рекурсии примет вид
Fib(i,p,n,q)=
Обратимся с Fib(1,1,5,1). Должно получиться 8.
Fib(1,1,5,1)®Fib(2,1,5,2)®Fib(3,2,5,3)®Fib(4,3,5,5)®Fib(5,5,5,8)®8
Итак, за счет согласованного рассмотрения логического и аппликативного стилей легко добывается знание, которое называют техникой накапливающего параметра или эффективной схемой МакКарти.
Неподвижная точка
Неподвижная точка является подходящим средством, чтобы показать возможности аппликативных языков. Рассмотрим абстракцию неподвижной точки
Y=lh.(lx.h(x x))(lx.h(x x))
Приспособим нашу функцию S к действию функционала Y.
S=lf.ln.
Развернем рекурсию
YS3®(lx.S(x x))(lx.S(x x))3
®S((lx.S(x x))(lx.S(x x)))3
Чтобы выделить существо дальнейших преобразований, изучим действие Y.
YS®S(YS)
Если предположить аппликативный (энергичный, вызов по значению) порядок вычислений, тогда зациклимся. Это произойдет из-за невозможности посчитать аргумент YS.
YS®S(US)®S(S(US))®S(S(S(US)))®¼
Если будут действовать отложенные вычисления (ленивые, вызов по имени), то есть будет нормальный порядок вычислений, тогда развернется рекурсия.
Перепишем наш пример.
YS3®S(US)3®
+
3® +(US(- 3 1))3® +(S(US)(- 3 1))3®Обозначив через S=ln.
+(S(- 3 1))3®
+(+(US(- 2 1))2)3®
+(+(1 2) 3)®
+ 3 3®6
Мы исходим из того, что примитивная функция + является строгой по отношению к своим аргументам. То есть она не будет выполняться пока не будут вычислены до конкретного числа оба аргумента.
Смешанные вычисления
Смешанные вычисления являются существом аппликативного программирования. Посредством обобщенной рекурсии (не примитивной) и бестиповости “произрастают” возможности интерпретации. Эта роль смешанных вычислений рассматривалась в дипломных работах [27], [28]. Здесь приводятся рассуждения на упрощенном примере.
Пусть задана примитивная функция +1=lx.(x+1).
Тогда можем посчитать +15®lx.(x+1)5®6.
Нарастим возможности за счет обобщения примитива до
+
lx.y.(x+y)и введения функции высшего порядка
F
lf.lx.(f x)Тогда, используя карринг, можем посчитать требуемое обращение F(+ 1) 5. Действительно
F(+1)5®lx.((+1)x)5®(+1)5®ly.(1+y)5®6
Введем двойную суперпозицию
К +1 вернулись для простоты записи. Попробуем посчитать +45 с помощью (+1) и F2. Можем действовать двумя способами. Обычный способ, соответствующий императивному стилю, представляется таким образом:
Þ+1(+17)®+18®9
Второй способ соответствует технике смешанных вычислений. Конструкцию предыдущего обращения F2+1 (+1(+15)) можем получить в виде F2+1(F2+15) посредством простого обращения F2F2+15. Это обращение ближе находится к формулировке “Что делать”. Действительно F2F2®lx.(F2(F2x)) то есть имеем выражение, которое двойную суперпозицию функции х, именно F2x, применит посредством двойной суперпозиции F2 (F2x).
F2 F2+1Þ F2 (F2+1)®lx.(F2+1)(F2x)
F2 F2+15Þ (F2+1)(F2+15)
Получили обещанное ранее обращение императивного случая. В дипломе [28] было показано, что пониманию “Что делать” также начинает помогать техника алгебры комбинаторов.
Денотационная семантика
За счет функционалов аппликативный стиль достигает хорошего уровня для формулировок “Что делать”. Приведем пример на языке FP. Функция факториал - рекурсивная
def fac=eq0®1, /*n=0®1
*O[id, facO(-O[id, 1])] /**(n, fac(n-1))
где O- функционал суперпозиции. Фактически запись передает посредством суперпозиции известное рекурсивное определение. Функция факториал нерекурсивна. Использует генератор t. Например,
t: 5®<1,2,3,4,5>
def facn=/*Ot
Означает а) сгенерировать последовательность чисел <1,...,n>; b) расставить (reduce) операцию * между числами последовательности слева направо 1*(2*(3*¼*(n-1 n)...)
Функция вычисления длины последовательности:
def len=null®0; /*nil®0
+O[1, lenO tl] /*+(1, len(tl(l)))
Нерекурсивная функция:
def len_n=/O+a1
Означает, а) заменить члены последовательности 1; в) суммировать их со значением, равным нулю в базовом случае. Например,
len_n:[a,b,c]®
/O+:[1,1,1]®
+(1,+(1,+(1,0)))®3
Знаменитая функция member
def mem=nullOI2®F;
eqO[I1, hdOI2]®T;
memO[I1, tlOI2]
Нерекурсивная функция поинтересней.
def mem_n=/or O a eq O distl
Конечно, без знания обращения к ней трудно догадаться, что происходит. Итак
mem_n:<1, <3,2,1>>®
/or O a eq:<<1,3>, <1,2>, <1,1>>®
/or O <eq:<1,3>, eq:<1,2>, eq:<1,1>>®
or(F, or(F,T))®T
Программирование без переменных
Во-первых, будем различать аппликативное и функциональное программирование. Аппликативный стиль выстраивается на построении текста - абстракции (функции) и аппликации (применение функции). Поэтому функционалы в нем моделируются. Функциональный стиль выстраивается на функциях и заданных функционалах. Т.к. это программирование без переменных, то вычисление осуществляется применением функционалов к функциям и значениям.
Воспользуемся теорией рекурсивной функции Клини, чтобы познакомить с функциональным стилем. Например, покажем, как можно обойтись без объектных переменных, что немыслимо для императивного стиля. Рассмотрим классический пример n! Зададим необходимые примитивы:
O=lx.O
J=lx.(x+1)
=lx1,...,lxn.xmЗададим необходимые функционалы:
суперпозиции
рекурсии
Определим х+у.
Таким образом, x+y через функционалы представляется следующим образом:
Посчитаем 3+3
3+0=
3+1=J
=1(3)=43+2=J
=J(4)=5Определим x*y
Таким образом, x´y через функционалы представляется
Посчитаем 3´2
3´0=О(о)=0
3´1=+(3,0)=3
3´2=+(3,3)=6
Ïîçâîëèì ñåáå ïåðåéòè ê ÿçûêó “ñâîáîäíîé öâåòèñòîé ïðîçû, îáåùàþùåé íè÷åì íå îãðàíè÷åííîå óäîâîëüñòâèå” [5]. Ýòî âûçâàíî íåîáõîäèìûì â âåê ñèñòåì ôèêñàöèåé öåëåïîëàãàíèÿ ïðîåêòà.
Âî-ïåðâûõ, õîòåëîñü áû îáúÿñíèòüñÿ ïî ïîâîäó âûáîðà çàäà÷è - áàçîâîå îáó÷åíèå èíôîðìàòèêå, ïðè÷åì ñ âûäåëåíèåì â íåé íàóêîåìêîãî ÿäðà. Äåëî â òîì, ÷òî íå ìû âûáèðàåì çàäà÷è, à îíè íàñ.  1969 ãîäó Ì. Ìèíñêèé [6] íà÷àë ñâîþ òüþðèíãîâñêóþ ëåêöèþ ñëîâàìè: “Ïðîáëåìà ñîâðåìåííîé èíôîðìàòèêè ñîñòîèò â íàâÿç÷èâîé îçàáî÷åííîñòè ôîðìîé â óùåðá ñîäåðæàíèþ”. Ìîæåì ñ óäîâëåòâîðåíèåì êîíñòàòèðîâàòü çíà÷èòåëüíîå ïðîäâèæåíèå, òàê êàê ïðîáëåìà óæå äîñòèãëà ïîëÿ çðåíèÿ îáðàçîâàíèÿ. Ïîñìîòðèì øèðå. Åñëè îïåðåòüñÿ íà òàêèå àâòîðèòåòû êàê À. Í. Óàéòõåä, Ê. Ïîïïåð è øêîëó ýâîëþöèîíèñòîâ (Í. Í. Ìîèñååâ, À. Í. Ñåâåðöîâ), òî ñëåäóåò ïðèçíàòü, ÷òî ñóùåñòâóþò ýïîõè ñìåíû ïîäñîçíàòåëüíîãî ñòèëÿ ìûøëåíèÿ (ñìåíû êàòåãîðèéíîãî àïïàðàòà). Áîëåå òîãî, óæå ïîäõîäèì ê òîìó, ÷òîáû ñ÷èòàòü íåîáõîäèìûì ôîðìèðîâàíèÿ óìåíèÿ ñàìèì íàñòðàèâàòüñÿ íà ðàçíûå êàòåãîðèéíûå ñòèëè (Ý. Â. Èëüåíêîâ, Â. Ñ. Áèáëåð). Ïðèçíàêîì ñìåíû ïîäñîçíàòåëüíîãî ñòèëÿ ÿâëÿåòñÿ óâåëè÷èâàþùàÿñÿ ðîëü ðàöèîíàëüíîãî. Ýòî åñòåñòâåííî, òàê êàê áàçà (êàê ÄÍÊ) äîëæíà ñîäåðæàòü ñâîè áóäóùèå ðåçóëüòàòû. Ñèíòåçèðóþùàÿ îñîáåííîñòü èíôîðìàöèîííîãî ìîäåëèðîâàíèÿ, çàìûêàåìàÿ ê òîìó æå íà êîíñòðóèðîâàíèè â ïðîãðàììèðîâàíèè, ôèêñèðóåò â íàñ êàòåãîðèéíûé àïïàðàò êëàññè÷åñêîãî íàó÷íîãî çíàíèÿ (È. Êàíò), íî ñ îñîáûì óïîðîì íà èíòåãðèðóþùóþ îñîáåííîñòü ñîçèäàíèÿ (òâîð÷åñòâà). Òåì ñàìûì ïðîèñõîäèò èçìåíåíèå íàñ êàê âèäà çà ñ÷åò ðàöèîíàëèçàöèè ñ íåîáõîäèìûì íàïîëíåíèåì òâîð÷åñêèì, à íå óçêîïðîôåññèîíàëüíûì. Êàê áû ìû íè ïðîòèâèëèñü ýòîìó, â êóëüòóðå äåéñòâóåò èíñòðóìåíò ïðèîáùåíèÿ (ñðàâíèì ñ ïèñüìåííîñòüþ) - ýòî êîìïüþòåð. Ïîýòîìó çàäà÷à âûáðàëà íàñ, íî ìû åå ðåøàåì â êîíêðåòíîé èíòåðïðåòàöèè: êîìïüþòåð êàê ÿçûêîâîå ñðåäñòâî ïðåäúÿâëåíèÿ çíàíèÿ äëÿ åãî èññëåäîâàíèÿ (âñïîìíèì: “ðåçóëüòàòîì âû÷èñëåíèÿ ÿâëÿåòñÿ ïîíèìàíèå à íå - ÷èñëî”).