答:
Static methods are bad – not because they are “pre-OOP”, but precisely because they themselves are dependencies that cannot be inverted. I was recently trying to test a codebase that involved a call such as

```<code>void foo() {
    ...
    Time now = Clock::getCurrentSystemTime();
    ...
}
</code>```

It makes sense that this is static since (a) this code is performance-sensitive, and (b) there can only be one current time. Unfortunately this meant I could not inject a Clock of my own for these tests so that I could test the behaviour of the system around certain times. In other words, that codebase violated the Dependency Inversion Principle.

Dependency inversion is simple: I just have to make the dependency explicit, and pass it as a parameter to the current code unit (e.g. object constructor, or method parameter):

```<code>type CurrentTimeProvider = () => Time;

void foo(CurrentTimeProvider currentTime) {
    ...
    Time now = currentTime();
    ...
}

// in production:
foo(Clock::getCurrentSystemTime);

// in testing:
foo(() => Time("2000-01-01T00:00:00.000Z"));
</code>```

There are no static methods involved here in any meaningful way. In more complicated cases, we would perhaps introduce a fully fledged Dependency Injection Container that takes care of resolving all dependencies. The DI container is itself an abstract factory object. Ideally, it would be passed around explicitly. Then:

```<code>type CurrentTimeProvider = () => Time;

void foo(DIContainer deps) {
    ...
    Time now = deps.get(CurrentTimeProvider)();
    ...
}

DiContainer deps;

// in production:
deps.set(CurrentTimeProvider, Clock::getCurrentSystemTime);
foo(deps);

// in testing:
deps.set(CurrentTimeProvider, () => Time("2000-01-01T00:00:00.000Z"));
foo(deps);
</code>```

Well, but people quickly get tired of any kind of manual dependency injection. So assuming that an un-invertable dependency on some dependency injection system is OK, we might make the DI container API static (or make the container a singleton, which is essentially the same thing). The above example might change to:

```<code>type CurrentTimeProvider = () => Time;

void foo() {
    ...
    Time now = DIContainer.get(CurrentTimeProvider)();
    ...
}

// in production:
DIContainer.set(CurrentTimeProvider, Clock::getCurrentSystemTime);
foo();

// in testing:
DIContainer.set(CurrentTimeProvider, () => Time("2000-01-01T00:00:00.000Z"));
foo();
</code>```

Actually, that's fairly elegant and sufficiently sane. Is this dazzlingly beautiful OOP design? Probably not, but you won't run into any kind of problem with this (unless you try to mock the dependency injection system itself). If you don't like such a global DI system (and I don't like it either), you can pick any of the other available strategies available for DI (again: explicit parameter/constructor injection, or injection of a DI container/factory object). In a language-agnostic view, the only thing in your program that can't be static is your program's entry point/main function.

Title: Dependency inversion without static methods?

Body:
It's clear that the dependency inversion principle and the use of interfaces makes software components less coupled and promotes maintainability. On the other hand, these principles make using static methods and factories necessary.
I think static methods should be out of any good object-oriented design, since they pollute the code with imperative programming practices that don't have anything to do with pure OOP.

My question is the following: is there a way to accomplish the DIP and effectively use interfaces to decouple components  without using static factory methods? Is it so hard to design maintainable software with pure and simple OOP? Are encapsulation, inheritance and polymorphism really not enough?

Body:
Static methods are bad – not because they are “pre-OOP”, but precisely because they themselves are dependencies that cannot be inverted. I was recently trying to test a codebase that involved a call such as

void foo() {
    ...
    Time now = Clock::getCurrentSystemTime();
    ...
}

It makes sense that this is static since (a) this code is performance-sensitive, and (b) there can only be one current time. Unfortunately this meant I could not inject a Clock of my own for these tests so that I could test the behaviour of the system around certain times. In other words, that codebase violated the Dependency Inversion Principle.

Dependency inversion is simple: I just have to make the dependency explicit, and pass it as a parameter to the current code unit (e.g. object constructor, or method parameter):

type CurrentTimeProvider = () => Time;

void foo(CurrentTimeProvider currentTime) {
    ...
    Time now = currentTime();
    ...
}

// in production:
foo(Clock::getCurrentSystemTime);

// in testing:
foo(() => Time("2000-01-01T00:00:00.000Z"));

There are no static methods involved here in any meaningful way. In more complicated cases, we would perhaps introduce a fully fledged Dependency Injection Container that takes care of resolving all dependencies. The DI container is itself an abstract factory object. Ideally, it would be passed around explicitly. Then:

type CurrentTimeProvider = () => Time;

void foo(DIContainer deps) {
    ...
    Time now = deps.get(CurrentTimeProvider)();
    ...
}

DiContainer deps;

// in production:
deps.set(CurrentTimeProvider, Clock::getCurrentSystemTime);
foo(deps);

// in testing:
deps.set(CurrentTimeProvider, () => Time("2000-01-01T00:00:00.000Z"));
foo(deps);

Well, but people quickly get tired of any kind of manual dependency injection. So assuming that an un-invertable dependency on some dependency injection system is OK, we might make the DI container API static (or make the container a singleton, which is essentially the same thing). The above example might change to:

type CurrentTimeProvider = () => Time;

void foo() {
    ...
    Time now = DIContainer.get(CurrentTimeProvider)();
    ...
}

// in production:
DIContainer.set(CurrentTimeProvider, Clock::getCurrentSystemTime);
foo();

// in testing:
DIContainer.set(CurrentTimeProvider, () => Time("2000-01-01T00:00:00.000Z"));
foo();

Actually, that's fairly elegant and sufficiently sane. Is this dazzlingly beautiful OOP design? Probably not, but you won't run into any kind of problem with this (unless you try to mock the dependency injection system itself). If you don't like such a global DI system (and I don't like it either), you can pick any of the other available strategies available for DI (again: explicit parameter/constructor injection, or injection of a DI container/factory object). In a language-agnostic view, the only thing in your program that can't be static is your program's entry point/main function.


问:
What is the algorithmic time complexity of this program?
I wrote a simple program in java to create and maintain Dynamic Arrays:

```<code>public class DynamicArrays {
    private Integer[] input = new Integer[1];
    private Integer length = 0;
    private Integer capacity = 1;

    /**
    * Big O Analysis of add:
    * 1+1+addBulk
    * 2+O(n)
    * So it seems add is an O(n) operation!
    * But add is only called when capacity is full and how many times can that happen?
    * Let's say there are 8 elements added.
    * so capacity will become full after 1st, 2nd, 4th additions. so its is Log(n) times?
    */
    public void add(Integer i) {
        input[length] = i;
        length++;
        if(capacity <= length)
            addBulk();
    }

    /**
    * Big O: O(n)
    */
    public void addBulk() {
        Integer[] newInput = new Integer[2*capacity];
        for(int i=0;i<input.length;i++)
            newInput[i] = input[i];
        input = newInput;
        capacity = capacity*2;
    }
}
</code>```

Now I wonder what is the time complexity of the add operation? If addBulk() is not called, it is O(1). Else it is O(n) because addBulk() copies all the elements. However addBulk is called log(n) times of the total input.

So is the complexity O(n*log(n)) ?

I also read somewhere that the amortized complexity of dynamic arrays addition is O(2*n), hence O(n). I couldn't relate to that point from the code.

Can you please clarify?

答:
It is amortised O (1) per insertion. Let's say n = 2^20. If you add 2^20 values, you call addBulk () 20 times, and it copies 1, 2, 4, 8, 16, ..., 2^18, 2^19 values. The sum is 2^20 = n. So n insertions take O (n), a single insertion is amortised constant time or O (1). </p>

<p>"Amortised" means that any single operation could take much longer than the suggested value, but that single operation does work that further operations will use, so when you do many operations, it will average out to the amortised time. </p>

ContentLicense: CC BY-SA 3.0

Body:
It is amortised O (1) per insertion. Let's say n = 2^20. If you add 2^20 values, you call addBulk () 20 times, and it copies 1, 2, 4, 8, 16, ..., 2^18, 2^19 values. The sum is 2^20 = n. So n insertions take O (n), a single insertion is amortised constant time or O (1).

"Amortised" means that any single operation could take much longer than the suggested value, but that single operation does work that further operations will use, so when you do many operations, it will average out to the amortised time.


问:
Dependency inversion without static methods?
It's clear that the dependency inversion principle and the use of interfaces makes software components less coupled and promotes maintainability. On the other hand, these principles make using static methods and factories necessary.
I think static methods should be out of any good object-oriented design, since they pollute the code with imperative programming practices that don't have anything to do with pure OOP.

My question is the following: is there a way to accomplish the DIP and effectively use interfaces to decouple components  without using static factory methods? Is it so hard to design maintainable software with pure and simple OOP? Are encapsulation, inheritance and polymorphism really not enough?

答:
If you really want to make your classes decoupled, then you will ignore all compile-time constructs that statically link the methods together and will go to the original OO definition of method calls, which is message passing.

