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?
What is the greatest age difference between a married couple in Tanach?
Can the damage from a Talisman of Pure Good (or Ultimate Evil) be non-lethal?
Could the Saturn V actually have launched astronauts around Venus?
Is it true that real estate prices mainly go up?
It's a yearly task, alright
Cultural lunch issues
Is a lawful good "antagonist" effective?
My adviser wants to be the first author
Identifying the interval from A♭ to D♯
Why is a Java array index expression evaluated before checking if the array reference expression is null?
How to explain that I do not want to visit a country due to personal safety concern?
Making a sword in the stone, in a medieval world without magic
What is a good source for large tables on the properties of water?
Why doesn't the EU now just force the UK to choose between referendum and no-deal?
Why does Deadpool say "You're welcome, Canada," after shooting Ryan Reynolds in the end credits?
What do these Greek words say? Possibly 2nd century
The use of "touch" and "touch on" in context
Can anyone tell me why this program fails?
Fill color and outline color with the same value
RegionDifference for Cylinder and Cuboid
How do anti-virus programs start at Windows boot?
MSTP and Rapid-PVST+
Make a transparent 448*448 image
What has been your most complicated TikZ drawing?
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 6 hours ago
TrevörTrevör
1818
$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 6 hours ago
TrevörTrevör
1818
$endgroup$
$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
6 hours ago
1
$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
6 hours ago
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
6 hours ago
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
6 hours ago
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
5 hours ago
|
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 6 hours ago
TrevörTrevör
1818
$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 6 hours ago
TrevörTrevör
1818
asked 6 hours ago
TrevörTrevör
1818
edited 5 hours ago
Trevör
asked 6 hours ago
TrevörTrevör
1818
asked 6 hours ago
TrevörTrevör
1818
asked 6 hours ago
TrevörTrevör
1818
1818
$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
6 hours ago
1
$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
6 hours ago
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
6 hours ago
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
6 hours ago
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
5 hours ago
|
show 10 more comments
$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
6 hours ago
1
$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
6 hours ago
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
6 hours ago
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
6 hours ago
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
5 hours ago
$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
6 hours ago
$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
6 hours ago
1
1
$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
6 hours ago
$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
6 hours ago
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
6 hours ago
$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
6 hours ago
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
6 hours ago
$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
6 hours ago
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
5 hours ago
$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
5 hours ago
|
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 6 hours ago
Yuval FilmusYuval Filmus
194k14183347
$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 6 hours ago
Yuval FilmusYuval Filmus
194k14183347
$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 6 hours ago
Yuval FilmusYuval Filmus
194k14183347
$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 6 hours ago
Yuval FilmusYuval Filmus
194k14183347
$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 6 hours ago
Yuval FilmusYuval Filmus
194k14183347
answered 6 hours ago
Yuval FilmusYuval Filmus
194k14183347
answered 6 hours ago
Yuval FilmusYuval Filmus
194k14183347
answered 6 hours ago
Yuval FilmusYuval Filmus
194k14183347
194k14183347
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
$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
6 hours ago
1
$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
6 hours ago
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
6 hours ago
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
6 hours ago
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
5 hours ago