not null

not null

[Georg Bauhaus]

As said to have been seen on /.
another financial disaster, again caused
by making references to nothing, in Algol W,
http://qconlondon.com/london-2009/presentation/Null+References:+The+Billion+Dollar+Mistake

Re: not null

[Hyman Rosen]

Georg Bauhaus wrote:
> As said to have been seen on /.
> another financial disaster, again caused
> by making references to nothing, in Algol W,
> http://qconlondon.com/london-2009/presentation/Null+References:+The+Billion+Dollar+Mistake

You are misreading the abstract. First of all, it's not
about some particular incident. He's talking about the
overall impact. Second, he's not talking about failure
to check for null references, he's talking about having
null references at all, so Ada is no better.

Re: not null

[Georg Bauhaus]

Hyman Rosen schrieb:
> Georg Bauhaus wrote:
>> As said to have been seen on /.
>> another financial disaster, again caused
>> by making references to nothing, in Algol W,
>> http://qconlondon.com/london-2009/presentation/Null+References:+The+Billion+Dollar+Mistake
>>
> 
> You are misreading the abstract. First of all, it's not
> about some particular incident. He's talking about the
> overall impact. Second, he's not talking about failure
> to check for null references, he's talking about having
> null references at all, so Ada is no better.

I didn't want to imply that Ada is any better WRT having
null refs. Except, perhaps, that some language lawyers
have said they would rather have wanted not null
to be the default, which is closer to not having
any null references in the first place.

The overall impact of refs not "attached" (to use
an Eiffel term; not null is spreading through languages
it seems; C++, too?) is a financial disaster, with
possibly one exception: there is money in a business
selling software components whose purpose is to guard
the holes kept open by operating system sellers.

(Antivirus etc.)

Re: not null

[Adam Beneschan]

On Mar 4, 6:56 am, Hyman Rosen <hyro...@mail.com> wrote:
> Georg Bauhaus wrote:
> > As said to have been seen on /.
> > another financial disaster, again caused
> > by making references to nothing, in Algol W,
> >http://qconlondon.com/london-2009/presentation/Null+References:+The+B...
>
> You are misreading the abstract. First of all, it's not
> about some particular incident. He's talking about the
> overall impact. Second, he's not talking about failure
> to check for null references, he's talking about having
> null references at all, so Ada is no better.

I'm having difficulty understanding the point.  You have to have the
idea of the lack of a reference.  How else would you implement a
linked list abstraction?  The first element has a reference to the
second, and the second has a reference to the third, but the last one
won't have a reference to anything.  This lack of a reference has to
be represented somehow, right?  Suppose that access values in Ada were
not allowed to have null values, and (for a linked list) you needed
the concept of a value that may or may not refer to another object.
You could write this as a variant record:

   type Obj_Reference (Present : Boolean) is record
      case Present is
         when True =>
            Ref : Obj_Access;  -- may not be null
         when False =>
            null;
      end case;
   end record;

I just don't see how this is an improvement; it simply shifts the
problem.  Whatever mistakes a programmer could in the actual Ada
language make by forgetting to check whether an access value is null,
he could make in the above example by forgetting to check the Present
discriminant.  And I suspect the same is true of any other "solution"
to the necessary concept of an "optional" reference that may refer to
an object or not; the set of mistakes you could make with that
solution is the same (if not greater) than the set you could make with
an access value that can be null---it's only that the syntax of those
mistakes would be different.

                              -- Adam

Re: not null

[Adam Beneschan]

On Mar 4, 7:22 am, Georg Bauhaus <rm.dash-bauh...@futureapps.de>
wrote:

> The overall impact of refs not "attached" (to use
> an Eiffel term; not null is spreading through languages
> it seems; C++, too?) is a financial disaster, with
> possibly one exception: there is money in a business
> selling software components whose purpose is to guard
> the holes kept open by operating system sellers.
>
> (Antivirus etc.)

Is there any basis for this last comment?  I've seen lots of reports
of vulnerabilities caused by buffer overflows combined with lack of
range checking, and by double-deallocation errors (deallocating the
same chunk of memory twice and making hash of your heap structures),
but I don't recall seeing any caused by null references.  Errors
involving null references seem a lot more likely just to make programs
die unexpectedly, than to allow arbitrary code execution or the like.

                                 -- Adam

