Abstract
We view Backus' FP as a framework consisting of a set of basic tools for programming in the functional style, which can accommodate a large number of changeable parts. We argue that functional forms logically belong to the latter because they are specific to the data type. To support a programming methodology based upon this view, we extend FP by introducing "fdef" — a facility for defining new functional forms, based upon the extended definitions of Backus. In an "fdef", the parameters of the form are specified on the left and the function that the functional form is to return as its result is written on the right. We use lazy evaluation instead of APPLY to implement this extension because we feel that APPLY is a hindrance to the algebraic style of proving FP programs. The significant feature of "fdef" is that algebraic laws can be generated from the definitions of functional forms.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arvind, Brock, J. D. and Pingali, K. "FP1.5: Backus' FP with higher order functions", M.I.T. Lab. for Computer Science, (Unpublished 1984).
Backus, J., "Can programming be liberated from the von Neumann style? A functional style and its algebra of programs," Comm. of the ACM, 21, 8, August 1978.
Backus, J., "The algebra of functional programs: function level reasoning, linear equations, and extended definitions" in Formalization of Programming Concepts, Lecture Notes in CS, Vol. 107, Springer-Verlag, April 1981.
Burge, W. H., Recursive Programming Technniques, Addison-Wesley Publishing Co., Reading, Massachusetts, 1975.
Curry, H. B. and Feys, R., Combinatory Logic, Vol. 1, North-Holland Publishing Co., Amsterdam, 1958.
Henderson, P. and Morris, J. M., "A lazy evaluator," Proc. of the 3rd ACM Symp. on Principles of Prog. Lang., 1976.
Henderson, P., Functional Programming, Applications and Implementation, Prentice-Hall, Englewood Cliffs, NJ, 1980.
Roberts, Nirmal P., Implementation of Higher-Order Functions in FP, M.Tech. thesis (August 1985), Dept. of Computer Sc. & Engg., Indian Institute of Technology Kanpur.
Smith, B. C., Reflection and Semantics in a Procedural Language, Ph. D. dissertation, M.I.T. Lab. for CS, LCS/TR/272, 1982.
Srinivas, Y. V., M.Tech. thesis (April 1985), Dept. of Computer Sc. & Engg., Indian Institute of Technology Kanpur.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1986 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Srinivas, Y.V., Sangal, R. (1986). A generalization of Backus' FP. In: Nori, K.V. (eds) Foundations of Software Technology and Theoretical Computer Science. FSTTCS 1986. Lecture Notes in Computer Science, vol 241. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-17179-7_8
Download citation
DOI: https://doi.org/10.1007/3-540-17179-7_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-17179-9
Online ISBN: 978-3-540-47239-1
eBook Packages: Springer Book Archive