компиляции. Например, процедура устранения использования промежуточных структур данных в программах в значительной степени упрощается, когда программы написаны с использованием операторов рекурсии (Wadler, 1981; Launchbury & Sheard, 1995; Takano & Meijer, 1995). Основополагающая система для преобразования программ, написанных с использованием операторов рекурсии, в настоящий момент активно развивается (de Moor & Sittampalan, 1998).

Полиморфизм в программировании. Написание программ, имеющих специфический тип, положило начало новому направлению, названному полиморфизмом в программировании (Backhouseet и др., 1998). Формально такие программы задаются одним или более типом данных. Программному полиморфизму уже найдено множество применений, включая выбор подходящего образца (Jeuring, 1995), и решение различных проблем оптимизации (Bird & de Moor, 1997).

Языки программирования. Целый ряд экспериментальных языков программирования показывают, что использование операторов рекурсии является более рациональным способом задания рекурсивных функций. Сюда входят такие языки, как алгебраический язык ADL (Kieburtz & Lewis, 1994), язык программирования Charity (Cockett & Fukushima, 1992) и язык программирования PolyP (Jansson & Jeuring, 1997).

7. БЛАГОДАРНОСТИ

Я хотел бы выразить благодарность Эрику Мейджеру и членам группы Languages and Programming group в университете Ноттингема за многие часы интересных разговоров по поводу оператора fold. Я также благодарен Роланду Бакхаусу, Марку П. Джоунсу, Филиппу Уодлеру, и анониму JFP за их детальные комментарии к статье, на основании которых были проведены существенные улучшения содержания. Работа была написана при поддержке Engineering and Physical Sciences Research Council (EPSRC). Грант на исследование GR/L74491, Structured Recursive Programming.

8. ССЫЛКИ

1)Aarts, Chritiene, Backhouse, Roland, Hoogendijk, Paul, Voermans, Ed, & van der Woude, Jaap. (1992). A relational theory of datatypes. Available on the World-Wide-Web from http: www.win.tue.nl/win/cs/wp/papers/papers.html.

2)Backhouse, Roland, Jansson, Patrik, Jeuring, Johan, & Meertens, Lambert. 1998 (Sept.). Generic programming: An introduction. Lecture Notes of the 3rd International Summer School on Advanced Functional Programming.

3)Backus, John. (1978). Can programming be liberated from the Von Neumann style? A functional style and its algebra of programs. Cacm, 9 (Aug.).

4)Barendregt, Henk. (1984). The lambda calculus { its syntax and semantics. North-Holland. Revised edition.

5)Bird, Richard. (1989). Constructive functional programming. Proc. Marktoberdorf International Summer School on Constructive Methods in Computer Science. Springer-Verlag.

6)Bird, Richard. (1998). Introduction to functional programming using Haskell (second edition). Prentice Hall.

7)Bird, Richard, & de Moor, Oege. (1997). Algebra of programming. Prentice Hall.

8)Bird, Richard, & Meertens, Lambert. (1998). Nested datatypes. Jeuring, Johan (ed), Proc. Fourth International Conference on Mathematics of Program Construction. LNCS, vol. 1422. Springer-Verlag.

9)Bird, Richard, & Wadler, Philip. (1988). An introduction to functional programming. Prentice Hall.

10)Cockett, Robin, & Fukushima, Tom. (1992). About Charity. Yellow Series Report No. 92/480/18. Department of Computer Science, The University of Calgary.

11)de Moor, Oege, & Sittampalan, Ganesh. 1998 (Sept.). Generic program transformation. Lecture Notes of the 3rd International Summer School on Advanced Functional Programming.

12)Fegaras, Leonidas, & Sheard, Tim. (1996). Revisiting catemorphisms over datatypes

with embedded functions. Proc. 23rd ACM SIGPLAN-SIGACT Symposium on

Principles of Programming Languages.

13)Fokkinga, Maarten. 1994 (June). Monadic maps and folds for arbitrary datatypes. Memoranda Informatica 94-28. University of Twente.