答:
Some parts of a coding standard should apply equally to the production code and the unit test. Most notably, the naming conventions, brace placement and indentation style.

The reason for that is that it gives all the code a consistent look.

Some parts do apply to unit tests, but you never tend to violate them anyway. Think about stuff like the complexity of functions.

Some parts, I would ignore for unit tests, such as requirements about moving similar code into functions. For me, a certain amount of copy-paste is acceptable in unit tests, but less so in production code.

So, in the end, yes coding standards mostly apply also to unit tests.

Title: Should I spend time prettifying unit tests?

Body:
The company I used to work for before we had automated unit tests to test our work. However the coding standards and architecture was not very important for tests. Of course you had to indent code correctly and put your braces where you are supposed to put your braces, but no one would go nit picking through your tests code. This seemed reasonable to me as the tests were usually changed frequently and the idea was to quickly write a test and then start seriously writing the code.

The new company has just got the hang of unit testing our work, but they expect you to spend time making sure the test code looks as pretty and well thought out as the code it is testing. I personally think it a waste of time since tests are internal and while test code should be neat, it does not have to be as perfectly engineered as the code that goes out the door to the customer.

Am I wrong in my belief? What is the right thing to do here fellow programmers?

Frequency of how often our programmers have to modify / extend / reuse existing unit tests varies, some more often and others less often. We are using Python Django and most of the test architecture is built-in and most tests are just simple functions. Very less setup/teardown needed.


问:
Should I spend time prettifying unit tests?
The company I used to work for before we had automated unit tests to test our work. However the coding standards and architecture was not very important for tests. Of course you had to indent code correctly and put your braces where you are supposed to put your braces, but no one would go nit picking through your tests code. This seemed reasonable to me as the tests were usually changed frequently and the idea was to quickly write a test and then start seriously writing the code.

The new company has just got the hang of unit testing our work, but they expect you to spend time making sure the test code looks as pretty and well thought out as the code it is testing. I personally think it a waste of time since tests are internal and while test code should be neat, it does not have to be as perfectly engineered as the code that goes out the door to the customer.

Am I wrong in my belief? What is the right thing to do here fellow programmers?

Frequency of how often our programmers have to modify / extend / reuse existing unit tests varies, some more often and others less often. We are using Python Django and most of the test architecture is built-in and most tests are just simple functions. Very less setup/teardown needed.

答:
The reason why you create pretty code is because it makes the code easier to maintain at a later stage.

When the requirements of your software change during the development, all unit-tests need to be changed to test correctness according to the new requirements instead of the old. To make this possible, the unit-tests need to be maintainable.

Also, when one of your tests fails, the programmer who broke the test will certainly want to know why it failed. To do that, he needs to look at your tests and find out what they are actually testing. That will be considerably easier when the test code is easy to understand.

So yes, you should aim for a high quailtiy standard when writing unit-testing code.

ContentLicense: CC BY-SA 3.0


问:
Can an EULA restrict what you can use an application for?
I realise this might be offtopic here  - but I couldn't find a better place in the stackexchange family. And this question has simply been bugging me for years..

What I wonder is: can an eula define WHAT you use an application for? IE: if I write a text editor, can I say "You can't write fantasy novels with it".

I'm wondering this because many applications have clauses like "you can't use XY to make something illegal". And actually wondering if this has any use? It is like saying that when you buy a car you lose the rights to drive it once you drive through a red light, or go speeding. I see it as "non of the car designer's business".

答:
Well a product being used for illegal, unethical or immoral activities can very much be their business.  If a user of your software used said software to to assist him in a criminal or damaging act then you the creator of the software are on the long line of parties being sued or potentially even prosecuted.  By stating the intended use and the explicit uses that are not allowed, you absolve yourself of responsibility for damages due to users breaching the terms of the Agreement that they had accepted.

This adult website powered by ChristiansMeetup.biz

The other reason why a EULA may forbid certain uses of software by end users is to avoid potential associations or affiliations that could be damaging to the organizations reputation.  In the example above, the fictional company ChristiansMeetup.biz could suffer reputation losses and have their bottom line hurt by allowing the intended use of its software to this particular end user.

Finally, your analogy with the car is flawed.

One can and certainly does lose the rights to drive for repeat dangerous traffic violations.

One must accept the rules of driving and pass tests on these rules to prove competent enough to drive.  Driving is a privilege not a right.

A legal contract between you and the car manufacturer over intended use is completely unnecessary as there are explicit laws that already define what the drivers behavior should be.  The car manufacturer doesn't have to worry about defining intended use because the government does that for them, and also states that the manufacturer is not at fault for driver errors.

A EULA is a legal contract and it exists specifically because the laws and regulations may not be existant or may be fuzzy on certain aspects.


问:
Is it ok to use static (compile-time) assertions in unit tests?
Or more generally: to trigger compiler errors in test projects if something that can be checked at compile time is wrong?</p>

答:
In principle, why not. A failed test is a failed test regardless of whether it happens at compile time or runtime. Compile time failures can also occur without an explicit static assertion.

On the other hand, if your unit tests are only executed infrequently (shame on you), say every few dozen check-ins, then a compile time check might hinder you in finding out if there are more breakages. That depends on your build structure and how your tests are organised.


问:
Can someone else patent my open-sourced algorithm?
I've written a recursive search algorithm to find the boundaries of a voxel data structure in order to render it more efficiently. I've looked around, and either it's such a simple and obvious technique that nobody's bothered to patent it, or it's novel and nobody's done it this way before.

It's openly "published" on GitHub and protected under the GPL. I'd like to show it to others, to see if it can be improved, however...

I fear that although I've written and published it, someone may attempt to patent the same idea.

Am I safe, protected by the banners of open source software, or must I attempt to protect myself like the big guns and patent trolls do?

It's my belief that software patents are evil, and that in order for the best software to be written, many eyes need to see it. I'm worried this may be a rather naïve viewpoint on how software is written, though, and I'm curious as to what others think.

答:
In the US, anyone can patent any idea at any time that doesn't already have a patent attached to it. If someone patents your idea, the burden of proof is then on you to prove that the original idea was yours and yours alone and also that the person who registered the patent got that idea from your work.

In all cases like this, it ends up in a court of law. If you're truly worried about it, you should:

Consult a patent attorney

Remove your code from open source until you've resolved the issues your attorney brings up

Document everything about your idea from the moment of inspiration to the work involved in bringing this idea to fruition.


答:
Disclaimer: I am not a lawyer. If you are concerned enough, seek professional legal advice.

Assuming we are dealing with US law, it would be very difficult for someone to patent it now because the code on GitHub would be prior art. However, someone may have already filed a patent before you first published the work to GitHub. Make sure you keep any notes, source code or similar material if it significantly predates the GitHub work.

I would not recommend looking for similar patents because they can be very difficult to read and, if you do find one and continue, your liability triples under US law.

However, I would recommend searching for similar implementations outside patents as there may be existing prior art elsewhere. As someone whose professional work used to include reviewing patent applications and looking for prior art, if you do not find anything similar, I would guess you are not searching in the right places or using the correct terms.

Also note that, even if someone else does patent it, they may not assert their right to prevent you using the invention. They would only do so if your use of the invention materially impacts their sales or otherwise made them more money than taking legal action against you.

As mentioned above, seek professional advice if it concerns you.

[Edit: Added the following.]

Also remember that the GitHub code is only prior art for that exact implementation. There may be variations, alternatives or improvements, for example, so keeping notes or a diary for potentially patentable work is critical.

Title: Can someone else patent my open-sourced algorithm?

Body:
I've written a recursive search algorithm to find the boundaries of a voxel data structure in order to render it more efficiently. I've looked around, and either it's such a simple and obvious technique that nobody's bothered to patent it, or it's novel and nobody's done it this way before.

It's openly "published" on GitHub and protected under the GPL. I'd like to show it to others, to see if it can be improved, however...

I fear that although I've written and published it, someone may attempt to patent the same idea.

Am I safe, protected by the banners of open source software, or must I attempt to protect myself like the big guns and patent trolls do?

It's my belief that software patents are evil, and that in order for the best software to be written, many eyes need to see it. I'm worried this may be a rather naïve viewpoint on how software is written, though, and I'm curious as to what others think.


答:
According to German patent law, an method can only be patented if it is new. That means, that it must not be publicly accessible before the patent was applied for. Normally making your algorithm available via GitHub is making it publicly available according to German patent law. However there are edge cases. However German patent law is very much restrictive than US patent law for example when it comes to patenting software.

Consulting a lawyer is a good idea.


答:
Should I spend time prettifying unit tests?

If prettifying means to make the unit test more consistent and easier to understand then yes.

As I have not written a book or interviewed many people I can only pass along my personal experience in this matter. Recently I spent a week on an F# project making a several hundred unit test consistent, easier to read and more comprehensive. In the process I learned a few things and developed a philosophy.

In making the unit test consistent, I began to see test cases that needed to be added to make the test for a function comprehensive. Because the unit test were consistent it was easy to spot the cases that needed to be added. Basically I tried to move the parameters and result for a function into an array element with all of the test cases for a function in one array one after the next. It made seeing the patterns of this input causes this output easy because you only had to look at the input and output, not all of the overhead needed for a test case. Then the mechanics of the test case followed pulling out the parameters and result and passing them through the test function.

For example:

```<code>let private butLastValues : (int list * int list)[] = [|
(
    // idx 0
    // lib.butLast.01
    // System.Exception - butlast
    [],
    [] // Dummy value used as place holder
);
(
    // idx 1
    // lib.butLast.02
    [1],
    []
);
(
    // idx 2
    // lib.butLast.03
    [1; 2],
    [1]
);
(
    // idx 3
    // lib.butLast.04
    [1; 2; 3],
    [1; 2]
);
|]

[<TestCase(0, TestName = "lib.butLast.01",     ExpectedException=typeof<System.Exception>, ExpectedMessage="butlast")>]
[<TestCase(1, TestName = "lib.butLast.02")>]
[<TestCase(2, TestName = "lib.butLast.03")>]
[<TestCase(3, TestName = "lib.butLast.04")>]

[<Test>]
let ``List butlast`` idx =
    let (list, _) = butLastValues.[idx]
    let (_, result) = butLastValues.[idx]
    butlast list
    |> should equal result
</code>```

