[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.lisp

strong typing and NIL

Helmut Jarausch

4/1/2015 2:58:00 PM

Hi,

assuming I have a structure Node

(defstruct (Node
(:conc-name "ND-")
)
(prio 0 :type fixnum)
(l-son nil :type Node)
(r-son nil :type Node)
(key nil :type KeyType)
)

and then I have

(defun Process-Tree (Nd)
(declare (Node Nd))
;;; allow Nd to be NIL here
)

Especially, when using Process-Tree recursively it will be called as
(Process-Tree nil) eventually.

But unfortunately this gives a type error.

Similarly, I have to

(setf (ND-l-son) nil)

some times, which gives a type error, as well.

So, what can I do without dismissing typing alltogether.

Many thanks for your patience,
Helmut

P.S. In C++ slang, I need a substitute for the generic null pointer.
18 Answers

Madhu

4/1/2015 3:20:00 PM

0

* jarausch@skynet.be <26b44f7e-1fbd-4001-914b-2121e5f62818@googlegroups.com> :
Wrote on Wed, 1 Apr 2015 07:57:32 -0700 (PDT):

| Hi,
|
| (defstruct (Node
| (:conc-name "ND-")
| )
| (prio 0 :type fixnum)
| (l-son nil :type Node)
| (r-son nil :type Node)

This is already wrong. You are declaring the slot type as
`Node' but initializing it to NIL, check your compiler notes.

You have to use a union type in the slot description:

(l-son nil :type (or node null))

| (key nil :type KeyType)
| )
|
| and then I have
|
| (defun Process-Tree (Nd)
| (declare (Node Nd))
| ;;; allow Nd to be NIL here
| )
|
| Especially, when using Process-Tree recursively it will be called as
| (Process-Tree nil) eventually.

(defun process-tree (nd)
(etypecase nd
(null ...) ;; deal with null
(node ...)))

--- Madhu

Kaz Kylheku

4/1/2015 3:37:00 PM

0

On 2015-04-01, jarausch@skynet.be <jarausch@skynet.be> wrote:
> Hi,
>
> assuming I have a structure Node
>
> (defstruct (Node
> (:conc-name "ND-")
> )
> (prio 0 :type fixnum)
> (l-son nil :type Node)
> (r-son nil :type Node)
> (key nil :type KeyType)
> )
>
> and then I have
>
> (defun Process-Tree (Nd)
> (declare (Node Nd))
> ;;; allow Nd to be NIL here
> )

(declare (type (or null node) nd))

NIL's type (class, actually) is called NULL. This NULL class is considered the
subclass of every other class. It has only one instance: NIL.

(By extreme contrast, the class T is the superclass of every class, and every
object is an instance of T).

Note that type declarations are mainly for optimization in Lisp; you
are not guaranteed to get type checking.

If you want to portably get a run-time error if ND is not NIL or a node, use
check-type:

(check-type nd (or null node))

>
> Especially, when using Process-Tree recursively it will be called as
> (Process-Tree nil) eventually.
>
> But unfortunately this gives a type error.
>
> Similarly, I have to
>
> (setf (ND-l-son) nil)
>
> some times, which gives a type error, as well.

Again, use the OR type constructor to combine types.

Pascal J. Bourguignon

4/1/2015 4:26:00 PM

0

Kaz Kylheku <kaz@kylheku.com> writes:

> NIL's type (class, actually) is called NULL. This NULL class is considered the
> subclass of every other class. It has only one instance: NIL.

Nope. You are confusing types and classes.
The bottom type is NIL, not NULL.


cl-user> (defclass plant () ())
#<standard-class plant>
cl-user> (ccl::subclassp 'null 'plant) ; notice, not standard subclassp
nil ; you'd have to write it with the MOP.
cl-user> (subtypep 'null 'plant)
nil
t
cl-user> (subtypep 'nil 'plant)
t
t

There's no class named NIL.
(it would have little purpose, since there's no object of type NIL!)


> (By extreme contrast, the class T is the superclass of every class, and every
> object is an instance of T).

And also T is the top type, the supertype of all types.


--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.� -- Carl Bass CEO Autodesk

Paul Wallich

4/1/2015 5:53:00 PM

0

On 4/1/15 10:57 AM, jarausch@skynet.be wrote:
> Hi,
>
> assuming I have a structure Node
>
> (defstruct (Node
> (:conc-name "ND-")
> )
> (prio 0 :type fixnum)
> (l-son nil :type Node)
> (r-son nil :type Node)
> (key nil :type KeyType)
> )
>
> and then I have
>
> (defun Process-Tree (Nd)
> (declare (Node Nd))
> ;;; allow Nd to be NIL here
> )
>
> Especially, when using Process-Tree recursively it will be called as
> (Process-Tree nil) eventually.
>
> But unfortunately this gives a type error.
>
> Similarly, I have to
>
> (setf (ND-l-son) nil)
>
> some times, which gives a type error, as well.
>
> So, what can I do without dismissing typing alltogether.
>
> Many thanks for your patience,
> Helmut
>
> P.S. In C++ slang, I need a substitute for the generic null pointer.

Is there a reason why you want a generic null pointer instead of a null
node? The performance hit would be negligible or zero, and you might
avoid some really stupid bugs.

paul

Kaz Kylheku

4/1/2015 6:38:00 PM

0

On 2015-04-01, Pascal J. Bourguignon <pjb@informatimago.com> wrote:
> Kaz Kylheku <kaz@kylheku.com> writes:
>
>> NIL's type (class, actually) is called NULL. This NULL class is considered the
>> subclass of every other class. It has only one instance: NIL.
>
> Nope. You are confusing types and classes.

No, I'm not; I confused NULL and NIL, though! And played it a too loose
with the "subclass" terminology.

NULL is not the subtype of every other type. (Pardon me while I wipe
some remaining egg off my face.) If that were true, then every type would have
NIL in its domain as a member. The object NIL would be a number, a string, a
vector, ...

It is NIL which has the property of being everthing's subtype, which is
possible since its membership is empty.

NULL does some parentage, which is obvious:

(subtypep 'null 'list) -> t
(subtypep 'null 'symbol) -> t
(subtypep 'null 't) -> t

since NIL is a list and a symbol, and everything is a T.

> There's no class named NIL.
> (it would have little purpose, since there's no object of type NIL!)

That little purpose could be:

(defmethod foo ((x nil) ...)
;; method not applicable to anything: impossible to dispatch!
...)

Similar in effect to:

#-(and) (defmethod foo ....)

:)

Helmut Jarausch

4/1/2015 6:42:00 PM

0

On Wednesday, 1 April 2015 19:52:52 UTC+2, paul wallich wrote:
> Is there a reason why you want a generic null pointer instead of a null
> node? The performance hit would be negligible or zero, and you might
> avoid some really stupid bugs.
>

Simply because I don't know how to create a null node.
Thanks for your help,
Helmut

Kaz Kylheku

4/1/2015 7:13:00 PM

0

On 2015-04-01, jarausch@skynet.be <jarausch@skynet.be> wrote:
> On Wednesday, 1 April 2015 19:52:52 UTC+2, paul wallich wrote:
>> Is there a reason why you want a generic null pointer instead of a null
>> node? The performance hit would be negligible or zero, and you might
>> avoid some really stupid bugs.
>>
>
> Simply because I don't know how to create a null node.

A null node (also called a sentinel node) is just a node of the same
type as other nodes (or possibly a simplified type) which plays
a specially designated role in the graph structure. Usually it is understood
as being outside of the graph, but its mandatory presence in the graph
eliminates various special cases.

For instance a doubly-linked list can be made circular, by tying both
ends to a sentinel node. When such a list is empty, the node points
to itself as a successor and predecessor.

The head of such a list is just (next sentinel), and
the condition for the list being empty is:

(defmethod is-empty ((l dl-list))
(let ((s (sentinel l)))
(eq s (next s)))) ;; does s point to itself as next?

Insertion is very simple, being something like:

(defmethod insert-before ((existing node) (new node))
(psetf (next new) existing
(prev new) (prev existing)
(next (prev existing)) new
(prev existing) new))

Notice how there are no tests for null anywhere: insert-before
will happily handle prepend:

(defmethod prepend ((l dl-list) (new node))
(insert-before (next (sentinel l)) new))

Making a sentinel node is easy:

(let ((s (make-instance 'node)))
(setf (next s) s
(prev s) s))

Barry Margolin

4/1/2015 7:36:00 PM

0

In article <874mozx1by.fsf@kuiper.lan.informatimago.com>,
"Pascal J. Bourguignon" <pjb@informatimago.com> wrote:

> Kaz Kylheku <kaz@kylheku.com> writes:
>
> > NIL's type (class, actually) is called NULL. This NULL class is considered
> > the
> > subclass of every other class. It has only one instance: NIL.
>
> Nope. You are confusing types and classes.
> The bottom type is NIL, not NULL.

And in order for it to be a subtype of every other type, the NIL type
has to be empty. If the NULL type were a subtype of every other type,
you wouldn't need (OR NULL type) to solve the OP's problem.

--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Günther Thomsen

4/3/2015 4:23:00 PM

0

> Note that type declarations are mainly for optimization in Lisp; you
are not guaranteed to get type checking.

You are not? We're talking here (much to WJ's chagrin) about Common Lisp, aren't we? While Lisp programmers might have a tendency to forgo type declarations and hope for the best, the language (or rather conforming implementations) will enforce type safety. (Or so I thought)

It seems that in Common Lisp the type declaration is underspecified. The hyperspec lists "... The interpretation of a type declaration is as follows:

1. During the execution of any reference to the declared variable within the scope of the declaration, the consequences are undefined if the value of the declared variable is not of the declared type. ..."
Ouch.

SBCL treats (sensibly) type declarations as assertions and
((lambda (x) (declare (type integer x)) (* x 2)) 3.0)
will invoke the debugger with a simple-type-error, but CLISP happily evaluates that form to 6.0

That's rather disappointing.

Kaz Kylheku

4/3/2015 4:56:00 PM

0

On 2015-04-03, Günther Thomsen <guenthert@gmail.com> wrote:
>> Note that type declarations are mainly for optimization in Lisp; you

Who wrote the above? When? Please don't trim attributions.

> are not guaranteed to get type checking.
>
> You are not? We're talking here (much to WJ's chagrin) about Common Lisp,
> aren't we? While Lisp programmers might have a tendency to forgo type
> declarations and hope for the best, the language (or rather conforming
> implementations) will enforce type safety. (Or so I thought)

But when have you had to write a declaration in Lisp to get that type safety?

Of course what the above means is "you're not guaranteed to get static
type checking out of declarations", not that "Lisp doesn't have
type checking".

> It seems that in Common Lisp the type declaration is underspecified. The
> hyperspec lists "... The interpretation of a type declaration is as follows:
>
> 1. During the execution of any reference to the declared variable within the
> scope of the declaration, the consequences are undefined if the value of the
> declared variable is not of the declared type. ..." Ouch.

See? So declarations act in a way that is *opposite* to safety.

They say "I hereby declare that I know what I'm doing, and that the
type of X is fixnum, and it is my responsibility to ensure that this
is true".

> SBCL treats (sensibly) type declarations as assertions and ((lambda (x)
> (declare (type integer x)) (* x 2)) 3.0) will invoke the debugger with a
> simple-type-error

But that is sub-optimal! YOu just declared to the compiler that you know
what you're doing, and it's still doing checks, some of which are run-time.

Aha! For that we have one more thing: (declare (safety 0) ...)

Now there don't have to be any run-time type checks.