Higher Order Function Syntax in Common Lisp

Question

I'm teaching myself Common Lisp using Norvig's Paradigms of AI Programming and came across something I didn't understand and he didn't explain.

(defun mappend (fn the-list)
  (apply #'append (mapcar fn the-list)))

What is the difference between calling a higher order function as follows, higherOrderFunc #'funcName funcArg and what he does when calling mapcar without #'? Is #' necessary when calling a higher order function?

Laster

Answer 1

Common Lisp has different namespaces for functions and variables.

(defun mappend (fn the-list)
   (apply #'append (mapcar fn the-list)))

Above MAPPEND gets defined with two local variables fn and the-list

APPLY gets passed the function value of APPEND.

MAPCAR gets passed the variable value of FN.

Similar see this:

CL-USER 129 >  (flet ((add-something (number)
                       (+ number 17)))
                (let ((add-something (lambda (number)
                                       (+ number 42))))
                  (list
                   (mapcar #'add-something '(1 2 3))
                   (mapcar add-something '(1 2 3)))))

->

((18 19 20) (43 44 45))

LET creates local variables, FLET creates local functions.

The first mapcar uses the function namespace and the second uses the variable namespace.

Common Lisp uses a special function namespace because it was thought to be more efficient (slightly easier to implement a fast Lisp) and to allow functions and variables to have the same name.

In Common Lisp we can write:

(defun list-me (list)
  (list list))

In Scheme, which does not have separate namespaces one would write something like this:

(define (list-me lst)
  (list lst))

Teazel

Can you explain the use of 'flet' and how it differs from 'let'? It seems define the scope of some temporary function in the way that 'let' defines the scope of some temporary variable. – Laster

One small addition to Rainer's answer in order to clarify a point that's implicit in it: When you call mappend, you need to pass the function argument as #'some-func. That gets the function value of the symbol some-func, which is then passed into mappend as the value of fn. – Bharat

Answer 2

#' is syntactic sugar for function: #'foo is read as (function foo).

Function is a special operator that returns the function value bound to the name given. If you pass a function as a parameter, that parameter (in your case, fn) has its value bound to the function. To pass it on to another function, you can simply put the variable name into the call form. However, to get the function value of a name, you need to access it with function.

Quinton

Answer 3

Using #' is not strictly required. If instead you simply pass 'foo the symbol-function will be invoked. Consider the following:

* (defvar foo #'(lambda (a) 'var))
* (setf (symbol-function 'foo) #'(lambda (a) 'fun))

* (mapcar 'foo '(a b))
(FUN FUN)

* (mapcar #'foo '(a b))
(FUN FUN)

* (mapcar foo '(a b))
(VAR VAR)

Practially #'foo or 'foo are equivalent:

X3J13 voted [...] to allow the 'function' to the only of type 'symbol' or 'function'; [...] one must use the 'function' special form [...] before a lambda-expression [...].

Specification of the function in flet has some interesting properties:

* (flet ((foo (a) 'FLET))
    (mapcar foo '(a b)))           ; Uses 'value' of foo
(VAR VAR)

* (flet ((foo (a) 'FLET))
    (mapcar 'foo '(a b)))          ; Uses 'function' of foo
(FUN FUN)

* (flet ((foo (a) 'FLET))
    (mapcar #'foo '(a b)))         ; Uses local binding 'flet' of foo
(FLET FLET)

Athalia

Do not do this, however; #'foo and 'foo are no more equivalent than (function foo) and (quote foo). That is to say, not very, even if they can be used in some of the same circumstances. Either way, using quoted symbols obscures the meaning of your code. – Transcalent

Not for local functions. (flet ((foo () 'bar)) (funcall 'foo)) does not work. Additionally there might be slight differences when using an optimizing compiler between (funcall (function bar)) and (funcall 'bar)). It's likely that the latter will always lookup the function via the symbol, while the first may see the lookup optimized away and using the current (during compilation) function binding during. A file compiler might want to do that. So: to be consistent using FUNCTION or #' is preferred. If you want late binding of global functions, use the symbol. – Teazel

Updated with flet use. Note: I agree use #' but my choice was not what was asked in the OQ. – Athalia