In making the unit test easier to read it became obvious that they were good enough to use for learning because the comprehensiveness of the unit test for a function became better than some of the documentation; it was real working examples that not only demonstrated a case but also showed what the result would be, be it a valid result, exception, or failure to complete.

Since our project was a translation of OCaml code from "Handbook of Practical Logic and Automated Reasoning" by John Harrison, we created both a direct translation version and an optimized version. Having made the test comprehensive it was easier to additionally test the optimized code and the normal code using the same test case.

So by spending time working with the unit test by hand and in detail, I learned more about how the code worked than just by reading the code. I began to see patterns in the test data that I would not be seen in the code and leveraged that to learn more about how the code worked.

If you view unit test as something that should be created and then left in a box only to be used by automated tools then I think you are missing something significant.

Body:
Should I spend time prettifying unit tests?

If prettifying means to make the unit test more consistent and easier to understand then yes.

As I have not written a book or interviewed many people I can only pass along my personal experience in this matter. Recently I spent a week on an F# project making a several hundred unit test consistent, easier to read and more comprehensive. In the process I learned a few things and developed a philosophy.

In making the unit test consistent, I began to see test cases that needed to be added to make the test for a function comprehensive. Because the unit test were consistent it was easy to spot the cases that needed to be added. Basically I tried to move the parameters and result for a function into an array element with all of the test cases for a function in one array one after the next. It made seeing the patterns of this input causes this output easy because you only had to look at the input and output, not all of the overhead needed for a test case. Then the mechanics of the test case followed pulling out the parameters and result and passing them through the test function.

For example:

let private butLastValues : (int list * int list)[] = [|
(
    // idx 0
    // lib.butLast.01
    // System.Exception - butlast
    [],
    [] // Dummy value used as place holder
);
(
    // idx 1
    // lib.butLast.02
    [1],
    []
);
(
    // idx 2
    // lib.butLast.03
    [1; 2],
    [1]
);
(
    // idx 3
    // lib.butLast.04
    [1; 2; 3],
    [1; 2]
);
|]

[<TestCase(0, TestName = "lib.butLast.01",     ExpectedException=typeof<System.Exception>, ExpectedMessage="butlast")>]
[<TestCase(1, TestName = "lib.butLast.02")>]
[<TestCase(2, TestName = "lib.butLast.03")>]
[<TestCase(3, TestName = "lib.butLast.04")>]

[<Test>]
let ``List butlast`` idx =
    let (list, _) = butLastValues.[idx]
    let (_, result) = butLastValues.[idx]
    butlast list
    |> should equal result

In making the unit test easier to read it became obvious that they were good enough to use for learning because the comprehensiveness of the unit test for a function became better than some of the documentation; it was real working examples that not only demonstrated a case but also showed what the result would be, be it a valid result, exception, or failure to complete.

Since our project was a translation of OCaml code from "Handbook of Practical Logic and Automated Reasoning" by John Harrison, we created both a direct translation version and an optimized version. Having made the test comprehensive it was easier to additionally test the optimized code and the normal code using the same test case.

So by spending time working with the unit test by hand and in detail, I learned more about how the code worked than just by reading the code. I began to see patterns in the test data that I would not be seen in the code and leveraged that to learn more about how the code worked.

If you view unit test as something that should be created and then left in a box only to be used by automated tools then I think you are missing something significant.


问:
What does this mean: Expression<Func<TModel, TValue>>
In ASP.Net MVC, in the razor view, you can type this kind of code:

```<code>@Html.EditorFor(model => model.Name)
</code>```

(in this case, it creates a textbox for the field Name of the object which is defined as the type of the model)

Now when i see the definition of the EditorFor method, it is this:

```<code>EditorFor<TModel, TValue>(this HtmlHelper<TModel> html, Expression<Func<TModel, TValue>> expression);
</code>```

So i tried implementing that kind of method myself, but i realy don't see what this means
Expression<Func<TModel, TValue>>

Who can explain to me what an expression is, and the Func, and the Expression of type Func?

The explanations i found where all so abstract it didn't give me a clue....

答:
The HTML Helpers use a trick that has been called "Static Reflection" that was brought to the .NET framework to support LINQ to SQL and Entity Framework. Basically the Expression captures a Lambda which is verified at compile time (hence the Static) in a syntactic tree. The tree can be walked and can give things like the name of the member that is referenced by the body of the lambda.

Essentially, it's a work around for .NET's lack of a "symbol" keyword like some other languages support.


答:
The complaint that the tests don't have to be "[as] well thought out as the code it is testing" is not a valid one.

If you are using the the tests to define the expected behaviour of the code, then if your expectations are created without rigour, the code which meets those expectations will be sloppy and badly thought out. You also may fail to cover all important cases or bake in badly thought out assumptions.

Someone should be able to come to the unit test and see what the test is saying about the behaviour of the unit under test, what the constraints on that behaviour are and how the unit is expected to be used. Add whatever architecture and documentation to the test is necessary to achieve that.


答:
In this specific example, the generated HTML looks like this:

```<code><input class="text-box single-line" id="Name" name="Name" type="text" value="ActualName" />
</code>```

If the parameter was just a Func, you would be able to get value ActualName, but not the name of the property you're accessing (Name). So, to get that name, you would need it as a string parameter (e.g. something like @Html.EditorFor(model => model.Name, "Name")).

This is not nice, because it means you have to enter the property name twice. Worse, you lose compile-time safety: if the property name changes, you won't get an error on the second parameter.

Title: What does this mean: Expression<Func<TModel, TValue>>

Body:
In ASP.Net MVC, in the razor view, you can type this kind of code:

```<code>@Html.EditorFor(model => model.Name)
</code>```

(in this case, it creates a textbox for the field Name of the object which is defined as the type of the model)

Now when i see the definition of the EditorFor method, it is this:

```<code>EditorFor<TModel, TValue>(this HtmlHelper<TModel> html, Expression<Func<TModel, TValue>> expression);
</code>```

So i tried implementing that kind of method myself, but i realy don't see what this means
Expression<Func<TModel, TValue>>

Who can explain to me what an expression is, and the Func, and the Expression of type Func?

The explanations i found where all so abstract it didn't give me a clue....

Body:
In this specific example, the generated HTML looks like this:

<input class="text-box single-line" id="Name" name="Name" type="text" value="ActualName" />

If the parameter was just a Func, you would be able to get value ActualName, but not the name of the property you're accessing (Name). So, to get that name, you would need it as a string parameter (e.g. something like @Html.EditorFor(model => model.Name, "Name")).

This is not nice, because it means you have to enter the property name twice. Worse, you lose compile-time safety: if the property name changes, you won't get an error on the second parameter.


问:
Convert grammar into an LL(1) grammar which recognises the same language
I have the following sample question for a compilers exam and wanted to check my solution.

```<code>Convert the following grammar into an LL(1) grammar which recognises the same
language:

E -> E + T
E -> T
T -> id
T -> id()
T -> id(L)
L -> E;L
L -> E
</code>```

For my answer I have

```<code>E  -> T E'
E' -> + T | ε
T  -> id
T  -> id()
T  -> id(L)
L  -> E L'
L' -> ;E | ε
</code>```

Can anybody verify the answer?

Edit

Ok so would it be similar to...

```<code>E  -> T E'
E' -> + E | ε
T  -> id
T  -> id()
T  -> id(L)
L  -> E L'
L' -> ;E | ε
</code>```

答:
E -> E + T | T

  T -> id | id() | id(L)

  L -> E;L | E

E -> TE'

E'-> +TE' | ε

L -> E;L | E

L -> EL'

L'-> ;L | ε

you need to transform T as I did with L otherwise it will be an LL(3)


答:
Yes, it is okay to use static/compile-time assertions in unit tests

In my experience, many developers don't the unit tests enough, although they may compile them. In a complex environment, it is not necessarily possible to run the unit tests on the build machine (environment setup, etc) but you could certainly compile the unit tests. Static assertions would find problems at that point regardless of whether they got run at all.

Also, we've found that it is less intrusive to add the unit tests to the list of objects that need compiling compared to forcing people to compile-then-run a unit test runner before you let them compile/package the main code. Your mileage may vary, of course.

Title: Is it ok to use static (compile-time) assertions in unit tests?

Body: Or more generally: to trigger compiler errors in test projects if something that can be checked at compile time is wrong?</p>


问:
How do you handle measuring Code Coverage in JavaScript
In order to measure Code Coverage for JavaScript unit tests, one needs to instrument the code, run the tests and then perform post-processing.

My concern is that, as a result, you are unit testing code that will never be run in production. Since JavaScript isn't compiled, what you test should be precisely what you execute.

So here's my question, how do you handle this? One thought I had was to run Unit Testing on the production code and use that for my pass fail. I would then create a shadow of my production code, with instrumentation and run my unit tests again; this would give me my code coverage stats.

Has anyone come across a method that is a little more graceful than this?

EDIT
I don't want to use browser plugins, because I then need to use a browser in order to run my unit tests.

答:
I'm not anti-testing but the very concept of trying to establish "code coverage" in client-side JavaScript strikes me as missing the point. Don't solve problems you don't have. Worry about actual risks, not every piece of code you've written. Risks in my book are code that comes into contact with third-party stuff you have no control over or a badly architected piece of an app where far too many hands are in the same cookie jar. If an entire app is brittle and prone to regression issues, all that attempting to achieve maximum code coverage does for you is enable more bad code.

