2
$\begingroup$

I am reading algorithms in a CS book where a potentially nil value is passed to a function, but neither the caller nor the callee check if the value is nil. Is this a common practice in algorithms?

To be more precise, I am implementing a red-black tree and the grandparent of a node is passed to a rotation function, but if correctly understand the algorithm, the grandparent might be nil at the time the rotation function is called.

I should probably warp such calls into a conditional block, but I was curious to know if this is common for algorithms to be specified that way, and if there are any additional advices on how to handle those cases.

Thank you

Improve this question
$\endgroup$
15
  • 2
    $\begingroup$ This is an implementation-specific detail. For example, some languages might not have nil pointers at all. Pseudocode abstracts away all these niceties. When you actually program the algorithms, you have to take all of this into account. $\endgroup$
    – Yuval Filmus
    Mar 14, 2019 at 15:36
  • 2
    $\begingroup$ In your specific example, the rotation function should not be called when there is no grandparent. If it is, then some mistake has happened. Algorithms are not supposed to handle programming mistakes. $\endgroup$
    – Yuval Filmus
    Mar 14, 2019 at 15:37
  • 2
    $\begingroup$ @Trevör Could you please edit the question to add an explicit reference to the exact place "in a CS book where a potentially nil value is passed to a function, but neither the caller nor the callee check if the value is nil"? As a general advice, always try to add a sample or two when a general discussion is coming. $\endgroup$
    – John L.
    Mar 14, 2019 at 16:04
  • 2
    $\begingroup$ @Trevör Just in case you are scared of copyright, it is fair use to mention, discuss and review the content of that textbook. $\endgroup$
    – John L.
    Mar 14, 2019 at 16:07
  • 1
    $\begingroup$ @Trevör However, a screenshot might be of concern since "No part of this book may be reproduced in any form or by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher." On the other hand, I would not believe that such a short quotation here might cause any serious consequence. $\endgroup$
    – John L.
    Mar 14, 2019 at 16:13

1 Answer 1

Reset to default
7
$\begingroup$

The concept of a nil pointer is an implementation detail which is programming language specific. In some implementations, an attempt to accept the grandparent when there is none will just trigger an exception. This hints that the algorithm designer should not worry about nil pointers.

Indeed, in your example, the rotation function should simply not be called on a node with no grandparent. If you use the data structure correctly, then this will simply not happen. There are only two cases in which you would try to rotate a node without grandparent:

  • Implementation bug. You haven't coded the algorithm correctly.
  • Non-conforming usage. Your program for some reason calls the rotation procedure directly.

If your program is correct and it is used according to the interface of the data structure, then you will never attempt to rotate a node without a grandparent. Therefore if your code is attempting to dereference a nil pointer, you can be sure that there is some bug in your code. During development, you should probably raise an exception. For production code, you should follow whatever convention you do in any other part of your code.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.