A FUNCTIONAL APPROACH TO COMPUTING: Notes 2000-03-15 S.Whitney FUNCTION: "any analytic expression whatsoever made up from that variable quantity and from numbers or constant quantities" [Euler/Boyer p.485] "5. In mathematics, a quantity so connected with another that no change can be made in the latter without producing a corresponding change in the former, in which case the dependent quantity is said to be a function of the other" [Webster's Twentieth Century Dictionary 1937] "4a. Also called correspondence, map, mapping, transformation. A relation between two sets in which one element of the second set is assigned to each element of the first set, as the expression y = 3x; operator. "4b. a formula expressing a relation between the angles of a triangle and its sides, as sine or cosine" [Random House Webster's College Dictionary 1997] Etymology: Lat. FONCTIO, a performance, EXECUTION [Webster 1997] FUNCTIONAL PARADIGM: Functions as objects, application as the basic interface? "...many [popular programming languages] prohibit functions (or procedures) from being the results of functions or the value of references, or sometimes even arguments to functions. In contrast, languages such as Iswim, PAL, Gedanken, Scheme, and ML were built around the rallying cry 'functions should be first-class citizens'." [Reynolds p.286] 1. CHRONOLOGY OF FUNCTIONS 1637 Descartes, La Geometrie: analytic geometry, curves (graphs) of equations 1671 Newton: calculus with "fluxions" 1694 Leibniz: "FUNCTIO" in calculus; symbolic notation 1734,48,50 Euler: "f(x); "sin x", "cos x", "tang x"; graph of a function 1751- d'Alembert, Encyclopedie: "fonction", "limite": functions as "rules" 1791 Gauss in a log table: "Primzahlen unter a (=) a/la" 1797 Lagrange, Theorie des FONCTIONS analytiques: "f'(x)" 1827 Abel, Recherches sur les fonctions elliptiques: "f x" 1829 Jacobi, Fundamenta nova theoriae functionum ellipticarum: "One must always (try to) invert" 1835 Hamilton: (a,b) for the complex numbers; complex plane known 1836 De Morgan, Treatise on the Calculus of Functions: British school (with Babbage, Boole) of symbolic algebra 1837 Dirichlet studying Fourier series: function as arbitrary correspondence [Boyer p.600] 1841 Jacobi, De determinantibus functionalibus: jacobians 1844 Grassmann, De lineale Ausdehnungslehre: n-vectors 1845 Cayley, On the Theory of Linear Transformations: linear algebra 1853 Hamilton, Lectures on Quaternions: 4-dimensional vector multiplication 1858 Cayley, Memoir on the Theory of Matrices 1860 Weierstrass: a continuous nowhere differentiable function (1872?) (also Bolzano 1830) 1881 Gibbs, Vector Analysis: linear algebra in the USA (with the Pierces) 1893 Heaviside, Electromagnetic Theory: Laplace transforms, operational calculus 1905 Einstein: tensors, transformations and special relativity 1908 Riesz: sets and arbitrary functions for integration 1920 Schonfinkel: combinators 1925 Heisenberg & Jordan: quantum mechanics and matrices 1930 van der Waerdan, Moderne Algebra, based on E.Noether's lectures at Goettingen 1936 Church & Rosser: lambda calculus to prove undecidability 1941 Church, The Calculi of Lambda-Conversion 1942,45 Eilenberg & MacLane: categories 1950 Schwartz: distributions 1958 Curry & Feys, Combinatory Logic 1960 Naur et al, Report on...ALGOL 60 (rev.1963) 1960 McCarthy, Recursive functions of symbolic expressions... 1962 Iverson, A Programming Language: APL 1962 McCarthy et al, LISP 1.5 Programmer's Manual: nil, cons, def, lambda, cond, append, car, cdr 1963 Lawvere: categorization of universal algebra (1970? topoi) 1966 Landin, The next 700 programming languages: ISWIM 1968 ? Macsyma, later (1975?) Maple, Mathematica 1969 van Wijngaarden et al, Report on the algorithmic language ALGOL 68 1969 Sammet, Programming Languages: History and Fundamentals 1970 Scott, Outline of a mathematical theory of computation 1971 Wirth, The Pascal programming language; 1972 Ritchie: C 1975 Sussman & Steele, SCHEME: An interpreter for extended lambda calculus 1978 Backus, Can programming be liberated from the von Neumann style? (ACM Turing Lecture): variables, assignment, repetition; aliasing, side effects, bottleneck; FP: ? LisP - lambda + some APL + id, comp, construc [sin, cos], constant, condition, while 1980 Iverson, Notation as a tool of thought (ACM Turing Lecture); ? J 1980 Seldin & Hindley, To H.B.Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism 1980 Henderson, Functional Programming:... 1982? Manna & Waldinger, The Logical Foundations of Computer Science: axiomatization of lists 1984 Barendregt, The Lambda-Calculus, North-Holland 1984 Steele, Common LISP: The Language 1985 Turner, Miranda: A non-strict functional language with polymorphic types 1987 Ghezzi & Jazayeri, Programming Language Concepts, 2d ed, chap.7: Functional programming (FP, LISP, APL) 1987 Peyton Jones, The Implementation of Functional Programming Languages: combinators mentioned [Reynolds p.312]) 1987 Seely, Categorical semantics for higher order polymorphic lambda calculus 1990 Huet, Logical Foundations of Functional Programming 1991 Milner et al, The Definition of Standard ML 1991 Pierce, Basic Category Theory for Computer Scientists 1992 Hudak et al, Report on the functional language Haskell 1993 A.Whitney: K 1996 Gosling et al, The Java Language Specification " During the nineteenth century, while Grassmann's hypercomplex numbers were hardly noticed, Hamilton's quaternion calculus fell flat on the mathematical world. Except for Tait and Gibbs, the majority of the scientists preferred to work with the old- fashioned Cartesian methods. Even as recently as thirty years ago the vector could hardly be said to have come into its own. In the preface to his ["Treatise on Vectorial Mechanics"] published in 1948, Milne records that he did not at first believe his teacher Chapman, when he told him (1924) that 'vectors were not merely a pretty toy, suitable only for elegant proof of general theorems, but were a powerful weapon of worka- day mathematical investigation, both in research and in solving problems of the types set in English examinations.' Since then mathematicians have ceased to look upon vectors as a 'mere shorthand for sets of Cartesian expressions' and have begun to realise that there is all the difference in the world between the old-fashioned methods of working with Cartesian co-ordinates and the new vectorial methods. The former is like picturing a building by looking at its plan and elevation, while the latter is like seeing it stereoscopically, that is, in its three- dimensional solidity. For, as Milene has remarked, the old- fashioned primary interest, to their projections on the three axes, whereas vector analysis provides a kinematic picture of the motion in question that gives far more insight into the phenomenon than the corresponding Cartesian analysis. Vector analysis views the phenomenon as a whole, and to that extent therefore it is more in tune with gestalt methodology. Because of its great power it is now being extensively applied to a whole gamut of diverse fields from econometrics to quantum mechanics." [J.SINGH, Great Ideas of Modern Mathematics, Dover 1959, p.91] 2. CONCEPTS: (o) Pre-functional: expression orientation, function definitions and calls, recursion (most languages) (a) Lists and vectors as (finite or 'fortuituous', vs. 'regular') functions: "Ever since the development of Lisp in the early 1960's, functional programming and list processing have been closely associated." [Reynolds p231]. Yet LisP has very poor vector management (car, cdr, cons). APL has excellent vector management but still distinguishes between vectors and functions. (b) Lambda calculus (function abstraction): f = Lxfx (lambda conversion) = Lyfy (alpha conversion or renaming of bound variables); (Lxe)d = e[d for x] (beta conversion); Lxex = e (eta conversion). Lambda calculus is central to the "functional programming community". It has been useful theoretically, to better understand the side effects of syntactic considerations such as renaming, but... "The intent is that renaming should preserve meaning... In fact, this property holds for most modern programming languages (functional or otherwise) but fails for a few early languages such as Lisp, Snobol and APL. ...its failure...is a rich source of programming errors..." [Reynolds p.233] (c) Combinators: identity Ix = x; first projector Kxy = x; distributor D(xy)z = (xz)yz; commutor Cxy = yx; constant; currying; axioms/equations between combinators are needed. "To work with combinators...look at the following parts of J: hooks (Curry's S) forks (one of Curry's, I forget which) reflex (~) (Curry's duplicator W) passive (~) (Curry's commutator C) rank (Curry's constant K, when applied to arrays) same ([ and ]) (Curry's identifier) @ @: & (Curry's compositor) ^:n (Curry's iterator) For example, in J you can define the commutativity of addition without variables by C =: + -: +~ (plus matches plus commute). Then 3 C 4 or any arithmetic pair yields 1." [Eugene McDonnell] (d) Category theory: composition not application is fundamental: (g.f)x = gfx ~= (gf)x . In the category of sets as objects and functions as morphisms, bijections are iso, injections mono, surjections epi, the empty set is initial and any one-element set is final. These concepts can be used as a set-replacing foundation for maths (Lawvere ca.1970) and theoretical com sci, but they haven't been much implemented to my knowledge. "Although we have avoided the topic of category theory, it is extremely useful in the investigation of intrinsic semantics [of types]." [Reynolds p.376] It's as if modern algebra, a level above programming, is more appropriate for theory/semantics than programming practice. (e) linear algebra: vectors, addition, scalar multiplication, scalar product; matrices, multiplication, identity, inverse, determinant, linear systems; least squares, quadratic forms,... (f) operators: functionals, dual space; delta, Laplacian (essentially the same as combinators) (g) functionalization of conditionals (AlgoL,APL,C,J,K)& loops(K) (h) algebraic manipulation: Macsyma, Maple, Mathematica; arbitrary precision (J also). This could be of interest for languages with lambda expressions, and has compiler optimization as an application. 3. REFERENCES: compilation of documents i know, with suggestions from the K list. Abbreviations: func.--> functional; math.--> mathematical; maths.--> mathematics; prog.--> programming Websites: www.abebooks.com, www.bookfinder.com, www.amazon.com BARENDREGT H. The Lambda Calculus: Its Syntax and Semantics, North-Holland 1984: "standard" CHURCH A. Introduction to Math.Logic, Princeton 1996, U$23: lambda approach COUSINEAU G, MAUNY M. The Func.Approach to Prog., EdiSciences 1995, Cambridge 1998: i found this today (3-16) in a bookstore; it seems to unite functional and logic programming and uses a dialect of ML CURRY H B. Foundations of Math.Logic, McGraw-Hill1963, Dover1977: general, some lambda and combinators FITCH F. Combinatory Logic, Yale : "my favorite intro" GHEZZI C, JAZAYERI M. Prog.Language Concepts, 2d ed, Wiley 1980,87,98: LisP and APL as (incomplete) func.languages GRASSMAN W K, TREMBLAY J-P. Logic and Discrete Maths, Prentice-Hall 1996: mention of func.prog.and DB management in a first year text on discrete maths. HOFSTADTER D R. Metamagical Themas, Basic Books 1985: several chapters on Lisp and recursion IVERSON K E. A Prog.Language, Wiley 1962: vector programming GRAHAM R L.et al. Concrete Maths:..., Addison-Wesley 1989,94 KX SYSTEMS. K Language Summary 1997 LEW A. Computer Science: A Math.Introduction, Prentice-Hall 1985: "comments on 'reduction' in APL and 'map' in LISP" NORDSTROM B.et al. Prog.in Martin-Lof's Type Theory:..., Oxford 1990: "prog.and intuitionistic maths." REVESZ G. Lambda-calculus, Combinators, and Functional Prog, Cambridge 1988: "compact survey of the subject" REYNOLDS J C. Theories of Prog.Languages, Cambridge 1998: imperative vs. func. ROSENBLOOM . Introduction to Math.Logic, : "combinators" SEBESTA R W. Concepts of Prog.Languages, Addison Wesley Longman 1999: chap.on func.prog. mentions LISP, Scheme, ML, COMMON LISP, Haskell; APL briefly mentioned elsewhere. WHITNEY S. Chronologie math.(notes de cours), UQAC 1995-8 WHITNEY S. Langage et traduction (notes de cours), UQAC 1997 www.rbjones.com/rbjpub/logic/cl/index.htm : "impressive web site" on lambda calculus and combinators http://www.latrobe.edu.au/www/philosophy/phimvt/j00syn.html : "Joy prog.language"; "lambda calculus, combinators, and...stack languages" "somewhere on the net (i've seen it recently), there is a very comprehensive set of lecture notes on the lambda calculus - at chalmers university perhaps?" 4. ACKNOWLEDGEMENTS: Thanks for comments and suggestions: S.Apter, B.Armstrong, B.Halchin, J.Karman, R.Macdonald, K.Mason, E.McDonnell, E.Naiman, J.Tuttle, A.Whitney, W.Winkler, M.Zarathustra