Executing code in client-side JS is trivial. You should be testing everything you do thoroughly as you write it and keeping things clean and decoupled to avoid regression errors in the first place.


问:
What are some things you have read that inspired and guided you as a programmer?
For example, being a beginner, I find a lot of inspiration and direction from reading this post by Bryan Woods.</p>

答: I found How to Become a Hacker very inspirational. It also gives a workable roadmap for developing as a programmer.</p>

ContentLicense: CC BY-SA 2.5


答:
In my experience, good programmers are perfectionists. Good programmers write all their programs in the same, consistent manner. They keep to the same coding style consistently and they avoid the same bad practices no matter what kind of program they are making.

Potentially bad programmers do the opposite. They always go looking for excuses to make the programs sloppy. Some warning signs are comments like "nobody will read this code but me", "this code will never be re-used", "I'll tidy it up later", "I obfuscated it to avoid extra typing" etc. Such programmers tend to write sloppy code not only in the quick & dirty tests, but also where it matters the most.

Consider this: how likely is it that you are going to re-use code from an old test when you are writing a new one? The answer is hopefully "quite likely".

Then of course, you may not need to produce the same amount of "overhead tasks" when coding some quick & dirty case. Source code and other documentation doesn't need to be detailed, quality checks like manual code review, static analysis etc needn't be rigorous, version handling and publishing don't need to be as formal. But there are no obvious reasons why the source code in itself should be more sloppy


问:
In javascript and other languages which lack a compiler, is unit testing a good method to ensure correct syntax and variable naming?
I've been working on a medium sized web application that makes very heavy use of javascript.  I tend to introduce common errors per 10 lines of code with either an unknown variable name or function name from another module\namespace or forgetting a return and other common errors.

I'm noticing I'm getting quite a lot of feedback in fixing these errors as a side effect of my qunit testing.  Is unit testing a typical way to make up for a compiler in dynamic languages?

答: Firebug and Chrome Developer Tools are more than sufficient for simple stuff like this. Just watch the console.</p>


问:
Low Latency Unix/Linux
Most low latency/high frequency programming jobs (based on job specs) appear to be implemented on unix platforms. In a lot of the specs they make particular request for people with "low latency linux" type of experience.

Assuming this does not mean a real-time linux OS, could people give me help with what this could be referring to? I know you can set CPU affinity to threads, but I am assuming they are asking for much more to it than that.

Kernel tuning? (although I heard manufacturers like solarflare produce kernel bypass network cards anyway)?

What about DMA or possibly shared memory between processes? If people could give me brief ideas I can go and do the research on google.

(This question will probably require somebody familiar with High Frequency Trading)

答:
In addition to the excellent hardware/setup tuning answer from @jimwise, "low latency linux" is implying:

C++ for reasons of determinism (no surprise delay while GC kicks in), access to low-level facilities (I/O, signals), language power (full use of TMP and STL, type safety).

prefer speed-over-memory: >512 Gb of RAM is common; databases are in-memory, cached up-front, or exotic NoSQL products.

algorithm choice: as-fast-as-possible versus sane/understandable/extensible, e.g. lock-free, multiple bit arrays instead of array-of-objects-with-bool-properties.

full use of OS facilities such as Shared Memory between processes on different cores.

secure. HFT software is usually co-located in an Stock Exchange so malware possibilities are unacceptable.

Many of these techniques have overlap with games development which is one reason why the financial software industry absorbs any recently-redundant games programmers (at least until they pay their rent arrears).

The underlying need is to be able to listen to a very high bandwidth stream of market data such as security (stocks, commodities, fx) prices and then make a very fast buy/sell/do-nothing decision based on the security, the price and current holdings.

Of course, this can all go spectacularly wrong, too.

So i'll elaborate on the bit arrays point. Let's say we have a High Frequency Trading system that operates on a long list of Orders (Buy 5k IBM, Sell 10k DELL, etc). Let's say we need to quickly determine if all of the orders are filled, so that we can move onto the next task. In traditional OO programming, this is going to look like:

```<code>class Order {
  bool _isFilled;
  ...
public:
  inline bool isFilled() const { return _isFilled; }
};

std::vector<Order> orders;
bool needToFillMore = std::any_of(orders.begin(), orders.end(),
  [](const Order & o) { return !o.isFilled(); } );
</code>```

the algorithmic complexity of this code going to be O(N) as it is a linear scan. Let's take a look at the performance profile in terms of memory accesses: each iteration of the loop inside std::any_of() is going to call o.isFilled(), which is inlined, so becomes a memory access of _isFilled, 1 byte (or 4 dependending on your architecture, compiler and compiler settings) in an object of let's say 128 bytes total. So we're accessing 1 byte in every 128 bytes. When we read the 1 byte, presuming worst-case, we'll get a CPU data cache miss. This'll cause a read request to RAM which reads an entire line from RAM (see here for more info) just to read out 8 bits. So the memory access profile is proportional to N.

Compare this with:

```<code>const size_t ELEMS = MAX_ORDERS / sizeof (int);
unsigned int ordersFilled[ELEMS];

bool needToFillMore = std::any_of(ordersFilled, &ordersFilled[ELEMS+1],
   [](int packedFilledOrders) { return !(packedOrders == 0xFFFFFFFF); }
</code>```

the memory access profile of this, assuming worst-case again, is ELEMS divided by the width of a RAM line (varies - could be dual-channel or triple-channel, etc).

So, in effect, we're optimising algorithms for memory access patterns. No amount of RAM will help - it's the CPU data cache size that causes this need.

Does this help?

There's an excellent CPPCon talk all about low-latency programming (for HFT) on YouTube: https://www.youtube.com/watch?v=NH1Tta7purM

Title: Low Latency Unix/Linux

Body:
In addition to the excellent hardware/setup tuning answer from @jimwise, "low latency linux" is implying:

C++ for reasons of determinism (no surprise delay while GC kicks in), access to low-level facilities (I/O, signals), language power (full use of TMP and STL, type safety).

prefer speed-over-memory: >512 Gb of RAM is common; databases are in-memory, cached up-front, or exotic NoSQL products.

algorithm choice: as-fast-as-possible versus sane/understandable/extensible, e.g. lock-free, multiple bit arrays instead of array-of-objects-with-bool-properties.

full use of OS facilities such as Shared Memory between processes on different cores.

secure. HFT software is usually co-located in an Stock Exchange so malware possibilities are unacceptable.

Many of these techniques have overlap with games development which is one reason why the financial software industry absorbs any recently-redundant games programmers (at least until they pay their rent arrears).

The underlying need is to be able to listen to a very high bandwidth stream of market data such as security (stocks, commodities, fx) prices and then make a very fast buy/sell/do-nothing decision based on the security, the price and current holdings.

Of course, this can all go spectacularly wrong, too.

So i'll elaborate on the bit arrays point. Let's say we have a High Frequency Trading system that operates on a long list of Orders (Buy 5k IBM, Sell 10k DELL, etc). Let's say we need to quickly determine if all of the orders are filled, so that we can move onto the next task. In traditional OO programming, this is going to look like:

class Order {
  bool _isFilled;
  ...
public:
  inline bool isFilled() const { return _isFilled; }
};

std::vector<Order> orders;
bool needToFillMore = std::any_of(orders.begin(), orders.end(),
  [](const Order & o) { return !o.isFilled(); } );

the algorithmic complexity of this code going to be O(N) as it is a linear scan. Let's take a look at the performance profile in terms of memory accesses: each iteration of the loop inside std::any_of() is going to call o.isFilled(), which is inlined, so becomes a memory access of _isFilled, 1 byte (or 4 dependending on your architecture, compiler and compiler settings) in an object of let's say 128 bytes total. So we're accessing 1 byte in every 128 bytes. When we read the 1 byte, presuming worst-case, we'll get a CPU data cache miss. This'll cause a read request to RAM which reads an entire line from RAM (see here for more info) just to read out 8 bits. So the memory access profile is proportional to N.

Compare this with:

const size_t ELEMS = MAX_ORDERS / sizeof (int);
unsigned int ordersFilled[ELEMS];