Of course, this will make your code more difficult to manage (potentially, I've had great success with distributed systems that use a message passing architecture) or debug via  compiler errors.

IIRC, IoC requires you to pass in the 'global' configuration object to each object via its constructor rather than the object fetching this config object when needed. Various container frameworks for IoC and DI may use statics, factories and whatnot, but you don;t have to use them. Whatever you do, do not get a framework's design choices confused for the fundamental aspect of the pattern you're using.

So, given the system you're working with, you have to trade off idealism for practicality. If this means using static methods, or globals or (horror!!!) even singletons, then use them. Your job is not to make perfect code, its to make easily understandable, easily maintainable code that fulfils its role in producing a product that does something useful for people.


问:
What's the proper way to model this real-world activity that seems to need circular references in OOP?
I've been wrestling with a problem in a Java project about circular references.  I'm trying to model a real-world situation in which it seems the objects in question are interdependent and need to know about each other.

The project is a generic model of playing a board game.  The basic classes are non-specific, but are extended to deal with specifics of chess, backgammon and other games.  I coded this up as an applet 11 years ago with half a dozen different games, but the problem is that it's full of circular references.  I implemented it back then by stuffing all the intertwined classes in a single source file, but I get the idea that that's bad form in Java.  Now I want to implement a similar thing as an Android app, and I want to do things properly.

The classes are:

RuleBook: an object that can be interrogated for such things as the
initial layout of the Board, other initial game State information
like who moves first, the Moves that are available, what happens to
the game State after a proposed Move, and an evaluation of a current
or proposed board position.

Board: a simple representation of a game board, which can be
instructed to reflect a Move.

MoveList: a list of Moves.  This is dual-purpose: a choice of moves
available at a given point, or a list of moves that have been made in
the game.  It could be split into two near-identical classes, but
that's not relevant to the question I'm asking and may complicate it
further.

Move: a single move.  It includes everything about the move as a list
of atoms: pick up a piece from here, put it down there, remove a
captured piece from there.

State: the full state information of a game in progress.  Not only
the Board position, but a MoveList, and other state information such
as who is to move now.  In chess one would record whether the king
and rooks of each player have been moved.

Circular references abound, for example: the RuleBook needs to know about the game State to determine what moves are available at a given time, but the game State needs to query the RuleBook for the initial starting layout and for what side effects accompany a move once it is made (e.g. who moves next).

I tried organising the new set of classes hierarchically, with RuleBook at the top as it needs to know about everything.  But this results in having to move lots of methods into the RuleBook class (such as making a move) making it monolithic and not particularly representative of what a RuleBook should be.

So what's the proper way to organise this?  Should I turn RuleBook into BigClassThatDoesAlmostEverythingInTheGame to avoid circular references, abandoning the attempt to model the real-world game accurately?  Or should I stick with the interdependent classes and coax the compiler into compiling them somehow, retaining my real-world model?  Or is there some obvious valid structure I'm missing?

Thanks for any help you can give!

答:
In my experience, circular references generally indicate that your design isn't well-thought-out.

In your design, I don't understand why RuleBook needs to "know" about the State. It might receive a State as a parameter to some method, sure, but why should it need to know (i.e. hold as an instance variable) a reference to a State? That doesn't make sense to me. A RuleBook doesn't need to "know" about the state of any particular game in order to do its job; the rules of the game don't change depending on the current state of the game. So either you've designed it incorrectly, or you've designed it correctly but are explaining it incorrectly.


问:
Why it is not possible to overload compound assignment operator in C#?
The title is be misleading, so please read entire question :-).

By "compound assignment operator" I have in mind a construct like this op=, for example +=. Pure assignment operator (=) does not belong to my question.

By "why" I don't mean an opinion, but resource (book, article, etc) when some of the designers, or their coworkers, etc. express their reasoning (i.e. the source of the design choice).

I am puzzled by asymmetry found in C++ and C# (yes, I know C# is not C++ 2.0) -- in C++ you would overload operator += and then almost automatically write appropriate + operator relying on previously defined operator. In C# it is in reverse -- you overload + and += is synthesised for you.

If I am not mistaken the later approach kills a chance for optimization in case of actual +=, because new object has to be created. So there has to be some big advantage of such approach, but MSDN is too shy to tell about it.

And I wonder what that advantage is -- so if you spotted explanation in some C# book, tech-talk video, blog entry, I will be grateful for the reference.

The closest thing I found is a comment on Eric Lippert blog Why are overloaded operators always static in C#? by Tom Brown. If the static overloading was decided first it simply dictates which operators can be overloaded for structs. This further dictates what can be overloaded for classes.

答:
I can't find the reference for this, but my understanding was that the C# team wanted to provide a sane subset of operator overloading. At the time, operator overloading had a bad rap. People asserted that it obfuscated code, and could only be used for evil. By the time C# was being designed, Java had shown us that no operator overloading was kind of annoying.

So C# wanted to balance operator overloading so that it was more difficult to do evil, but you could make nice things too. Changing the semantics of assignment was one of those things that was deemed always evil. By allowing += and its kin to be overloaded, it would allow that sort of thing. For example, if += mutated the reference rather than making a new one, it wouldn't follow the expected semantics, leading to bugs.

ContentLicense: CC BY-SA 4.0


问:
verify a defect is a production defect or not
As a QA person, I always believe that a defect should have all the steps needed for anyone fixing it to be able to reproduce it.

however, is it crazy to think that every defect QA opens need to be checked if it already exists in production too? Reason, why I ask is we have a dev manager who constantly whines about, well if QA would have done this investigation whether if this issue exists in production or not it would save  time for dev folks. I understand that but I still think its kinda non sense to check if every bug QA finds in testing cycle exists in production too.

答:
Two separate questions here, should the productive system be checked and who should do it? Let's assume we're talking about two separate departments in the same company ...

Which department has the time to do it? In most projects I've experienced, be it waterfall or scrum, tests become the bottleneck as the release draws near. It might make sense to hand the check on the productive environment off to the dev staff for that reason alone.

On the other hand, many testers earn less than developers, so it makes economic sense to let them do the legwork if they're available in sufficient numbers.

Who has the necessary access to the productive environment? Where I work, Development often doesn't have it, just Operations (of course) and QA (because they're doubling as 2nd Level Support).

Tell your dev manager that you're happy to do the checks on stage, productive or whatever system as long as the project budget and schedule reflect this responsibility.


答:
As a developer I get this problem a lot.

Some new feature is sent to test and a bug is reported which describes behaviour which although it 'seems wrong' is present in the live enviroment.

This is a problem because we have had time assigned to develop the new feature. Not to fix a random 'bug'

Often there has to be an extended discussion about whether the behaviour is a bug at all, what priority fixing it should take etc.

The problem stems from creating additional test cases and not running them against live before adding them to the test suite.

Developers using scrum or some other aglie process usualy have thier time quite tightly managed.

If testers raise bugs ad hoc rather than against the specific requirements the developers are working too it causes delay and frustration.

Title: verify a defect is a production defect or not

Body:
As a QA person, I always believe that a defect should have all the steps needed for anyone fixing it to be able to reproduce it.

however, is it crazy to think that every defect QA opens need to be checked if it already exists in production too? Reason, why I ask is we have a dev manager who constantly whines about, well if QA would have done this investigation whether if this issue exists in production or not it would save  time for dev folks. I understand that but I still think its kinda non sense to check if every bug QA finds in testing cycle exists in production too.


问:
How to use one web page to create and edit database entries
My team and I are developing a java web application which allows our admins to create and edit "methods" which can later be viewed by other users.

We are currently discussing the best way to implement this and aim for a screenflow similar to creating / editing events in google calendar.

I.e. The admin starts on a page which shows all current "methods" and a "create new method" button. If he chooses to edit a "method" he is redirected to page "EDIT" where he can change the method's attributes (editing and then sending it via AJAX to update the attribute).
If he chooses to create a new method he should be redirected to a page looking the same, changing attributes, etc. But if he does not change anything and goes back / closes the browser the method should not be saved.

We currently have 2 ideas to do this, both with some drawbacks:

A) Create the "method" with default values and redirect the user to the edit-page. Drawback: Should the user go back or close the browser, we have created an unnecessary entry in the db, which our product owner would like to avoid. (There is a 'delete' button, but this would require another action by the admin)

B) We create separate pages for create and edit (and the corresponding handlers). Drawback: We have to create and maintain 2 (or even 4) files which do basically the same thing.

Is there any way to negate our drawbacks or another alternative how to implement this? We are using Java Web Projects, JSPs and Servlets as technology.

答:
I'm not familiar with the particular technologies that you're using, but maybe I can offer some advice.

If I understand you correctly, you have two identical User Interfaces (views) with two different behaviors. This tells me that you only need to have one view, but two controllers. When your user clicks "new", the view is shown with a "Create" controller that tells it how to behave. When the user clicks "edit", they're shown the same view with an "Edit" controller that behaves a little differently.

This saves you from coding two different UIs. You only have to maintain the logic that dictates how they behave.

I recommend reading up on the Model-View-Controller pattern for more information.


问:
Handling DomainExceptions using REST endpoint
Suppose I'm doing some DDD.
Now, I have a microservice reflecting a bounded context/a part of a bounded context.

Now, suppose there is a REST endpoint:

```<code>'/somedomainmodel/someaction'
</code>```

