Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!icdoc!syma!aarons From: aarons@syma.sussex.ac.uk (Aaron Sloman) Newsgroups: comp.lang.lisp Subject: Re: Why aren't CL functions 1st class objects? Summary: being able to create new functions is important Keywords: functions as first class objects Message-ID: <3563@syma.sussex.ac.uk> Date: 3 Oct 90 22:01:47 GMT References: <1990Sep13.202219.21047@oracle.com> <3437@skye.ed.ac.uk> <3806@goanna.cs.rmit.oz.au> <3450@skye.ed.ac.uk> <3477@skye.ed.ac.uk> Organization: School of Cognitive & Computing Sciences, Sussex Univ. UK Lines: 119 jeff@aiai.ed.ac.uk (Jeff Dalton) writes: > Another source for claims about "first class" is Stoy's book on > denotational semantics. He says something about what "first class" > means, and gives some examples, but does not (if I recall correctly) > try to condense the definition into a neat little list or "bill of > rights". > > One of the examples is a function that returns a function. It may > have been a definition of composition, but I'm not sure. In any > case, compose can be written in Scheme or Common Lisp; it cannot > be written in (portable) C. I suspect that the lists of rights > have this sort of thing in mind when they talk about objects > being "returned as results". > Yes I think you have hit the nail on the head: whatever the people who made such lists (of features of first class objects) might have had in mind, I suspect that this is perhaps the most important, or one of the most important features of languages that are thought of as treating functions as "first class" objects. What I assume you are talking about is the ability to create new functions at run-time, as opposed simply to the ability to return them as results, store them in data-structures, etc. Run time function creation adds enormously to the expressive power of a language, especially if you already have functions that can take functions as arguments and then apply them. Being able to create new functions that can then be handed as arguments to old ones enormously increases the re-usability of functions, allowing many decisions to be left to the program at run-time instead of all possibilities having to be anticipated by the programmer and explicitly coded in advance. Function composition is just one example. Another is being able to provide a general function that can be instantiated to different specific forms in different contexts. (Function composition is an instance of this.) There are several different techniques for run-time function creation that I can think of off the top of my head: 1. Create a function data-structure that can be interpreted. Easy in any language that normally provides an interpreter and a rich collection of data structuring facilities. Many languages make it possible to write interpreters for new languages. E.g. in C one can write an interpreter for Lisp. 2. Create compiled functions at run time, e.g. from a list or other structure defining the function. I have the impression that having an incremental compiler is more powerful than being able simply to (a) create object files, (b) dynamically link in object files. For many purposes (a) and (b) would be too slow. 3. Partial application: freezing values into a pre-existing procedure by binding some of its formal parameters to actual instances. The Pop family makes very heavy and frequent use of this (e.g. a function that takes a character repeater and creates an item repeater uses partial application to produce new instances of a general function.) 4. Lexical closures Less efficient (??) but more general. E.g. allows you to define a function that returns a family of functions sharing some environment. (You can do this with partial application too but it's more clumsy.) (Using partial application and lexical closures is generally far more efficient than incrementally compiling new procedures, though it may be better to compile a new procedure when it is complex and likely to be used repeatedly. However, the ability to create a new definition and compile it is more general. It doesn't require that a suitably general schema already exist.) 5. Create a function object by combining a function that has dynamically scoped free variables with a binding environment. I believe this was available in several lisp systems prior to Common Lisp. But I don't know if anyone ever uses it now that lexical closures are available. It's possible, but tortuous, in Pop-11, but as far as I can see has no advantages over partial application or lexical closures. I've probably missed something important? Should the creation of a process that can be run and suspended and re-run and remembers its environment in-between, be another example? (Some lisps and Pop-11 provide this. Simlua-67 had a simplified version.). Not many languages that I am aware of can do all these things. In fact, apart from Common Lisp and Pop-11 are there any others? (T perhaps? I can't remember enough about it.) Prolog seems to provide a similar kind of power to function creation in a totally different way, insofar as it allows new rules to be added to the database by programs (interpreted or compiled, depending on the implementation.) Allowing a new class to inherit a method from its superclass is in some ways like partial application or creation of lexical closures. (The latter can be used as an implementation technique for OOP.) Scheme and ML provide lexical closures, which probably give most of the generality. An ML implementation may permit incremental compilation, but as far as I know it is not part of the definition of the language. Ditto Scheme? I suspect there are ways in C of creating new structures and putting machine instructions into them, then running them. But this is not so much a principled feature of the language, as an indication of how low level it is? Aaron