bool needToFillMore = std::any_of(ordersFilled, &ordersFilled[ELEMS+1],
   [](int packedFilledOrders) { return !(packedOrders == 0xFFFFFFFF); }

the memory access profile of this, assuming worst-case again, is ELEMS divided by the width of a RAM line (varies - could be dual-channel or triple-channel, etc).

So, in effect, we're optimising algorithms for memory access patterns. No amount of RAM will help - it's the CPU data cache size that causes this need.

Does this help?

There's an excellent CPPCon talk all about low-latency programming (for HFT) on YouTube: https://www.youtube.com/watch?v=NH1Tta7purM


问:
Can branching ever be considered a bad practice?

Possible Duplicate:

  To branch or not to branch?

A co-worker is against branching.  I use branching all the time.  I put the team onto a  basic 3 branch system.  I create my own feature branches.  Said co-worker tends to have good ideas, follow best practices and I tend to agree with him on many such things.  Except this.

The successful software shops I've read about: Microsoft, Google, fogcreek all use branching.  My co-worker argues that because of the way our shop runs (medical field), branching causes problems.  Instead, he says we should create many small project's (*.csproj files) and never work on the same code at the same time.

I agree, we have issues with merging.  I argue the root cause of these issues are a lack team communication and a lack of knowledge on how to correctly use our source control system to full effect (TFS).  I consider his approach to be programming in Silo's and a DLL management nightmare.

Are there situations where Branching is a bad idea?  Am I wrong?

答:
My personal experience with this is that training will help in this cases.

I had the same problem (with SVN) with co-workers. After training my co-workers one project group (where I was not member of) only developed on branches after that never on trunk.

The most important thing in training is that merging (and conflicts during that) are normal and no exception. If your co-workers lose the fear to merge and having conflicts (because this is normal) then after some time the situation should clear.


答:
The question is awfully general - I can say, with some assurance, that there is ALWAYS some situation where X is a bad idea, no matter how good an idea X is normally.

Your co-worker is clinging to a view that was NECESSARY back in the day, when good source control and merge tools did not exist. He essentially doesn't believe that merging can work on a day-to-day basis.

Less than 5 years ago, I worked with some people who insisted on locking checkouts (you had to checkout before editing, and only one person could check a file out at a time) because they just couldn't understand that merging was possible and worked just fine.

The question is: WHY does your co-worker not believe in merging? I've believed in it ever since I first saw it work in CVS many moons ago.

My guess is that there is something in how you are operating that is causing merge problems, and your co-worker can't see that it's possible due to some operational issue on your team's part. Until you figure out what that is, you're never going to convince him.

Title: Can branching ever be considered a bad practice?

Body:
Possible Duplicate:

  To branch or not to branch?

A co-worker is against branching.  I use branching all the time.  I put the team onto a  basic 3 branch system.  I create my own feature branches.  Said co-worker tends to have good ideas, follow best practices and I tend to agree with him on many such things.  Except this.

The successful software shops I've read about: Microsoft, Google, fogcreek all use branching.  My co-worker argues that because of the way our shop runs (medical field), branching causes problems.  Instead, he says we should create many small project's (*.csproj files) and never work on the same code at the same time.

I agree, we have issues with merging.  I argue the root cause of these issues are a lack team communication and a lack of knowledge on how to correctly use our source control system to full effect (TFS).  I consider his approach to be programming in Silo's and a DLL management nightmare.

Are there situations where Branching is a bad idea?  Am I wrong?


答: Even the best ideas can be taken to a ridiculous extreme.  While most versioning systems can handle lots of branches without issues, the problem would be on the human end, as you end up getting lost on which branch belongs to whom, was the branch to be worked on later or to be made inactive, etc.  </p>


问:
Holding mutable data in a single place
Given a mutable property, it generally makes sense to only hold/store that property in a single place. When the data needs to change you only need to update a single field, and you can completely avoid bugs where the different fields get out of sync.

An extremely simple example could be:

The 'right' approach:

```<code>class Owner {
    String name;
}

class Dog {
    Owner owner;

    String getOwnersName() {
        return owner.name;
    }
}
</code>```

The 'wrong' approach:

```<code>class Owner {
    String name;
}

class Dog {
    Owner owner;
    String ownerName;

    String getOwnersName() {
        return ownerName;
    }
}
</code>```

Experience has taught me that it's very seldom a good idea to break this rule of thumb. The risk of bugs being introduced and the increased effort required to understand the code almost always outweighs any benefit.

My question is, is there a name for this rule/principle?

Bonus points for linking to articles/blogs/etc. which make the argument for this clearly. Double bonus points for counter-arguments!

答: This is a facet of Don't repeat yourself, and arguably the single most important meta-principle of computer programming.</p>

Title: Holding mutable data in a single place


答:
Well, more branches implies more complexity. Imagine your software grows, the team grows, time passes... I think the main issue is dealing with merging and conflicts if the branches start to diverge too much and people work parallely on them.

Stupid example: we had two big branches, with changes in overlapping areas, and a guy had the super smart idea to change all tabs to spaces on trunk ...arrrrghh ...the merging was a nightmare. Actually, the merging tool didn't even cope with it correctly, so in the end, I "not merged" thousands of lines one-by-one by hand.

Additionally, when time passes, you've to keep track of what is in what, which one is still active, which one not, if some branch stays inactive too long, it becomes harder to merge, or perhaps someone will forget a mini-fix while resolving a conflict, etc.

I guess, in the end, it's all a question about the right balance. Make a branch when you need to, but don't make them "just for fun". I would also tend to easier make a branch with Git or Mercurial than I would with SVN, they are easier and more flexible when dealing with branches while SVN has several times been a PITA for me. So I guess it depends on what you use as well ...but less branches usually makes life easier.


问:
What "version naming convention" do you use?
Are different version naming conventions suited to different projects? What do you use and why?

Personally, I prefer a build number in hexadecimal (e.g 11BCF), this should be incremented very regularly. And then for customers a simple 3 digit version number, i.e. 1.1.3.

```<code>1.2.3 (11BCF) <- Build number, should correspond with a revision in source control
^ ^ ^
| | |
| | +--- Minor bugs, spelling mistakes, etc.
| +----- Minor features, major bug fixes, etc.
+------- Major version, UX changes, file format changes, etc.
</code>```

答:
I try to use the RubyGems Rational Versioning policy in which:

The Major version number is incremented when binary compatibility is broken

The minor version number is incremented when new functionality is added

The build number changes for bug fixes.


答:
If the unit tests run flawlessly, but the main code doesn't run, then the project is a failure.  If the main code runs flawlessly, but the unit tests don't, then the project is a success (albeit with imperfect methodology).  </p>

<p>If you're doing something that spends a significant amounts of time and only results in the unit tests being prettier, you're wasting time.  </p>

Body:
If the unit tests run flawlessly, but the main code doesn't run, then the project is a failure.  If the main code runs flawlessly, but the unit tests don't, then the project is a success (albeit with imperfect methodology).

If you're doing something that spends a significant amounts of time and only results in the unit tests being prettier, you're wasting time.


答:
Database people call it Normalization.  Good system designs tend to start with only normalized data and only make exceptions as needed.

One counter-example not mentioned in the Normalization article is concurrent programming.  When two or more processes access the same piece of mutable data, there are all sorts of issues where process A starts a read, then process B performs a write, which value does process A read?  The old one, or the new one?  If your data is a complex object, A may get a pointer to a new, but uninitialized object and start using it before it is fully created.

When you have to share mutable data across processes, it is often better to make (immutable) defensive copies of your data.  That way process A can fully guarantee that process B reads a correct, fully initialized value and that process B cannot then accidentally or intentionally change the value of A's data (or vice-versa).

This is the reason that Java has the convention of using those annoying get/set methods.  If you expose a field with a get/set, then later discover an issue where a client of your class is changing your class's underlying behavior in an unsafe way, then without changing your class's interface you can:

Make the underlying data immutable

Return a defensive copy from the get() method

Add synchronization to the get/set methods

Immutable data is the simplest and most reliable solution when it's practical to design your class so that the data in it does not change.  If the object has a small memory footprint and will not be created so many times as to fill memory with tiny copies of itself, then a defensive copy is probably more efficient than synchronization.  If the underlying object is expensive to create, has a large memory footprint, or needs to be created so many times that it would fill memory quickly, then synchronization may be better than defensive copies.

Newer languages like Ruby and Scala generate implicit get/set methods for you so that it looks like you are accessing the fields directly, but you can later override the default get/set methods as described above.  Functional languages like Scala, Clojure, or Haskell assume all data is immutable unless you specify otherwise.

Even within a single process it's very easy to pass myObject to different methods or use it on different pages of code within the same procedure and one place it sets myObject.color = BLUE and somewhere else it sets myObject.color = RED and each place expects myObject to retain its color.  It's easy to make this kind of programming error whenever code becomes complicated enough.

Title: Holding mutable data in a single place

Body:
Given a mutable property, it generally makes sense to only hold/store that property in a single place. When the data needs to change you only need to update a single field, and you can completely avoid bugs where the different fields get out of sync.

An extremely simple example could be:

The 'right' approach:

```<code>class Owner {
    String name;
}

class Dog {
    Owner owner;

    String getOwnersName() {
        return owner.name;
    }
}
</code>```

The 'wrong' approach:

```<code>class Owner {
    String name;
}

class Dog {
    Owner owner;
    String ownerName;

    String getOwnersName() {
        return ownerName;
    }
}
</code>```

Experience has taught me that it's very seldom a good idea to break this rule of thumb. The risk of bugs being introduced and the increased effort required to understand the code almost always outweighs any benefit.

My question is, is there a name for this rule/principle?

Bonus points for linking to articles/blogs/etc. which make the argument for this clearly. Double bonus points for counter-arguments!


答:
I would strongly recommend that you run a controlled comparative trial to find out which way is better for your project instead of wasting efforts and ruining team communication on fruitless "theoretical" debates.

In one of my past projects we wasted time like that for more than a year until we decided to do such a trial run. First, we run it for a few months, carefully tracking time spent on branching made the "established" way. Then, we spent few months running and tracking "alternative" approach.

After completion of our comparison, we simply studied results of tracking and have chosen the way that looked less effort consuming (if memory serves, we had about 4 hours a week average per developer using one way versus 0.5 for another way). No debates, no hurt feelings, just business. People get objective numbers, compare and make informed decision, it is that simple.

This will prove difficult... I can't imagine an objective way to reconcile this.

Well in our case it wasn't really difficult. It likely looks difficult the same way as it is difficult to debate branching approaches differences "theoretically". When running the real trial, all this broad stuff magically gets split into small, concrete, manageable use cases that are much much easier to evaluate.

Things worth keeping in mind is that 1) few months mentioned above were proven sufficient to carefully evaluate efforts supposed to be related to one or other approach and 2) while trial is running, it is most important to just carefully write down stuff, leaving discussions on it to be dealt with separately. It was like,

"spent one hour integrating with half-baked component change committed by John"

goes to ticket labeled branching-strategy-1

"spent one hour investigating the bug introduced in recent branch merge from Paul"

goes to ticket labeled branching-strategy-2

At the end of the trial, this data is "extracted" from issue tracker, discussed and clarified. Results are exported to Excel, difference is calculated and preference is made based on that.

It is really important here that teammates record anything that looks like maybe related, because if not recorded, data that is maybe important is lost. As opposed to that, for the data that is recorded, it's not difficult to drop out the stuff that deemed irrelevant in a more thorough discussion at retrospective analysis.

