Implicit nil checks in algorithmsWhat is the purpose of using NIL for representing null nodes?Running Time of AlgorithmsAlgorithms Big O notationFootprint finding algorithmHow to systematically think about building implicit tree or a search space graph?Enforcing application layer consensus on top of a distributed consensus protocolWhat you want to “prove” in algorithmsExplicit algorithms and algorithms involving unknownsHindley-Milner type inference for language with implicit type castingIn this implementation of Hoare-partitioning Quicksort, why are additional checks for $i leq j$ needed?
A variation to the phrase "hanging over my shoulders"
Mimic lecturing on blackboard, facing audience
Were Persian-Median kings illiterate?
Why does the Sun have different day lengths, but not the gas giants?
C++ copy constructor called at return
Which Article Helped Get Rid of Technobabble in RPGs?
The IT department bottlenecks progress, how should I handle this?
Why is it that I can sometimes guess the next note?
What is the English pronunciation of "pain au chocolat"?
Has any country ever had 2 former presidents in jail simultaneously?
15% tax on $7.5k earnings. Is that right?
Why does Carol not get rid of the Kree symbol on her suit when she changes its colours?
It grows, but water kills it
How to make money from a browser who sees 5 seconds into the future of any web page?
A Trivial Diagnosis
Giving feedback to someone without sounding prejudiced
Does an advisor owe his/her student anything? Will an advisor keep a PhD student only out of pity?
Why do ¬, ∀ and ∃ have the same precedence?
Non-trope happy ending?
Is there a nicer/politer/more positive alternative for "negates"?
How does electrical safety system work on ISS?
What (the heck) is a Super Worm Equinox Moon?
Will number of steps recorded on FitBit/any fitness tracker add up distance in PokemonGo?
Why do some congregations only make noise at certain occasions of Haman?
Implicit nil checks in algorithms
What is the purpose of using NIL for representing null nodes?Running Time of AlgorithmsAlgorithms Big O notationFootprint finding algorithmHow to systematically think about building implicit tree or a search space graph?Enforcing application layer consensus on top of a distributed consensus protocolWhat you want to “prove” in algorithmsExplicit algorithms and algorithms involving unknownsHindley-Milner type inference for language with implicit type castingIn this implementation of Hoare-partitioning Quicksort, why are additional checks for $i leq j$ needed?
$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
195k14183347
$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
195k14183347
$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
195k14183347
$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
195k14183347
$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
195k14183347
answered Mar 14 at 15:42
Yuval FilmusYuval Filmus
195k14183347
answered Mar 14 at 15:42
Yuval FilmusYuval Filmus
195k14183347
answered Mar 14 at 15:42
Yuval FilmusYuval Filmus
195k14183347
195k14183347
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