Trying to learn about the "Code as Data" feature of CL, I'd like to
have some feedback if I'm on the right track or already misusing
things. So it would be nice if somebody could take the time to comment
on the following toy-code.

Consider the following example: I have a list of names (let's call it
*names*), represented as (first-name last-name) lists. I now want to
write a function that, given two strings, returns a list of all
"matching" names, where a nil argument matches all strings. For
example:

(defvar *names* '(("John" "Doe") ("Jane" "Doe") ("John" "Wayne")))

(get-matching-names "Jane" "Doe") => (("Jane" "Doe"))
(get-matching-names "John" nil) => (("John" "Doe") ("John" "Wayne"))
(get-matching-names nil "Doe") => (("John" "Doe") ("Jane" "Doe"))

Pretending *names* might be huge and testing whether an argument is
nil might be expensive, I don't want to do the test for every name, so
the general idea is to first build some function based on the passed
arguments that returns whether a given name matches, and use this to
filter the list of names, like this:

(defun get-matching-names (first-name last-name)
  (let ((predicate <somehow build the predicate function here>))
    (loop for name in *names*
          if (funcall predicate name)
          collect name)))

(BTW: Although I'm reasonably sure that there is some function that
returns a list of all elements in another list that satisfy a given
predicate -- like in (filter #'evenp '(1 2 3 4)) => (2 4) -- I didn't
find it right now. So I reinvent it using LOOP for now, but I would
appreciate it if someone could point me a ready-made version.)

So here's what I came up with so far:

(defun get-matching-names (first-name last-name)
  (let ((predicate (eval `(lambda (name)
                            (and ,(if first-name
                                      `(string= ,first-name (first name))
                                    t)
                                 ,(if last-name
                                      `(string= ,last-name (second name))
                                    t))))))
    (loop for name in *names*
          if (funcall predicate name)
          collect name)))

While this might be not optimal (`(get-matching-names nil nil)' would
use `(lambda (name) (and t t))' where `(lambda (name) t)' would be
sufficient), it doesn't look too bad, IMHO. One thing that still bugs
me is the use of EVAL. I tried using FUNCTION, but that doesn't seem
to work with a backquoted expression (as far as I understand, because
backquote falls under the clause that forbids macros and special forms
as the NAME-argument to FUNCTION). Given that EVAL doesn't seem to
have a better reputation among CLers than it's equivalents in other
languages, I wonder: is there a better way to get a function from a
list built at runtime?

(defun get-matching-names (first last)
  (if (null first)
      (if (null last)
          *names*
        (remove-if-not #'(lambda(pair)
                           (string= last (second pair)))
                       *names*))
    (if (null last)
        (remove-if-not #'(lambda(pair)
                           (string= first (first pair)))
                       *names*)
      (remove-if-not #'(lambda(pair)
                         (and (string= first (first pair))
                              (string= last (second pair))))
                     *names*))))

If you want to have closures, try

(defun get-matching-names (first last)
  (flet ((*generate-predicate (first last)
                              (if (null first)
                                  (if (null last)
                                      nil
                                    #'(lambda(pair)
                                        (string= last (second pair))))
                                (if (null last)
                                    #'(lambda(pair)
                                        (string= first (first pair)))
                                  #'(lambda(pair)
                                      (and (string= first (first pair))
                                           (string= last (second
pair))))))))
    (let ((predicate (*generate-predicate first last)))
      (if (null predicate)
        *names*
        (remove-if-not predicate *names*)))))

So thats what flet is supposed to do! Thanks, also for the pointer to
remove-if-not. That, however, raises another, completly unrelated
question: Why are the *-if-not forms deprecated? Is this something to
really worry about?