...And yes, in our trial we dropped some records that way, ...and no, there was no heated debate there, because 1) this was all about discussing real, concrete use cases, practical and material up to point of feeling quite strategy agnostic. And because 2) the team was interested in finding the way that saves our efforts for more interesting stuff rather than in religious debates on whether to branch or not to branch.

This somewhat resembles a Postel's law (aka robustness principle),

be conservative in what you do, be liberal in what you accept from others

As for situations where Branching is a bad idea, well when preparing trial run mentioned above we studied available information (summarized in another answer at Programmers) - just to find out if maybe we can avoid spending few months on running the comparative trials.

From what we learned back then, the answer is "it depends on the project":

there's no commonly agreed "best" branching strategy applicable to any project

most resources seem to agree that choosing productive strategy depends on the particular project specifics

side note. Based on above it looks like any changes to project branching strategy need to be tested, measured and compared to other options tested...


答: It's called a Single Source of Truth. As far as counterarguments go, that article points out its main drawback, which is difficulty scaling.  However, even in large distributed systems, you want to have a single source of truth locally.</p>

Title: Holding mutable data in a single place


答:
I think you've answered your own question

```<code>we have issues with merging. I argue the root cause of these issues are a lack team
communication and a lack of knowledge on how to correctly use our source control system
to full effect (TFS).
</code>```

If your team isn't communicating as well as it could then having code in branches or in separate little projects doesn't really matter. That said in your comments you're talking about giving people the opportunity to learn more about this tool/option, and that's got to be a good thing. Branching is like any tool, it can be really useful it can also be abused.

At my current place we don't use branching, not through choice mainly because we are so small, and there's lots of other things we need to put in place first. If we did have branching we could write more patches, do more prototypes and merge back into the main code base.

I think Branching could cause a problem if ignored and allowed to get out of hand. Like anything that grows via branches, a bit of pruning won't do any harm.

Body:
I think you've answered your own question

we have issues with merging. I argue the root cause of these issues are a lack team
communication and a lack of knowledge on how to correctly use our source control system
to full effect (TFS).

If your team isn't communicating as well as it could then having code in branches or in separate little projects doesn't really matter. That said in your comments you're talking about giving people the opportunity to learn more about this tool/option, and that's got to be a good thing. Branching is like any tool, it can be really useful it can also be abused.

At my current place we don't use branching, not through choice mainly because we are so small, and there's lots of other things we need to put in place first. If we did have branching we could write more patches, do more prototypes and merge back into the main code base.

I think Branching could cause a problem if ignored and allowed to get out of hand. Like anything that grows via branches, a bit of pruning won't do any harm.


问:
Why does git allow you to "change history"?

Possible Duplicate:

  When should the VCS history of a project be deleted?

I am experienced using svn and recently started learning git. I was quite shocked to learn that git has features that allow you to "rewrite history".

Coming from svn, I had accepted as sacrosanct the source control principle that once a change is committed, there is no way to "undo" the commit itself... the most one can do is execute a later commit that effectively "reverses" the changes made in the earlier commit, but one can always reproduce the state of any commit that had been done in the past.

What is the rationale for changing this "principle"? Is there something different about git that makes this OK, or does the design of git reflect a different "philosophy" of source control that differs with the "philosophy" of svn?

答:
The most important reason is security. Suppose you accidentally check in a file that contains a cleartext password, or some other sensitive information. Even if you check in a new version with the information deleted, it's still visible in the history.

It can also be useful sometimes to make the history "cleaner". For example, when you're working in your own repository, you might check in multiple small changes as you experiment to see what works. When you finally get the change working, you might not want to push all those changes to another repository -- so you can collapse them into a single change. As you're developing in your private sandbox, you probably want a very detailed history of what changes you've made, and the ability to go back to previous versions. Once you've finally solved the problem, and the fix turns out to be, say, a self-explanatory one-line change, there's no need to push all that history to another repo (perhaps one that acts as the central repo for the project).


答:
I believe that the core of the question has to do with merging not branching. I believe what worries your supervisor is merging back (most common case as well as it derives from your question). This after git made it easy to merge (“IT DOES NOT MATTER HOW EASY IT IS TO BRANCH, ONLY HOW EASY IT IS TO MERGE” - Lunus Torvalds), has propagated to most Version Control Systems.

The  brain does not help but to regress to previous experiences. It seems that last time your colleague checked on the issue, the available solutions were not at a good level. Therefore he devised a workaround (the mini projects) and forgot to  check again, say five years later. Very common, specially when people move to middle management.


问:
Starting Up Code Review Process Where there Previously Was None?
Any tips for a group needing to start code reviews? We have no real software engineering processes currently. I have been working as software engineer for 7 years and have never seen any real processes implemented at the various places I have worked, though many books espouse all kinds of engineering methodologies. The management supports the idea of enabling new processes, though there is some resistance from the senior engineer who has over 20 years of software engineering experience.

We are a set of two programmers, with no software engineering manager. We report direct to the managing director of the Company. But we work on numerous software projects. The real reason why we have to begin performing code reviews is because of PA-DSS requirements. Therefore, I am pushing for us to do code reviews all around - not just on the payment application software.

答:
Since there are only two of you, theoretically you do not really need a formal review process.  What should be happening is that when one of you finishes a piece of code he should simply say to the other: "Here's what I did.  Please take a look."

This, of course, assumes that both of you are reasonable, sufficiently disciplined, and that you both have a sufficient grip on your own egos.  If these assumptions are false, then you do need a formal process enforced from the top.  The simplest thing to do is to make a rule that all commits or merges to the trunk must be looked at and approved by the other person, or at least one other person, in case your team grows.

This does not apply to you yet, but in my experience formal code reviews by even a team of 4 people end up taking way too much time, and 90% of the comments from individual reviewers are the same.  That's why we switched to this one-reviewer system.


问:
Algorithm to denormalize database
I have built a QlikView script generator (QVS), that can be used to generate large script files for data imports from SQL Server to QlikView.

QlikView does not like 'fully' normalised database structures (loops between several tables): for example, three tables A, B, C in SQL Server could have three PK/FK links; in QlikView it requires just two. So, I now have to 'denormalize', or remove the loops between tables...

Currently I am creating an 'exclusion table', which I traverse with an quad-imbedded for-loop, to isolate and remove constraints in the DB structure before generating the script file. This seems to work, but takes WAY too long as the number of tables can be large.

Is there another way that I can achieve what I want more economically?

答:
Standard algorithm for denormalization:

Let's take that rows of A,B,C tables are linked in mn:n:1 proportion.

Make three inserted cycles  by each C by each appropriate B by each appropriate A.

For each row in the inner cycle make a new row of the result table.

Title: Algorithm to denormalize database


问:
How to preserve order of incoming requests on a multithreaded server
I want to write a multithreaded server application which is able to process requests in a multithreaded fashion while keeping up execution order of incoming requests of the same client.

For example if client A sends a message M1 and then a message M2 the muiltithreaded server must process these requests in exactly the same order, first M1 and then M2. However, there is no guarantee that threads that process these incoming requests do process these messages in the same order.

For example, thread T1 consumes message M1, thread T2 consumes message M2 and completes processing the message and is able to accept further messages before T1 has finished it's job.

After a message has been processed the result will be passed to some other process for further processing (of which only one exists in the whole computation), this process will schedule sending a response to the client.

These mutliple threads do only exist for the purpose of preprocessing data for some other process. This particular problem sounds like a problem with pipeline characteristics, first M1, then M2, then M3, etc. However, I wanted to parallalize as much as possible to achieve a higher number of communication cycles between the server and the clients.

What architecture / pattern / technique is well suited for such a task?

答:
One name for this kind of requirement is "Unit of Order".

For example, in Weblogic JMS, it provide such feature that, conceptually, you can put an UOO identifier with your message when you are putting message to queue.  Weblogic JMS will guarantee that messages of same UOO being processed in chronological order.  However, messages under different UOOs can be processed in parallel.

It all depends on what platform or technology you are going to implement it, which I believe there are a lot of way to achieve similar effect.

OwnerDisplayName: xSNRG

OwnerDisplayName: Adrian Shum


答: Git follows the principle of not cementing policy into the code, that flexibility in the hands of highly technical users is more important than restricting them from making mistakes.  Rewriting history is impossible to do in git without people noticing, as the SHA-1 hash for a commit and all subsequent commits will change.  This is actually an improvement from svn, which doesn't make it easy to rewrite history, but does make it possible, and makes it difficult to detect when you do.</p>

Title: Why does git allow you to "change history"?

Body:
Possible Duplicate:

  When should the VCS history of a project be deleted?

I am experienced using svn and recently started learning git. I was quite shocked to learn that git has features that allow you to "rewrite history".

Coming from svn, I had accepted as sacrosanct the source control principle that once a change is committed, there is no way to "undo" the commit itself... the most one can do is execute a later commit that effectively "reverses" the changes made in the earlier commit, but one can always reproduce the state of any commit that had been done in the past.

What is the rationale for changing this "principle"? Is there something different about git that makes this OK, or does the design of git reflect a different "philosophy" of source control that differs with the "philosophy" of svn?


答:
CVCS and DVCS have big difference not only in first letter of abbreviations, but in core principles: for CVCS published commit is common shared history, committed but not pushed commit in DVCS - local personal history, which doesn't affect anybody except author.

In latter case mutations of history are problem only of the one person, responsible for *their own mess and chaotic way of working.

And, at last, it's just another style, style with the rights to life also. "Practice is the criterion of truth", thus: if rewriting is not thrown away, nothing prevents to use it in tool, there it can be done easy.


问:
Is initializing a char[] with a string literal bad practice?
I was reading a thread titled "strlen vs sizeof" on CodeGuru, and one of the replies states that  "it's anyways [sic] bad practice to initialie [sic] a char array with a string literal."

Is this true, or is that just his (albeit an "elite member") opinion?

Here is the original question:

