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?
Could the Saturn V actually have launched astronauts around Venus?
How to answer questions about my characters?
Is Mortgage interest accrued after a December payment tax deductible?
How to simplify this time periods definition interface?
RegionDifference for Cylinder and Cuboid
At what level can a dragon innately cast its spells?
Rejected in 4th interview round citing insufficient years of experience
I need to drive a 7/16" nut but am unsure how to use the socket I bought for my screwdriver
Co-worker team leader wants to inject his friend's awful software into our development. What should I say to our common boss?
Replacing Windows 7 security updates with anti-virus?
PTIJ: Who should pay for Uber rides: the child or the parent?
Instead of Universal Basic Income, why not Universal Basic NEEDS?
Does splitting a potentially monolithic application into several smaller ones help prevent bugs?
Is a lawful good "antagonist" effective?
Life insurance that covers only simultaneous/dual deaths
Checking if rendered lightning:input components are populated
Is having access to past exams cheating and, if yes, could it be proven just by a good grade?
Why does Deadpool say "You're welcome, Canada," after shooting Ryan Reynolds in the end credits?
How to explain that I do not want to visit a country due to personal safety concern?
Rules about breaking the rules. How do I do it well?
Check this translation of Amores 1.3.26
An Accountant Seeks the Help of a Mathematician
My story is written in English, but is set in my home country. What language should I use for the dialogue?
Why doesn't the EU now just force the UK to choose between referendum and no-deal?
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 4 hours ago
TrevörTrevör
1768
$endgroup$
|
show 8 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 4 hours ago
TrevörTrevör
1768
$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
4 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
4 hours ago
$begingroup$
@YuvalFilmus So, do you mean I should just warp calls in aif ... != nil ...?
$endgroup$
– Trevör
4 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
4 hours ago
1
$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
4 hours ago
|
show 8 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 4 hours ago
TrevörTrevör
1768
$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 4 hours ago
TrevörTrevör
1768
asked 4 hours ago
TrevörTrevör
1768
edited 3 hours ago
Trevör
asked 4 hours ago
TrevörTrevör
1768
asked 4 hours ago
TrevörTrevör
1768
asked 4 hours ago
TrevörTrevör
1768
1768
$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
4 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
4 hours ago
$begingroup$
@YuvalFilmus So, do you mean I should just warp calls in aif ... != nil ...?
$endgroup$
– Trevör
4 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
4 hours ago
1
$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
4 hours ago
|
show 8 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
4 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
4 hours ago
$begingroup$
@YuvalFilmus So, do you mean I should just warp calls in aif ... != nil ...?
$endgroup$
– Trevör
4 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
4 hours ago
1
$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
4 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
4 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
4 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
4 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
4 hours ago
$begingroup$
@YuvalFilmus So, do you mean I should just warp calls in a
if ... != nil ... ?$endgroup$
– Trevör
4 hours ago
$begingroup$
@YuvalFilmus So, do you mean I should just warp calls in a
if ... != nil ... ?$endgroup$
– Trevör
4 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
4 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
4 hours ago
1
1
$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
4 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
4 hours ago
|
show 8 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 4 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 4 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 4 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 4 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 4 hours ago
Yuval FilmusYuval Filmus
194k14183347
answered 4 hours ago
Yuval FilmusYuval Filmus
194k14183347
answered 4 hours ago
Yuval FilmusYuval Filmus
194k14183347
answered 4 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
4 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
4 hours ago
$begingroup$
@YuvalFilmus So, do you mean I should just warp calls in a
if ... != nil ...?$endgroup$
– Trevör
4 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
4 hours ago
1
$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
4 hours ago