My API user is doing a POST request with somehow invalid data.
I'm using Java and assume that following chain is executed:

request is handled by a Spring controller or something else

controller is invoking a method on an application service

application service is doing some action on a domain model

But as I mentioned before, data provided by an user is somehow incorrect and could cause my domain object to get into invalid state. So a subclass of DomainException extends RuntimeException is thrown.

Now: how should I handle this? Suppose my endpoint is used by a frontend and I want to display a proper message to user.

Should I return a status code and a message in a response?
Where should it be detected and how? In an application service? Or maybe in a controller? And since it's not a checked exception, how should I handle it? Try/Catch for a runtime exception seems to be awful.

Maybe if we're talking about specifing implementation, should I use something like spring's @ExceptionHandler?

答:
I prefer to do something like this:

The rest end point will receive an request with data then,

Business service class is called with the data

Validate the data if invalid throw an exception with proper description, e.g.: throw new InvalidArgumentException("invalid objet Id");

On controller if above exception is thrown then return 400 Bad Request with error description e.g.: {"ok":false, "error":"invalid_argument","msg":"invalid objet Id"}

By doing this way the business class can be used anywhere and response can be handled accordingly.


答:
Recently I wrote a detailed post on these and some related questions.

Should I return a status code and a message in a response?

Yes, but message should not contain exception message unless that message was crafted specifically to be shown to end user. Since you talk about DomainException, which probably should be quite specific about explaining what happened and why, you may show this exception message to a user. However, I recommend you to separate domain-level exceptions from API-level exceptions, and make latter be 100% "user-safe", so you can show them to end user without worrying it contains something like "MySQLIntegrityConstraintViolationException".

API-level exceptions should look like this:

```<code>// Assume that all those exception classes extend some base class `ApiException`

throw new ApiNotFoundException(404, "Entity with id=" + id + " not found.");

throw new ApiDatabaseUnavailableException(502, "Database server is unavailable. Retry later.")

throw new ApiConstraintViolationException(422, // WebDAV, Unprocessable Entity
    "Entity with id=" + id + " cannot be deleted " +
    "because it is a parent of entity with id=" + childId + ". "
    "Delete all children first.");
</code>```

Where should it be detected and how?

There are several layers in application where different types of exceptions whould be handled. Basic idea is: handle standard Java exceptions (NPEs, IllegalArgument, etc.) as soon as possible, wrap them into something more specific and throw further. Then later you can handle domain-specific exception in a middle layer, and finally API-specific exceptions can all be handled in a single "catch-them-all" handler/interceptor.

See Logging Exceptions: Where to Log Exceptions? and my post for details.

And since it's not a checked exception, how should I handle it? Try/Catch for a runtime exception seems to be awful.

try/catch is just fine if you catch exceptions at the right level. The main mistake I see people make (which initially made me write about it) is catching exceptions too far up in the call stack from the place they've been thrown - basically, too "late". In such cases people try to guess what happened by examining exception type and/or pattern-matching a message. That was indeed horrible when I saw NPE was interpreted as "item not found in the database" (it actually was just random null somewhere in between).

Maybe if we're talking about specifing implementation, should I use something like spring's @ExceptionHandler?

You should use that kind of things as well, but only for API/domain-level exceptions.

Title: Handling DomainExceptions using REST endpoint

Body:
Suppose I'm doing some DDD.
Now, I have a microservice reflecting a bounded context/a part of a bounded context.

Now, suppose there is a REST endpoint:

```<code>'/somedomainmodel/someaction'
</code>```

My API user is doing a POST request with somehow invalid data.
I'm using Java and assume that following chain is executed:

request is handled by a Spring controller or something else

controller is invoking a method on an application service

application service is doing some action on a domain model

But as I mentioned before, data provided by an user is somehow incorrect and could cause my domain object to get into invalid state. So a subclass of DomainException extends RuntimeException is thrown.

Now: how should I handle this? Suppose my endpoint is used by a frontend and I want to display a proper message to user.

Should I return a status code and a message in a response?
Where should it be detected and how? In an application service? Or maybe in a controller? And since it's not a checked exception, how should I handle it? Try/Catch for a runtime exception seems to be awful.

Maybe if we're talking about specifing implementation, should I use something like spring's @ExceptionHandler?

Body:
Recently I wrote a detailed post on these and some related questions.

Should I return a status code and a message in a response?

Yes, but message should not contain exception message unless that message was crafted specifically to be shown to end user. Since you talk about DomainException, which probably should be quite specific about explaining what happened and why, you may show this exception message to a user. However, I recommend you to separate domain-level exceptions from API-level exceptions, and make latter be 100% "user-safe", so you can show them to end user without worrying it contains something like "MySQLIntegrityConstraintViolationException".

API-level exceptions should look like this:

// Assume that all those exception classes extend some base class `ApiException`

throw new ApiNotFoundException(404, "Entity with id=" + id + " not found.");

throw new ApiDatabaseUnavailableException(502, "Database server is unavailable. Retry later.")

throw new ApiConstraintViolationException(422, // WebDAV, Unprocessable Entity
    "Entity with id=" + id + " cannot be deleted " +
    "because it is a parent of entity with id=" + childId + ". "
    "Delete all children first.");

Where should it be detected and how?

There are several layers in application where different types of exceptions whould be handled. Basic idea is: handle standard Java exceptions (NPEs, IllegalArgument, etc.) as soon as possible, wrap them into something more specific and throw further. Then later you can handle domain-specific exception in a middle layer, and finally API-specific exceptions can all be handled in a single "catch-them-all" handler/interceptor.

See Logging Exceptions: Where to Log Exceptions? and my post for details.

And since it's not a checked exception, how should I handle it? Try/Catch for a runtime exception seems to be awful.

try/catch is just fine if you catch exceptions at the right level. The main mistake I see people make (which initially made me write about it) is catching exceptions too far up in the call stack from the place they've been thrown - basically, too "late". In such cases people try to guess what happened by examining exception type and/or pattern-matching a message. That was indeed horrible when I saw NPE was interpreted as "item not found in the database" (it actually was just random null somewhere in between).

Maybe if we're talking about specifing implementation, should I use something like spring's @ExceptionHandler?

You should use that kind of things as well, but only for API/domain-level exceptions.


问:
Is it good programming practice to create files with no extension?
I often store data in external files when Python coding.

Should I always save them with an extension - i.e. .txt?

Is there any reason not to (other than saving bytes) to not give the extension? I know it will only be my code reading this file (there would be no reason for someone to open it).

答:
I will answer this question for people in general out there, but I should first point out that even for you in particular, there is probably no such thing as "only my code will be reading this file". There will be times when you will need to view or edit the file, no?  So then, besides your own code, your favorite editor will also be reading that file, at the very least.

If you are only going to be using command-line tools, (and you don't care if your choices essentially sentence yourself to always be using nothing but command-line tools,) then extensionless files should be fine.  That's because command-line tools follow the verb-noun paradigm of user interface design, according to which you first choose the verb, (you type the name of the command to execute,) and then you choose the noun on which the verb will act (you type the file name as a command-line argument to the command.) So, essentially, the computer is not burdened with having to keep track of the type of each file, and instead this task is delegated to the computer's trusty servant, the human.

If you are going to be using some graphical user interface OS invented within the last, oh, 40 years or so, which in all likelihood follows the noun-verb paradigm instead, then you will most probably need filename extensions. You see, the noun-verb paradigm allows you to first select one or more files, and then perform either the default action on them, (double click usually edits,) or choose an action from a list of actions (context menu) that are known by the operating system to be applicable to files of that type. Of course, in order for this to work, the Operating System must know the type of each file. The problem is that for some unfortunate as much as unfathomable reason, certain operating systems (i.e. Windows) tend to have no formal mechanism for knowing the type of each file, so they rely on hacks like the filename extension for guessing file types. So, if you would like to take advantage of the fact that your operating system can save you from extra clicks and extra keystrokes by knowing the type of each file, then filename extensions are your friend.

Other than that, no, there is no compulsory technical reason for always giving each filename an extension. It is just a very useful thing to have.


问:
Is it worth it to use a message-queue framework in this case?
We have these things called "executions" that are run at certain times. They have a delay property that basically says "execute me after delay microseconds`. Currently we are using Cassandra as a queue, but this is definitely not scalable, and the database is not the best tool for a queue.

I could implement this as a priority queue, but since we expect to receive a large number of messages, I cannot keep this in memory. I was thinking of using Apache's ActiveMQ which supports priority, but I'm wondering if it's worth it to bring in an entire framework. My other option is to implement a priority-queue that is written to disk (using MappedByteBuffer). The second option is more work, but more directly addresses our use-case. I don't mind using ActiveMQ and it would most certainly be easier, but I'm just wondering if it is worth it to bring in an entire framework when I'm only going to be using a small part of it.

Some more context:

We have these scripts that pull in data from different sources. The script returns the data, along with an "execution" object that says "run me again after delay microseconds" (basically polling for new data). Currently this execution is written to Cassandra, and a thread periodically polls and picks these up and then calls the appropriate script.

As I read more into message queues, I'm realizing that it may not even work. ActiveMQ has a fixed list of priorities, whereas I want a priority queue that supports arbitrary priority-values.

I guess it's more or less a scheduler. Each execution is "scheduled" to be run after delay microseconds. Would it be more appropriate to use a scheduling framework here? Is there one that supports priorities?

答:
Think about what you really have to keep in memory in order to execute the jobs; it may be as simple as just a job ID, next-execution-time, and periodic-repeat-time.  In the simplest (and possibly oversimplified) case, everything can stay in the database and the execution 'engine' only has to know the next job to execute.

Profile it, consider likely and peak loads, then add work agents and dispatchers and queues (oh my!) as needed. Or something completely different ;)


