Блок рекурсивных определений letrec | MetodPro.ru

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

Блок рекурсивных определений letrec


Вычисление рекурсивного блока осложняется тем, что список значений z не может быть вычислен сразу, поскольку выражения e1…ek являются взаимно рекурсивными. В этом случае целесообразно использовать рекурсивное окружение или замкнутое, которое позволяет ссылаться само на себя, до тех пор, пока не будут получены окончательные значения выражений e1…ek. Для этого создадим фиктивный список значений v’, который будет равносоставленным по отношению к списку n’ = ((x1…xk).n). В списке v’ на первом месте поместим специальный атом, обозначающий незавершенное значение  v’ = (Ω.v). Затем, вычислим все фактические параметры e1…ek Относительно нового окружения n’ v’ z=evallist[(e1…ek),n’,v’]. При этом мы получим множество замыканий, в которых присутствует фиктивное окружение (ссылка на n’ и v’). Теперь заменим атом Ω списком z, используя для этого вспомогательную функцию  complete. Эта функция получает на вход 2 аргумента: список v’ и список z; и заменяет голову списка v’ (Ω) списком z. В результате будет сформировано циклическое или замкнутое окружение.

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

Правило вычисление выражения letrec:

eval[(letrec e (x1 e1)…(xk…ek),n,v)] = eval [e,n’,complete(v’,z)], где n’ = ((x1…xk).n), v’ = (Ω.v), z= evallist[(e1…ek),n’,v’].

(letrec e

             (f (lambda y’ e’))

 

Ω

 

             (g (lambda y2 e2)))



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

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