:)w

  There are at least two different ways to look at this.  The first is to
  realize that a compiler will expect to read code and then examine the
  mechanisms by which the compiler reads code.  Common Lisp has the
  function `read´ which is used by the compiler to read the code.  By
  making this an ordinary part of the language and exporting it to the
  environment that ordinary users can use, too, programs that need to work
  on code can use it to read code and be able to work with it without
  having to duplicate the work the compiler needs to do to read code.  You
  realize that this in sharp contrast to most other programming languages,
  which generally do not contain neither functionality nor the system types
  to deal with source code.  This leads us to the second way to look at
  code is data.  The fundamental data type for source code is the list, and
  this is the same list as user programs work with.  (Some therefore think
  that the only data type in Lisp is the list, but even though we do not
  represent source code with vectors or strings, these types are just as
  fundamental to the programmers as the list.  Just wanted to clear that
  thing up preventatively.)  Since the functions to manipulate the list are
  ordinary parts of the languages and exported to the user environment like
  `read´, there is some functionality waiting to happen like an emergent
  property of the language: functions called by the compiler to operate on
  the code being compiled.  Languages without `read´ invent some complex
  rewriting systems and a lot of theory to go with them, but Common Lisp
  offers the programmer the /macro/, which processes an expression in the
  language as data, but it really is code and momentarily be turned into
  machine code by the compiler.  This leads to yet another way to look at
  "code is data", because functions are also ordinary language objects and
  may be passed around at will.  This is usually referred to as first-order
  functions and not usually as "code is data".  Then there is `eval´, of
  course, but I personally think that this is not the regular meaning of
  "code is data", either.  Common Lisp would have "code is data" even if
  you did not have `eval´ or the compiler available at run-time.

| Pretending *names* might be huge and testing whether an argument is nil
| might be expensive, I don't want to do the test for every name, so the
| general idea is to first build some function based on the passed
| arguments that returns whether a given name matches, and use this to
| filter the list of names, like this:

  Although testing for `nil´ is among the fastest things a Common Lisp
  program can do, it will probably slow things down a bit, so this is not
  an unreasonable plan.  However, actually constructing the code at runtime
  is not a good idea in this particular case.  Much better techniques are
  available.  For instance, while you have seen that you can create a
  /predicate/ according to the parameters, there are other options.