问:
Apache License: Why no recursion?
So this is my question: supposedly we can use the Apache License to include externally-written modules of code, within our applications. Yet, if I'm not mistaken, the License seems to state that we are required to include a copy of the Apache License when we distribute our code.

Then, when the recipients of our application notice the Apache license, what's to prevent them from thinking that our application is also falling within the Apache License, and hence they would also have permission to modify and distribute our application?

Do we have to augment the Apache License to simply state that it only applies to a portion of our code, and provide a link to the original modules that were used/copied/implemented-from-an-outside-source?

答:
when the recipients of our application notice the Apache license, what's to prevent them from thinking that our application is also falling within the Apache License

Don't make them guess your license terms. You need to include your own license terms. And then have a paragraph about the modules you used and their respective license.

Title: Apache License: Why no recursion?


问:
What mistakes do your users make, and how can you update your application to handle them?
In fact this question is about cautions to be taken to enhance quality user experience and reduce avoidable support calls.</p>

答:
I don't feel like getting specific break/fix examples is as important as realizing this:

Users do not read your manual, or watch your tutorials. They learn your software through exploration.

If through that exploration they break something, as a programmer it is your job to either warn them of the danger or prevent it from happening in the first place. I can't remember where I saw it now, but in the back of my mind I always try to "make doing the right thing easy" for the user of my software.

If you insist on examples:

User was able to enter a lowercase name that broke the integration code / fixed by performing input validation

User was able to click the wrong button after performing an action / fixed by only showing the correct buttons.

User was able to do X accidentally / fixed by warning them they are about to do X.

See where this is going?  :)

ContentLicense: CC BY-SA 2.5


答:
Then, when the recipients of our application notice the Apache license, what's to prevent them from thinking that our application is also falling within the Apache License, and hence they would also have permission to modify and distribute our application?

Nothing is to prevent them "thinking" that.

However, "thinking" that you / they are covered by a particular license is not good enough.  It won't satisfy a law court ... and it won't satisfy the person who is providing legal advice to the user of your application.

Everyone is best served if you are crystal clear what licensing terms apply to your application.  And the fact that the Apache license requires you to do this merely means that you can't choose to be vague about it.

Furthermore, if you fail to comply with the terms of a "copyright based license", then you are violating the copyright of the software you are using, and that places you at legal risk.

Just do it.

Title: Apache License: Why no recursion?

Body:
So this is my question: supposedly we can use the Apache License to include externally-written modules of code, within our applications. Yet, if I'm not mistaken, the License seems to state that we are required to include a copy of the Apache License when we distribute our code.

Then, when the recipients of our application notice the Apache license, what's to prevent them from thinking that our application is also falling within the Apache License, and hence they would also have permission to modify and distribute our application?

Do we have to augment the Apache License to simply state that it only applies to a portion of our code, and provide a link to the original modules that were used/copied/implemented-from-an-outside-source?


答:
As I understand you need to:

run the script

get the data and schedule next script execution after delay with some priority

I would implement step 2. using some scheduling framework, like Quartz. Quartz provides ability to prioritize executions in case they are triggered at the same time:

```<code>Trigger trigger = newTrigger()
    .withIdentity(triggerKey("myTrigger", "myTriggerGroup"))
    .startAt(futureDate(delay, SECONDS))
    .withPriority(priority)
    .build();
</code>```

Full example can be found in Quartz tutorial.

This approach does not require any additional database tables. If you need persistence you can use JDBC JobStore configuration to store scheduling data in database.

Title: Is it worth it to use a message-queue framework in this case?

Body:
We have these things called "executions" that are run at certain times. They have a delay property that basically says "execute me after delay microseconds`. Currently we are using Cassandra as a queue, but this is definitely not scalable, and the database is not the best tool for a queue.

I could implement this as a priority queue, but since we expect to receive a large number of messages, I cannot keep this in memory. I was thinking of using Apache's ActiveMQ which supports priority, but I'm wondering if it's worth it to bring in an entire framework. My other option is to implement a priority-queue that is written to disk (using MappedByteBuffer). The second option is more work, but more directly addresses our use-case. I don't mind using ActiveMQ and it would most certainly be easier, but I'm just wondering if it is worth it to bring in an entire framework when I'm only going to be using a small part of it.

Some more context:

We have these scripts that pull in data from different sources. The script returns the data, along with an "execution" object that says "run me again after delay microseconds" (basically polling for new data). Currently this execution is written to Cassandra, and a thread periodically polls and picks these up and then calls the appropriate script.

As I read more into message queues, I'm realizing that it may not even work. ActiveMQ has a fixed list of priorities, whereas I want a priority queue that supports arbitrary priority-values.

I guess it's more or less a scheduler. Each execution is "scheduled" to be run after delay microseconds. Would it be more appropriate to use a scheduling framework here? Is there one that supports priorities?

Body:
As I understand you need to:

run the script

get the data and schedule next script execution after delay with some priority

I would implement step 2. using some scheduling framework, like Quartz. Quartz provides ability to prioritize executions in case they are triggered at the same time:

Trigger trigger = newTrigger()
    .withIdentity(triggerKey("myTrigger", "myTriggerGroup"))
    .startAt(futureDate(delay, SECONDS))
    .withPriority(priority)
    .build();

Full example can be found in Quartz tutorial.

This approach does not require any additional database tables. If you need persistence you can use JDBC JobStore configuration to store scheduling data in database.


问:
std::vector Non-Array Implementation?
I've seen some posts on the StackExchange family of sites talking about std::vector implementations. They all seem to indicate that std::vector is implemented strictly as an array (in practice), and that C++ 2003 dictates contiguity of elements - pretty much closing non-array loopholes.

Now I thought that I had read once of a non-array implementation of std::vector - perhaps this predated the 2003 enforcement of contiguity? (Edit: Herb Sutter makes note of this here) I believe it was something like a series of linked arrays with decreasing or increasing sizes under the hood but I can't remember the details. Does anyone know of std::vector implementations (or perhaps, more broadly, non-STL vector implementations) that use a non-array approach like this?

Edit: I'd like to clarify here that the emphasis is less on strict std::vector implementation for C++ and rather more on 1) historical STL implementations prior to C++ 2003 contiguous elements constraints or possibly even 2) "vector" implementations in other languages - that do not use the usual array-like structure. A VList implementation of a vector might be a potential example and I'm looking for others.

答:
It's legally possible to implement std::vector<T> without using arrays (or data structures that use arrays under the hood). The only stipulation is that std::vector<T>::max_size() must return a value of 0 or 1.

Example:

```<code>// A standard's conforming sketch for (std::vector) that does not use arrays
// under the hood.
template <typename T>
class vector {
public:
    typedef T * iterator;

    vector () {}

    // This is provably guaranteed to be O(1) in the number of elements in the vector.
    void push_back (T const & x) {
        if (!ptr) {
            ptr = new T(x);
        }
        else {
            throw "You've been a bad boy. You've viloated this->max_size().";
        }
    }

    void pop_back () {
        assert(ptr);
        ptr.reset(nullptr);
    }

    size_t size () const {
        return ptr ? 1 : 0;
    }

    size_t max_size () const {
        return 1;
    }

    T * data () {
        return ptr;
    }

    iterator begin () {
        return ptr;
    }

    iterator end () {
        // Technically adding 1 to a non-array pointer is undefined (or at least
        // something to that effect). This problem can be mitigated by using a
        // proper iterator class instead of a typedef'ed pointer.
        return ptr ? ptr + 1 : ptr;
    }

private:
    std::unique_ptr<T> ptr;
};
</code>```

The max_size() == 0 case is trivial. Left as an exercise for the reader.

Title: std::vector Non-Array Implementation?

Body:
It's legally possible to implement std::vector<T> without using arrays (or data structures that use arrays under the hood). The only stipulation is that std::vector<T>::max_size() must return a value of 0 or 1.

Example:

// A standard's conforming sketch for (std::vector) that does not use arrays
// under the hood.
template <typename T>
class vector {
public:
    typedef T * iterator;

    vector () {}

    // This is provably guaranteed to be O(1) in the number of elements in the vector.
    void push_back (T const & x) {
        if (!ptr) {
            ptr = new T(x);
        }
        else {
            throw "You've been a bad boy. You've viloated this->max_size().";
        }
    }

    void pop_back () {
        assert(ptr);
        ptr.reset(nullptr);
    }

    size_t size () const {
        return ptr ? 1 : 0;
    }

    size_t max_size () const {
        return 1;
    }

    T * data () {
        return ptr;
    }

    iterator begin () {
        return ptr;
    }