Re: not null

[Robert A Duff]

Hyman Rosen <hyrosen@mail.com> writes:

> Georg Bauhaus wrote:
>> As said to have been seen on /.
>> another financial disaster, again caused
>> by making references to nothing, in Algol W,
>> http://qconlondon.com/london-2009/presentation/Null+References:+The+Billion+Dollar+Mistake
>
> You are misreading the abstract. First of all, it's not
> about some particular incident. He's talking about the
> overall impact.

Yes.  (I think Georg Bauhaus understood that.)

>... Second, he's not talking about failure
> to check for null references, he's talking about having
> null references at all, so Ada is no better.

There's nothing wrong with allowing programmers to use null pointers.

There's a lot wrong with giving programmers a null value for all
pointer types, whether they're wanted or not.  It's just a tripping
hazard.

Ada is a little bit better than languages that always allow null,
because it allows you to declare "not null" on an access [sub]type.
It would be even better if "not null" were the default -- ideally,
you should get a null value only if you ask for it explicitly.
It's too late to fix it now.

Ada is also better than languages that say deref of null leads to
unpredictable behavior.  At least you get a run-time error in Ada.
But it's still a tripping hazard.

See OCaml for a language that gets this right.

- Bob

Re: not null

[Dmitry A. Kazakov]

On Wed, 4 Mar 2009 08:09:56 -0800 (PST), Adam Beneschan wrote:

> On Mar 4, 6:56 am, Hyman Rosen <hyro...@mail.com> wrote:
>> Georg Bauhaus wrote:
>>> As said to have been seen on /.
>>> another financial disaster, again caused
>>> by making references to nothing, in Algol W,
>>>http://qconlondon.com/london-2009/presentation/Null+References:+The+B...
>>
>> You are misreading the abstract. First of all, it's not
>> about some particular incident. He's talking about the
>> overall impact. Second, he's not talking about failure
>> to check for null references, he's talking about having
>> null references at all, so Ada is no better.
> 
> I'm having difficulty understanding the point.  You have to have the
> idea of the lack of a reference.  How else would you implement a
> linked list abstraction?

Recursive types is not the single case where references are used. For smart
pointers not null constraint is very useful. Though it is quite painful to
make use of it, because of broken initialization issues. It is also useful
for access discriminants etc. Granted, the latter shouldn't be access. I
mean it should better be:

   type T (X : Limited_Foo) is ...

rather than awful

   type T (X : not null access Limited_Foo) is ...

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: not null

[Colin Paul Gloster]

On March 4th, 2009, the following webpage was mentioned on news:comp.lang.ada :

|-------------------------------------------------------------------------------------------|
|"[..]                                                                                      |
|http://qconlondon.com/london-2009/presentation/Null+References:+The+Billion+Dollar+Mistake"|
|-------------------------------------------------------------------------------------------|

It seems that Prof. Hoare has made another mistake, as I note that
webpage contained:
"[..] In recent years, a number of program analysers like PREfix and
PREfast in Microsoft [..] give warnings if there is a risk they may be
non-null. [..]"

Warnings might make sense if there is a risk that they could be null,
but why would a possibility of being non-null instead justify the
terms "warnings" and "risk"?

With kind regards,
Colin Paul Gloucester

Re: not null

[Brian Drummond]

On Wed, 4 Mar 2009 08:09:56 -0800 (PST), Adam Beneschan <adam@irvine.com> wrote:

>On Mar 4, 6:56 am, Hyman Rosen <hyro...@mail.com> wrote:
>> Georg Bauhaus wrote:
>> > As said to have been seen on /.
>> > another financial disaster, again caused
>> > by making references to nothing, in Algol W,
>> >http://qconlondon.com/london-2009/presentation/Null+References:+The+B...
>>
>> You are misreading the abstract. First of all, it's not
>> about some particular incident. He's talking about the
>> overall impact. Second, he's not talking about failure
>> to check for null references, he's talking about having
>> null references at all, so Ada is no better.
>
>I'm having difficulty understanding the point.  You have to have the
>idea of the lack of a reference.  How else would you implement a
>linked list abstraction?  

Possibly by pointing from the end back to the list head. 

