In reading Graham's _ANSI Common Lisp_, I encountered functions that
  return functions.  There's an example in the book of a definition of
  complement:

  (defun our-complement (f)
    #'(lambda (&rest args)
        (not (apply f args))))

  I understand this definition; a function name is taken, and a
  function is returned.  The returned function takes any number of
  optional arguments and returns the complement value of calling the
  passed function name on args.

  I tried to twist Graham's function a bit:

  (defun my-complement (f)
    (lambda (&rest args)
      (not (apply f args))))

  This returns a lambda expression.  Since I know:

  ((lambda (x) (+ x 1)) 1) => 2

  I assumed:

  ((my-complement #'oddp) 2)

  Would be a valid function call, but my compiler seems to disagree.
  Can someone please explain why this fails?

Look for #' and funcall in the help files.

        (our-complement (lambda (x) (evenp (1+ x))))

Will return a function as well.

        (funcall (my-complement #'oddp) 2)

will do what you want.

Cheers

In CL, the car of a form is a function name.  (lambda (x) x) is
the name of an anonymous function.  Think of functions as being
named by either common nouns [lambda expressions] or proper nouns
[lambda expressions you've given a name to].  Likewise, the FUNCTION
special form takes a function name, and #'(lambda (x) (+ x 3)) is
the "common noun" form of something you'd call ADD3 if you called
it often enough to care about giving it a name.

In Scheme, the care of a form is an expression in the variable
namespace.  This makes life simpler in some ways and more complex in
others.  It means you cannot simultaneously accomodate a variable
named list and a function named list, even the simultaneous presence
of two meanings of the same word is both semantically well-formed and
something that the human brain is known to have experience with, to
process correctly and efficiently, and is known through tons of
experiential data about the formation of natural languages to actively
prefer.  (I know of no modern, successful, human language that does
not overload word meanings based on context.  Surely if having only
one meaning per word, independent of context, were important, there
would be some evidence of a similarly anal natural language that has
survived and thrived.)

When you write (foo x y z) to call a function in Lisp, FOO is a symbol
naming the function.  I.e., it's not a function object, just its name.
(lambda ...) is just another way of naming a function, so you get to
write ((lambda ...) x y z) to call that function.

When you write (foo x y z) to call a function in Scheme, FOO is a
function object -- you can put a symbol there, of course, or even an
arbitrary expression, since the position is evaluated, but ultimately
what you want is a function.  (lambda ...) doesn't _name_ a function;
it's an expression that you can evaluate to get a function.

Note that the first position is *not* evaluated in Lisp -- (lambda ...)
is just the name of a function, not something you can evaluate; in
CLtL Common Lisp (the original Common Lisp, prior to the ANSI
standardization), LAMBDA was not a function, a macro or a special
form; it had no definition at all, and (lambda (x) (1+ x)) would just
signal an "undefined function" error.

In ANSI Common Lisp, LAMBDA is a macro whose expansion is the same
LAMBDA form wrapped in a FUNCTION form; e.g.,

  (lambda (x) (+ x 1)) => (function (lambda (x) (+ x 1)))

which is the same as #'(lambda (x) (+ x 1)), of course.  FUNCTION is a
special operator, similar to QUOTE, so the lambda form inside it is
*not* calling for another invocation of the macro.

In your first case, ((lambda (x) (+ x 1)) 1) in Lisp, you're just
using the fact that a lambda form names a function.  The position is
not evaluated, and the macro doesn't come into play.

In your second case, (funcall (lambda (x) (+ x 1)) 1), you're using
the LAMBDA macro; its expansion is using the FUNCTION special form to
get an actual function object named by the lambda form.

In your third case, ((lambda (x) (+ x 1)) 1) in Scheme, you're
evaluating the lambda form itself to produce a function.
[i.e., lambda is a special form in Scheme; it's not in CL]

  You have asked a very typical Scheme question, and people are somewhat
  sensitive to this sort of question because Scheme victims keep asking it
  over and over.  It seems that this one-namespace thing acts like a virus
  that takes over the host system to produce more of its own kind.

  The problem is one of faulty reasoning and muddy thinking, and this is
  also typical of Scheme victims.

| CMUCL groks ((lambda (x) (+ x 1)) 1) for me just like a Scheme would, it
| doesn't only accept (funcall (lambda (x) (+ x 1)) 1).  Is that a liberty
| taken by CMUCL authors to make it more friendly for Schemers, or is that
| in accordance with CL specs?

  This has already been asnwered with a reference to the Hyperspec.  Please
  pay attention, or you just annoy people.  Perhaps you did not understand
  the answer you got.  Let ma assume you did not, and try a different angle:

  (foo ...) calls the function named foo.  ((lambda ..) ...) calls the
  "anonymous" function that _is_ (lambda ...).  Kent calls the function
  itself its name, but I find that confusing -- your name is _not_ your
  identity, it is a label on your identity.  An anonymous function has its
  own identity as a function, but no name.  Specifically, it _is_ a
  function.  Now, you can call the function directly, or you can call it by
  its name, which the compiler will resolve for you to either be the
  lexically defined functionn or the globally defined function that is the
  value of the symbol with the name you gave.  The first position in a form
  either _is_ a function or _names_ a function.  (In addition to all the
  other types of operators, of course.)

  Now, how is this different from Scheme and from your faulty reasoning?
  Suppose you think that (lambda ...) _evaluates_ to a function when it is
  in the first position of a form.  This is clearly not how Common Lisp
  does it, because it expressly does _not_ evaluate the first position, but
  it _is_ how Scheme does things.  If you did not pay much attention to the
  differences in evaluation rules between Scheme and Common Lisp -- and it
  seems you have not really studied the evaluation rules of either language
  just sort of adopted them by osmosis (example) -- you would perhaps think
  that the operator is somehow evaluated in a different way in Common Lisp.
  But Common Lisp does expressly _not_ evaluate the operator.  The operator
  either is a function or names a function.  So if you place something
  there that would need to be _evaluated_ to produce a function, it is just
  not how Common Lisp does things.  In summary, ((lambda ...) ...)  works
  because it _is_ a function, not because it _evaluates_ to a function.

  In (funcall (lambda ...) ...), (lambda ...) evaluates to a function, and
  the _function_ funcall is called with a regular evaluated value.  I quote
  from the standard and its entry on funcall:

The difference between funcall and an ordinary function call is that in the
former case the function is obtained by ordinary evaluation of a form, and
in the latter case it is obtained by the special interpretation of the
function position that normally occurs.

  Note the special interpretation.

let's look at LAMBDA in common-lisp

i did this in clisp

[1]> ((lambda (x) (+ x 3)) 4)
7
[2]> (#'(lambda (x) (+ x 3)) 4)

*** - EVAL: #'(LAMBDA (X) (+ X 3)) is not a function name

[3]> (funcall #'(lambda (x) (+ x 3)) 4)
7

the function object #'(lambda (x) (+ x 3)) does not _name_ a function,
it _is_ a function.  apparently, by contrast, (lambda (x) (+ x 3)) is,
in itself, a function _name_.

i gather this not so much from myoptically parsing the words in the
error message but condensing other people's posts around me.  the
error message just happened to be very accurate and straightforward
for this purpose.

all this is somewhat obscured by the macro overloading that lambda
has.  plain (lambda (x) (+ x 3)) will magically expand to #'(lambda
(x) (+ x 3)) in the appropriate place (like as an argument to mapcar).
and thus you have

[4]> (funcall (lambda (x) (+ x 3)) 4)
7

this is just the LAMBDA side.  but i hope it helps.

If you want to put a function object there, you'll have to type
(#.#'(lambda ...) 4) [or just (#.(lambda ...) 4)]