    iterator end () {
        // Technically adding 1 to a non-array pointer is undefined (or at least
        // something to that effect). This problem can be mitigated by using a
        // proper iterator class instead of a typedef'ed pointer.
        return ptr ? ptr + 1 : ptr;
    }

private:
    std::unique_ptr<T> ptr;
};

The max_size() == 0 case is trivial. Left as an exercise for the reader.


问:
Is Non-Deterministic Resource-Management a Leaky Abstraction?
From what I can see, there are two pervasive forms of resource-management: deterministic destruction and explicit. Examples of the former would be C++ destructors and smart pointers or Perl's DESTROY sub, whilst an example of the latter would be Ruby's blocks-to-manage-resources paradigm or .NET's IDispose interface.

Newer languages seem to opt for the latter, perhaps as a side-effect of using garbage collection systems of the non-reference-counting variety.

My question is this: given that destructors for smart pointers or reference-counting garbage collection systems -- almost being the same thing -- allow implicit and transparent resource destruction, is it a less leaky abstraction than the non-deterministic types which rely on explicit notation?

I'll give a concrete example. If you have three C++ subclasses of a single superclass, one may have an implementation that doesn't need any specific destruction. Perhaps its does its magic in another way. The fact that it doesn't need any special destruction is irrelevant -- all of the subclasses are still used in the same way.

Another example uses Ruby blocks. Two subclasses need to free resources, so the superclass opts for an interface that uses a block in the constructor, even though other specific subclasses might not need it since they require no special destruction.

Is it the case that the latter leaks implementation details of the resource destruction, whilst the former does not?

EDIT: Comparing, let's say, Ruby to Perl might be more fair since one has deterministic destruction and the other hasn't, yet they're both garbage-collected.

答:
My question is this: given that destructors for smart pointers or reference-counting garbage collection systems -- almost being the same thing -- allow implicit and transparent resource destruction, is it a less leaky abstraction than the non-deterministic types which rely on explicit notation?

Having to watch for cycles by hand is neither implicit nor transparent. The only exception is a reference counting system with a language that prohibits cycles by design. Erlang might be an example of such a system.

So both approaches leak. The main difference is that destructors leak everywhere in C++ but IDispose is very rare on .NET.


问:
Share service instances amongst all controllers?
We've taken over coding on a .NET MVC project, and as I'm relatively inexperienced with many of the MVC design approaches, I'm working on getting a good understanding of the design choices.

One aspect that's caught my attention is that each controller class is initialised using existing instances of services. In my non-MVC past, I usually kick off a service just when I need it, or at most have a service instance for that controller instance.

To show exactly what I mean:

```<code>namespace Project.Controllers
{
    public class AccountController : BaseController
    {
        private readonly IAccountService _iAccountService;
        private readonly ISettingsService _iSettingService;
        private readonly IGenericContentService _genericContentService;
        private readonly IMemberService _memberService;

        public AccountController(IAccountService iAccountService, ISettingsService iSettingService, IGenericContentService genericContentService, IMemberService memberService)
        {
            _iAccountService = iAccountService;
            _iSettingService = iSettingService;
            _genericContentService = genericContentService;
            _memberService = memberService;
        }
    }
}
</code>```

I think the below code is what's causing it to init the controllers with the required services:

```<code>namespace Project.Framework.Bootstrappers
{
    public class MyApplicationRegistry : Registry
    {
        public MyApplicationRegistry()
        {
            Scan(assemblyScanner =>
             {
                 assemblyScanner.TheCallingAssembly();
                 assemblyScanner.WithDefaultConventions();
             });

            For<HttpContextBase>().Use(() => new HttpContextWrapper(HttpContext.Current));
            For<MembershipProvider>().Use(Membership.Provider);
        }
    }
}
</code>```

My guess is that this improves performance, as you don't need a fresh instance of a service class each time you need it, or even for each controller.

But this design does make the code a bit more unwieldy. Changing a service method requires you to keep both the interface and the class synced, which just makes for a bit more "overhead" for each code change.

There's two other options I see:

Create an instance for each service for each controller. I can see how this could become a problem for a heavily used application, but until then I don't see how it's an issue.

Make the service methods all static so you don't need to create an instance of the class. To me it seems they pretty much are that already. So in my mind, this seems like a nice alternative. But I do suspect a general distaste for static methods these days for reasons I'm still learning.

So how do these options compare? Am I missing something, and why does the above code pattern seem to be fairly popular for .NET MVC?

Looks like this is Dependency Injection

I did a bunch of more reading, and I see that this design is for dependency injection, and uses the StructureMap library. The merits of efficient, decoupled code are quite compelling, so it's seeming like the code I've shown is better than my two options, primarily from a design standpoint but also a performance standpoint.

答:
It looks like Dependency injection has been implemented in the MVC project.

This is considered best practice these days and def superior to your two options!

You would expect the services to be instanciated per request rather than singletons which would persist over all requests. (although these are sometimes used)

However its not really clear that your interpretation of the code is correct. I think its likely that the DI is following best practice and you should read up some more before you think about changing it!


问:
Name of data structure that's tree-like with multiple root nodes
I'm attempting to implement a data structure, and using a more traditional tree data structure, but I'm not using the root node as it holds no real value in the context I'm using it in.

Ideally, I want to use a structure that is a tree, but that has multiple root nodes (and that is not just a list of trees). Is there a name for a data structure like this?

答: You don't have one tree with multiple roots, you have a grab bag of separate trees, each with a unique root. In graph theory, a bunch of disconnected trees are called forest. But if the trees don't really belong together, it might be more useful to think of it just as a collection (list, map, etc.) of trees.


问:
Are hex dump and binary-to-text encoding related or different things?
Binary-to-text encoding is to represent binary data as characters.

Hex dump of binary files seem also do the same for reading binary files.

Are they related or different things?

答:
A binary-to-text encoding is something designed for efficient data transfer through a "text only" medium rather than for human readability. A hex dump is something designed for human readability and not efficiency.

If you convert binary into hex digits, you're looking at a maximum of 4 bits of binary data per character. This means the size of the text will be at least twice as large as the original binary data.

This assumes there's no spaces or anything between the hex numbers. For a hexdump there are spaces between them that reduces efficiency further. For example, you might have a space between each pair of digits, an address or offset on the left, a new line character on the right, etc.

For better "binary to text" you'd use a larger base to reduce the number of characters. For example, if you can use 64 characters you might convert the binary into base64 (and not base16), and in that case you get 6 bits of binary data into each character, and the size of text will be 1.3333 times as large as the binary data (instead of 2 times as large or worse).

The best case (assuming characters are fixed size) is to use as many of the characters as you can; which depends on where the text is going (e.g. if it's going across a "7-bit ASCII" serial port you might be able to use 128 characters, if it's going in XML you might not be able to use a bunch of control characters and be left with maybe 95 characters, if it needs to be case insensitive you might be down to about 50 characters, etc).


问:
What kind of design diagram is this?
Here is a kata for the Bowling Game problem. Slide 9 (below) shows a design diagram. But its not obvious to me which box is a class and which is a property or method from the makeup of the boxes themselves.

Is this a UML object diagram and if so, isn't there a better way to express class properties as part of the class as a whole? I realise +score(): int is a method but what about 'Frame'?

The Frame box looks the same as the Game box. In the final solution only a Game class is created and Frame is only really used as the number of times to loop within the scoring algorithm

I realise this is quite a specific case but I'm interested in how the diagram is used to model the problem. As illustrated in this question, I immediately think 'Frame' is a class name when looking at the diagram.

答: Yes, it's kind of UML. It seems to me that this diagram shows the number of potential runtime instances in addition to the releations between classes. Kind of entity relationship diagram and class diagram rolled into one picture. Works only if entities and classes have a 1:1 relationship.</p>

Title: What kind of design diagram is this?


问:
Node.js and CPU intensive web applications
Some time ago I made this question about porting a Silverlight application to web. We lack experience working with web applications and have started to look for training and resources. We have noted that there is a strong trend about Node.js at the moment, and while we are aware its popularity and support, we have some doubts about its suitability for our needs. Our application would consist on one to several web applications, linked to different operational units in the company, each one performing several different functions. Some of these function, however, would include Reporting and Data analysis, requiring sometimes (but not always) long-running operations related to number crunching and transformation of significant amounts of data.

In the past, these cpu-expensive operations were managed client-side with Silverlight, but in our future set-up, they would be done in the server, and I have found several resources in the net pointing to possible problems that an application with these requirements might face in Node.js due its architecture. Of course, there is  many other resources claiming that those problems do not exist or are easily solvable with certain module or offloading heavy tasks to another server. The last solution, however, would be difficult to implement for us due several reasons.

So now the question. Can Node.js manage applications required to perform CPU-intensive tasks as described?

The application started as a windows form application, but we were more or less forced to move to web due the higher ups decided it was the solution for several problems the application had, and they do not think that returning to a desktop application is an option. Also, we have little to no control over the production server(one server and one backup server that mirrors the first, with a load balancer) , and must trust the company that manage them to do all the installation. This mean that, to maintain our sanity and theirs, the set-up of the application should be as simple as possible.