```<code>#include <stdio.h>
#include<string.h>
main()
{
    char string[] = "october";
    strcpy(string, "september");

    printf("the size of %s is %d and the length is %d\n\n", string, sizeof(string), strlen(string));
    return 0;
}
</code>```

right. the size should be the length plus 1 yes?

this is the output

the size of september is 8 and the length is 9

size should be 10 surely. its like its calculating the sizeof string before it is changed by strcpy but the length after.

Is there something wrong with my syntax or what?

Here is the reply:

It's anyways bad practice to initialie a char array with a string literal. So always do one of the following:

```<code>const char string1[] = "october";
char string2[20]; strcpy(string2, "september");
</code>```

答:
Primarily because you won't have the size of the char[] in a variable / construct that you can easily use within the program.

The code sample from the link:

```<code> char string[] = "october";
 strcpy(string, "september");
</code>```

string is allocated on the stack as 7 or 8 characters long.  I can't recall if it's null-terminated this way or not - the thread you linked to stated that it is.

Copying "september" over that string is an obvious memory overrun.

Another challenge comes about if you pass string to another function so the other function can write into the array.  You need to tell the other function how long the array is so it doesn't create an overrun.  You could pass string along with the result of strlen() but the thread explains how this can blow up if string is not null-terminated.

You're better off allocating a string with a fixed size (preferably defined as a constant) and then pass the array and fixed size to the other function.  @John Bode's comment(s) are correct, and there are ways to mitigate these risks.  They also require more effort on your part to use them.

In my experience, the value I initialized the char[] to is usually too small for the other values I need to place in there.  Using a defined constant helps avoid that issue.

sizeof string will give you the size of the buffer (8 bytes); use the result of that expression instead of strlen when you're concerned about memory.

Similarly, you can make a check before the call to strcpy to see if your target buffer is large enough for the source string: if (sizeof target > strlen(src)) { strcpy (target, src); }.

Yes, if you have to pass the array to a function, you'll need to pass its physical size as well: foo (array, sizeof array / sizeof *array);. – John Bode

Body:
Primarily because you won't have the size of the char[] in a variable / construct that you can easily use within the program.

The code sample from the link:

 char string[] = "october";
 strcpy(string, "september");

string is allocated on the stack as 7 or 8 characters long.  I can't recall if it's null-terminated this way or not - the thread you linked to stated that it is.

Copying "september" over that string is an obvious memory overrun.

Another challenge comes about if you pass string to another function so the other function can write into the array.  You need to tell the other function how long the array is so it doesn't create an overrun.  You could pass string along with the result of strlen() but the thread explains how this can blow up if string is not null-terminated.

You're better off allocating a string with a fixed size (preferably defined as a constant) and then pass the array and fixed size to the other function.  @John Bode's comment(s) are correct, and there are ways to mitigate these risks.  They also require more effort on your part to use them.

In my experience, the value I initialized the char[] to is usually too small for the other values I need to place in there.  Using a defined constant helps avoid that issue.

sizeof string will give you the size of the buffer (8 bytes); use the result of that expression instead of strlen when you're concerned about memory.

Similarly, you can make a check before the call to strcpy to see if your target buffer is large enough for the source string: if (sizeof target > strlen(src)) { strcpy (target, src); }.

Yes, if you have to pass the array to a function, you'll need to pass its physical size as well: foo (array, sizeof array / sizeof *array);. – John Bode


问:
How should non-functional changes be committed?
I'm working a small-to-medium legacy codebase and when working on a ticket I will come across code that should be cleaned-up or that I need to clean-up just to be able to understand the follow of the application.

A real example is:

```<code>if( !a && b ){
     doSomething1();
     doSomething2();
     doSomething3();
     doSomething4();
     doSomething5();
}else if( a ){
     doSomething1();
     doSomething2();
     doSomething3();
     doSomething4();
     doSomething5();
}else if( !b && ( a || c )  ){
     doSomething1();
     doSomething2();
     doSomething3();
     doSomething4();
     doSomething5();
}
</code>```

Another is fixing typos and Engrish in comments and documentation across a dozen source files.

However, often this clean-up ends up not related to the main issue and I wonder how is it best to commit the clean-up. The way I see it, there are three options:

Before the fix: this works chronologically since this is the order in which they occur but if they break something they complicate the fix and it makes it harder to diff the fix with what was in production. It also introduces an additional commit which is noise.

With the fix: but that obscures the actual replacement of defective code with files where findGeoragphy was correct to findGeography.

After the fix: this requires removing and clean-up you made that helped you understand the code and then retesting the fix, committing the fix, and then going back and redoing the clean-up. This allows the cleanest diff to the defective code, but duplicates effort and can lead to spurious commits as well.

tl;dr: So, what is the best method of committing clean-up code?

Context: We have no unit-tests and development proceeds by running changes and eye-balling them and throwing them over the wall to QA to validate through manual regression fixes. Also, if we don't do some form clean-ups the code becomes unintelligible. I know this is far from ideal, but this is real enterprise dev that puts food on my table and not my choice.

答:
I prefer the extra commit before the fix.  This clearly separates the two tasks you are doing, and allows other people to see what was cleanup versus what was a bug fix.  Also, cleanup (for me at least) is usually a lot faster, so if I commit a cleanup fix, I don't have to worry as much about someone making a difficult-to-merge change while I'm working on the longer task.

I have used the "commit with the fix" approach at places with policies that require a change request ID with every commit, and don't allow developers to create new change requests just for cleanup code.  Yes, such policies are unproductive, but workplaces like that do exist.


答:
I follow a process similar to Karl's answer.  I prefer a separate commit of the cleanup / refactoring prior to the feature changes for a few reasons:

Separating the two commits will explain your process and thinking better to others who look at the logs.

It provides a specific set of changes useful during a code review.

It means if you want to roll back your feature changes you still keep the cleanup / refactor.

The cleanup changes can be tested separately and prior to feature updates.

Title: How should non-functional changes be committed?

Body:
I'm working a small-to-medium legacy codebase and when working on a ticket I will come across code that should be cleaned-up or that I need to clean-up just to be able to understand the follow of the application.

A real example is:

```<code>if( !a && b ){
     doSomething1();
     doSomething2();
     doSomething3();
     doSomething4();
     doSomething5();
}else if( a ){
     doSomething1();
     doSomething2();
     doSomething3();
     doSomething4();
     doSomething5();
}else if( !b && ( a || c )  ){
     doSomething1();
     doSomething2();
     doSomething3();
     doSomething4();
     doSomething5();
}
</code>```

Another is fixing typos and Engrish in comments and documentation across a dozen source files.

However, often this clean-up ends up not related to the main issue and I wonder how is it best to commit the clean-up. The way I see it, there are three options:

Before the fix: this works chronologically since this is the order in which they occur but if they break something they complicate the fix and it makes it harder to diff the fix with what was in production. It also introduces an additional commit which is noise.

With the fix: but that obscures the actual replacement of defective code with files where findGeoragphy was correct to findGeography.

After the fix: this requires removing and clean-up you made that helped you understand the code and then retesting the fix, committing the fix, and then going back and redoing the clean-up. This allows the cleanest diff to the defective code, but duplicates effort and can lead to spurious commits as well.

tl;dr: So, what is the best method of committing clean-up code?

Context: We have no unit-tests and development proceeds by running changes and eye-balling them and throwing them over the wall to QA to validate through manual regression fixes. Also, if we don't do some form clean-ups the code becomes unintelligible. I know this is far from ideal, but this is real enterprise dev that puts food on my table and not my choice.


问:
Unforeseen Spike in a Sprint... what to do?
I did a look around and couldn't find a question that addresses my case, so I figured I would post.

I have a situation where as a new team, we ran into 2 unforseen spikes (is there a better term?) during a sprint.  We 'thought' we knew, but then we had to research mid way, so this introduced a spike.

My questions are:

If we have an outage/process issue (Jenkins craps out, requires 8 hours of debugging / setup by a dev or more), is this a spike or somethine else? Do I create a spike, throw it into Sprint (mid sprint), do I then subtract hours from overall sprint (8hr spike = minus 8hrs of planned tasks?) or just end up with undelivered items for next sprint?

If I had an estimate of 8 hours for something, then the devs find, in fact they need to research more, do I have a spike there too? remove task times? etc;

I want to make sure I have a better hand at planning out these 'unforeseen' events, and have a good idea of deliverables for the sprint.

I'm looking at this from a purely Project Management perspective where I need to report up the chain on progress / burndown of tasks / deliverables.

答:
If Jenkins craps out, that's a distraction rather than a spike. A spike is the R in R&D. A spike is "we know we're going to need to do X, but don't know how big X is or what X means, so let's figure it out this sprint, so we can plan for it next sprint".

If a task takes more hours because it takes more research then you planned, then it takes more hours -- that's all that means. Your burndown will reflect that and you can learn from it.

Remember that a burndown and all those points and hours and tasks etc. aren't a contract. You don't win anything by hitting your numbers or lose anything by missing; they are a tool to help estimate. If you're way off, study why, and try to figure out how to do better next time.