(defun get-matching-name (first-name last-name)
  (cond
   ((and first-name last-name)
    ;; if multiple matches for one full name are possible, use
    ;; (remove (list first-name last-name) *names* :test-not #'equal)
    (find (list first-name last-name) *names* :test #'equal))
   (first-name
    (remove first-name *names* :test #'string/= :key #'first))
   (last-name
    (remove last-name *names* :test #'string/= :key #'second))
   (t
    *names*)))

  It really would be useful to agree on a name for the opposite of
  `remove´/`delete´, like perhaps `collect´/`retain´.

| While this might be not optimal [...], it doesn't look too bad, IMHO.

  I think run-time construction of functions like this should be done when
  you have an input language that is more complex to handle than the code
  that would process it as an interpreted mini-language.

| One thing that still bugs me is the use of EVAL.

  Note that (compile nil '(lambda ...)) produces a compiled function.

| Given that EVAL doesn't seem to have a better reputation among CLers than
| it's equivalents in other languages, I wonder: is there a better way to
| get a function from a list built at runtime?

  `eval´ is perfectly acceptable when the purpose is to evaluate user code
  or expressions from an input language.  As a general principle: If the
  code you evaluate does not come from a run-time source, you should not
  perform run-time evaluation of it, either.

[ If you should dislike the tone or any part or aspect of the contents of
  this message so much that you feel compelled to attack or denounce me
  instead of staying focuesd on the questions you asked and the purpose you
  had when you asked them, please do not post your hostility. ]

--
Erik Naggum, Oslo, Norway

  They were deemed to be replaceable with `complement´ that was created to
  make the `:test-not´ keywords obsolete because the semantics of supplying
  both `:test´ and `:test-not´ arguments was unclear.  In practice, using
  `complement´ in preference to `-if-not´ and `:test-not´has not been a
  succcess.

| Is this something to really worry about?

  No.  The `-if-not´ functions will remain in a future version of the
  standard as it was a mistake to deprecate them.  However, the likelihood
  of there being a future version of the standard is pretty low, too, so if
  you want to use `:test-not´ arguments, rest assured that they have
  well-defined semantics when not used in the presence of `:test´ and vice
  versa.

  The complications mainly involve the use of `apply´ on an argument list
  that may contain `:test´ or `:test-not´ arguments and you supply other
  arguments before them.  The obvious solution of using the first match is
  underspecified and cannot be trusted to be implemented everywhere.
  However, if an implementation chooses to treat an argument list like
  `:test-not foo :test bar´ to mean that `bar´ will be called and not `foo´,
  it is clearly a design mistake and should be reported as a bug.

--
Erik Naggum, Oslo, Norway

    HM> One thing that still bugs
    HM> me is the use of EVAL. I tried using FUNCTION, but that doesn't seem
    HM> to work with a backquoted expression (as far as I understand, because
    HM> backquote falls under the clause that forbids macros and special forms
    HM> as the NAME-argument to FUNCTION). Given that EVAL doesn't seem to
    HM> have a better reputation among CLers than it's equivalents in other
    HM> languages, I wonder: is there a better way to get a function from a
    HM> list built at runtime?

You can also look up what (COERCE lambda-expression 'FUNCTION)
does.  It is not so different from (COMPILE NIL lambda-expression),
but COERCE might not compile the lambda expression which might make
debugging easier (depending very much, of course, on the
implementation and how it is configured).

In fact, if

  (typep foo 'function) => nil

which implies that FOO evaluates to a lambda expression, then

  (compile nil foo) === (compile nil (coerce foo 'function))

On the other hand, the FUNCTION special form, of course, must have
the literal lambda expression available at compile time, and it
does not evaluate its argument (which wouldn't have made sense), and
#'(LAMBDA ...) is read as (FUNCTION (LAMBDA ...)) and not as
(FUNCTION (QUOTE (LAMBDA ...))).  This also shows why FUNCTION
cannot be given a backquoted form.

And just in case, let me explicitly note that since interesting
lexical closures (i.e., over non-null lexical environments) can
only be made at compile time, (COERCE lambda-expression 'FUNCTION)
(and hence (COMPILE NIL lambda-expression)) will only produce
non-interesting lexical closures.

EVAL has a very good reputation, I think, but code that uses EVAL
where it is not warranted would have its reputation suffer.  (Don't
shoot down sparrows with spitfires...)

---Vassil.

    HM > Why are the *-if-not forms deprecated?

    WD> Have a look at notes section for the `complement' function in the
    WD> hyperspec[1]. My reading of this is that if you wrapper the test
    WD> function in the *-if form with something that with the same input return
    WD> the logical opposite, and lets for the sake of argument call this
    WD> `complement', you no longer require assoc-if-not, count-if-not,
    WD> delete-if-not, find-if-not, member-if-not, nsubst-if-not,
    WD> nsubstitute-if-not, position-if-not, rassoc-if-not, remove-if-not,
    WD> subst-if-not and substitute-if-not.

The important issue here was that including both :TEST and
:TEST-NOT in the list of keyword arguments to various functions was
conceptually not a good idea.  On the other hand, given *-IF and
COMPLEMENT, *-IF-NOT are merely redundant, but do not otherwise
spoil anything, so it is less likely for them to actually go away.

Personally, I don't like the deprecation of *-IF-NOT functions, for
example, because I find REMOVE-IF-NOT more useful than REMOVE-IF.  I
used to think KEEP-IF would be a better name for REMOVE-IF-NOT, but
seeing Erik Naggum's suggestion, I would vote for RETAIN-IF.

---Vassil.

    [...]
    WD> [2] (Hmmm. Employer: The plane has just crashed and we have identified
    WD> the problem to your use of the deprecated count-if-not function in the
    WD> guidance systems. You: I can explain that. There was this bloke on
    WD> comp.lang.lisp who said...)

So let me be another bloke on comp.lang.lisp who says, `Recompile
your code if you get a new version of the language implementation,
even if you are sure the format of compiled code didn't change.'

---Vassil.

    [...]
    VN> I would vote for RETAIN-IF.

...not that there is likely to be such a vote any time soon,
regardless of whether I get to vote...

---Vassil.

 > On the other hand, given *-IF and COMPLEMENT, *-IF-NOT are merely
 > redundant, but do not otherwise spoil anything, so it is less likely
 > for them to actually go away.
I think this is true but I think what I was saying is true too. I have
now found the reference I half remembered[1]. In the benefits
section discussing the removal of the if not stuff, the ANSI issue states:

"Takes a step toward being able to flush the -IF-NOT functions and the
:TEST-NOT keywords, both of which are high on the list of what people
are referring to when they say Common Lisp is bloated by too much garbage."

This is my interpretation of this. I've not been involved in the ANSI
process and look forward to being corrected if I am in error.

 > Personally, I don't like the deprecation of *-IF-NOT functions, for
 > example, because I find REMOVE-IF-NOT more useful than REMOVE-IF.
I agree -- if it were in my gift to make this decision.

:)w

    [...]
    VN> On the other hand, given *-IF and COMPLEMENT, *-IF-NOT are merely
    VN> redundant, but do not otherwise spoil anything, so it is less likely
    VN> for them to actually go away.
    WD> I think this is true but I think what I was saying is true too.

Yes; I was merely complementing your post, making the point that we
have two kinds of `garbage' here: the co-existence of :TEST and
:TEST-NOT is (somewhat) harmful garbage, while the existence of
*-IF-NOT is (perhaps) redundant, but otherwise harmless garbage.

Anyway, this point is largely moot (see Erik Naggum's post earlier
in this thread), so my post is also redundant garbage, though
otherwise harmless...

---Vassil.