Most of us have a background limited to .net desktop and Silverlight applications, and we have to rely on others for counsel in pure web applications. This question is only one of many we are trying to give an answer in order to have a clear understanding of what options we have available and the pros and cons of each one. As "What is the pros and cons of X" might not be an appropriate format for a question in this site, and since most of them are covered anyway all over the net, I decided to make the question about one of those points I was having more doubts.

答:
The main problem that Node.js has in your usecase is that it runs on a single thread. This means that a CPU-intensive task has a great chance of blocking the whole server until it has finished.

On the other hand, you could use a task queue running on another server (or process), as described in this answer. If you do this, your client-facing server shouldn't block.


答:
The diagram is a UML class diagram, using the notations for classes, associations (with multiplicities), and generalization. Although the notation is using perfectly valid UML, it appears to be in one of the less complete notations that Martin Fowler describes as UML as Notes or UML as Sketch. It's using the symbology of the language correctly, but omitting details to make it easier to read. Such a notation is useful to communicate between people, but wouldn't support something like forward engineering from models to code.

In the diagram that you presented, each of the boxes is a class. There is a Game class with public methods roll(int) and score(), a Frame class with public method score(), and a Roll class with a private member variable pins. There's also a TenthFrame class that inherits from Frame.

Some details about the members of classes have been omitted from the diagram. For example, there is an association relationship between Game and Frame - Game knows of 10 instances of Frame. The use of the association relationship implies that Game not only knows about the interface of Frame (a dependency on Frame), but also maintains 10 instances as part of the object. Although you could show this explicitly by adding a member variable to Game that shows an array of 10 Frame objects, this is simply duplicating what the association relationship is already showing you. There is a similar relationship between Frame and Roll - a Frame has at least 1 and no more than 2 Rolls.

Looking through the slides that you linked to, you are right that the final solution doesn't appear to use anything other than a Game class (at least that I can see looking through the code in the slide deck). When following the principles of Agile Modeling, there would be a Single Source of Information, meaning those models would have likely been thrown away after the code was written and they have outlived their usefulness.

