Beginners question on eg in Practical Common Lisp

Discussion of Common Lisp
Post Reply
junket
Posts: 7
Joined: Thu Dec 31, 2009 4:40 am
Location: dublin, ireland

Beginners question on eg in Practical Common Lisp

Post by junket » Thu Dec 31, 2009 5:17 am

Hello all,
I am new here, and also new to lisp. After a brief online tutorial I am looking at Practical Common Lisp.
However I have quite quickly been presented with something that I cannot quite understand.
I am referring to the query function in chapter 3 (a simple database.)
I do not understand how the select (remove-if-not... ) function and the where function (below) work in this context.
My problem is with the returns of true (t). I think that they are necessary because of the 'and' macro, which would return nil if one of its components was false. Meanwhile, the &key will automatically set the value to nil (or a set default value) if it does not receive the relevant parameter.
So what happens to the else-ish t returns in expressions such as (if title (equal (getf cd :title) title) t)? He seems to say that the clauses return t if no matching argument is received, which makes sense. Does the &key parameter override these returns? Do they fall beneath it? Where do they go?
I have not seen thus far in lisp a return within a function that the function does not itself return. Is this what happens here?
In Java, (the only other language I even slightly know) the destination of a return is always evident, as far as I know. In lisp it seems a little more complicated.
Any comments or references to online sources would be very welcome.
Thanks!
Here's the relevant function:
The function looks like this:

(defun where (&key title artist rating (ripped nil ripped-p))
#'(lambda (cd)
(and
(if title (equal (getf cd :title) title) t)
(if artist (equal (getf cd :artist) artist) t)
(if rating (equal (getf cd :rating) rating) t)
(if ripped-p (equal (getf cd :ripped) ripped) t))))

This function returns an anonymous function that returns the logical AND of one clause per field in our CD records. Each clause checks if the appropriate argument was passed in and then either compares it to the value in the corresponding field in the CD record or returns t, Lisp's version of truth, if the parameter wasn't passed in. Thus, the selector function will return t only for CDs that match all the arguments passed to where.7

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Beginners question on eg in Practical Common Lisp

Post by nuntius » Thu Dec 31, 2009 8:45 am

junket wrote:I have not seen thus far in lisp a return within a function that the function does not itself return. Is this what happens here?
In Java, (the only other language I even slightly know) the destination of a return is always evident, as far as I know. In lisp it seems a little more complicated.
In C/C++/Java, most statements have no return value. In Lisp, all forms return the last evaluated value. Thus (if t 5 6) returns 5 since the true branch was taken and 5 was evaluated. Some macros insert a hidden evaluation to return an earlier value (e.g. PROG1). An explicit RETURN is only needed for control flow (to exit a loop, leave a function early, etc.). An explicit VALUES with no arguments is needed to actually not return anything.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Beginners question on eg in Practical Common Lisp

Post by ramarren » Thu Dec 31, 2009 9:42 am

junket wrote:So what happens to the else-ish t returns in expressions such as (if title (equal (getf cd :title) title) t)? He seems to say that the clauses return t if no matching argument is received, which makes sense. Does the &key parameter override these returns? Do they fall beneath it? Where do they go?
I have not seen thus far in lisp a return within a function that the function does not itself return. Is this what happens here?
I don't really understand these questions, so I will try to explain what happens here.

AND returns the last result of forms which are its arguments which is not NIL, or NIL if they are all. The default default value of the key argument is NIL (as opposed to explicit default argument value).

So the form mentioned in the quote does is: IF the argument TITLE is non-nil, which means we are trying to match the title, then the form (equal (getf cd :title) title) is evaluated, which compares the argument to what is stored in the database, which returns either T (for true) or NIL (for false). If it is false, then the whole AND form returns NIL, if it is T, evaluation continues with the next form.

On the other hand when the TITLE argument is NIL, the whole form just returns T (the trivial else branch), and the evaluation continues to the next form in AND. That is, the default value of NIL means to ignore the argument when matching against the database.

There is no non-local exit in this function, except for the short-circuiting behaviour of the AND macro, which doesn't matter anyway, since it is not side-effecting. So I do not understand your questions about "these" returns, as every form returns to a form containing it as usual. Unless it was just a confusion over lack of expression/statement dichotomy, but that was explained in the PCL footnote.

junket
Posts: 7
Joined: Thu Dec 31, 2009 4:40 am
Location: dublin, ireland

Re: Beginners question on eg in Practical Common Lisp

Post by junket » Fri Jan 01, 2010 8:23 am

Thank you to both of you for your help.

The question I was trying to ask was why the T returns for the default NIL &key parameters were "trivial", but I did not express myself very clearly.
As far as I can now see, it is simply because:
(remove-if-not #'(lambda (cd) t) *db*)
returns *db* in its entirety.
Is that right?

I think I am going to have to look at a bit of set/list logic because I find T/NIL a bit confusing in lisp as they pertain to lists.

Thanks again

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Beginners question on eg in Practical Common Lisp

Post by ramarren » Fri Jan 01, 2010 10:35 am

junket wrote:As far as I can now see, it is simply because:
(remove-if-not #'(lambda (cd) t) *db*)
returns *db* in its entirety.
Is that right?
Yes. REMOVE-IF-NOT takes a function of one argument and a list, and removes, or rather, possibly creates a new list without, any element for which the test function returns false. The perhaps better name in other languages for this function is Filter.

Since #'(lambda (cd) t) is an anonymous function which ignores its argument and always returns true, REMOVE-IF-NOT using it as a test predicate will, indeed, return the whole list. Note that in Common Lisp there is only one false value, NIL, and all other values are considered true, although T is canonical truth value. Also note that NIL is both a symbol and an empty list. This comes handy when writing a base case for recursion on lists, although this is usually not the best style.

junket
Posts: 7
Joined: Thu Dec 31, 2009 4:40 am
Location: dublin, ireland

Re: Beginners question on eg in Practical Common Lisp

Post by junket » Fri Jan 01, 2010 12:04 pm

Great thanks a million! I much appreciate that explanation. You've been very helpful.

(I'm presuming it's not best style to return nil as a base case for recursions as tail-end recursion is favoured to building up and returning a stack. (That's at least what I gathered from the tutorial I looked at.))

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

Re: Beginners question on eg in Practical Common Lisp

Post by nuntius » Fri Jan 01, 2010 12:42 pm

junket wrote:I'm presuming it's not best style to return nil as a base case for recursions as tail-end recursion is favoured to building up and returning a stack. (That's at least what I gathered from the tutorial I looked at.)
In Scheme, the compiler must optimize a recursive tail-call by eliding the stack frame. The Common Lisp standard does not require this optimization. As a result, some people swear by recursion and others by looping/iteration. Either way, nil is the favored CL symbol for none, not found, not applicable, etc.

Here are a couple style guides that are worth reading.
http://p-cos.net/lisp/guide.html
http://norvig.com/luv-slides.ps (pdf) -- see page 58

Post Reply