答:
If the fix might have to be patched into an existing release, you should check in the fix first, and then the clean-up after that, or you are (at least some of the time) making the person who needs to apply the fix work harder than they need to (either to understand what changed, or to patch the cosmetic changes before patching the real fix (I'll note that I have made more than a few alledgedly cosmetic changes which ended up breaking something, so patching more than the minimum change to fix a defect can increase the risk of releasing something bad).

Yes, this is extra work. Yes, it's a pain. But yes, it's the right way to do things. My normal workflow is to do everything in one sandbox (clean-up and defect fixing), then create a new sandbox, apply only the minimal defect fix change from it, check this change out in the original sandbox, and check in the clean-up code. It's not that much extra work, in my experience.


问:
Word for the superset of files and folders
I'm trying to come up with a name for a class that can represent both files and folders. Anyone know a word for this?</p>

答:
It depends on the operating system and the file system. On Unix, a directory is just a special file, so the correct term would be file.

NTFS has a similar unifying concept, albeit much more complex than on Unix, called attribute.


答:
Easiest way to start code review:  just start doing it with one of open-source review tool. http://ostatic.com/blog/open-source-code-review-tools
You may start from simple process: every day one developer review code of second developer and vice versa. If review will help you improve your code, than you may think about "real tech process"</p>

Title: Starting Up Code Review Process Where there Previously Was None?

Body:
Any tips for a group needing to start code reviews? We have no real software engineering processes currently. I have been working as software engineer for 7 years and have never seen any real processes implemented at the various places I have worked, though many books espouse all kinds of engineering methodologies. The management supports the idea of enabling new processes, though there is some resistance from the senior engineer who has over 20 years of software engineering experience.

We are a set of two programmers, with no software engineering manager. We report direct to the managing director of the Company. But we work on numerous software projects. The real reason why we have to begin performing code reviews is because of PA-DSS requirements. Therefore, I am pushing for us to do code reviews all around - not just on the payment application software.


答: As everything (except the root folder or root of a drive) is ultimately contained within a folder, you could just go for FolderElement, although FilesystemObject (as suggested by @FrustratedWithFormsDesigner in a comment) also sounds good.

Title: Word for the superset of files and folders

Body: I'm trying to come up with a name for a class that can represent both files and folders. Anyone know a word for this?</p>


问:
Has research been done on the effectiveness of Planning Poker as an estimation technique?
Although it is a commonly held opinion that planning poker improves the accuracy of project estimations (a small sample of which demonstrated on this question), has any defined research been done on the subject?

More specifically, I am looking for non-circumstantial information showing that planning poker would be an improvement over traditional estimation techniques.

答:
Google Scholar turns up some papers

You might find the following papers useful, but they are behind a paywall and may be a little dated now:

Combining Estimates with Planning Poker -- An Empirical Study 2007

An empirical study of using planning poker for user story estimation 2006

You might also want to consider A Case Study on Agile Estimating and Planning using Scrum 2011 (free PDF) starting around page 123.


答:
It's anyways bad practice to initialie a char array with a string literal.

The author of that comment never really justifies it, and I find the statement puzzling.

In C (and you've tagged this as C), that's pretty much the only way to initialize an array of char with a string value (initialization is different from assignment).  You can write either

```<code>char string[] = "october";
</code>```

or

```<code>char string[8] = "october";
</code>```

or

```<code>char string[MAX_MONTH_LENGTH] = "october";
</code>```

In the first case, the size of the array is taken from the size of the initializer.  String literals are stored as arrays of char with a terminating 0 byte, so the size of the array is 8 ('o', 'c', 't', 'o', 'b', 'e', 'r', 0).  In the second two cases, the size of the array is specified as part of the declaration (8 and MAX_MONTH_LENGTH, whatever that happens to be).

What you cannot do is write something like

```<code>char string[];
string = "october";
</code>```

or

```<code>char string[8];
string = "october";
</code>```

etc.  In the first case, the declaration of string is incomplete because no array size has been specified and there's no initializer to take the size from.  In both cases, the = won't work because a) an array expression such as string may not be the target of an assignment and b) the = operator isn't defined to copy the contents of one array to another anyway.

By that same token, you can't write

```<code>char string[] = foo;
</code>```

where foo is another array of char.  This form of initialization will only work with string literals.

EDIT

I should amend this to say that you can also initialize arrays to hold a string with an array-style initializer, like

```<code>char string[] = {'o', 'c', 't', 'o', 'b', 'e', 'r', 0};
</code>```

or

```<code>char string[] = {111, 99, 116, 111, 98, 101, 114, 0}; // assumes ASCII
</code>```

but it's easier on the eyes to use string literals.

EDIT2

In order to assign the contents of an array outside of a declaration, you would need to use either strcpy/strncpy (for 0-terminated strings) or memcpy (for any other type of array):

```<code>if (sizeof string > strlen("october"))
  strcpy(string, "october");
</code>```

or

```<code>strncpy(string, "october", sizeof string); // only copies as many characters as will
                                           // fit in the target buffer; 0 terminator
                                           // may not be copied, but the buffer is
                                           // uselessly completely zeroed if the
                                           // string is shorter!
</code>```

Title: Is initializing a char[] with a string literal bad practice?

Body:
I was reading a thread titled "strlen vs sizeof" on CodeGuru, and one of the replies states that  "it's anyways [sic] bad practice to initialie [sic] a char array with a string literal."

Is this true, or is that just his (albeit an "elite member") opinion?

Here is the original question:

```<code>#include <stdio.h>
#include<string.h>
main()
{
    char string[] = "october";
    strcpy(string, "september");

    printf("the size of %s is %d and the length is %d\n\n", string, sizeof(string), strlen(string));
    return 0;
}
</code>```

right. the size should be the length plus 1 yes?

this is the output

the size of september is 8 and the length is 9

size should be 10 surely. its like its calculating the sizeof string before it is changed by strcpy but the length after.

Is there something wrong with my syntax or what?

Here is the reply:

It's anyways bad practice to initialie a char array with a string literal. So always do one of the following:

```<code>const char string1[] = "october";
char string2[20]; strcpy(string2, "september");
</code>```

Body:
It's anyways bad practice to initialie a char array with a string literal.

The author of that comment never really justifies it, and I find the statement puzzling.

In C (and you've tagged this as C), that's pretty much the only way to initialize an array of char with a string value (initialization is different from assignment).  You can write either

char string[] = "october";

or

char string[8] = "october";

or

char string[MAX_MONTH_LENGTH] = "october";

In the first case, the size of the array is taken from the size of the initializer.  String literals are stored as arrays of char with a terminating 0 byte, so the size of the array is 8 ('o', 'c', 't', 'o', 'b', 'e', 'r', 0).  In the second two cases, the size of the array is specified as part of the declaration (8 and MAX_MONTH_LENGTH, whatever that happens to be).

What you cannot do is write something like

char string[];
string = "october";

or

char string[8];
string = "october";

etc.  In the first case, the declaration of string is incomplete because no array size has been specified and there's no initializer to take the size from.  In both cases, the = won't work because a) an array expression such as string may not be the target of an assignment and b) the = operator isn't defined to copy the contents of one array to another anyway.

By that same token, you can't write

char string[] = foo;

where foo is another array of char.  This form of initialization will only work with string literals.

EDIT

I should amend this to say that you can also initialize arrays to hold a string with an array-style initializer, like

char string[] = {'o', 'c', 't', 'o', 'b', 'e', 'r', 0};

or

char string[] = {111, 99, 116, 111, 98, 101, 114, 0}; // assumes ASCII

but it's easier on the eyes to use string literals.

EDIT2

In order to assign the contents of an array outside of a declaration, you would need to use either strcpy/strncpy (for 0-terminated strings) or memcpy (for any other type of array):

if (sizeof string > strlen("october"))
  strcpy(string, "october");

or

strncpy(string, "october", sizeof string); // only copies as many characters as will
                                           // fit in the target buffer; 0 terminator
                                           // may not be copied, but the buffer is
                                           // uselessly completely zeroed if the
                                           // string is shorter!


