DOC PREVIEW
UMBC CMSC 331 - Returning Functions

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

5Returning FunctionsThe previous chapter showed how the ability to pass functions as arguments leadsto greater possibilities for abstraction. The more we can do to functions, the morewe can take advantage of these possibilities. By defining functions to build andreturn new functions, we can magnify the effect of utilities which take functionsas arguments.The utilities in this chapter operate on functions. It would be more natural, atleast in Common Lisp, to write many of them to operate on expressions—that is,as macros. A layer of macros will be superimposed on some of these operatorsin Chapter 15. However, it is important to know what part of the task can bedone with functions, even if we will eventually call these functions only throughmacros.5.1 Common Lisp EvolvesCommon Lisp originally provided several pairs of complementary functions. Thefunctions remove-if and remove-if-not make one such pair. If pred is apredicate of one argument, then(remove-if-not #’pred lst)is equivalent to(remove-if #’(lambda (x) (not (pred x))) lst)6162 RETURNING FUNCTIONSBy varying the function given as an argument to one, we can duplicate theeffect of the other. In that case, why have both? CLTL2 includes a new functionintendedforcases like this: complementtakes a predicate p and returns a functionwhich always returns the opposite value. When p returns true, the complementreturns false, and vice versa. Now we can replace(remove-if-not #’pred lst)with the equivalent(remove-if (complement #’pred) lst)With complement, there is little justification for continuing to use the -if-notfunctions.1Indeed, CLTL2 (p. 391) says that their use is now deprecated. If theyremain in Common Lisp, it will only be for the sake of compatibility.The new complement operator is the tip of an important iceberg: functionswhich return functions. This has long been an important part of the idiom ofScheme. Scheme was the first Lisp to make functions lexical closures, and it isthis which makes it interesting to have functions as return values.It’s not that we couldn’t return functions in a dynamically scoped Lisp. Thefollowing function would work the same under dynamic or lexical scope:(defun joiner (obj)(typecase obj(cons #’append)(number #’+)))It takes an object and, dependingon its type, returns a functionto add such objectstogether. We could use it to define a polymorphic join function that worked fornumbers or lists:(defun join (&rest args)(apply (joiner (car args)) args))However,returningconstant functionsis the limit of what we can do with dynamicscope. What we can’t do (well) is build functions at runtime; joiner can returnone of two functions, but the two choices are fixed.On page 18 we saw another function for returning functions, which relied onlexical scope:(defun make-adder (n)#’(lambda (x) (+ x n)))1Except perhaps remove-if-not, which is used more often than remove-if.5.2 ORTHOGONALITY 63Calling make-adder will yield a closure whose behavior depends on the valueoriginally given as an argument:> (setq add3 (make-adder 3))#<Interpreted-Function BF1356>> (funcall add3 2)5Under lexical scope, instead of merely choosing among a group of constant func-tions, we can build new closures at runtime. With dynamic scope this techniqueis impossible.2If we consider how complement would be written, we see that ittoo must return a closure:(defun complement (fn)#’(lambda (&rest args) (not (apply fn args))))The function returned by complement uses the value of the parameter fn whencomplement was called. So instead of just choosing from a group of constantfunctions, complement can custom-build the inverse of any function:> (remove-if (complement #’oddp) ’(123456))(135)Being able to pass functions as arguments is a powerful tool for abstraction.The ability to write functions which return functions allows us to make the mostof it. The remaining sections present several examples of utilities which returnfunctions.5.2 OrthogonalityAn orthogonallanguageisonein which youcanexpress alotbycombiningasmallnumber of operators in a lot of different ways. Toy blocks are very orthogonal; aplastic model kit is hardly orthogonal at all. The main advantage of complementis that it makes a language more orthogonal. Before complement, CommonLisp had pairs of functions like remove-if and remove-if-not, subst-if andsubst-if-not, and so on. With complement we can do without half of them.The setf macro also improves Lisp’s orthogonality. Earlier dialects of Lispwould often have pairs of functions for reading and writing data. With property-lists, for example, there would be one function to establish properties and anotherfunction to ask about them. In Common Lisp, we have only the latter, get.To2Under dynamic scope, we could write something like make-adder, but it would hardly everwork. The binding of n would be determined by the environment in which the returned function waseventually called, and we might not have any control over that.64 RETURNING FUNCTIONS(defvar *!equivs* (make-hash-table))(defun ! (fn)(or (gethash fn *!equivs*) fn))(defun def! (fn fn!)(setf (gethash fn *!equivs*) fn!))Figure 5.1: Returning destructive equivalents.establish a property, we use get in combination with setf:(setf (get ’ball ’color) ’red)We may not be able to make Common Lisp smaller, but we can do somethingalmost as good: use a smaller subset of it. Can we define any new operatorswhichwould, like complement and setf, help us toward this goal? There is at leastone other way in which functions are grouped in pairs. Many functions also comein a destructive version: remove-if and delete-if, reverse and nreverse,append and nconc. By defining an operator to return the destructive counterpartof a function, we would not have to refer to the destructive functions directly.Figure 5.1 contains code to support the notion of destructive counterparts.The global hash-table *!equivs* maps functions to their destructive equivalents;! returns destructive equivalents; and def! sets them. The name of the ! (bang)operator comes from the Scheme convention of appending ! to the names offunctions with side-effects. Now once we have defined(def! #’remove-if #’delete-if)then instead of(delete-if #’oddp lst)we would say(funcall (! #’remove-if) #’oddp lst)Here the awkwardness of Common Lisp masks the basic elegance of the idea,which would be more visible in Scheme:((! remove-if) oddp lst)5.3 MEMOIZING 65(defun memoize (fn)(let ((cache (make-hash-table


View Full Document

UMBC CMSC 331 - Returning Functions

Documents in this Course
Semantics

Semantics

14 pages

Java

Java

12 pages

Java

Java

31 pages

V

V

46 pages

Semantics

Semantics

11 pages

Load more
Download Returning Functions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Returning Functions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Returning Functions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?