Связывание. Замыкание функций | MetodPro.ru

Реклама на сайте

Связывание. Замыкание функций


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

X-> (A B)

Y->(C D), если x->C, то X-> (A B) заменится на то X->С.

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

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

Замыкание =  [λ-выражение, окружение]

Пример. F=λx.x*2+y и контекст {y->3}, то замыкание функции f будет представлять собой f->[ λx.x*2+y, {y->3}]. Если определения функций являются взаимно – рекурсивными, то при вычислении функционального значения возникает ряд трудностей, которые связаны с тем, что выражения e1,e2,ek из блока letrec должны вычисляться в окружении, в котором формальные параметры x1,x2…xk связаны и вычислены. Однако значения, с которыми они должны быть связаны являются значениями выражений e1, e2, ek. Чтобы обойти эти трудности можно использовать рекурсивное окружение. В этом случае, если обозначить рекурсивный контекст через альфа, то значение каждого ei является замыкание вида альфа [ei,альфа], где в контексте альфа каждые переменные из x1,x2.. связаны с соответствующим значением e1,e2… .

α = {x1 -> [e1,α]

x2->[e2,α]

Xk-> [ek,α]}

Когда во время вычисления либо выражение E, либо любого из выражений ei встречается ссылка на переменную xi, то в качестве ее значения берется замыкание вида [ei,α]

(letrec (dlin ( quote (a b)))

( dlin  (lambda (x)

         (cond (equal x (quote ()))

                   (quote 0)

                   (add (quote 1) (dlin (CDR x)))

))

))

Для вычислений берется контекст, в котором переменной dlin соответствует замыкание вида:

α = {dlin -> [λx. (cond (equal x (quote ()))

                   (quote 0)

                   (add (quote 1) (dlin (CDR x))), α] x-> (a,b)}

Поскольку список является непустым, то выполняется рекурсивный вызов dlin (cdr x). При этом  

 

Мы вызываем функцию dlin. При этом значение переменной dlin остается прежним, а контекст α пополняется новой связью. α = { x->(b)} При этом обеспечивается доступ ко всем необходимым е. Контекст α будет пополнятся новыми связями до тех пор, пока не будет истинно условие выхода из рекурсии. В этом случае на каждом шаге к полученному значению будет добавляться единица.



Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем