Implicit nil checks in algorithms
$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
algorithms
asked Mar 14 at 15:24
TrevörTrevör
1819
$endgroup$
|
show 10 more comments
$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
algorithms
asked Mar 14 at 15:24
TrevörTrevör
1819
$endgroup$
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 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 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$
– Apass.Jack
Mar 14 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$
– Apass.Jack
Mar 14 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$
– Apass.Jack
Mar 14 at 16:13
|
show 10 more comments
$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
algorithms
asked Mar 14 at 15:24
TrevörTrevör
1819
$endgroup$
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
algorithms
algorithms
asked Mar 14 at 15:24
TrevörTrevör
1819
asked Mar 14 at 15:24
TrevörTrevör
1819
edited Mar 14 at 16:17
Trevör
asked Mar 14 at 15:24
TrevörTrevör
1819
asked Mar 14 at 15:24
TrevörTrevör
1819
asked Mar 14 at 15:24
TrevörTrevör
1819
1819
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 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 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$
– Apass.Jack
Mar 14 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$
– Apass.Jack
Mar 14 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$
– Apass.Jack
Mar 14 at 16:13
|
show 10 more comments
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 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 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$
– Apass.Jack
Mar 14 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$
– Apass.Jack
Mar 14 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$
– Apass.Jack
Mar 14 at 16:13
2
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 at 15:36
$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 at 15:36
2
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 at 15:37
$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 at 15:37
2
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$
– Apass.Jack
Mar 14 at 16:04
$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$
– Apass.Jack
Mar 14 at 16:04
2
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$
– Apass.Jack
Mar 14 at 16:07
$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$
– Apass.Jack
Mar 14 at 16:07
1
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$
– Apass.Jack
Mar 14 at 16:13
$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$
– Apass.Jack
Mar 14 at 16:13
|
show 10 more comments
1 Answer
1
active
oldest
votes
$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.
answered Mar 14 at 15:42
Yuval FilmusYuval Filmus
195k14184347
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "419"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105582%2fimplicit-nil-checks-in-algorithms%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
answered Mar 14 at 15:42
Yuval FilmusYuval Filmus
195k14184347
$endgroup$
add a comment |
$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.
answered Mar 14 at 15:42
Yuval FilmusYuval Filmus
195k14184347
$endgroup$
add a comment |
$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.
answered Mar 14 at 15:42
Yuval FilmusYuval Filmus
195k14184347
$endgroup$
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.
answered Mar 14 at 15:42
Yuval FilmusYuval Filmus
195k14184347
answered Mar 14 at 15:42
Yuval FilmusYuval Filmus
195k14184347
answered Mar 14 at 15:42
Yuval FilmusYuval Filmus
195k14184347
answered Mar 14 at 15:42
Yuval FilmusYuval Filmus
195k14184347
195k14184347
add a comment |
add a comment |
Thanks for contributing an answer to Computer Science Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105582%2fimplicit-nil-checks-in-algorithms%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
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 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 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$
– Apass.Jack
Mar 14 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$
– Apass.Jack
Mar 14 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$
– Apass.Jack
Mar 14 at 16:13