What it looks like happened is that the authors used UML (since it's a familiar and standardized notation) to walk through the problem and explain how it was decomposed. However, as they were writing code, they decided that they didn't need all of the classes to realize the simplest implementation. However, the act of modeling improved their understanding of the problem and the rules associated with it, but may not have driven the implementation.

Title: What kind of design diagram is this?

Body:
Here is a kata for the Bowling Game problem. Slide 9 (below) shows a design diagram. But its not obvious to me which box is a class and which is a property or method from the makeup of the boxes themselves.

Is this a UML object diagram and if so, isn't there a better way to express class properties as part of the class as a whole? I realise +score(): int is a method but what about 'Frame'?

The Frame box looks the same as the Game box. In the final solution only a Game class is created and Frame is only really used as the number of times to loop within the scoring algorithm

I realise this is quite a specific case but I'm interested in how the diagram is used to model the problem. As illustrated in this question, I immediately think 'Frame' is a class name when looking at the diagram.


问:
What are some (best) practices of organizing configuration data for applications?
I am working on an application (in php) that needs some rules to evaluate the labelling of some data. Since these rules might change someday, I decided not to hardcode them, rather handle them as configuration for my application.

The above situation might be specific, so my question goes: What are the common (preferably) best practices in early development stage regarding configurations of application with respect to future maintainability?

Edit: This question, unlike some others on this site, doesn't focus on sensitive information (e.g. connection strings), but rather on a general approach to store configs.

答:
If you are coding in some scripting language like PHP, then investing any effort to avoid hard-coding is a waste of time.

It is a script!  Hard-code away!  Hard-code everything!

Scripting code is not "hard" code to begin with.

EDIT: please do not confuse "hard coding vs. configuration files" with "declaring constants vs. reusing literals". This question is about "hard coding vs. configuration files".


答:
I wouldun't put it quite like Mike Nakis did, but he has a point.

In a scripting language like PHP, I would recommend creating a class with the various configuration values hard coded either as read only properties or class constants.

It's a scripting language , there is no difference between pushing configfromdb.php, config.yaml, and config.php, and they are harder to deal with due to the extra layer of indirection.

Title: What are some (best) practices of organizing configuration data for applications?

Body:
I am working on an application (in php) that needs some rules to evaluate the labelling of some data. Since these rules might change someday, I decided not to hardcode them, rather handle them as configuration for my application.

The above situation might be specific, so my question goes: What are the common (preferably) best practices in early development stage regarding configurations of application with respect to future maintainability?

Edit: This question, unlike some others on this site, doesn't focus on sensitive information (e.g. connection strings), but rather on a general approach to store configs.


问:
How to think as a C programmer after biased with OOP language?
Previously, I've only used Object Oriented Programming languages (C++, Ruby, Python, PHP), and am now learning C. I'm finding it difficult to figure out the proper way to do things in a language with no concept of an 'Object'. I realize that it's possible to use OOP paradigms in C, but I'd like to learn the C-idiomatic way.

When solving a programming problem, the first thing I do is to imagine an object that will solve the problem. What steps do I replace this with, when using a non-OOP Imperative Programming paradigm?

答:
A C program is a collection of functions.

A function is a collection of statements.

You can encapsulate data with a struct.

That's it.

How did you write a class?  That's pretty much how you write a .C file.  Granted, you don't get things like method polymorphism and inheritance, but you can simulate those with different function names and composition anyway.

To pave the way, study Functional Programming.  It's really quite amazing what you can do without classes, and some things actually work better without the overhead of classes.

Further Reading

Object-Orientation in ANSI C


答:
The way the program is built is basically defining which actions (functions) must be performed in order to solve the problem (that is why it is called procedural language). Each action will correspond to a function. Then you need to define what kind of information each function will receive and what information they need to return.

The program is normally separated in files (modules) each file will normally have a group of functions that are related. In the beginning of each file you declare (outside any function) variables that will be used by all functions in that file. If you use the "static" qualifier those variables will be only visible inside that file (but not from other files). If you don't use "static" qualifier on variables defined outside of functions they will be accessible from other files as well and these other files should declare the variable as "extern" (but not define it) so the compiler will look for them in other files.

So in short you first think about the procedures (functions) then you make sure all function have access to the information they need.

Title: How to think as a C programmer after biased with OOP language?

Body:
Previously, I've only used Object Oriented Programming languages (C++, Ruby, Python, PHP), and am now learning C. I'm finding it difficult to figure out the proper way to do things in a language with no concept of an 'Object'. I realize that it's possible to use OOP paradigms in C, but I'd like to learn the C-idiomatic way.

When solving a programming problem, the first thing I do is to imagine an object that will solve the problem. What steps do I replace this with, when using a non-OOP Imperative Programming paradigm?


答:
I think taking a look at some of the examples of binary-to-text encoding may help clear this up. These are pulled from your Wikipedia link.

For example, let's start with the "Percent Encoding". You've likely seen this one in URLs, with all sorts of things like "%20" showing up (that represents a space). Transmitting raw binary data (and even some things like spaces) is not allowed as part of a URL, but from time to time it would be nice to have a way to tell a computer on the other end about some "out of band" binary information. In this way, "Percent Encoding" acts simply as a very inefficient tunnel for binary data - harmless because it is text, unless the other end is specifically looking for binary data. On the other hand, reading the encoding looks something like a hex dump and is not impossible to decode by hand.

Or consider Uuencoding or MIME's usage of Base64. Here the goal is not only to tunnel binary data over text, but to do it in such a way that the transfer is fairly efficient. However, it is much harder to read it and make sense of it.

Note here that in both cases, the web forms a common backdrop behind the technology usage. I don't believe that this an accident, as web technologies were very much designed for interchange, and text (for some definition of text) forms a sort of lowest common denominator.

Now compare that with a hex dump. The whole point of a hex dump is to convey binary information to you - not a computer - with ease. In both cases it is the transfer of binary information to a specific audience through the allowed means, so there is some commonality. But for binary-to-text it is usually to a computer and via ASCII, and for a hex dump it is to a person via hexadecimal. That being said, a hex dump certainly could be used as a binary-to-text method in a pinch.

Side note: I think the inclusion of S-Records (etc) in the list is interesting. I suppose they could be considered binary-to-text encodings, but strictly speaking they can convey not only a specific binary file, but rather act as a binary patch - which is a broader goal; the binary-to-text encoding is probably more accurately a part of the S-Record. If I were trying to learn about binary-to-text encodings, I feel like these might muddy the waters a bit.

Title: Are hex dump and binary-to-text encoding related or different things?

Body:
Binary-to-text encoding is to represent binary data as characters.

Hex dump of binary files seem also do the same for reading binary files.

Are they related or different things?


问:
What's the proper way to model this real-world activity that seems to need circular references in OOP?
I've been wrestling with a problem in a Java project about circular references.  I'm trying to model a real-world situation in which it seems the objects in question are interdependent and need to know about each other.

The project is a generic model of playing a board game.  The basic classes are non-specific, but are extended to deal with specifics of chess, backgammon and other games.  I coded this up as an applet 11 years ago with half a dozen different games, but the problem is that it's full of circular references.  I implemented it back then by stuffing all the intertwined classes in a single source file, but I get the idea that that's bad form in Java.  Now I want to implement a similar thing as an Android app, and I want to do things properly.

The classes are:

RuleBook: an object that can be interrogated for such things as the
initial layout of the Board, other initial game State information
like who moves first, the Moves that are available, what happens to
the game State after a proposed Move, and an evaluation of a current
or proposed board position.

Board: a simple representation of a game board, which can be
instructed to reflect a Move.

MoveList: a list of Moves.  This is dual-purpose: a choice of moves
available at a given point, or a list of moves that have been made in
the game.  It could be split into two near-identical classes, but
that's not relevant to the question I'm asking and may complicate it
further.

Move: a single move.  It includes everything about the move as a list
of atoms: pick up a piece from here, put it down there, remove a
captured piece from there.

State: the full state information of a game in progress.  Not only
the Board position, but a MoveList, and other state information such
as who is to move now.  In chess one would record whether the king
and rooks of each player have been moved.

Circular references abound, for example: the RuleBook needs to know about the game State to determine what moves are available at a given time, but the game State needs to query the RuleBook for the initial starting layout and for what side effects accompany a move once it is made (e.g. who moves next).

I tried organising the new set of classes hierarchically, with RuleBook at the top as it needs to know about everything.  But this results in having to move lots of methods into the RuleBook class (such as making a move) making it monolithic and not particularly representative of what a RuleBook should be.

So what's the proper way to organise this?  Should I turn RuleBook into BigClassThatDoesAlmostEverythingInTheGame to avoid circular references, abandoning the attempt to model the real-world game accurately?  Or should I stick with the interdependent classes and coax the compiler into compiling them somehow, retaining my real-world model?  Or is there some obvious valid structure I'm missing?

Thanks for any help you can give!

答:
I think the problem here is that you have not given a clear description of what tasks are to be handled by which classes. I will describe what I think is a good description of what each class should do, then I will give an example of generic code that illustrates the ideas. We will see that the code is less coupled, and so it doesn't really have circular references.

Let's start with describing what each class does.

The GameState class should only contain information about the current state of the game. It should not contain any information about what the past states of the game or what future moves are possible. It should only contain information about what pieces are on what squares in chess, or how many and what type of checkers are on what points in backgammon. The GameState will have to contain some extra information, like information about castling in chess or about the doubling cube in backgammon.

The Move class is a little tricky. I would say that I can specify a move to play by specifying the GameState that results from playing the move. So you could imagine that a move can just be implemented as a GameState. However, in go (for example) you could imagine that is a lot easier to specify a move by specifying a single point on the board. We want our Move class to be flexible enough to handle either of these to cases. Therefore the Move class is actually going to be an interface with a method that takes a pre-move GameState and returns a new post-move GameState.

Now the RuleBook class is responsible for knowing everything about the rules. This can be broken down into three things. It needs to know what the initial GameState is, it needs to know what moves are legal, and it needs to be able to tell if one of the players has won.

You could also make a GameHistory class to keep track of all the moves that have been made and all the GameStates that have happened. A new class is necessary because we decided that a single GameState should not be responsible for knowing all the GameStates that came before it.

This concludes the classes/interfaces I will discuss. You also have a Board class. But I think boards in different games are different enough that it is hard to see what could generically be done with boards. Now I will go on to give generic interfaces and implement generic classes.

First is GameState. Since this class is completely dependent on the particular game, there is no generic Gamestate interface or class.

Next is Move. As I said, this can be represented with a interface that has a single method that takes a pre-move state and produces a post-move state. Here is the code for this interface:

```<code>package boardgame;

/**
 *
 * @param <T> The type of GameState
 */
public interface Move<T> {

    T makeResultingState(T preMoveState) throws IllegalArgumentException;

}
</code>```

Notice that there is a type parameter. This is because, for example, a  ChessMove will need to know about the particulars of the pre-move ChessGameState. So, for example, the class declaration of ChessMove would be

class ChessMove extends Move<ChessGameState>,

where you would have already defined a ChessGameState class.

Next I will discuss the generic RuleBook class. Here is the code:

```<code>package boardgame;

import java.util.List;

/**
 *
 * @param <T> The type of GameState
 */
public interface RuleBook<T> {

    T makeInitialState();

    List<Move<T>> makeMoveList(T gameState);

    StateEvaluation evaluateState(T gameState);

    boolean isMoveLegal(Move<T> move, T currentState);

}
</code>```

Again there is a type parameter for the GameState class. Since the RuleBook is supposed to know what the initial state is, we have put a method to give the initial state. Since the RuleBook is supposed to know what moves are legal, we have methods to test if a move is legal in a given state and to give a list of legal moves for a given state. Finally, there is a method to evaluate the GameState. Notice the RuleBook should only be responsible for describing if one or the other players has already won, but not who is in a better position in middle of a game. Deciding who is in a better position is a complicated thing that should be moved into its own class. Therefore the StateEvaluation class is actually just a simple enum given as follows:

```<code>package boardgame;

/**
 *
 */
public enum StateEvaluation {

    UNFINISHED,
    PLAYER_ONE_WINS,
    PLAYER_TWO_WINS,
    DRAW,
    ILLEGAL_STATE
}
</code>```

Lastly, let's describe the GameHistory class. This class is responsible for remembering all positions that were reached in the game as well as the moves that were played. The main thing it should be able to do is record a Move as played. You can also add functionality for undoing Moves. I have an implementation below.

```<code>package boardgame;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @param <T> The type of GameState
 */
public class GameHistory<T> {

    private List<T> states;
    private List<Move<T>> moves;

    public GameHistory(T initialState) {
        states = new ArrayList<>();
        states.add(initialState);
        moves = new ArrayList<>();
    }

    void recordMove(Move<T> move) throws IllegalArgumentException {
        moves.add(move);
        states.add(move.makeResultingState(getMostRecentState()));
    }

    void resetToNthState(int n) {
        states = states.subList(0, n + 1);
        moves = moves.subList(0, n);
    }

    void undoLastMove() {
        resetToNthState(getNumberOfMoves() - 1);
    }

    T getMostRecentState() {
        return states.get(getNumberOfMoves());
    }

    T getStateAfterNthMove(int n) {
        return states.get(n + 1);
    }

    Move<T> getNthMove(int n) {
        return moves.get(n);
    }

    int getNumberOfMoves() {
        return moves.size();
    }

}
</code>```

Finally, we could imagine making a Game class to tie everything together. This Game class is supposed to expose methods that make it possible for people to see what the current GameState is, see who, if anyone has one, see what moves can be played, and play a move. I have an implementation below

```<code>package boardgame;

import java.util.List;

/**
 *
 * @author brian
 * @param <T> The type of GameState
 */
public class Game<T> {

    GameHistory<T> gameHistory;
    RuleBook<T> ruleBook;

    public Game(RuleBook<T> ruleBook) {
        this.ruleBook = ruleBook;
        final T initialState = ruleBook.makeInitialState();
        gameHistory = new GameHistory<>(initialState);
    }

    T getCurrentState() {
        return gameHistory.getMostRecentState();
    }

    List<Move<T>> getLegalMoves() {
        return ruleBook.makeMoveList(getCurrentState());
    }

    void doMove(Move<T> move) throws IllegalArgumentException {
        if (!ruleBook.isMoveLegal(move, getCurrentState())) {
            throw new IllegalArgumentException("Move is not legal in this position");
        }
        gameHistory.recordMove(move);
    }

    void undoMove() {
        gameHistory.undoLastMove();
    }

    StateEvaluation evaluateState() {
        return ruleBook.evaluateState(getCurrentState());
    }

}
</code>```

Notice in this class that the RuleBook is not responsible for knowing what the current GameState is. That is the GameHistory's job. So the Game asks the GameHistory what the current state is and gives this information to the RuleBook when the Game needs to say what the legal moves are or if anyone has won.

Anyway, the point of this answer is that once you have made a reasonable determination of what each class is responsible for, and you make each class focused on a small number of responsibilities, and you assign each responsibility to a unique class, then the classes tend to be decoupled, and everything gets easy to code. Hopefully that is apparent from the code examples I gave.

Body:
I think the problem here is that you have not given a clear description of what tasks are to be handled by which classes. I will describe what I think is a good description of what each class should do, then I will give an example of generic code that illustrates the ideas. We will see that the code is less coupled, and so it doesn't really have circular references.

Let's start with describing what each class does.

The GameState class should only contain information about the current state of the game. It should not contain any information about what the past states of the game or what future moves are possible. It should only contain information about what pieces are on what squares in chess, or how many and what type of checkers are on what points in backgammon. The GameState will have to contain some extra information, like information about castling in chess or about the doubling cube in backgammon.

The Move class is a little tricky. I would say that I can specify a move to play by specifying the GameState that results from playing the move. So you could imagine that a move can just be implemented as a GameState. However, in go (for example) you could imagine that is a lot easier to specify a move by specifying a single point on the board. We want our Move class to be flexible enough to handle either of these to cases. Therefore the Move class is actually going to be an interface with a method that takes a pre-move GameState and returns a new post-move GameState.

Now the RuleBook class is responsible for knowing everything about the rules. This can be broken down into three things. It needs to know what the initial GameState is, it needs to know what moves are legal, and it needs to be able to tell if one of the players has won.

You could also make a GameHistory class to keep track of all the moves that have been made and all the GameStates that have happened. A new class is necessary because we decided that a single GameState should not be responsible for knowing all the GameStates that came before it.

This concludes the classes/interfaces I will discuss. You also have a Board class. But I think boards in different games are different enough that it is hard to see what could generically be done with boards. Now I will go on to give generic interfaces and implement generic classes.

First is GameState. Since this class is completely dependent on the particular game, there is no generic Gamestate interface or class.

Next is Move. As I said, this can be represented with a interface that has a single method that takes a pre-move state and produces a post-move state. Here is the code for this interface:

package boardgame;

/**
 *
 * @param <T> The type of GameState
 */
public interface Move<T> {

    T makeResultingState(T preMoveState) throws IllegalArgumentException;

}

Notice that there is a type parameter. This is because, for example, a  ChessMove will need to know about the particulars of the pre-move ChessGameState. So, for example, the class declaration of ChessMove would be

class ChessMove extends Move<ChessGameState>,

where you would have already defined a ChessGameState class.

Next I will discuss the generic RuleBook class. Here is the code:

package boardgame;

import java.util.List;

/**
 *
 * @param <T> The type of GameState
 */
public interface RuleBook<T> {

    T makeInitialState();

    List<Move<T>> makeMoveList(T gameState);

    StateEvaluation evaluateState(T gameState);

    boolean isMoveLegal(Move<T> move, T currentState);

}

Again there is a type parameter for the GameState class. Since the RuleBook is supposed to know what the initial state is, we have put a method to give the initial state. Since the RuleBook is supposed to know what moves are legal, we have methods to test if a move is legal in a given state and to give a list of legal moves for a given state. Finally, there is a method to evaluate the GameState. Notice the RuleBook should only be responsible for describing if one or the other players has already won, but not who is in a better position in middle of a game. Deciding who is in a better position is a complicated thing that should be moved into its own class. Therefore the StateEvaluation class is actually just a simple enum given as follows:

package boardgame;

/**
 *
 */
public enum StateEvaluation {

    UNFINISHED,
    PLAYER_ONE_WINS,
    PLAYER_TWO_WINS,
    DRAW,
    ILLEGAL_STATE
}

Lastly, let's describe the GameHistory class. This class is responsible for remembering all positions that were reached in the game as well as the moves that were played. The main thing it should be able to do is record a Move as played. You can also add functionality for undoing Moves. I have an implementation below.

package boardgame;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @param <T> The type of GameState
 */
public class GameHistory<T> {

    private List<T> states;
    private List<Move<T>> moves;

    public GameHistory(T initialState) {
        states = new ArrayList<>();
        states.add(initialState);
        moves = new ArrayList<>();
    }

    void recordMove(Move<T> move) throws IllegalArgumentException {
        moves.add(move);
        states.add(move.makeResultingState(getMostRecentState()));
    }

    void resetToNthState(int n) {
        states = states.subList(0, n + 1);
        moves = moves.subList(0, n);
    }

    void undoLastMove() {
        resetToNthState(getNumberOfMoves() - 1);
    }

    T getMostRecentState() {
        return states.get(getNumberOfMoves());
    }

    T getStateAfterNthMove(int n) {
        return states.get(n + 1);
    }

    Move<T> getNthMove(int n) {
        return moves.get(n);
    }

    int getNumberOfMoves() {
        return moves.size();
    }

}

Finally, we could imagine making a Game class to tie everything together. This Game class is supposed to expose methods that make it possible for people to see what the current GameState is, see who, if anyone has one, see what moves can be played, and play a move. I have an implementation below

package boardgame;

import java.util.List;

/**
 *
 * @author brian
 * @param <T> The type of GameState
 */
public class Game<T> {

    GameHistory<T> gameHistory;
    RuleBook<T> ruleBook;

    public Game(RuleBook<T> ruleBook) {
        this.ruleBook = ruleBook;
        final T initialState = ruleBook.makeInitialState();
        gameHistory = new GameHistory<>(initialState);
    }

    T getCurrentState() {
        return gameHistory.getMostRecentState();
    }

    List<Move<T>> getLegalMoves() {
        return ruleBook.makeMoveList(getCurrentState());
    }

    void doMove(Move<T> move) throws IllegalArgumentException {
        if (!ruleBook.isMoveLegal(move, getCurrentState())) {
            throw new IllegalArgumentException("Move is not legal in this position");
        }
        gameHistory.recordMove(move);
    }

    void undoMove() {
        gameHistory.undoLastMove();
    }

    StateEvaluation evaluateState() {
        return ruleBook.evaluateState(getCurrentState());
    }

}

Notice in this class that the RuleBook is not responsible for knowing what the current GameState is. That is the GameHistory's job. So the Game asks the GameHistory what the current state is and gives this information to the RuleBook when the Game needs to say what the legal moves are or if anyone has won.

Anyway, the point of this answer is that once you have made a reasonable determination of what each class is responsible for, and you make each class focused on a small number of responsibilities, and you assign each responsibility to a unique class, then the classes tend to be decoupled, and everything gets easy to code. Hopefully that is apparent from the code examples I gave.


问:
Algorithm to detect if a word is spelled correctly
I am trying to develop a javascript spellchecker that doesn't use a dictionary, and can correctly, given a single word, detect if a word is spelled correctly or not. Right now, I just have a list of sub strings that never occur within words, and if the word contains one of those sub strings, I count it as misspelled. For example, I would have a substring "lll", and if a word contains "lll" it would be counted as misspelled (such as "I'lll").

However, I'm finding this doesn't work as well as expected. Most misspelled words seem to involve letters in the wrong order, or words that don't follow common rules. The above approach doesn't work for either of these issues. For example, there is no good substring for the spelling "accidant".

I'm looking for a more effective method of determining if a word is probably misspelled or not, ideally something that solves the issues of letters in incorrect order and keys near the correct letter on a keyboard accidentally being pressed (but solutions to other common causes of misspellings are fine).

This is english-only, so it doesn't need to work with other languages.
Also, false positives are a much larger problem for me than false negatives, so I would prefer to err on the side of saying words are spelled correctly when in fact they are not.

答:
Since I'm working on a similar problem myself, I can provide some guidance.

The quickest way I've found to find errors (but not necessarily correct them) is to use n-gram searches.  You can store these in an array which is the nth-power of the alphabet size.  Given an array @words that includes every single word in a corpus of texts from your language and an trigram (n-gram of three elements):

my %ngrams;
my $ngramSize = 3;
for my $word (@words) {
    next if length($word) < $ngramSize;
    $trigrams{substr($word,$_,$ngramSize)}++ for (0..length($word) -$ngramSize);
}
```

You would probably want to normalize the data in some way, and then you can store it more efficiently.  For example, you could take the median occurrence count and set that to be 255, clipping any values higher, and then proportioning out anything less).  That would let you store, for instance, a rough English spell checker using trigrams in 17K, or even as little as 2K if you're willing to go for a black-or-white good/bad trigram (and since most trigrams will probably not exist, you can probably perform even further compression).

Because that would load very quickly, you could use that to quickly generate candidates with 90% accuracy and then, once a full and proper spell checker is downloaded, use that, prioritizing the likely misspelled ones before checking the likely correct ones.  If you're expecting the user to use your site regularly, you can also save the dictionary to local storage for virtually instant recall, rather than have them need to download it every single time.

But English spelling, with our incredibly irregular spelling and constant importing of words without adaptation, absolutely requires a dictionary (although, because we are primarily an analytical language, we actually can store all of the dictionary in memory unlike highly inflected or polysynthetic languages)

Body:
Since I'm working on a similar problem myself, I can provide some guidance.

The quickest way I've found to find errors (but not necessarily correct them) is to use n-gram searches.  You can store these in an array which is the nth-power of the alphabet size.  Given an array @words that includes every single word in a corpus of texts from your language and an trigram (n-gram of three elements):

my %ngrams;
my $ngramSize = 3;
for my $word (@words) {
    next if length($word) < $ngramSize;
    $trigrams{substr($word,$_,$ngramSize)}++ for (0..length($word) -$ngramSize);
}

You would probably want to normalize the data in some way, and then you can store it more efficiently.  For example, you could take the median occurrence count and set that to be 255, clipping any values higher, and then proportioning out anything less).  That would let you store, for instance, a rough English spell checker using trigrams in 17K, or even as little as 2K if you're willing to go for a black-or-white good/bad trigram (and since most trigrams will probably not exist, you can probably perform even further compression).

Because that would load very quickly, you could use that to quickly generate candidates with 90% accuracy and then, once a full and proper spell checker is downloaded, use that, prioritizing the likely misspelled ones before checking the likely correct ones.  If you're expecting the user to use your site regularly, you can also save the dictionary to local storage for virtually instant recall, rather than have them need to download it every single time.

But English spelling, with our incredibly irregular spelling and constant importing of words without adaptation, absolutely requires a dictionary (although, because we are primarily an analytical language, we actually can store all of the dictionary in memory unlike highly inflected or polysynthetic languages)