Hello all,
consider the following small example code:
(defun rotate-left (x)
"assume x is a list"
(and x (append (rest x) (list (first x))))))
(defun rotate-left (x)
"x can be anything"
(when (listp x)
(and x (append (rest x) (list (first x))))))
which is the better, or more standard approach to
designing functions?
Let the function throw an exception upon incorrect argument type
or check for correct argument type and always evaluate?
Thanks
···@zedat.fu-berlin.de (Stefan Ram) writes:
> John <····@zero.spam.net> writes:
>>(defun rotate-left (x)
>> "assume x is a list"
>> (and x (append (rest x) (list (first x))))))
>>(defun rotate-left (x)
>> "x can be anything"
>> (when (listp x)
>> (and x (append (rest x) (list (first x))))))
>>which is the better
If you have a type you can use check-type:
(defun proper-list-p (x)
(or (null x)
(and (consp x)
(proper-list-p (cdr x)))))
(deftype proper-list () `(satisfies proper-list-p))
(defun rotate-left (x)
(check-type x proper-list "Argument to ROTATE-LEFT must be a proper list!")
(and x (append (rest x) (list (first x)))))
[211]> (rotate-left '(a b c))
(B C A)
[212]> (rotate-left '(a b . c))
*** - The value of X should be Argument to ROTATE-LEFT must be a proper list!.
The value is: (A B . C)
The following restarts are available:
STORE-VALUE :R1 You may input a new value for X.
ABORT :R2 ABORT
Break 1 [213]> :q
[214]> (rotate-left 'c)
*** - The value of X should be Argument to ROTATE-LEFT must be a proper list!.
The value is: C
The following restarts are available:
STORE-VALUE :R1 You may input a new value for X.
ABORT :R2 ABORT
Break 1 [215]> :q
[216]>
Note that if you don't write this check-type, you still get the
checking (for free) by the function called from yours. If the error
message is clear enough for your need, then you don't need to add the
CHECK-TYPE.
[217]> (rotate-left '(a b . c))
*** - APPEND: A proper list must not end with C
The following restarts are available:
ABORT :R1 ABORT
Break 1 [218]>
In general, you can also use ASSERT:
(defun rotate-left (x)
(assert (and (proper-list-p x)
(every (function oddp) x))
(x)
"Argument to ROTATE-LEFT must be a proper list of ODD numbers, not ~S"
x)
(and x (append (rest x) (list (first x)))))
This allows you to recover from an error:
[226]> (rotate-left '(a b . c))
** - Continuable Error
Argument to ROTATE-LEFT must be a proper list of ODD numbers, not (A B . C)
If you continue (by typing 'continue'): You may input a new value for X.
The following restarts are also available:
ABORT :R1 ABORT
Break 1 [227]> continue
New X: (1 3 5)
(3 5 1)
[228]>
> I prefer the first one.
>
> - It is faster than the second one, because
> one check is omitted.
Yes, in general it's good enough and faster to rely on the subroutines
to do the checking.
> - The function-call contract places the burden
> to submit valid arguments to the caller.
> So, if the callee would always check this, it
> would be checked twice. (However, this might
> make sense during debugging.)
You must distinguish internal interfaces from external interfaces.
Inside a module, you may want to avoid checking the clauses of the
contracts in deep loops for performance reasons, but disabling all the
ASSERTs in production code is not a good idea either.
At the interface between a module and client code, it is more
interesting to check the contract, the more so when the parties
responsible of the different modules are distinct.
You could encapsulate these checks in a macro such as:
(eval-when (:compile-toplevel :load-toplevel :execute)
(defconstant +debug-level+ 2
"2 = debug even internal loops
1 = debug all but internal loops
0 = compiling production code"))
(defmacro when-debug (level &body body)
(when (<= level +debug-level+)
`(progn ,@body)))
(defun entry-point (data-from-client)
(when-debug 0
(assert (predicate-1-p data-from-client))
(assert (predicate-2-p data-from-client)))
(do-something data-from-client *some-data*))
(defun do-something (data-1 data-2)
(when-debug 1
(assert (heavy-predicate-3-p data-1 data-2))
(when-debug 0
(assert (light-predicate-3-p data-1 data-2))
(check-type data-2 higher-type))
(loop :for i :from 0
:while (predicate-3-p data-1 data-2)
:do (when-debug 2
(assert (predicate-4-p i data-1 data-2)))
(setf data-2 (something i data-1 data-2))))
Then you only need to change the constant +debug-level+ and reload or
recompile to remove the checks from the inner loops.
> - Assume you are calling rotate-left within a loop
> for the same argument list l. To make the process
> safe, it would suffice to do the check for the
> list-property of l once outside of the loop and to
> proof that this property is an invariant of the loop.
> If the callee would than still always check it
> within the loop, time is wasted.
Of course, ROTATE-LEFT is not an entry point for a module, so the
checking is better done outside of it.
> - Assume one of the two versions from above is given
> in a library, and the other version is wanted:
> It is always possible to get the second behavior
> by adding a wrapper to the first behavior, while
> it is impossible to get from the second library
> function to the faster version of the first function.
--
__Pascal Bourguignon__ http://www.informatimago.com/
What is this talk of 'release'? Klingons do not make software 'releases'.
Our software 'escapes' leaving a bloody trail of designers and quality
assurance people in it's wake.
I'd say version one is a more standard approach. Since CL code is safe
(unless declared otherwise) calling rest on a non-list isn't as tragic
as it could be. If it does happen it is easy to find the offending
caller in the debugger.
If you are using CMUCL, another (less standard) approach is to add a
type declaration.
(defun rotate-left (x)
(declare (type list x))
(and x (append (rest x) (list (first x)))))
then if you use something that is clearly not a list such as
(defstruct list-holder
(data nil :type list))
and forget to call the accessor
(defun do-some-rotating ()
(let ((x (make-list-holder :data '(1 2 . 3))))
(values (rotate-left x))))
at compile time CMUCL's type checker will catch the mistake and report
a warning ...
; In: DEFUN DO-SOME-ROTATING
; (ROTATE-LEFT X)
; ==>
; X
; Warning: Result is a LIST-HOLDER, not a (VALUES &OPTIONAL LIST &REST
T).
;
This isn't quite as big a hammer as calling listp or adding an assert
though. Unfortunately when I call the data accessor in the above
example, I don't get a warning, which is too bad b/c the information is
there to produce one.
John wrote:
> Hello all,
>
> consider the following small example code:
>
> (defun rotate-left (x)
> "assume x is a list"
> (and x (append (rest x) (list (first x))))))
>
> (defun rotate-left (x)
> "x can be anything"
> (when (listp x)
> (and x (append (rest x) (list (first x))))))
>
> which is the better, or more standard approach to
> designing functions?
It depends on what you are doing (of course).
The second one has a few problems:
1. The documentation lies. While it is technically true that X can
be anything, it won't get rotated unless X is a list. Someone who just
saw the docstring might think he could use it on a string.
2. The error case is silently discarded. Should a non-list flow
into this function, for whatever, reason, no error is raised and the
wonderfully ambiguous value NIL is returned.
> Let the function throw an exception upon incorrect argument type
> or check for correct argument type and always evaluate?
Let the *caller* decide what he wants. If your program punts for some
reason, the caller ought to be able to provide a reasonable workaround
(or rethrow the error so *his* caller can deal with it).
What I often do is this: if the function is an `API' function, use
check-type and assertions to ensure that callers of the API obey the
contracts. I don't expect callers to read the code (or the docs) to
find out how to use the API, so good check-types are very handy.
If the function is an `internal' one, I might create a `fast' version
that avoids as much checking as possible. It being internal, I can be
sure that the callers `know what they are doing'. If the function is
both speed-critical *and* an API function, I generally create 2
versions: a well-checked one and a
cross-your-fingers-you-*were*-sure-that-was-a-list-because-I'm-gonna-take-your-word-for-it
version.
In article <······················@comcast.com>,
····@zero.spam.net says...
>
> Hello all,
>
> consider the following small example code:
>
> (defun rotate-left (x)
> "assume x is a list"
> (and x (append (rest x) (list (first x))))))
>
> (defun rotate-left (x)
> "x can be anything"
> (when (listp x)
> (and x (append (rest x) (list (first x))))))
>
> which is the better, or more standard approach to
> designing functions?
>
> Let the function throw an exception upon incorrect argument type
> or check for correct argument type and always evaluate?
In general case you cannot check argument type at all, i.e. it
is undecidable problem. For example
(execute NT n)
where function is meant to execute non-halting Turing machine
for first n steps. Obviously, non-halting-Turing-machine-p
cannot be written.
Majorinc wrote:
> In general case you cannot check argument type at all, i.e. it
> is undecidable problem. For example
>
> (execute NT n)
>
> where function is meant to execute non-halting Turing machine
> for first n steps. Obviously, non-halting-Turing-machine-p
> cannot be written.
That's generally not a show-stopper. It isn't as if the code following
the check-type will erroneously be run.
In article <1137529540.739548.148770
@f14g2000cwb.googlegroups.com>, ··········@gmail.com says...
> Majorinc wrote:
> > In general case you cannot check argument type at all, i.e. it
> > is undecidable problem. For example
> >
> > (execute NT n)
> >
> > where function is meant to execute non-halting Turing machine
> > for first n steps. Obviously, non-halting-Turing-machine-p
> > cannot be written.
>
> That's generally not a show-stopper. It isn't as if the code following
> the check-type will erroneously be run.
Generally, there is little use of my observation - but it is
argument that such kind of assertions can make serious
problems. Sometimes it is not that test is undecidable - but
hard to implement or slow ...
On Tue, 17 Jan 2006 14:52:02 +0100, <Majorinc> wrote:
> In article <······················@comcast.com>,
> ····@zero.spam.net says...
>>
>> Hello all,
>>
>> consider the following small example code:
>>
>> (defun rotate-left (x)
>> "assume x is a list"
>> (and x (append (rest x) (list (first x))))))
>>
>> (defun rotate-left (x)
>> "x can be anything"
>> (when (listp x)
>> (and x (append (rest x) (list (first x))))))
>>
>> which is the better, or more standard approach to
>> designing functions?
>>
>> Let the function throw an exception upon incorrect argument type
>> or check for correct argument type and always evaluate?
>
> In general case you cannot check argument type at all, i.e. it
> is undecidable problem. For example
>
> (execute NT n)
>
> where function is meant to execute non-halting Turing machine
> for first n steps. Obviously, non-halting-Turing-machine-p
> cannot be written.
The halting problem only states it is not guarantied to halt.
In particular the size of a data set is not guarantied to be finite.
Exactly how do you create a infinate tape with finite memory.
On a Turing machine with a finite tape there you can drop the
halting problem. A exception for circular lists which require
spesial handeling.
Thus there is a way to check type.
like..
(defvar e '(1 2 3))
(check-type e list)
NIL
(assert (and (listp e) (every (lambda #'integer-p e))
NIL
..for example
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
In article <·················@mjolner.upc.no>,
··············@chello.no says...
> The halting problem only states it is not guarantied to halt.
> In particular the size of a data set is not guarantied to be finite.
> Exactly how do you create a infinate tape with finite memory.
> On a Turing machine with a finite tape there you can drop the
> halting problem. A exception for circular lists which require
> spesial handeling.
> Thus there is a way to check type.
Neither 1 divided with 7 cannot be calculated exactly into
decimal form without infinite memory, but you can still define
rational numbers and do exact operations on them.
On the same way, you can define non-halting TM without need to
execute them at all - or at least beyond your actual memory.
OK? You might simply do some statistical research on non-
halting TM's - how they look like, is it more probable that
they have even or odd number of instructions etc.
Now, if you write function that accepts non-halting Turing
machine as an argument, you cannot write test for that
argument. Whatever test you write, there is a non-halting TM
that will fall that test. And if test run out of memory that
means nothing.
Majorinc wrote:
> On the same way, you can define non-halting TM without need to
> execute them at all - or at least beyond your actual memory.
> OK? You might simply do some statistical research on non-
> halting TM's - how they look like, is it more probable that
> they have even or odd number of instructions etc.
What's a non-halting TM? For every TM I've seen, when I tried to find
out if they halted, I didn't stop, so I never found out.
> Now, if you write function that accepts non-halting Turing
> machine as an argument, you cannot write test for that
> argument. Whatever test you write, there is a non-halting TM
> that will fall that test. And if test run out of memory that
> means nothing.
But how do you know if a TM is halting or not?
--
The problems of the real world are primarily those you are left with
when you refuse to apply their effective solutions.
Edsger W. Dijkstra
John wrote:
> Hello all,
>
> consider the following small example code:
>
> (defun rotate-left (x)
> "assume x is a list"
> (and x (append (rest x) (list (first x))))))
>
> (defun rotate-left (x)
> "x can be anything"
> (when (listp x)
> (and x (append (rest x) (list (first x))))))
>
> which is the better, or more standard approach to
> designing functions?
>
> Let the function throw an exception upon incorrect argument type
> or check for correct argument type and always evaluate?
>
For this small function its better to let the function throw
an exception. So the first is better. Just a note, there
are other ways to code your example.
(defun rotate-left (x)
(etypecase x
(null nil)
(list (append (rest x) (list (first x))))))
CL-USER 1 > (rotate-left (list 1 2 3 4 5))
(2 3 4 5 1)
CL-USER 2 > (rotate-left 10)
Error: 10 fell through ETYPECASE expression.
Wanted one of (NULL LIST).
1 (abort) Return to level 0.
2 Return to top loop level 0.
Type :b for backtrace, :c <option number> to proceed, or :? for other options
CL-USER 3 : 1 >