问:
Is Clojure a 3GL or a 4GL?
A bit of background (in case I'm mistaken)...

I think I understand that (it's an oversimplification):

manually entering codes into memory (or on a punchcard) is "first generation language"

using mnemonics corresponding to CPU instructions would be a 2GL (like assembly language)

C/C#/Java/Objective-C are all 3GLs

SQL is a 4GL

Where would Clojure stand in such a classification?

I'm particularly confused by this Wikipedia sentence:

The archetypical example of a declarative language is the fourth
  generation language SQL, as well as the family of functional languages
  and logic programming.

This sentence seems to imply that all functional languages are declarative.  Is that correct?

Then Clojure can be used in a functional way (and it is probably recommended to use it "as much as possible" in a FP style), so is Clojure a declarative language ?

Also, I can see that Clojure make it really easy to create 4GLs (e.g. as embedded DSLs, like core.logic reproducing logic programming in about 200 lines of code) but is Clojure itself a 4GL?

答:
Clojure is a 3GL

First, some definitions for the avoidance of doubt.

A first generation language (1GL) is a machine level programming language. No automated translation is in place so programming is through a bank of switches on the front panel.

A second generation language (2GL) is a categorization of assembly languages. This normally targets specific chipsets and allows for source code to be used.

A third generation language (3GL) is a refinement of a 2GL and are termed "High level languages". This introduces logical structure to source code and makes the language more programmer-friendly. Examples include C/C++/C#/Java etc. They usually have an interpreter or compiler.

A fourth generation language (4GL) was in favour between 1970-1990 and is commonly understood to be a programming environment. This tends to be read as a collection of applications that support the creation of 3GL source code. Often this is a visual workbench environment such as an IDE, or perhaps a table-driven system configuration environment (Oracle middleware for example). There is also the possiblility that a 4GL could be considered a domain specific language (DSL).

In light of the above definition, Clojure would appear to fit much more closely within the frame of a 3GL since it is only the rather loose domain specific language interpretation that would lift it to a 4GL.

Title: Is Clojure a 3GL or a 4GL?


问:
Is it a good idea to provide different function signatures that do the same thing?
Here is a C++ class that gets constructed with three values.

```<code>class Foo{

    //Constructor
    Foo(std::string, int, char);

private:
    std::string foo;
    char bar;
    int baz;
};
</code>```

All of the parameter types are different.

I could overload the constructor so that order doesn't matter.

```<code>class Foo{

    //Constructors
    Foo(std::string, char, int);
    Foo(std::string, int, char);
    Foo(char, int, std::string);
    Foo(char, std::string, int);
    Foo(int, std::string, char);
    Foo(int, char, std::string);

private:
    std::string foo;
    char bar;
    int baz;
};
</code>```

But is that a good idea?

I started doing it because I knew what things a class/function needed;

I didn't always remember what order it took them in.

I've been assuming that the compiler optimizes this as if I called the same constructor.

```<code>//compiler will implement this with the same code?
//maybe not.. I could call a function to get a parameter,
//and that function could change the state of the program, before calling
//a function to get another parameter and the compiler would have to
//implement both
Foo foo1("hello",1,'a');
Foo foo2('z',0,"world");
</code>```

What are your opinions on overloading a function so that the order doesn't matter?

Also, If I'm writing some utility functions,

Is it a good idea to provide different function names that do the same thing?

eg.

```<code>void Do_Foo();
void DoFoo();
void do_foo();
//etc..
</code>```

I don't often see these two but similar conventions.

Should I break or embrace the habit?

答:
I could overload the constructor so that order [of the parameters] doesn't matter... But is that a good idea?

No.

Having different constructor overloads will have the opposite effect of what you are intending.  The programmer coming after you expects different overloads to have different behavior, and will ask: "What sort of different behavior is being expressed by each of these overloads?

Most programmers expect the discipline of having method parameters in a predefined order, and tools like IntelliSense will tell them the expected order of the parameters as they enter them.

Having multiple function names that do the same thing is the same problem; programmers expect the variants to have different behavior.  One function or method per behavior, please, and just adopt a consistent naming pattern.

ContentLicense: CC BY-SA 4.0


答:
Consider FileNode or FileSystemNode.

I've used FileNode in previous projects, the other devs were able to guess what it did from the name.  The -Node part lets others know you're working with a tree.


答:
Why don't you just call you class "FilesAndFolders" or do you have a character-limit for naming?
Well I guess you could call all of them entities, so: "FileSystemEntity"</p>


问:
Loop Invariants in Python
I have a bit of experience with loop invariants but I'm not really clear on them. I'm trying to learn them through an example in Python. Can someone point one out or help me understand? </p>

<p>I've searched both on programmers.SX and on the web but the only things I could find were invariants and design by contract -- nothing on loop invariants. </p>

答:
A loop invariant is simply something that is true on every iteration of the loop. For example, take a really trivial while loop:

```<code>while x <= 5:
  x = x + 1
</code>```

Here the loop invariant would be that x ≤ 6. Obviously, in real life, loop invariants are going to be more complicated--finding the loop invariant in general is something of an art and cannot easily be done algorithmically (as far as I know).

So, why is this useful? Well, at a coarse level, it's good for debugging: if you identify an important invariant, it's easy to check that it holds even when you modify some code. You could just add an assert statement of some sort:

```<code>while x <= 5:
  x = x + 1
  assert x <= 6
</code>```

More specifically, these invariants help us reason about how loops behave. This is where axiomatic semantics and Hoare logic come in. (This part of the answer is a little bit more advanced and esoteric, so don't worry about it too much.) Just in case you're rusty on notation: ⇒ means "implies", ∧ means "and" and ¬ means "not".

The basic idea is that we want a systematic way to prove properties of our code. The way we approach this is by looking at preconditions and postconditions in the code. That is, we want to prove that if some condition A holds before we run our code, some condition B holds after we run it. We generally write this as:

```<code>{A} code {B}
</code>```

In general, this is pretty simple. You can intuitively figure out how to prove something like {x = 0} x = x + 1 {x = 1}. You can do this by substituting x + 1 for x in the postcondition, giving you a logic formula of x = 0 ⇒ x + 1 = 1 which is obviously true. This is how you deal with assignment in general: you just substitute the new value for the variable in the postcondition.

Other constructs like multiple statements in a row and if statements are pretty intuitive as well.

However, how do you do this for loops? That's a difficult question because you do not know (in general) how many times a given loop will iterate. This is where loop invariants come in. We are looking at a loop like:

```<code>while cond: code
</code>```

There are two possibilities here. If cond is False, then it's trivial: the loop doesn't do anything, so we just get A ⇒ B. But what if the loop actually gets run? This is where we need the invariant.

The idea behind the invariant is that it always holds inside the loop. When you are inside the while loop, cond is always true. So we get an assertion like this:

```<code>{A ∧ cond} code {A}
</code>```

This just writes out what we needed formally: given that A (the loop invariant) and cond hold at the beginning of the loop body, A has to hold at the end. If we can prove this for the loop body, we know that A will hold no matter how many times the loop executes. So, given the above statement is true, we can infer:

```<code>{A} while cond: code {A}
</code>```

as an added bonus, since the while loop just finished, we know that cond has to be false. So we can actually write out the full result as:

```<code>{A} while cond: code {A ∧ ¬cond}
</code>```

So lets use these rules to prove something about my example above. What we want to prove is:

```<code>{x ≤ 0} while x <= 5: x = x + 1 {x = 6}
</code>```

That is, we want to show that if we start with a small x, at the end of the loop x will always be 6. This is pretty trivial, but it makes a good illustrative example. So the first step is to find a loop invariant. In this case, the invariant is going to be x ≤ 6. We now need to show that this is actually a loop invariant:

```<code>{x ≤ 5 ∧ x ≤ 6} x = x + 1 {x ≤ 6}
</code>```

That is, if x is less than or equal to 5, x is less than or equal to 6 after running x = x + 1. We can do this using the substitution rule outlined above, but it's pretty obvious anyhow.

So, knowing this, we can infer the rule for the whole loop:

```<code>{x ≤ 6} while x <= 5: x = x + 1 {x ≤ 6 ∧ ¬(x ≤ 5)}
</code>```

So this tells us that, at the end of the loop, x is both greater than 5 and less than or equal to 6. This simplifies to x = 6. Since x ≤ 6 whenever x ≤ 0, we've proved our initial statement.

Now, this might seem to be a lot of ostentation for proving something very obvious. After all, any programmer could have told you the value of x at the end of this loop! However, the important idea is that this method scales to more complicated loops which may not be immediately obvious. But if you can come up with an invariant for such a loop, you can use it to prove more interesting properties.

Anyhow, I hope that wasn't too confusing and gave you a good idea of why loop invariants are important at a more fundamental level.

Title: Loop Invariants in Python

Body:
A loop invariant is simply something that is true on every iteration of the loop. For example, take a really trivial while loop:

while x <= 5:
  x = x + 1

Here the loop invariant would be that x ≤ 6. Obviously, in real life, loop invariants are going to be more complicated--finding the loop invariant in general is something of an art and cannot easily be done algorithmically (as far as I know).

So, why is this useful? Well, at a coarse level, it's good for debugging: if you identify an important invariant, it's easy to check that it holds even when you modify some code. You could just add an assert statement of some sort:

while x <= 5:
  x = x + 1
  assert x <= 6

More specifically, these invariants help us reason about how loops behave. This is where axiomatic semantics and Hoare logic come in. (This part of the answer is a little bit more advanced and esoteric, so don't worry about it too much.) Just in case you're rusty on notation: ⇒ means "implies", ∧ means "and" and ¬ means "not".

The basic idea is that we want a systematic way to prove properties of our code. The way we approach this is by looking at preconditions and postconditions in the code. That is, we want to prove that if some condition A holds before we run our code, some condition B holds after we run it. We generally write this as:

{A} code {B}

In general, this is pretty simple. You can intuitively figure out how to prove something like {x = 0} x = x + 1 {x = 1}. You can do this by substituting x + 1 for x in the postcondition, giving you a logic formula of x = 0 ⇒ x + 1 = 1 which is obviously true. This is how you deal with assignment in general: you just substitute the new value for the variable in the postcondition.

Other constructs like multiple statements in a row and if statements are pretty intuitive as well.

However, how do you do this for loops? That's a difficult question because you do not know (in general) how many times a given loop will iterate. This is where loop invariants come in. We are looking at a loop like:

while cond: code

There are two possibilities here. If cond is False, then it's trivial: the loop doesn't do anything, so we just get A ⇒ B. But what if the loop actually gets run? This is where we need the invariant.

The idea behind the invariant is that it always holds inside the loop. When you are inside the while loop, cond is always true. So we get an assertion like this:

{A ∧ cond} code {A}

This just writes out what we needed formally: given that A (the loop invariant) and cond hold at the beginning of the loop body, A has to hold at the end. If we can prove this for the loop body, we know that A will hold no matter how many times the loop executes. So, given the above statement is true, we can infer:

{A} while cond: code {A}

as an added bonus, since the while loop just finished, we know that cond has to be false. So we can actually write out the full result as:

{A} while cond: code {A ∧ ¬cond}

So lets use these rules to prove something about my example above. What we want to prove is:

{x ≤ 0} while x <= 5: x = x + 1 {x = 6}

That is, we want to show that if we start with a small x, at the end of the loop x will always be 6. This is pretty trivial, but it makes a good illustrative example. So the first step is to find a loop invariant. In this case, the invariant is going to be x ≤ 6. We now need to show that this is actually a loop invariant:

{x ≤ 5 ∧ x ≤ 6} x = x + 1 {x ≤ 6}

That is, if x is less than or equal to 5, x is less than or equal to 6 after running x = x + 1. We can do this using the substitution rule outlined above, but it's pretty obvious anyhow.

So, knowing this, we can infer the rule for the whole loop:

{x ≤ 6} while x <= 5: x = x + 1 {x ≤ 6 ∧ ¬(x ≤ 5)}

So this tells us that, at the end of the loop, x is both greater than 5 and less than or equal to 6. This simplifies to x = 6. Since x ≤ 6 whenever x ≤ 0, we've proved our initial statement.

Now, this might seem to be a lot of ostentation for proving something very obvious. After all, any programmer could have told you the value of x at the end of this loop! However, the important idea is that this method scales to more complicated loops which may not be immediately obvious. But if you can come up with an invariant for such a loop, you can use it to prove more interesting properties.

Anyhow, I hope that wasn't too confusing and gave you a good idea of why loop invariants are important at a more fundamental level.