It would make the "end of list" test more expensive (the head might have to be
kept in a register or passed around as another argument). I don't think it would
be pretty, but can't see any fundamental reason why it shouldn't work.

- Brian

Re: not null

[Adam Beneschan]

On Mar 4, 5:32 pm, Brian Drummond <brian_drumm...@btconnect.com>
wrote:
> On Wed, 4 Mar 2009 08:09:56 -0800 (PST), Adam Beneschan <a...@irvine.com> wrote:
> >On Mar 4, 6:56 am, Hyman Rosen <hyro...@mail.com> wrote:
> >> Georg Bauhaus wrote:
> >> > As said to have been seen on /.
> >> > another financial disaster, again caused
> >> > by making references to nothing, in Algol W,
> >> >http://qconlondon.com/london-2009/presentation/Null+References:+The+B...
>
> >> You are misreading the abstract. First of all, it's not
> >> about some particular incident. He's talking about the
> >> overall impact. Second, he's not talking about failure
> >> to check for null references, he's talking about having
> >> null references at all, so Ada is no better.
>
> >I'm having difficulty understanding the point.  You have to have the
> >idea of the lack of a reference.  How else would you implement a
> >linked list abstraction?
>
> Possibly by pointing from the end back to the list head.
>
> It would make the "end of list" test more expensive (the head might have to be
> kept in a register or passed around as another argument). I don't think it would
> be pretty, but can't see any fundamental reason why it shouldn't work.

Sure you could make it work, but what would be the point of doing so?
And would it be any less error-prone?  Actually, it might even be
moreso---when writing the operation to insert an element at the front
of the list, you could forget to modify the reference in the tail.

To me, a circular list and a linked list that isn't circular are two
different abstractions (perhaps they have different topological
properties, in some sense).  Forcing one to be implemented as the
other is hardly a recipe for making programs more reliable.

You could also make the "end of list" point to some special dummy
object.  That would probably be better than forcing the list to be
circular, but again just as pointless.  I believe my earlier comment,
that the same set of mistakes applies as to a language that involves
null reference, but the syntax of those mistakes is different, applies
to both of these "solutions".

                               -- Adam

Re: not null

[Adam Beneschan]

On Mar 4, 12:38 pm, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:

> Recursive types is not the single case where references are used. For smart
> pointers not null constraint is very useful.

Right, I didn't say a "not null" constraint isn't useful; I'm just
saying that it's also useful to have access objects that *can* be
null, if needed.  Actually, I'm not clear on whether anyone disagrees
with that.  This points to a curiosity in Hoare's abstract: first he
implies that inventing "null references" was a big mistake, and then
he says "declarations for non-null references" is the solution.  If
allowing null references is a mistake, then the solution is to
disallow them---not to allow the programmer to declare a reference
that may not be null, right?  I think maybe Hoare misstated the
problem.  The mistake wasn't inventing null references; the mistake
was not providing a way for the programmer to disallow selected
reference types or variables (objects) from being null.    This
misstatement may have led to some confusion on this thread.

                                 -- Adam

Re: not null

[Dmitry A. Kazakov]

On Wed, 4 Mar 2009 17:54:16 -0800 (PST), Adam Beneschan wrote:

> On Mar 4, 12:38 pm, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
> wrote:
> 
>> Recursive types is not the single case where references are used. For smart
>> pointers not null constraint is very useful.
> 
> Right, I didn't say a "not null" constraint isn't useful; I'm just
> saying that it's also useful to have access objects that *can* be
> null, if needed.  Actually, I'm not clear on whether anyone disagrees
> with that.  This points to a curiosity in Hoare's abstract: first he
> implies that inventing "null references" was a big mistake, and then
> he says "declarations for non-null references" is the solution.  If
> allowing null references is a mistake, then the solution is to
> disallow them---not to allow the programmer to declare a reference
> that may not be null, right?

Right, this is what smart pointers use, not a constraint in the sense of an
Ada subtype, but a type that does not have null as a value. A smart pointer
is always valid.

> I think maybe Hoare misstated the
> problem.  The mistake wasn't inventing null references; the mistake
> was not providing a way for the programmer to disallow selected
> reference types or variables (objects) from being null.    This
> misstatement may have led to some confusion on this thread.

Yes, there are two cases: dynamically constrained references and statically
constrained ones. Both have their uses.

Concerning the invention of null, I can understand Hoare's point. There is
a comparable case with IEEE 754, where ideal values like NaN were invented.
Sometimes this adds a lot of pain, which could be spared. Sometimes it does
not.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: not null

[Jacob Sparre Andersen]

Adam Beneschan wrote:
> Hyman Rosen wrote:

> > [...] he's talking about having null references at all, so Ada is
> > no better.
> 
> I'm having difficulty understanding the point.  You have to have the
> idea of the lack of a reference.

> [...]  Suppose that access values in Ada were not allowed to have
> null values, and (for a linked list) you needed the concept of a
> value that may or may not refer to another object.  You could write
> this as a variant record:
> 
>    type Obj_Reference (Present : Boolean) is record
>       case Present is
>          when True =>
>             Ref : Obj_Access;  -- may not be null
>          when False =>
>             null;
>       end case;
>    end record;
> 
> I just don't see how this is an improvement; it simply shifts the
> problem.

No.

> Whatever mistakes a programmer could in the actual Ada language make
> by forgetting to check whether an access value is null, he could
> make in the above example by forgetting to check the Present
> discriminant.

No.  The _compiler_ checks the discriminant.  The programmer will get
a Constraint_Error if he tries to use "Ref" while "Present" is false.
And he can't change "Present" to true without also assigning "Ref" a
value.

Greetings,

Jacob
-- 
"For there are only two reasons why war is made against a
 republic: The one, to become lord over her: the other, the
 fear of being occupied by her."       -- Nicolo Machiavelli

Re: not null

[Brian Drummond]

On Wed, 4 Mar 2009 17:47:03 -0800 (PST), Adam Beneschan <adam@irvine.com> wrote:

>On Mar 4, 5:32 pm, Brian Drummond <brian_drumm...@btconnect.com>
>wrote:
>> On Wed, 4 Mar 2009 08:09:56 -0800 (PST), Adam Beneschan <a...@irvine.com> wrote:

>> >I'm having difficulty understanding the point.  You have to have the
>> >idea of the lack of a reference.  How else would you implement a
>> >linked list abstraction?
>>
>> Possibly by pointing from the end back to the list head.
>>
>> It would make the "end of list" test more expensive (the head might have to be
>> kept in a register or passed around as another argument). I don't think it would
>> be pretty, but can't see any fundamental reason why it shouldn't work.
>
>Sure you could make it work, but what would be the point of doing so?
>And would it be any less error-prone?  Actually, it might even be
>moreso---when writing the operation to insert an element at the front
>of the list, you could forget to modify the reference in the tail.

I wasn't suggesting it was a good idea... 

Agree on all the above; and the error wouldn't bes ignificantly easier to find.

OTOH uninitialised (or incorrectly incremented) pointers in some languages cause
real grief... (my Algol W days are so far behind me, I can't remember if an
uninitialised reference was even possible)

>You could also make the "end of list" point to some special dummy
>object. 

I don't see that as semantically different from a null pointer.
Which perhaps just helps to make your point
>that the same set of mistakes applies as to a language that involves
>null reference, but the syntax of those mistakes is different, applies
>to both of these "solutions".

In which case, Hoare's point remains a mystery to me.

- Brian

Re: not null

[Georg Bauhaus]

Adam Beneschan schrieb:

> You could also make the "end of list" point to some special dummy
> object.  That would probably be better than forcing the list to be
> circular, but again just as pointless.  I believe my earlier comment,
> that the same set of mistakes applies as to a language that involves
> null reference, but the syntax of those mistakes is different, applies
> to both of these "solutions".

Or an Admin object pointing to itself or else to the real nodes
that are end nodes if they point to themselves, ... etc., I'd guess.

Where null values are probably inferior compared to
special objects is when "null.all" yields an access
error (at best; SEGFAULT or similar when checks have been suppressed).
To me, this exception is from the set of most unspecific exceptions
I can think of.  I'd prefer something more specific, maybe
related to tampering with the elements of the list, for example.

Re: not null

[Georg Bauhaus]

Adam Beneschan schrieb:
> On Mar 4, 7:22 am, Georg Bauhaus <rm.dash-bauh...@futureapps.de>
> wrote:
> 
>> The overall impact of refs not "attached" (to use
>> an Eiffel term; not null is spreading through languages
>> it seems; C++, too?) is a financial disaster, with
>> possibly one exception: there is money in a business
>> selling software components whose purpose is to guard
>> the holes kept open by operating system sellers.
>>
>> (Antivirus etc.)
> 
> Is there any basis for this last comment?  I've seen lots of reports
> of vulnerabilities caused by buffer overflows combined with lack of
> range checking, and by double-deallocation errors (deallocating the
> same chunk of memory twice and making hash of your heap structures),
> but I don't recall seeing any caused by null references.  Errors
> involving null references seem a lot more likely just to make programs
> die unexpectedly, than to allow arbitrary code execution or the like.

You have caught me in an argument over CeBIT discussions
concerning the security of OSs and server software,
so I might have been carried away.

OTOH, the very presence of null values seems close
to the causes of buffer overflow, of accessing/overwriting
data off bounds, etc. This is simply because NULL
(similarly, '\0') is thought of as a regular thing,
for the programmer to handle routinely with any
sequential piece of data.
strcat(3) and relatives, as its counterparts at the
end of arrays of structures, rely on null values.
You need the dangerous thing to get anything done.
Caveat emptor.

Re: not null

[Dmitry A. Kazakov]

On Thu, 05 Mar 2009 11:32:13 +0000, Brian Drummond wrote:

> On Wed, 4 Mar 2009 17:47:03 -0800 (PST), Adam Beneschan <adam@irvine.com> wrote:
> 
>>You could also make the "end of list" point to some special dummy
>>object. 
> 
> I don't see that as semantically different from a null pointer.
> Which perhaps just helps to make your point

Well, many lists are never empty. Such lists (single or doubly-linked) can
be made circular. This strategy has several advantages. One of them is that
null pointers are never used. (An item outside any list points to itself.)

(Granted, a wrongly implemented list iteration may cycle rather than
crash.)

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: not null

[Adam Beneschan]

On Mar 5, 6:24 am, Georg Bauhaus <rm.dash-bauh...@futureapps.de>
wrote:
> Adam Beneschan schrieb:
>
>
>
> > On Mar 4, 7:22 am, Georg Bauhaus <rm.dash-bauh...@futureapps.de>
> > wrote:
>
> >> The overall impact of refs not "attached" (to use
> >> an Eiffel term; not null is spreading through languages
> >> it seems; C++, too?) is a financial disaster, with
> >> possibly one exception: there is money in a business
> >> selling software components whose purpose is to guard
> >> the holes kept open by operating system sellers.
>
> >> (Antivirus etc.)
>
> > Is there any basis for this last comment?  I've seen lots of reports
> > of vulnerabilities caused by buffer overflows combined with lack of
> > range checking, and by double-deallocation errors (deallocating the
> > same chunk of memory twice and making hash of your heap structures),
> > but I don't recall seeing any caused by null references.  Errors
> > involving null references seem a lot more likely just to make programs
> > die unexpectedly, than to allow arbitrary code execution or the like.
>
> You have caught me in an argument over CeBIT discussions
> concerning the security of OSs and server software,
> so I might have been carried away.
>
> OTOH, the very presence of null values seems close
> to the causes of buffer overflow, of accessing/overwriting
> data off bounds, etc. This is simply because NULL
> (similarly, '\0') is thought of as a regular thing,
> for the programmer to handle routinely with any
> sequential piece of data.

On most systems, though, if you try to handle NULL as just with any
other pointer, and dereference it, your program will immediately crash
and burn on an invalid memory reference fault.  Yes, I realize this
isn't the case on all platforms.  Plus, in C, where pointer arithmetic
is common, you can add something to NULL and try to dereference that,
causing serious problems.  So there do seem to be ways that bad use of
a null pointer could cause a program to behave in a way that would
allow a virus to get installed.  I just think it's a lot less common.

                                -- Adam

Re: not null

[Adam Beneschan]

On Mar 5, 12:49 am, Jacob Sparre Andersen <spa...@nbi.dk> wrote:

> > Whatever mistakes a programmer could in the actual Ada language make
> > by forgetting to check whether an access value is null, he could
> > make in the above example by forgetting to check the Present
> > discriminant.
>
> No.  The _compiler_ checks the discriminant.  The programmer will get
> a Constraint_Error if he tries to use "Ref" while "Present" is false.

It also checks access values and raises Constraint_Error if they're
null, so I don't understand what your point is.

                              -- Adam

Re: not null

[Jacob Sparre Andersen]

Adam Beneschan wrote:
> Jacob Sparre Andersen wrote:

>> > Whatever mistakes a programmer could in the actual Ada language
>> > make by forgetting to check whether an access value is null, he
>> > could make in the above example by forgetting to check the
>> > Present discriminant.
>>
>> No.  The _compiler_ checks the discriminant.  The programmer will
>> get a Constraint_Error if he tries to use "Ref" while "Present" is
>> false.
>
> It also checks access values and raises Constraint_Error if they're
> null, so I don't understand what your point is.

Neither do I.  Must have been sleepy.

Greetings,

Jacob
-- 
A password should be like a toothbrush. Use it every day;
change it regularly; and DON'T share it with friends.

Re: not null

[Jack Mitchell]

In message <qcauq45pgq84rvntrggh90hdd68ji6btl2@4ax.com>, Brian Drummond 
<brian_drummond@btconnect.com> writes
>On Wed, 4 Mar 2009 08:09:56 -0800 (PST), Adam Beneschan 
><adam@irvine.com> wrote:
>
>>On Mar 4, 6:56 am, Hyman Rosen <hyro...@mail.com> wrote:
>>> Georg Bauhaus wrote:
>>> > As said to have been seen on /.
>>> > another financial disaster, again caused
>>> > by making references to nothing, in Algol W,
>>> >http://qconlondon.com/london-2009/presentation/Null+References:+The+B...
>>>
>>> You are misreading the abstract. First of all, it's not
>>> about some particular incident. He's talking about the
>>> overall impact. Second, he's not talking about failure
>>> to check for null references, he's talking about having
>>> null references at all, so Ada is no better.
>>
>>I'm having difficulty understanding the point.  You have to have the
>>idea of the lack of a reference.  How else would you implement a
>>linked list abstraction?
>
>Possibly by pointing from the end back to the list head.
>
>It would make the "end of list" test more expensive (the head might have to be
>kept in a register or passed around as another argument). I don't think 
>it would
>be pretty, but can't see any fundamental reason why it shouldn't work.
>
>- Brian

The other way to avoid needing null references is to point back not to 
the start of the list, but to your self.

-- 
Jack Mi_Remove_tchell

Re: not null

[Hibou57 (Yannick Duchêne)]

On 4 mar, 17:09, Adam Beneschan <a...@irvine.com> wrote:
> I'm having difficulty understanding the point.  You have to have the
> idea of the lack of a reference.  How else would you implement a
> linked list abstraction?  The first element has a reference to the
> second, and the second has a reference to the third, but the last one
> won't have a reference to anything.  This lack of a reference has to
> be represented somehow, right?  Suppose that access values in Ada were
> not allowed to have null values, and (for a linked list) you needed
> the concept of a value that may or may not refer to another object.
> You could write this as a variant record:
>                               -- Adam

I use to think about it a long time ago and was thinking that the best
null or nil reference to an object would be a reference to a null or
nil object (a special singleton object). I do not mean an object which
will stand for all null references, rather an object for each type.

An other view : a null reference is a kind of boolean (it used this
way and cannot be used another way).... and with hindsight, this may
perhaps look funny. This boolean is a kind of constraint on a kind of
record with a discriminent (conceptually).

Just to talk about lists, this may be a circular list, with a flag on
the last element telling it is has a special meaning.

Re: not null

[Hibou57 (Yannick Duchêne)]

On 4 mar, 17:16, Adam Beneschan <a...@irvine.com> wrote:
> Errors
> involving null references seem a lot more likely just to make programs
> die unexpectedly, than to allow arbitrary code execution or the like.
>
>                                  -- Adam

Indeed, as long as a null reference is a $0000000.... memory offset,
most of modern processor allow exception to be raised in such
circumstance (at least which special access right on the memory block
starting at this offset, or else with special descriptors).

It is likely to be detected as soon as possible.

Re: not null

[Harald Korneliussen]

On Mar 4, 5:09 pm, Adam Beneschan <a...@irvine.com> wrote:

> I'm having difficulty understanding the point.  You have to have the
> idea of the lack of a reference.  How else would you implement a
> linked list abstraction?

You can use algebraic data types to do that in a type safe manner.
Haskell, Ocaml and many smaller functional languages do: If a function
returns a "Maybe Integer" type, the compiler will warn you if you
pretend it's an Integer without dealing with the "Nothing" case.

Re: not null

[Jacob Sparre Andersen]

Harald Korneliussen wrote:
> Adam Beneschan wrote:

> > I'm having difficulty understanding the point. �You have to have
> > the idea of the lack of a reference. �How else would you implement
> > a linked list abstraction?
> 
> You can use algebraic data types to do that in a type safe manner.
> Haskell, Ocaml and many smaller functional languages do: If a
> function returns a "Maybe Integer" type, the compiler will warn you
> if you pretend it's an Integer without dealing with the "Nothing"
> case.

Can this be implemented as a static check?  (Or is there a good reason
that it is only a warning?)

It would be nice(TM) if Ada compilers could do something like that for
with null access types.

Greetings,

Jacob
-- 
Adlai Stevenson said it all when, at an event during the
1956 Presidential campaign, a woman shouted, "You have the
vote of every thinking person!" Stevenson shouted back,
"That's not enough, madam, we need a majority!"

Re: not null

[Harald Korneliussen]

On Mar 6, 1:43 pm, Jacob Sparre Andersen <spa...@nbi.dk> wrote:
> Harald Korneliussen wrote:
> > You can use algebraic data types to do that in a type safe manner.
> > Haskell, Ocaml and many smaller functional languages do: If a
> > function returns a "Maybe Integer" type, the compiler will warn you
> > if you pretend it's an Integer without dealing with the "Nothing"
> > case.
>
> Can this be implemented as a static check?  (Or is there a good reason
> that it is only a warning?)
>
> It would be nice(TM) if Ada compilers could do something like that for
> with null access types.
>

It can be enforced, of course. It could be implemented in Ada, but to
do it without serious program analysis, I think there would need to be
a special function that separates the cases (Null and not null) and
sends the program down one path or the other - naturally, with only
the not-null path having access to a variable of the base type. The
compiler could then insure that (almost) the only operation that could
be performed on the possibly-null type was this function.

In Haskell and Ocaml this is done with pattern matching on types.

Re: not null

[Dmitry A. Kazakov]

On Fri, 6 Mar 2009 04:01:45 -0800 (PST), Harald Korneliussen wrote:

> On Mar 4, 5:09�pm, Adam Beneschan <a...@irvine.com> wrote:
> 
>> I'm having difficulty understanding the point. �You have to have the
>> idea of the lack of a reference. �How else would you implement a
>> linked list abstraction?
> 
> You can use algebraic data types to do that in a type safe manner.

No, you cannot, if safe = static. The nodes of the list have contracts to
support certain operations. The only problem with null is that the virtual
object corresponding to null does not fulfill the contract:

Do_It (Next (Node)) raises Constraint_Error, instead of doing things.
Whether you replace null with a reference to some fake object would change
nothing. The fact is, beyond the list end there is no objects fulfilling
the contract. Period.

> Haskell, Ocaml and many smaller functional languages do: If a function
> returns a "Maybe Integer" type, the compiler will warn you if you
> pretend it's an Integer without dealing with the "Nothing" case.

Same in Ada:

   type Base_Node is ...;
   function Next (X : Base_Node) return Base_Node'Class;

   type Node is new No_Node with ...
   procedure Do_It (X : Node);

The compiler gives you an error (much better than warning) when you call
Do_It on something that is not in Node'Class. You have to cast it to Node
first and have a chance of Constraint_Error. What does change? Nothing.

So the point Adam IMO makes. If you do it dynamically checked null is as
good as anything else. Statically it is does not go, unless lists are
infinite or cyclic.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: not null

[Harald Korneliussen]

On Mar 6, 4:21 pm, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:
> On Fri, 6 Mar 2009 04:01:45 -0800 (PST), Harald Korneliussen wrote:
> > On Mar 4, 5:09 pm, Adam Beneschan <a...@irvine.com> wrote:
>
> >> I'm having difficulty understanding the point.  You have to have the
> >> idea of the lack of a reference.  How else would you implement a
> >> linked list abstraction?
>
> > You can use algebraic data types to do that in a type safe manner.
>
> No, you cannot, if safe = static. The nodes of the list have contracts to
> support certain operations. The only problem with null is that the virtual
> object corresponding to null does not fulfill the contract:

I don't understand your code example. But kind of like some Java
functions won't compile unless they're surrounded by an appropriate
try/catch block, you can make in Haskell a linked list get_next
function that causes the compiler to protest - at compile time,
naturally - if used in a context where the possibility of returning
Nothing (null) isn't considered.

(Embarrassingly enough, the built-in linked list of Haskell does not
do this, for historical reasons. Instead it uses the more old-
fashioned and unsafe way of throwing an exception, and unlike in Java
you don't have to  catch or explicitly say that you won't. But it's
easy to write a list that does it right)

Re: not null

[Dmitry A. Kazakov]

On Fri, 6 Mar 2009 08:59:41 -0800 (PST), Harald Korneliussen wrote:

> On Mar 6, 4:21�pm, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
> wrote:
>> On Fri, 6 Mar 2009 04:01:45 -0800 (PST), Harald Korneliussen wrote:
>>> On Mar 4, 5:09�pm, Adam Beneschan <a...@irvine.com> wrote:
>>
>>>> I'm having difficulty understanding the point. �You have to have the
>>>> idea of the lack of a reference. �How else would you implement a
>>>> linked list abstraction?
>>
>>> You can use algebraic data types to do that in a type safe manner.
>>
>> No, you cannot, if safe = static. The nodes of the list have contracts to
>> support certain operations. The only problem with null is that the virtual
>> object corresponding to null does not fulfill the contract:
> 
> I don't understand your code example. But kind of like some Java
> functions won't compile unless they're surrounded by an appropriate
> try/catch block, you can make in Haskell a linked list get_next
> function that causes the compiler to protest - at compile time,
> naturally - if used in a context where the possibility of returning
> Nothing (null) isn't considered.

But this has nothing to do with null as a value. It does to exception
handling. The problem was moved to the client, which is the point.

(It is a pity that Ada does not have contracted exceptions.) 

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: not null

[Georg Bauhaus]

Dmitry A. Kazakov schrieb:
> On Fri, 6 Mar 2009 08:59:41 -0800 (PST), Harald Korneliussen wrote:
> 
>>> The nodes of the list have contracts to
>>> support certain operations. The only problem with null is that the virtual
>>> object corresponding to null does not fulfill the contract:
>> I don't understand your code example. But kind of like some Java
>> functions won't compile unless they're surrounded by an appropriate
>> try/catch block, you can make in Haskell a linked list get_next
>> function that causes the compiler to protest - at compile time,
>> naturally - if used in a context where the possibility of returning
>> Nothing (null) isn't considered.

HUGS at least does not seem to complain about a
function definition that does not have a definition
for a Nothing argument.
(Example shows something like Ada's accessing an
array named cs at index k with bounds checks handled
proactively.
Haskell's index operator !! does raise index errors.)

module M where

element :: [Char] -> Int -> Maybe Char
element cs k =
    if k >= 0 && k < (length cs) then
        Just (cs !! k)
    else
        Nothing

test :: Maybe a -> a
test (Just x) = x
-- test Nothing = '!'  -- deliberately commented

main = putChar( test (element("ABC")(3)))


M> main

Program error: pattern match failure: test Nothing



> But this has nothing to do with null as a value. It does to exception
> handling. The problem was moved to the client, which is the point.
> 
> (It is a pity that Ada does not have contracted exceptions.) 

But isn't it really the client that should
deal with contracts that it violates?

If there are more capable Haskell translators,
they should be able to reject the definition
of function ``test'' just like Ada rejects a case
statement that does not cover all values.
GHC does at least warn. (I'm not that familiar
with Haskell.)

Re: not null

[Dmitry A. Kazakov]

On Fri, 06 Mar 2009 21:05:25 +0100, Georg Bauhaus wrote:

> But isn't it really the client that should
> deal with contracts that it violates?

Why should you care about the contract you are going to violate?

The whole idea of "not null" was not to test for it. If you accept testing
then there is no more problem with null.

Obviously there is a multiplying factor N when handling null is moved to N
clients of reusable code.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de