Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Creating functions at runtime

10 views
Skip to first unread message

Henrik Motakef

unread,
Oct 5, 2002, 3:19:32 PM10/5/02
to
Hi,

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?

TIA
Henrik

Karsten Poeck

unread,
Oct 5, 2002, 4:51:24 PM10/5/02
to

"Henrik Motakef" <henrik....@web.de> wrote in message
news:87lm5cp...@pokey.henrik-motakef.de...
> Hi,

> 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:
>

In order not to test for every name you don't need to generate the function
at runtime,
e.g.

(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*)))))


Karsten


Henrik Motakef

unread,
Oct 5, 2002, 5:37:37 PM10/5/02
to
"Karsten Poeck" <vs1...@terra.es> writes:

> In order not to test for every name you don't need to generate the function
> at runtime,

Ah, but would it be fun then? ;-)

> If you want to have closures, try

[snip code]

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?

Regards
Henrik

Will Deakin

unread,
Oct 5, 2002, 5:55:43 PM10/5/02
to
Henrik Motakef wrote:
> Why are the *-if-not forms deprecated?
Have a look at notes section for the `complement' function in the
hyperspec[1]. My reading of this is that if you wrapper the test
function in the *-if form with something that with the same input return
the logical opposite, and lets for the sake of argument call this
`complement', you no longer require assoc-if-not, count-if-not,
delete-if-not, find-if-not, member-if-not, nsubst-if-not,
nsubstitute-if-not, position-if-not, rassoc-if-not, remove-if-not,
subst-if-not and substitute-if-not.

> Is this something to really worry about?

I'm not losing any sleep over this. (Although this is about as useless a
piece of reassurance as I could possibly give[2].

:)w

[1] www.lispworks.com/reference/HyperSpec/Body/f_comple.htm#complement
[2] (Hmmm. Employer: The plane has just crashed and we have identified
the problem to your use of the deprecated count-if-not function in the
guidance systems. You: I can explain that. There was this bloke on
comp.lang.lisp who said...)

Erik Naggum

unread,
Oct 5, 2002, 9:10:27 PM10/5/02
to
* Henrik Motakef

| 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.

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

Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.

Erik Naggum

unread,
Oct 5, 2002, 10:01:04 PM10/5/02
to
* Henrik Motakef

| Why are the *-if-not forms deprecated?

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.

Vassil Nikolov

unread,
Oct 5, 2002, 11:38:47 PM10/5/02
to
On 05 Oct 2002 21:19:32 +0200, Henrik Motakef <henrik....@web.de> said:

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.

--
Garbage collection is charged at 0.19e-9 cents a cons. Bulk rates
are also available: please contact memory management for details.

Vassil Nikolov

unread,
Oct 5, 2002, 11:51:54 PM10/5/02
to
On Sat, 5 Oct 2002 21:55:43 +0000 (UTC), Will Deakin <aniso...@hotmail.com> said:

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 Nikolov

unread,
Oct 5, 2002, 11:55:33 PM10/5/02
to
On Sat, 5 Oct 2002 21:55:43 +0000 (UTC), Will Deakin <aniso...@hotmail.com> said:

[...]
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 Nikolov

unread,
Oct 6, 2002, 1:06:14 AM10/6/02
to
On 05 Oct 2002 23:51:54 -0400, Vassil Nikolov <vnik...@poboxes.com> said:

[...]
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...

Will Deakin

unread,
Oct 6, 2002, 5:17:47 PM10/6/02
to
Vassil Nikolov wrote:
> 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.
Sure.

> 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

[1] www.lispworks.com/reference/HyperSpec/Issues/iss172_w.htm

Vassil Nikolov

unread,
Oct 7, 2002, 12:57:06 AM10/7/02
to
On Sun, 6 Oct 2002 21:17:47 +0000 (UTC), Will Deakin <aniso...@hotpop.com> said:

[...]
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...

Will Deakin

unread,
Oct 7, 2002, 3:27:00 AM10/7/02
to
Vassil Nikolov wrote:
> Yes;
(shhh, I fear we me may be in agreement... ;)

> I was merely complementing your post, making the point that we
> have two kinds of `garbage' here
Sure -- and to be honest I hadn't thought through the keyword stuff
which is relatively more toxic than the other

> ...so my post is also redundant garbage, though otherwise harmless...
This almost sounds like a cool bleak bleak epitaph (`his life's work was
...')

:)w

0 new messages