问:
Is collection object better being immutable?
As per this link, it is an advice that:

A good object should never change his encapsulated state. Remember, an object is a representative of a real-life entity, and this entity should stay the same through the entire life of the object. In other words, an object should never betray those whom he represents. He should never change owners. :)

Be aware that immutability doesn't mean that all methods always return the same values. Instead, a good immutable object is very dynamic. However, he never changes his internal state.

Is it better to re-introduce collections(in java) like class LinkedList  maintaining immutability of state by supporting operations like add/remove item?

Without performance overheads, Can this collection(class LinkedList) be introduced as immutable collection?

Because, below are the advantages in favor of immutability:

immutable objects are always thread-safe

they help to avoid temporal coupling

their usage is side-effect free

答:
I think it's easier to reason about an object that doesn't change state once initialized.  For example value objects are pretty easy to reason about.  Assign a value and query for properties.

This is not always possible and I don't think it's a big deal, but it adds a level of complexity.  Your methods might rely on a consistent internal state which is easier to break if your object keeps changing.

If you need go for an object that frequently changes state, the methods that change the state should be limited and documented.  Limit your use of setters and prefer methods that "takes care of an action".

If complexity arise some further extraction might be needed, your Factory or something else, but I would not generalize the rule, I would judge case by case if the overhead actually solves a real problem.

I wouldn't worry about performance until I have a performance problem.

First Rule of Program Optimization: Don’t do it
  - Michael A. Jackson


问:
Packaging structure of Java collections (java.util) - why does Iterable sit in java.lang?
As per the below diagram, except for interface Iterable, all the remaining constructs (interface / class / abstract class) sit in same package java.util

Why does Iterable sit in java.langpackage?

Note: The intention is to understand the packaging aspect of java programming.

答:
As explained in its javadoc, the purpose of Iterable is to support particular language syntax:

Implementing this interface allows an object to be the target of the "foreach" statement

As such, it belongs to the lang package, which

Provides classes that are fundamental to the design of the Java programming language.

Other classes at the diagram belong to JCF and hence, are in the util package which

Contains the collections framework...

ContentLicense: CC BY-SA 3.0


答:
As per this link

Seeing as rule #1 is horrible, I would caution against taking the rest of the blog post as law. Though really, no blog post should be taken as law.

And the quote itself is rather contradictory:

A good object should never change his encapsulated state.

Be aware that immutability doesn't mean that all methods always return the same values.

Here's the thing, if you have immutable state, and your methods return different values then at least one of two things are true:

Your function varies based on its inputs.

Your function has side effects (works with something that does have mutable state).

(The example in the article hits on #2.)

The second of these conditions defeats the purpose of having immutable objects, and making that distinction between "encapsulated state" and other state is facetious at worst, impractical at best.

And the first of these conditions is good. Functions should only vary on their inputs where possible. Hiding the immutable state in the class harms that a little bit on the clarity front, but varies greatly on what you're actually doing.

Anyways, on to your question:

Without performance overheads, can such implementations(class LinkedList) be introduced by instantiating as immutable objects?

It depends on your language/implementation. Linked lists lend themselves fairly well to immutable construction because the innards of each "link" aren't really mutable. It's relatively easy to make new links with new pointers.

In Java, I doubt you could do such things without some overhead due to the hit to the garbage collector. You can't even do object pooling since there's no way to reuse the immutable objects reliably. And you certainly couldn't do it while maintaining the existing Java interfaces, which are designed with mutability (and maintaining a reference to the list) in mind.

Does a good object never change its state?

Such an absolute is not correct. Yes, immutability provides a number of benefits. Yes, you should probably default to making your objects immutable in Java and many other languages. But there are many perfectly good objects that change their state, and not a few objects (collections especially) where the mutable object is far better (more usable, more robust, more performant, more flexible, more maintainable) than an immutable design.

Title: Is collection object better being immutable?

Body:
As per this link, it is an advice that:

A good object should never change his encapsulated state. Remember, an object is a representative of a real-life entity, and this entity should stay the same through the entire life of the object. In other words, an object should never betray those whom he represents. He should never change owners. :)

Be aware that immutability doesn't mean that all methods always return the same values. Instead, a good immutable object is very dynamic. However, he never changes his internal state.

Is it better to re-introduce collections(in java) like class LinkedList  maintaining immutability of state by supporting operations like add/remove item?

Without performance overheads, Can this collection(class LinkedList) be introduced as immutable collection?

Because, below are the advantages in favor of immutability:

immutable objects are always thread-safe

they help to avoid temporal coupling

their usage is side-effect free


问:
Why left recursion not looping?
I'm trying to read the parser of PHP, that says:

```<code>top_statement_list:
        top_statement_list  top_statement
    |   /* empty */
;
</code>```

It is a left-recursion, but why it don't looping infinitely?

My question is because I'm trying building a parser for study, but I don't know how code that. Maybe it is similar to (regex-alike) {top_statement}*? In case, it'll try resolve how much top_statement it can.

答: Left-recursive grammars can generally be rewritten by adding symbols and rearranging slightly.  Wikipedia has a good example for a simple four-function calculator grammar.  Since you know the first terminal you see in a top_statement_list must be a valid nonterminal for the beginning of a top_statement, you can rewrite to check for a top_statement instead of a top_statement_list first.

Title: Why left recursion not looping?


问:
JS Async: . Can I forget callbacks all together and replace with promises and/or generators
I've been using Nodejs and I really dislike callbacks (as i think most people do.)
I'm starting to learn about promises and generators. Both are a lot cleaner and I'd like to forget the horrors of callbacks all together and erase them from my memory.

Is there any reason I need to use callbacks.  Can I completely abandon them and use promises or generators instead of them and never need to write another callback?  Or do they have some use case where they are needed?

答: The short answer is yes, you can pretty much replace callbacks with promises.  The caveat is some library APIs use callbacks so you are unlikely to be able to avoid them altogether. </p>


问:
Using auto-increment clustered key and guid primary key together
My boss is the db administrator in a new software project and he came up with that design where every table will have both a auto-increment clustered key and a guid primary key (or possibly composite guid keys on some rare cases). Every relations between tables will still use pk as references, making the clustered field never used in views, procedures, functions or any code at all.

I'm no db guru, but I wonder if in this scenario it's even worth having a clustered index at all? I mean, won't records systematically be added to the end of tables? If so then why would I need this field?

答:
Advantage:

GUID is unique so in the long run if you run into this scenario where you can join using just Guid rather than PK+other field. ex:there sales, order, adjustment, and there is stock, instead of join using PK and transaction type, you can just join using Guid since it 99.9...%  guaranteed unique.

By using GUID you can generate GUID from code so it remove a need to do callback to get new PK.

By having auto-increment you can get latest transaction just by ordering auto-increment instead of transaction date(stackoverflow using this method)


问:
How to choose NOT to use a framework (Caliburn.Micro, etc.) in a given MVVM application?
I have once started a MVVM/WPF project, which was eventually built and deployed, and for that I studied a lot of the Caliburn.Micro MVVM Framework. The fact is: I ended up not using Caliburn.Micro for that, and ended up implementing some MVVM concepts myself (specifically, just the ViewModelBase and RoutedCommand classes).

Now I was assigned to a somewhat larger project along the same lines: a "Single-User Rich Client Offline Desktop Application", so to say, and I decided to use Caliburn.Micro. And that's where my "problem" begins.

I have read in this famous blog post, whose title says that "If you're using MVVM then you need a framework", that:

"Trying to do something like MVVM without a framework is a huge amount of work. Tons of duplicate code, reinventing the wheel, and retraining people to think differently.

At least with a framework you avoid the duplicate code and hopefully don’t have to reinvent the wheel – allowing you to focus on retraining people. The retraining part is generally unavoidable, but a framework provides plumbing code and structure, making the process easier."

I would agree upon first reading but my actual experience with Caliburn.Micro (CM) in my actual application is being of cluelessness and disorientation. That is, the framework didn't make the process easier at all, quite the opposite. Reading the ever-repeating examples provided by Rob Eisenberg in the rather (too) informal documentation, and trying to infer usage patterns from the convoluted provided samples, and their utterly indirect class and interface relationships, where things seem to be designed to work based on side-effects, seems humanly impossible unless you are a seasoned genius (sorry for the rant, but I guess you know what I mean).

Not to mention that any above-trivial scenario seems to involve IoC containers, which is something I have never worked with, and which seem to solve a problem I might not even have. I don't feel like spending more project hours learning those things instead of thinking about my problem and application domains. I just wanted a banana, but CM gave me a gorilla (IoC) holding a basket of bananas.

Now that I am considering to move back to my homespun MVVM framework - composed only of the handful of MVVM-specific classes I actually want to implement - I would like at least to give CM a chance, in case I am losing something here, or just plainly doing things "the wrong way" out of sheer inexperience and ignorance. And so the question is:

There are widespread consensus that "frameworks make things easier and more natural", but if I happen to be experiencing quite the opposite, does this mean that I shouldn't use the framework, or that I am trying to learn it the wrong way? Is there a clue that I shouldn't even be using a framework in the first place? Or is there some "right" way to figure out how to use CM for simple MVVM development?

答:
I have tried CaliburnMicro and MVVMLight and when using Caliburn I really feel what you feel, sure it feels really magical able to bind a control to a property just by using Name="PropertyName" instead of old Text="{Bind PropertyName}" but in the end Caliburn goes way overboard to do this magical thing.  When something goes wrong it is really hard to debug and to make things worse they have a lot of ways to do one thing.

In contrast, MVVMLight is really thin.  When you use it you probably realize that it is almost 100% like your MVVM Framework, with some feature sprinkled in it.

I know this doesn't answer your question "How NOT to use framework" but frankly I can't recommend you go that route. I think you are just lost because you used a full featured framework instead of using a simple one first.

ContentLicense: CC BY-SA 4.0


问:
Is anything in programming truly evil?
So, there are a bunch of questions appearing asking is X evil, is Y evil.

My view is that there are no language constructs, algorithms or whatever which are evil, just ones which are badly used.  Hell, if you look hard enough there are even valid uses of goto.

So does absolute evil, that is something which is utterly incompatible with best practice in all instances, exist in programming?  And if so what is it?  Or is it just bad programmers not knowing when something is appropriate?

Edit: To be clear, I'm not talking about things programmers do (such as not checking return codes or not using version control - they're choices made by bad programmers), I mean tools, languages, statements, whatever which are just bad...

答:
Some programming instructions / style / conventions are very often misused to make terrible, evil if you will code, but in the hands of a master programmer they can be used in a very elegant fashion, good if you will.

On the other hand I know of nothing that can prevent incompetent or inexperienced programmers from from producing bad, evil if you will code even with the best tools, languages, and so on.

By avoiding often misused elements, such as goto, the hope is that mediocre programmers can avoid the evil and perhaps make it somewhat easier to write good code.

ContentLicense: CC BY-SA 2.5

Title: Is anything in programming truly evil?


问:
Retrieving maximum value from a range in unsorted array
I have an unsorted array. I have queries in which I give a range and then the maximum value from that range has to returned.
For example:

```<code>array[]={23,17,9,45,78,2,4,6,90,1};
query(both inclusive): 2 6
answer: 78
</code>```

Which algorithm or data structure do I construct to quickly retrieve maximum value from any range. (There are a lot of queries)

EDIT:
This is indeed a simple version of the actual problem. I can have the array size as large as 100000 and the number of queries upto 100000. So I definitely require some preprocessing which'll facilitate a fast query response.

答:
The binary tree/segment tree-based solutions are indeed pointing in the right direction. One might object that they require a lot of extra memory, however. There are two solutions to these problems:

Use an implicit data structure instead of a binary tree

Use an M-ary tree instead of a binary tree

The first point is that because the tree is highly structured, you can use a heap-like structure to implicitly define the tree rather than representing the tree with nodes, left and right pointers, intervals etc.. That saves a lot of memory with essentially no performance hit - you do need to perform a little more pointer arithmetic.

The second point is that, at the cost of a little more work during evaluation, you can use an M-ary tree rather than a binary tree. For instance if you use a 3-ary tree you will compute the max of 3 elements at a time, then 9 elements at a time, then 27, etc. The extra storage required is then N/(M-1) - you can prove using the geometric series formula. If you choose M = 11, for example, you will require 1/10th the storage of the binary tree method.

You can verify that these naive and optimized implementations in Python give the same results:

```<code>class RangeQuerier(object):
    #The naive way
    def __init__(self):
        pass

    def set_array(self,arr):
        #Set, and preprocess
        self.arr = arr

    def query(self,l,r):
        try:
            return max(self.arr[l:r])
        except ValueError:
            return None
</code>```

vs.

```<code>class RangeQuerierMultiLevel(object):
    def __init__(self):
        self.arrs = []
        self.sub_factor = 3
        self.len_ = 0

    def set_array(self,arr):
        #Set, and preprocess
        tgt = arr
        self.len_ = len(tgt)
        self.arrs.append(arr)
        while len(tgt) > 1:
            tgt = self.maxify_one_array(tgt)
            self.arrs.append(tgt)

    def maxify_one_array(self,arr):
        sub_arr = []
        themax = float('-inf')
        for i,el in enumerate(arr):
            themax = max(el,themax)
            if i % self.sub_factor == self.sub_factor - 1:
                sub_arr.append(themax)
                themax = float('-inf')
        return sub_arr

    def query(self,l,r,level=None):
        if level is None:
            level = len(self.arrs)-1

        if r <= l:
            return None

        int_size = self.sub_factor ** level

        lhs,mid,rhs = (float('-inf'),float('-inf'),float('-inf'))

        #Check if there's an imperfect match on the left hand side
        if l % int_size != 0:
            lnew = int(ceil(l/float(int_size)))*int_size
            lhs = self.query(l,min(lnew,r),level-1)
            l = lnew
        #Check if there's an imperfect match on the right hand side
        if r % int_size != 0:
            rnew = int(floor(r/float(int_size)))*int_size
            rhs = self.query(max(rnew,l),r,level-1)
            r = rnew

        if r > l:
            #Handle the middle elements
            mid = max(self.arrs[level][l/int_size:r/int_size])
        return max(max(lhs,mid),rhs)
</code>```

Body:
The binary tree/segment tree-based solutions are indeed pointing in the right direction. One might object that they require a lot of extra memory, however. There are two solutions to these problems:

Use an implicit data structure instead of a binary tree

Use an M-ary tree instead of a binary tree

The first point is that because the tree is highly structured, you can use a heap-like structure to implicitly define the tree rather than representing the tree with nodes, left and right pointers, intervals etc.. That saves a lot of memory with essentially no performance hit - you do need to perform a little more pointer arithmetic.

The second point is that, at the cost of a little more work during evaluation, you can use an M-ary tree rather than a binary tree. For instance if you use a 3-ary tree you will compute the max of 3 elements at a time, then 9 elements at a time, then 27, etc. The extra storage required is then N/(M-1) - you can prove using the geometric series formula. If you choose M = 11, for example, you will require 1/10th the storage of the binary tree method.

You can verify that these naive and optimized implementations in Python give the same results:

class RangeQuerier(object):
    #The naive way
    def __init__(self):
        pass

    def set_array(self,arr):
        #Set, and preprocess
        self.arr = arr

    def query(self,l,r):
        try:
            return max(self.arr[l:r])
        except ValueError:
            return None

vs.

class RangeQuerierMultiLevel(object):
    def __init__(self):
        self.arrs = []
        self.sub_factor = 3
        self.len_ = 0

    def set_array(self,arr):
        #Set, and preprocess
        tgt = arr
        self.len_ = len(tgt)
        self.arrs.append(arr)
        while len(tgt) > 1:
            tgt = self.maxify_one_array(tgt)
            self.arrs.append(tgt)

    def maxify_one_array(self,arr):
        sub_arr = []
        themax = float('-inf')
        for i,el in enumerate(arr):
            themax = max(el,themax)
            if i % self.sub_factor == self.sub_factor - 1:
                sub_arr.append(themax)
                themax = float('-inf')
        return sub_arr

    def query(self,l,r,level=None):
        if level is None:
            level = len(self.arrs)-1

        if r <= l:
            return None

        int_size = self.sub_factor ** level

        lhs,mid,rhs = (float('-inf'),float('-inf'),float('-inf'))

        #Check if there's an imperfect match on the left hand side
        if l % int_size != 0:
            lnew = int(ceil(l/float(int_size)))*int_size
            lhs = self.query(l,min(lnew,r),level-1)
            l = lnew
        #Check if there's an imperfect match on the right hand side
        if r % int_size != 0:
            rnew = int(floor(r/float(int_size)))*int_size
            rhs = self.query(max(rnew,l),r,level-1)
            r = rnew

        if r > l:
            #Handle the middle elements
            mid = max(self.arrs[level][l/int_size:r/int_size])
        return max(max(lhs,mid),rhs)


答:
Without performance overheads, can such implementations(class LinkedList<E>) be introduced by instantiating as immutable objects?

Yes, it can. In fact, a linked list is the prime example of a persistent immutable collection. (I assume by "without performance overheads" you are talking about persistence?)

```<code>public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    private final E value;
    private final LinkedList<E> next;

    static final empty = new Empty();

    LinkedList(E value, LinkedList<E> next) {
        this.value = value;
        this.next = next;
    }

    Optional<E> value() {
        return Optional.of(value);
    }

    Optional<LinkedList<E>> next() {
        return Optional.of(next);
    }

    private class Empty extends LinkedList<Object> {
        private Empty() {}

        Optional<E> value() {
            return Optional.empty();
        }

        Optional<LinkedList<E>> next() {
            return Optional.empty();
        }
    }
}
</code>```

I don't know Java very well, but something like this should get you started.

Body:
Without performance overheads, can such implementations(class LinkedList<E>) be introduced by instantiating as immutable objects?

Yes, it can. In fact, a linked list is the prime example of a persistent immutable collection. (I assume by "without performance overheads" you are talking about persistence?)

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    private final E value;
    private final LinkedList<E> next;

    static final empty = new Empty();

    LinkedList(E value, LinkedList<E> next) {
        this.value = value;
        this.next = next;
    }

    Optional<E> value() {
        return Optional.of(value);
    }

    Optional<LinkedList<E>> next() {
        return Optional.of(next);
    }

    private class Empty extends LinkedList<Object> {
        private Empty() {}

        Optional<E> value() {
            return Optional.empty();
        }

        Optional<LinkedList<E>> next() {
            return Optional.empty();
        }
    }
}

I don't know Java very well, but something like this should get you started.


答:
tl;dr The author seems to think all objects are value objects, but this is not true.

Value objects should be immutable because their existence represents a specific value out of some value space.

For example, an object that represents a pixel color value could be made immutable.
The property of immutability can be used to reason about the problem more easily, reuse objects, cache computations, and more.

On the other hand, a thread object will need to reflect the status of a thread of execution, allowing you to query the state of the thread (myThread.isRunning(), for example). You can't expect this to work if the object were immutable, unless you can have the reference myThread swapped out from under you, but IMO this adds complexity that goes against the grain of the problem.


问:
Is continuous integration more than just automatically testing code?
Is continuous integration about more than just automatically testing code, either periodically or after every commit to the main repository?

Before today, I'd heard the term CI, and about CI services such as Jenkins, and RunCodeRun, and assumed that it was merely about having a server independent of developers' machines that checked that the automated tests of a project passed, and alerting people if it doesn't.

However, Wikipedia's definition seems to be different.

If my understanding of what CI is is incorrect, is there any term that merely refers to automatically running tests on an independent server?

答:
The gist of CI is to avoid any kind of long-term branches. If you have a team working on a product, a model opposed to CI is to pick a new requirement for a feature to develop for the product. Then the team creates a feature branch in the VCS, apart from the "trunk" or "master" branch, they develop and test the feature for several days in isolation, reintegrate it afterwards into the trunk and then do final integration tests (note that in between other parts of the team could have made changes to the trunk as well).

In CI, you split the new feature into several sub-parts, each of them creating still a working and compilable product, and integrate that sub-part into the main trunk very often, typically multiple times a day. There are no branches with big differences from the trunk, and if different groups of people are working on different features simultanously, they will daily ("continously") reintegrate all their changes to the code base. Almost all tests are always running on the "integrated" work, there will be almost no tests on non-integrated parts (except the tests each dev runs on his own local copy before committing his changes).

For this, you should have a server supported automatic build process in place and a lot of automatic tests which run at that server as well. This will give immediate feedback to the team if the changes they made might cause any problems on the integrated product. You won't need an "extra test phase" to check if the integration of a bigger feature into the product causes any problems. But those automatisms are just supporting tools to make CI work well, these steps are not the steps which actually define CI.


问:
Beginners C# question about Array.Reverse
I am sitting through a very well-explained and thorough video tutorial series, using Visual Studio 2012 as my developing environment.

Anyway, one thing that is hard to figure out is this.  Say you have this code

```<code>static void Main()
{
    int[] myArray = {0, 1, 2, 3};
    Array.Reverse(myArray);
    foreach (int item in myArray) Console.WriteLine(item);
    Console.ReadLine();
//console says 3,2,1,0
}

static void Main()
{
    int[] myArray = {0, 1, 2, 3};
    myArray.Reverse();
    foreach (int item in myArray) Console.WriteLine(item);
    Console.ReadLine();
//console says 0, 1, 2, 3
}
</code>```

I'm not getting why using the base class's method permanently changes the order of the elements in the array from that point on, versus using the instance of the Array class (myArray) which only changes it for the current line, then it reverts back to the un-reversed order.  Can anyone explain this?

答:
In the first program, you called Array.Reverse, a static method of the Array class that reverses the array in-place.

In your second program, you called Enumerable.Reverse, an extension method that works on any kind of enumerable. As an array is a kind of enumerable, it does work on arrays. But it does not do in-place reversion, but instead returns a new enumerable that is the reverse of the one you passed in.

You could have done this:

```<code>static void Main()
{
    int[] myArray = {0, 1, 2, 3};
    var somethingThatCanBeUsedByforEachAndReturnsYourArrayReversed = myArray.Reverse();
    foreach (int item in somethingThatCanBeUsedByforEachAndReturnsYourArrayReversed)
    {
       Console.WriteLine(item);
    }
    Console.ReadLine();
//console says 0, 1, 2, 3
}
</code>```

But to be honest, if you are still learning, leave your hands off of Enumerables and LinQ. They are great, but right now, way over your head. Simply deleting using System.Linq from your source file will make your life a lot easier while still learning.

Body:
In the first program, you called Array.Reverse, a static method of the Array class that reverses the array in-place.

In your second program, you called Enumerable.Reverse, an extension method that works on any kind of enumerable. As an array is a kind of enumerable, it does work on arrays. But it does not do in-place reversion, but instead returns a new enumerable that is the reverse of the one you passed in.

You could have done this:

static void Main()
{
    int[] myArray = {0, 1, 2, 3};
    var somethingThatCanBeUsedByforEachAndReturnsYourArrayReversed = myArray.Reverse();
    foreach (int item in somethingThatCanBeUsedByforEachAndReturnsYourArrayReversed)
    {
       Console.WriteLine(item);
    }
    Console.ReadLine();
//console says 0, 1, 2, 3
}

But to be honest, if you are still learning, leave your hands off of Enumerables and LinQ. They are great, but right now, way over your head. Simply deleting using System.Linq from your source file will make your life a lot easier while still learning.


答:
Grammar rewriting

Left-recursive grammars can be automatically rewritten to eliminate the left-recursion. Any recursion must have some base case, so we can substitute that instead. Assume this example grammar:

```<code>A ::= A B
    | A C
    | D
    | E
</code>```

We can introduce a helper rule A_rest to group all left-recursive alternatives into a single alternative, and a helper rule A_init that contains all alternatives without left recursion,

```<code>A ::= A A_rest | A_init
A_rest ::= B | C
A_init ::= D | E
</code>```

We can now rewrite A to

```<code>A ::= A_init | A_init A'
A' ::= A_rest | A_rest A'
</code>```

and have exchanged left-recursion for right-recursion. This allows an LL parser to recognize left-recursive grammars – with one caveat: this rewrite changes the structure of the resulting parse tree!

Assume the input 1 - 2 - 3, where - is the normal left-associative subtraction operator. Because it is left-associative, this has to be interpreted as (1 - 2) - 3, and the interpretation 1 - (2 - 3) is invalid. So the description of this operator is necessarily left-recursive:

```<code>Subtraction ::= Subtraction '-' Number | Number
</code>```

This rule would give us the parse tree

```<code>              Subtraction
                 / | \
      Subtraction '-' Number=3
           / | \
Subtraction '-' Number=2
    |
Number=1
</code>```

, which corresponds to the precedence (1 - 2) - 3. But if we rewrite the rule to eliminate left-recursion, we get the rule

```<code>Subtraction ::= Number | Number Subtraction'
Subtraction' ::= '-' Number | '-' Number Subtraction'
</code>```

This rule would give us the parse tree

```<code>    Subtraction
        / \
Number=1   Subtraction'
          /     |     \
      '-'    Number=2  Subtraction'
                          / \
                       '-'   Number=3
</code>```

, which corresponds to the precedence 1 - (2 - 3) which is wrong. Also, the parse tree looks severely mangled and does not represent the logical structure of the input any longer. This is bad, and unusable for practical applications. We could try to fix up the parse tree by juggling nodes around, but there is a better alternative:

Use a better algorithm: LR parsers

Top-down parsing algorithms of the kind you are probably using (recursive descent?) are limited in their expressiveness, their correctness, and in their efficiency. The only thing they have going for them is that they use a very intuitive approach, and this is probably the only reason they are still being commonly used. Other parsing algorithms such as LR or LALR can parse a broader range of grammars and can do so in linear time, but are less intuitive and difficult to write by hand. Which is why we generally use parser generators to create a parser from a grammar, rather than writing the grammar by hand.

The grammar file you linked to is a Yacc grammar. Yacc is a parser generator tool that uses the LALR algorithm – no problems with left recursion, almost as general as LR, but needs smaller “state tables” than real LR. LALR has some annoying limitations, but it is currently the most common parsing algorithm in practical use for implementing “real” programming languages.

Bottom-up algorithms such as LR can parse a broader range of grammars because they decide which alternative to apply after they have seen the appropriate input. Using the Subtraction example, assume we see the token stream

```<code>Number=1 '-' Number=2 '-' Number=3
</code>```

and have the grammar

```<code>Subtraction → Subtraction '-' Number
Subtraction → Number
</code>```

. I will use a · to denote the current position in a rule

initialize the parser. We have an empty token stack, and are at the beginning of all alternatives:

```<code>Subtraction → · Subtraction '-' Number
Subtraction → · Number
</code>```

read token Number=1. The token stack of the parser is now

```<code>| Number=1 |
</code>```

this completes the rule Subtraction → Number ·, so we can reduce the right-hand side of the rule to the left-hand side by adding a parse tree fragment to the stack. The token stack is now:

```<code>| Subtraction |
|     |       |
|  Number=1   |
</code>```

read token '-'. The token stack is

```<code>| Subtraction | '-' |
|     |       |     |
|  Number=1   |     |
</code>```

we are in the rules

```<code>Subtraction → Subtraction '-' · Number
</code>```

read token Number=2. The token stack is

```<code>| Subtraction | '-' | Number=2 |
|     |       |     |          |
|  Number=1   |     |          |
</code>```

this completes the rule

```<code>Subtraction → Subtraction '-' Number ·
</code>```

so we can reduce to

```<code>|         Subtraction      |
|            / | \         |
| Subtraction '-' Number=2 |
|     |                    |
| Number=1                 |
</code>```

and so on for the remaining tokens, until no input tokens are left, and the token stack consists of a single item: the final parse tree.

Recognizing where we are in which rule and whether a rule was completed by this token is generally done by a DFA state machine, which is why we need to calculate state tables from the grammar when constructing the parser.

Title: Why left recursion not looping?

Body:
I'm trying to read the parser of PHP, that says:

```<code>top_statement_list:
        top_statement_list  top_statement
    |   /* empty */
;
</code>```

It is a left-recursion, but why it don't looping infinitely?

My question is because I'm trying building a parser for study, but I don't know how code that. Maybe it is similar to (regex-alike) {top_statement}*? In case, it'll try resolve how much top_statement it can.

Body:
Grammar rewriting

Left-recursive grammars can be automatically rewritten to eliminate the left-recursion. Any recursion must have some base case, so we can substitute that instead. Assume this example grammar:

A ::= A B
    | A C
    | D
    | E

We can introduce a helper rule A_rest to group all left-recursive alternatives into a single alternative, and a helper rule A_init that contains all alternatives without left recursion,

A ::= A A_rest | A_init
A_rest ::= B | C
A_init ::= D | E

We can now rewrite A to

A ::= A_init | A_init A'
A' ::= A_rest | A_rest A'

and have exchanged left-recursion for right-recursion. This allows an LL parser to recognize left-recursive grammars – with one caveat: this rewrite changes the structure of the resulting parse tree!

Assume the input 1 - 2 - 3, where - is the normal left-associative subtraction operator. Because it is left-associative, this has to be interpreted as (1 - 2) - 3, and the interpretation 1 - (2 - 3) is invalid. So the description of this operator is necessarily left-recursive:

Subtraction ::= Subtraction '-' Number | Number

This rule would give us the parse tree

              Subtraction
                 / | \
      Subtraction '-' Number=3
           / | \
Subtraction '-' Number=2
    |
Number=1

, which corresponds to the precedence (1 - 2) - 3. But if we rewrite the rule to eliminate left-recursion, we get the rule

Subtraction ::= Number | Number Subtraction'
Subtraction' ::= '-' Number | '-' Number Subtraction'

This rule would give us the parse tree

    Subtraction
        / \
Number=1   Subtraction'
          /     |     \
      '-'    Number=2  Subtraction'
                          / \
                       '-'   Number=3

, which corresponds to the precedence 1 - (2 - 3) which is wrong. Also, the parse tree looks severely mangled and does not represent the logical structure of the input any longer. This is bad, and unusable for practical applications. We could try to fix up the parse tree by juggling nodes around, but there is a better alternative:

Use a better algorithm: LR parsers

Top-down parsing algorithms of the kind you are probably using (recursive descent?) are limited in their expressiveness, their correctness, and in their efficiency. The only thing they have going for them is that they use a very intuitive approach, and this is probably the only reason they are still being commonly used. Other parsing algorithms such as LR or LALR can parse a broader range of grammars and can do so in linear time, but are less intuitive and difficult to write by hand. Which is why we generally use parser generators to create a parser from a grammar, rather than writing the grammar by hand.

The grammar file you linked to is a Yacc grammar. Yacc is a parser generator tool that uses the LALR algorithm – no problems with left recursion, almost as general as LR, but needs smaller “state tables” than real LR. LALR has some annoying limitations, but it is currently the most common parsing algorithm in practical use for implementing “real” programming languages.

Bottom-up algorithms such as LR can parse a broader range of grammars because they decide which alternative to apply after they have seen the appropriate input. Using the Subtraction example, assume we see the token stream

Number=1 '-' Number=2 '-' Number=3

and have the grammar

Subtraction → Subtraction '-' Number
Subtraction → Number

. I will use a · to denote the current position in a rule

initialize the parser. We have an empty token stack, and are at the beginning of all alternatives:

Subtraction → · Subtraction '-' Number
Subtraction → · Number

read token Number=1. The token stack of the parser is now

| Number=1 |

this completes the rule Subtraction → Number ·, so we can reduce the right-hand side of the rule to the left-hand side by adding a parse tree fragment to the stack. The token stack is now:

| Subtraction |
|     |       |
|  Number=1   |

read token '-'. The token stack is

| Subtraction | '-' |
|     |       |     |
|  Number=1   |     |

we are in the rules

Subtraction → Subtraction '-' · Number

read token Number=2. The token stack is

| Subtraction | '-' | Number=2 |
|     |       |     |          |
|  Number=1   |     |          |

this completes the rule

Subtraction → Subtraction '-' Number ·

so we can reduce to

|         Subtraction      |
|            / | \         |
| Subtraction '-' Number=2 |
|     |                    |
| Number=1                 |

and so on for the remaining tokens, until no input tokens are left, and the token stack consists of a single item: the final parse tree.

Recognizing where we are in which rule and whether a rule was completed by this token is generally done by a DFA state machine, which is why we need to calculate state tables from the grammar when constructing the parser.


问:
How can I avoid the use of strings?
I'm implementing a program where the user can 'create a musical scale' from a variety of notes (identified by their names), and the program will generate music from this scale.

I want to implement a class that takes a note and a length, and generates a SoundWave. So one option would be to expose the following method:

```<code>public SoundWave GenerateNote(string noteName, double length);
</code>```

However, I think it would be best to try and avoid strings. So I can think of two additional options:

```<code>public SoundWave GenerateNote(Note note, double length);
// Note is a simple object with a string name and a double frequency.
</code>```

And:

```<code>public void Scale { get; set; }
public SoundWave GenerateNote(int noteIndex, double length);
</code>```

Thing is, I won't be able to avoid strings completely, because as I said the user will select notes identified by their names. So what would be the best option you can think of?

答:
Thing is, I won't be able to avoid strings completely, because as I said the user will select notes identified by their names. So what would be the best option you can think of?

Is this going to be a command line program? If so, it's of course impossible to avoid dealing with string since that's what the user is typing in. I'd give the Note class a static parse(string s) method that produces a Note instance.

Once you have a GUI, though, you'll probably have the user choose from a selection of existing notes.

Title: How can I avoid the use of strings?


答:
The point of avoiding strings is not that they are inherently bad and should never be used. If that were the case, we'd omit them from our programming languages.

What should be avoided is the use of strings to represent alternative values when the possible values are in fact a small set of predefined options, rather than any possible string. The danger that someone will forget which values are allowed and which aren't is just too great.

Therefore, mechanisms have been invented to support that common case better. In business logic, you should be using enums instead of strings; in GUIs, you should have drop-down lists rather than text input fields for such data. But nothing stops you from using strings for data that really are arbitrary, such as user names.

Title: How can I avoid the use of strings?

Body:
I'm implementing a program where the user can 'create a musical scale' from a variety of notes (identified by their names), and the program will generate music from this scale.

I want to implement a class that takes a note and a length, and generates a SoundWave. So one option would be to expose the following method:

```<code>public SoundWave GenerateNote(string noteName, double length);
</code>```

However, I think it would be best to try and avoid strings. So I can think of two additional options:

```<code>public SoundWave GenerateNote(Note note, double length);
// Note is a simple object with a string name and a double frequency.
</code>```

And:

```<code>public void Scale { get; set; }
public SoundWave GenerateNote(int noteIndex, double length);
</code>```

Thing is, I won't be able to avoid strings completely, because as I said the user will select notes identified by their names. So what would be the best option you can think of?


答:
Asumming there are a finite set of notes, e.g. A, C, D, E, …, it seems an enumerated type would fit your purpose best. An enumerated type (available in most programming languages) can take values from a small set, where the type definition contains all values which are allowed. So, for example, you could use values MON, TUE, WED, THU, FRI, SAT, SUN for a DayOfWeek enum type, or A, C, D, … for Note type.

Using enums gives your code improved readabilty and makes some kinds of errors impossible, such as passing the string xyz as your note name. With an enumerated type it is simply not possible to pass an illegal value.

Title: How can I avoid the use of strings?


答:
Do not confuse user interface issues with programming interface issues.

The fact that the user will enter notes by name is a user interface issue, and of absolutely no concern to your GenerateNote() function, which is part of a programming interface.

As a matter of fact, the user interface could, in theory, allow the user to select among different notations, (A, B, C...) or (Do, Re, Mi...) so clearly, the task of mapping strings entered by the user to actual note objects should be handled by the user interface, and these strings should never be allowed to propagate to other parts of your application.  The fact that a Note object may contain its own name is not even necessarily pertinent to the mapping, since the user may enter "Do", and the user interface will have to map this to a Note object bearing the name "A".  Similarly, when the user interface displays the Note objects back to the user, it needs to perform the reverse transformation, and again, it may need to show 'Do' while the object bears the name 'A'.  So, the two are completely unrelated.

A noteIndex of type int is as bad as a string, because you are using a general purpose data type there where a more specific data type (an actual Note class) could be used instead.  The general purpose data type is meaningless in and of itself, and its meaning is in fact whatever meaning is assigned to it at runtime (instead of compile-time) by code that handles it, so its existence constitutes a completely unnecessary and dangerous (see error prone) indirection.  The best practice in Software Engineering is to use a special type for each different concept that your logic deals with.  That's what "Strong Typing" is all about.

So, definitely go with a Note object.

Why not just use a double frequency and get it over with?  Well, again, the answer is "Strong Typing". Take an example from a different application: suppose you are writing software that deals with automobiles, so you are dealing with things like "speed" and "fuel consumption".  The proper thing to do is to have a "Speed" data type, which contains a double, and a "FuelConsumption" data type, which contains another double, so that you never pass doubles around, because at some point a double which was meant to stand for "Speed" will mistakenly be passed to a function which expected a double that was meant to stand for "FuelConsumption", and all kinds of funny things will happen then.  Good luck with debugging a system built this way!  With strong typing, the compiler makes sure that you can not do the wrong thing.

Title: How can I avoid the use of strings?


问:
Are Constant Time and Amortized Constant Time effectively considered equivalent?
I need to write a RandomQueue that allows for appends and random removal in Constant Time ( O(1) ).

My first thought was to back it with some kind of Array (I chose an ArrayList), since arrays have constant access via an index.

Looking over the documentation though, I realized that ArrayLists' additions are considered Amortized Constant Time, since an addition may require a reallocation of the underlying array, which is O(n).

Are Amortized Constant Time and Constant Time effectively the same, or do I need to look at some structure thay doesn't require a full reallocation on every addition?

I'm asking this because array based structures aside (which as far as I know will always have Amortized Constant Time additions), I can't think of anything that will meet the requirements:

Anything tree based will have at best O(log n) access

A linked list could potentially have O(1) additions (if a reference to the tail is kept), but a random removal should be at best O(n).

Here's the full question; in case I glazed over some important details:

Design and implement a RandomQueue. This is an implementation of the Queue interface in which the remove() operation removes an element that is chosen uniformly at random among all the elements currently in the queue. (Think of a RandomQueue as a bag in which we can add elements or reach in and blindly remove some random element.) The add(x) and remove() operations in a RandomQueue should run in constant time per operation.

答:
It depends – on whether you are optimizing for throughput or for latency:

Latency-sensitive systems need consistent performance. For such a scenario, we have to emphasize worst-case behaviour of the system. Examples are soft real time systems such as games that want to achieve a consistent framerate, or web servers that have to send a response within a certain tight timeframe: wasting CPU cycles is better than being late.

Throughput-optimized systems don't care about occasional stalls, as long as the maximal amount of data can be processed in the long run. Here, we are primarily interested in amortized performance. This is generally the case for number crunching or other batch-processing jobs.

Note that one system can have different components that must be categorized differently. E.g. a modern text processor would have a latency-sensitive UI thread, but throughput-optimized threads for other tasks such as spellchecking or PDF exports.

Also, algorithmic complexity often does not matter as much as we'd might think: When a problem is bounded to a certain number, then actual and measured performance characteristics are more important than the behaviour “for very large n”.


答:
Amortized Constant Time can almost always be considered equivalent to Constant Time, and without knowing the specifics of your application and the type of usage you are planning to do to this queue, most chances are that you will be covered.

An array list has the concept of capacity, which is basically equal to the largest size/length/count of items that has ever been required of it thus far.  So, what will happen is that in the beginning the array list will keep reallocating itself to increase its capacity as you keep adding items to it, but at some point the average number of items added per unit time will inevitably match the average number of items removed per unit time, (otherwise you would eventually run out of memory anyway,) at which point the array will stop reallocating itself, and all appends will be met at constant time of O(1).

However, keep in mind that by default, random removal from an array list is not O(1), it is O(N), because array lists move all the items after the removed item one position down to take the place of the removed item.  In order to achieve O(1) you will have to override the default behavior to replace the removed item with a copy of the last item of the array list, and then remove the last item, so that no items will be moved.  But then, if you do that, you do not exactly have a queue anymore.

Title: Are Constant Time and Amortized Constant Time effectively considered equivalent?

Body:
I need to write a RandomQueue that allows for appends and random removal in Constant Time ( O(1) ).

My first thought was to back it with some kind of Array (I chose an ArrayList), since arrays have constant access via an index.

Looking over the documentation though, I realized that ArrayLists' additions are considered Amortized Constant Time, since an addition may require a reallocation of the underlying array, which is O(n).

Are Amortized Constant Time and Constant Time effectively the same, or do I need to look at some structure thay doesn't require a full reallocation on every addition?

I'm asking this because array based structures aside (which as far as I know will always have Amortized Constant Time additions), I can't think of anything that will meet the requirements:

Anything tree based will have at best O(log n) access

A linked list could potentially have O(1) additions (if a reference to the tail is kept), but a random removal should be at best O(n).

Here's the full question; in case I glazed over some important details:

Design and implement a RandomQueue. This is an implementation of the Queue interface in which the remove() operation removes an element that is chosen uniformly at random among all the elements currently in the queue. (Think of a RandomQueue as a bag in which we can add elements or reach in and blindly remove some random element.) The add(x) and remove() operations in a RandomQueue should run in constant time per operation.


问:
Does a serializable singleton imply both value and reference semantics at the same time?
I was reading Effective Java, and I came across passages that talk about ways you might implement a serializable singleton, as if this was a perfectly normal thing to do in Java. This immediately baffled me, because my intuition says that:

Being serializable necessarily implies value semantics.

Being a singleton necessarily implies reference semantics.

Value and identity semantics are mutually exclusive.

The Effective Java author even appears to share at least some of this intuition, if I'm reading this later passage correctly:

As a rule of thumb, value classes such as Date and BigInteger should
  implement Serializable, as should most collection classes. Classes representing
  active entities, such as thread pools, should rarely implement Serializable.

When I searched the book, this site and some blog posts, I found a lot of examples where readResolve() is little more than return INSTANCE;. Maybe I'm just really bad at Java, but a class like that looks to me as if it's saying "when deserializing an object of this class, ignore the serialized data completely and return the existing instance" which would imply the object is not actually serializable in any meaningful way. And yet there's this SO answer which seems to say "the only use for readResolve() is to make serializable singletons", so...that's about where I gave up and started writing this question.

Are there any huge misunderstandings in what I've said so far? If not, what would be a legitimate use case for a serializable singleton class, and what would its semantics be?

答:
If you're doing logging, it would often be convenient to log the state of any singletons, as they represent global state that might be required to reproduce a crash. If your singleton can be logged by serializing a complete representation of itself, this is ideal as you might also be able to deserialize that state and rerun your program with the singleton in the same state.

tl;dr, reproducibility.

Edit: I didn't really want to get too far into the relationship of Value and Reference semantics, because I'm not a Java guy and it sounds like the books you're saying understand these things in a more specific way that probably makes complete sense in Java, so I don't know that I should contradict them or you.

However, I'll give two cents on this. Value and reference semantics (to me) generally relate to what happens when you copy something: do you copy the values (and have a genuine, new, fresh object), or do you copy a reference (so you have a new reference to the same thing). However, the whole point of Singletons is that they're not copyable at all. So in my mind, I wouldn't really think of a Singleton as having either semantics.

Now, in C++, this is a bit clearer: generally in C++ when you have a singleton, you can't get the "actual" singleton object, only a reference to it. And the reference of course has reference semantics, which says nothing about the semantics of the singleton, which is ok, because you can't get access to the actual singleton. In Java though, this is a lot blurrier because you generally manipulate all objects by reference. So it looks like a singleton is just behaving like any other by-reference object.


问:
Would you create a specialized type just to wrap a primitive?
Often times in programming, we need to represent some value which can easily be represented using a simple primitive type.

For example, in a game we might need to represent the velocity of a moving object. This could easily be represented with a double value. This object might also have a value of mass; this can also be represented with a double.

Some would argue that we should have a Speed type and a Mass type for each of these, instead of the general-purpose double type. The argument for that is that this way we take advantage of 'strong-typing'; the compiler doesn't let us pass a speed for a mass or a mass for a speed and make mistakes like those.

This argument makes sense. However, I can't help but thinking that this would be an overkill.

So what would you use? A simple double (following KISS and keeping everything as simple as possible) or a type made for a specific purpose?

答:
I would say yes if that type has a meaning more than just the simple value. In your example,  Speed and Mass might be represented by a double, but they have different meanings, and they have different calculations that can be done on them.

I can tell you from personal experience that doing this (it's called micro domain btw), has made my code much more readable and saved me lots of times from passing the wrong variable by mistake.


问:
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>

答:
Having a good user interface and providing an adequate learning experience goes a long way towards preventing users from doing bad things.

Good user interfaces should be
frictionless.

Instead of throwing up a dialog box (an expensive operation, and one that users ignore after awhile) to confirm a delete, perform the delete, and offer a way to undo.

Good user interfaces should be
discoverable.

Although the ribbon in Microsoft Office gets a lot of flak because it forces old users of Word to change their ways, the ribbon is a shining example of how you can make an interface discoverable (i.e. easy to discover).

Good user interfaces, like good code,
should be self-explanatory.

Nobody reads the manual.  The only manual I ever got my users to read was a PowerPoint presentation containing step-by-step walkthroughs of the software.  I have seen these done with video tools like Camtasia, but PowerPoints are better because you can easily flip backwards and forwards through the steps.


答:
You could probably figure this out by checking over the use cases of a quick sample. I'd say this makes sense if you can easily summarize and implement each of the use cases of, say, a numerical type. The entire point of a type system is to help you realize when you're working with the wrong type, and that can catch lots of issues before they happen. It could also make it easier to change the arguments of a method if you decide to, say, reorder "position / velocity" so it reads better; everything that doesn't match will throw a compile error.

But if you have a type that is always added to, subtracted to, divided, and all kinds of different math operations in various service classes, and doing so without taking out the primitive type is annoying, then that may indicate there's a better design for it.

Since all primitives have something they're being used for (self-obvious), it's possible to mis-apply that principle; it would of course be overkill to do things like wrap an "enabled:Boolean" property as "enabled:EnabledState" unless you had a very good reason (cvars, in a video game, might be a good example but I have not implemented such a system before)

Title: Would you create a specialized type just to wrap a primitive?

Body:
Often times in programming, we need to represent some value which can easily be represented using a simple primitive type.

For example, in a game we might need to represent the velocity of a moving object. This could easily be represented with a double value. This object might also have a value of mass; this can also be represented with a double.

Some would argue that we should have a Speed type and a Mass type for each of these, instead of the general-purpose double type. The argument for that is that this way we take advantage of 'strong-typing'; the compiler doesn't let us pass a speed for a mass or a mass for a speed and make mistakes like those.

This argument makes sense. However, I can't help but thinking that this would be an overkill.

So what would you use? A simple double (following KISS and keeping everything as simple as possible) or a type made for a specific purpose?


答:
The question seems to specifically ask for constant time, and not an amortized constant time. So with respect to the quoted question, no, they are not effectively the same*.  Are they however in real world applications?

The typical issue with amortized constant is that occasionally you have to pay the accumulated debt. So while inserts are generally constant, sometimes you have to suffer the overhead of reinserting everything again when a new block is allocated.

Where the difference between constant time and amortized constant time is relevant to an application depends on whether this occasional very slow speed is acceptable. For a very large number of domains this is generally okay. Especially if the container has an effective maximum size (like caches, temp buffers, working containers) you could effectively pay they costs only once during execution.

In response critical applications these times may be unacceptable. If you are required to meet a short time turnaround guarantee you cannot rely on an algorithm that will occasionally exceed that. I have worked on such projects before, but they are exceedingly rare.

It also depends on how high this cost actually is. Vectors tend to perform well since their reallocation cost is relatively low. If you go to hash map however, the reallocation can be a lot higher. Though again, for most applications probably fine, especially longer lived servers with an upper bound on the items in the container.

*There's a bit of an issue here though. In order to make any general purpose container be constant time for insertion one of two things must hold:

The container must have a fixed maximum size; or

you can assume memory allocation of individual elements is constant time.


答:
Automated testing would be a term for just running the tests every day, even if you only merged the code into a complete state once a month, or never.

Arguably a bad idea, because if you keep different strands of development in different long running branches you will be merging the tests and code at the same time. And if the features interact in any way, merging them should move some tests from passing to failing; if not, you weren't testing things adequately.

As a result, it becomes hard to figure out which tests failures are regressions, which are to be expected given the current state of integration, which have been temporarily disabled, and so on. In other words, interpreting the test results becomes a manual process, even if the execution of them is automated. Which risks wasting the effort put into automating the test in the first place.

One partial way round this is to have all automated test be strictly unit tests; literally one class at a time, mocking everything else with no exceptions. And then do all other testing either manually, or via some automated system outside the scope of the repository and its branches.

Title: Is continuous integration more than just automatically testing code?

Body:
Is continuous integration about more than just automatically testing code, either periodically or after every commit to the main repository?

Before today, I'd heard the term CI, and about CI services such as Jenkins, and RunCodeRun, and assumed that it was merely about having a server independent of developers' machines that checked that the automated tests of a project passed, and alerting people if it doesn't.

However, Wikipedia's definition seems to be different.

If my understanding of what CI is is incorrect, is there any term that merely refers to automatically running tests on an independent server?


答:
It depends on the language as well as how much effort you are willing to invest for increased correctness.  There is a delicate balance between "concise code" and "rigorous code", but the location of this will vary from language to language and also depending on personal taste and circumstances.  For example, if you're just prototyping, it may not be worthwhile at all.

In some cases, the benefit is worth the extra cost – the most commonly cited example are string wrappers that allow unsafe input strings to be distinguished from strings written by the programmer, thus reducing the risk of an accidental injection attack when these strings are concatenated carelessly.

One can do the same with quantities too.  Some languages even have libraries that allow you to deal with units in a general way, if the type system is powerful enough to support such a feature.

Performance-wise, many languages are capable optimizing out trivial wrapper data types, so it may not have any performance impact at all, except perhaps reducing compilation speed slightly.


问:
At which point using string-based enums can become a real problem?
This is a direct follower to this question. An answer given to that questions says (my understanding), that nowadays using string-based enums instead of integers isn't a much problem, because hosting costs and general DB costs are today much, much lower, so we can afford for some "database size waste" (generalization).

I'm interested, at which point this can turn itself around and even in nowadays become a real problem?

Suppose I have a table with n columns, out of which four columns uses string-based enums instead of integers. Assume, that each enum is 8 characters long, if that matters (probably yes -- string column size). Now, suppose, that I'm filling this table with records. When I may start thinking, that using enums was a wrong decision?

At 100k records? At 1M records or maybe not before reaching 1G of records?

Is there an easy way for me to determine:

what would be size difference, if my database with n records would be using integers instead of strings?

what general database size could become a real problem for my hosting?

I've heard that on simple, shared hosting a 1 GB database size becomes a problem and bigger databases are not allowed / not much liked by hosting's admins. But, since I'm a complete database newbie, I don't know, if that is true? And how does it becomes, when we talk about VPSs or even dedicated hosting?

答:
The problem is not space. Because space is cheap.

It really takes a good book to explain what is wrong with repeating texts in a column, but it's a bad idea. You will get it when you read about database normalization. Database normalization is what strong typing is for programming languages. You can live without, especially for very small projects, but it's way easier to end up with a complete mess. So for starters, do it the traditional way.

Basically, you should have a lookup table with all your values and the primary key of said table should be in the table where you would have entered the text. As a foreign key relationship.

This means the database has to join those two tables. But that's a databases job. Only if you think you have such a heavy load that you need to optimize (hint: as long as you are only talking about millions of records and gigabytes, you don't), you should flatten your table relationships.

Again, read a good book about database design first, it will save you a lot of headaches.


问:
Naming convention for getting the primitive backing a type?
I have a class that is backed by a double value, and I am wondering about accessor method names that preserve abstraction. Based on my experience in Java, there seems to be at least two precedents:

toDouble(), which mirrors toString()

doubleValue(), similar to Double.doubleValue() and BigInteger.doubleValue()

I need access to this value to perform some computations. Would it be most appropriate to return a double value as I've mentioned, or provide public multiply(), add(), etc. methods?

Is there any common practice or precedent for a class used in this way?

答:
Is there any documented preference, in Java, for either of these conventions?

The preference is that the end user has no idea what the backing primitive is for your type. This is encapsulation at its essence.

Now, if your object exposes an interface to get a double (regardless of what the backing datatype is), either because you're serializing your object, or because it makes sense to provide that interface, then do so. But the naming convention needs to specifically focus on what the data is (be a serialized form, seconds since unix epoch, etc.) not what it does (serve as the implementation details of your object).


答:
F# solves this problem nicely with measures:

```<code>[<Measure>] type cm
[<Measure>] type ml = cm^3
</code>```

For other languages, its a tradeoff (like everything). Encapsulating primitives may have an impact on performance and space, but has benefits in type safety. You may confuse younger developers (and possibly older ones too), so there are potential readability issues, as well as productivity losses if you don't implement the thing correctly, or if the language doesn't allow you to fully implement something like this. For instance, would you be able to implicitly cast to your new encapsulated type? MyNewType i = 2; How does equality work? i == 2. etc.

Body:
F# solves this problem nicely with measures:

[<Measure>] type cm
[<Measure>] type ml = cm^3

For other languages, its a tradeoff (like everything). Encapsulating primitives may have an impact on performance and space, but has benefits in type safety. You may confuse younger developers (and possibly older ones too), so there are potential readability issues, as well as productivity losses if you don't implement the thing correctly, or if the language doesn't allow you to fully implement something like this. For instance, would you be able to implicitly cast to your new encapsulated type? MyNewType i = 2; How does equality work? i == 2. etc.


答: I'm in favor of the micro domain types as @Miki describes them.  I've done both and the code that has the custom types is easier to maintain than the code using primitive types, especially in large projects.  Making changes and/or finding uses is easier, and the compiler can help catch errors, too.  What's not to like?  Of course, C# has structs which makes using a wrapper practically free, for example, an array of structs is very efficient compared to an array of objects, and also, the CLR does particularly well with 1-element structs.  With Java, I think you pay a price for the wrapper (have they added value types yet?).</p>


问:
What is the middleware (if any) in web-service consumed by a website?
I am trying to identify the parts of an architecture.

The server (Python) acts as a web-service, delivering files and data. The client (JS) requests the data which it needs by sending xmlhttprequests to the server.

I read that there can be a "middleware" layer that connects the application with its node of the distributed system. The point of the middleware is to abstract away the underlying network communication

SOAP is given as an example for being a middleware protocol. I do not use SOAP (or REST) Does that mean I do not have a middleware? I'm using plain old HTTP for the communication. Is that enough of an abstraction to be called a middleware? On the other hand, HTTP is part of the TCP/IP stack, which makes me think it is a part of the network communication and not an abstraction thereof. That would suggest that I do not use/have a middleware.

What exactly is a middleware in this scenario?

further confusion

One part of the problem is that it's not very clear what the middleware actually is and that there are different definitions of it.

What I found so far and what I asked this question upon is that there exists one layer of middleware, per node in the distributed system. The middleware layers are not directly connected. It is the network underneath the middleware that ensures the connection. The middleware is there to provide an abstraction layer between the application and the network.

See this image:

Each middleware block is separate. that makes sense. Chances are that the middleware for Mac OS is an entirely different thing than the middleware for Windows. On each application builds upon its specific middleware.

Another way to think about it is that the middleware actually is pretty much the only thing that connects the nodes of the distributed system as can be seen in the image from wikipedia:

This looks like a contradiction. In one scenario, each part of the application talks to its individual middleware, which in turn talks to the node of the network. The middleware is the common base line that separates the distributed application from the distributed system underneath. In the other, the middleware is some big blob that spans across all nodes which means that there is no such thing as individual middlewares for each node.

I have the growing suspicion that everybody makes up their own interpretation of this not strictly defined terminology.

the answer

is that there is no (clear) answer. The accepted answer provides reasonable thoughts about the whole matter. The terminology falls apart if applied in a rigorous concrete way.

答:
Wikipedia has a suitable definition for Middleware.  It says:

Middleware is the software that connects software components or enterprise applications. [It] is the software layer that lies between the operating system and the applications on each side of a distributed computer network. Typically, it supports complex, distributed business software applications.

In other words, it's the software in the middle, in between systems.  It is the way that distinct software systems communicate with each other.

If you're working with heterogenous systems, the way you communicate with them, and the way you fulfill each system's expectations in terms of interface and workflow, can vary drastically from system to system.  Some systems are fairly straightforward to work with; they have standard web services and a sensible REST interface. Others may not have such niceties, and may actually require you to scrape their websites to get any useful information from them, or even import a text or binary file in some proprietary format.  The use of SOAP or REST does not necessarily define middleware, in that regard.

Some middleware attempts to map systems to each other through configurable interfaces, business rules and workflows.  Biztalk is one such attempt.  As different systems begin to converge on standardized ways of communicating with each other (i.e. REST models), such mapping should become less common; the programmer will put more focus on the business processes required to connect different systems together, rather than communication protocols.


答:
Actually, internally the database is not going to store your string representation of your enum in every record. It is effectively making a lookup table of it's own and translating the stored integer value to string (and back) when you interact with the database...

From: http://dev.mysql.com/doc/refman/5.0/en/enum.html

If you retrieve an ENUM value in a numeric context, the column value's index is returned.  For example, you can retrieve numeric values from an ENUM column like this:

mysql> SELECT enum_col+0 FROM tbl_name;

Title: At which point using string-based enums can become a real problem?

Body:
This is a direct follower to this question. An answer given to that questions says (my understanding), that nowadays using string-based enums instead of integers isn't a much problem, because hosting costs and general DB costs are today much, much lower, so we can afford for some "database size waste" (generalization).

I'm interested, at which point this can turn itself around and even in nowadays become a real problem?

Suppose I have a table with n columns, out of which four columns uses string-based enums instead of integers. Assume, that each enum is 8 characters long, if that matters (probably yes -- string column size). Now, suppose, that I'm filling this table with records. When I may start thinking, that using enums was a wrong decision?

At 100k records? At 1M records or maybe not before reaching 1G of records?

Is there an easy way for me to determine:

what would be size difference, if my database with n records would be using integers instead of strings?

what general database size could become a real problem for my hosting?

I've heard that on simple, shared hosting a 1 GB database size becomes a problem and bigger databases are not allowed / not much liked by hosting's admins. But, since I'm a complete database newbie, I don't know, if that is true? And how does it becomes, when we talk about VPSs or even dedicated hosting?


问:
How widespread is the use of arabic numerals in Japanese and Chinese?
I'm localising a times-table app aimed at children. I understand that the Japanese and Chinese languages have a variety of ways to represent numbers. I also have read that, particularly with Japanese, 0-9 are commonly used for representing numbers.

Is it appropriate to use arabic numerals (particularly in education apps) is in Japanese and Chinese culture?

I know that arabic numerals aren't the solution to representing number. I also know that Japanese and Chinese cultures are completely different; however they are both very large markets with some similar challenges in localisation. I also know that large and small numbers (like 1,001 or 1.001) are formatted differently. This question is specific to integers less than 999 and greater than 0.

答: I asked a colleague who is a principal at an international school in China about this. She said that numerals are commonly used in China to represent number, and that arabic numerals are most appropriate for this use-case. This explains the way iOS handles the localisation of number for Chinese locales - converting words but leaving number as-is, even when using NSString localizedStringWithFormat: and NSNumberFormatter localizedStringFromNumber:myNumber numberStyle:NSNumberFormatterDecimalStyle].


问:
find second smallest element in Fibonacci Heap
I need to describe an algorithm that finds the second smallest element in a Fibonacci-Heap using the Operations: Insert, ExtractMin, DecreaseKey and GetMin. The last one is an algorithm previously implemented to find and return the smallest element of the heap.

I thought I'd start by extracting the minimum, which results in its children becoming roots. I could then use GetMin to find the second smallest element. But it seems to me that I'm overlooking other cases because I don't know when to use Insert and DecreaseKey, and the way the question is phrased seems to suggest I should need them.

答:
a=extractMin; res=getMin; insert(a);return res;

[Folks: when answers are posted as comments, would you please add them as an answer and close the question. Thanks]


问:
Does it make sense to use jQuery in modern-webkit-only web applications?
I'm lately working on a few mobile web apps for Android (2.3+) and iOS (4+). Their browsers support most of ECMAScript5, which is very powerful, and I wanted to use language features where possible, resorting to jQuery only when I had to.

Turns out the only thing I use jQuery for is to have a shorter alternative for document.querySelectorAll. Might as well get rid of it.

If I only have to support modern WebKit browsers, is it a good idea to get rid of jQuery (and other general-purpose libraries)? They are a layer of indirection, after all.

(The apps don't have to make AJAX calls so far, I guess that's one thing that's going to get ugly. But is it worth keeping jQuery just for that?)

答:
I'd say, when you don't know what to do, just use jQuery.

jQuery has lots of value, handles edge-cases and avoid headaches for you: https://decadecity.net/talks/what-has-jquery-ever-done-for-us

Using jQuery is standing on the shoulders of giants.


问:
Using auto-increment clustered key and guid primary key together
My boss is the db administrator in a new software project and he came up with that design where every table will have both a auto-increment clustered key and a guid primary key (or possibly composite guid keys on some rare cases). Every relations between tables will still use pk as references, making the clustered field never used in views, procedures, functions or any code at all.

I'm no db guru, but I wonder if in this scenario it's even worth having a clustered index at all? I mean, won't records systematically be added to the end of tables? If so then why would I need this field?

答:
It is not unusual to have several keys in a table and there's nothing fundamentally wrong with that. If a table has more than one key then the choice of "primary" key is unimportant - or only as significant as you want to make it.

Your boss is correct that it is usually a good idea for every SQL Server table to be clustered. Guids don't make for good clustered indexes and where there is no decent candidate for clustering it sometimes make sense to add an incrementing integer key for clustering. What I think is wrong in this case is the suggestion that you do this for every table. Key selection should be based on actual requirements and practical considerations for each table. One size fits all solutions are really no help.


问:
Efficient way to handle foreign keys
I am building a script that checks a large network of sites for invalid links. The idea is to flag links that continuously show as not available so that they can be cleaned by the administration team.

The basic process is this:

Grab a set of pages - approximately 30K per day, not the same 30K each day - and extract all links from the pages

Insert Unique URLs into the Links Table

Insert records into LinksInPage containing the anchor text for each link as well as the associated LinkID for each link

Check the status of each link utilizing HEAD/GET methods and inserting results into the LinkResults table

I am currently planning on building this database structure in an relational database.

Tables:

Links

LinkID     (auto inc)

URL    (varchar)

LinksInPage

LinkID (foreign key to Links.LinkID)

AnchorText (varchar)

Page URL   (varchar)

LinkResults

LinkID (foreign key to Links.LinkID)

DateOfCheck (date)

StatusCode (int)

NumFailures (int)

My question:

How can I efficiently handle non-unique links in this situation (I'm open to completely changing how the database is laid out)?

For example, on day one if I check example.com, I insert a record into the Links table. On day two, if I have another page that also links example.com, I don't want
a duplicate entry in the Links table, but I do need a record in LinksInPage that points to the same LinkID. At, assuming at least one link per page, 30K links daily I don't think querying for a LinkID at each insert is going to be efficient.
Storing everything in memory also seems like it will lead to problem in the future as the number of links gets larger.

I also need to be able to handle the LinkID when inserting link results. Again, looking up the LinkID at each insert seems inefficient.

The plan is to build this utilizing Python.

答:
looking up the LinkID at each insert seems inefficient

You never tested it, I assume? Sounds like a typical case of premature optimization. Using proper indexing, especially for the URLs, should make a query for an URL roughly as fast as an INSERT into the same table (maybe the INSERT will become a little bit slower since the index has to be updated). And when I understood you correctly, you will need about one SELECT query per INSERT. So the speed will mainly depend on the kind of database you pick, the network latency betweeen you application and the database, and if you create the correct indexes. Running time will not grow by an order of magnitude just because you have to make one lookup for existing elements before you do an INSERT.

So my advice is: implement and measure. If you actually have a bottleneck, you might look for further improvements like utilizing stored procedures, fine tuning your code or your database.

Title: Efficient way to handle foreign keys


答:
Enums are not only faster to insert, delete, update and read. They also take up less disk space, and most importantly: they ensure that you can only store a limited set of values.

If you create a field, and you only want to allow values "male" or "female", then an enum is handy to make sure that nobody stores "man".

Text fields are just a bad solution to store a limited set of values, for similar reasons that you shouldn't use text fields to store numbers or dates, regardless of the performance implications.


问:
Why should I use lookup tables at all?
This question confirmed, what I was already aware of -- instead of directly storing strings in table, I should rather use integers or enums and join them with lookup table, to get, as a result, string, that I actually want.

But, why should I use lookup at all? If I'm getting an integer from base table, what prevents me (or what should prevent me) from loading lookup values from file (for example an associative array stored in text file or directly in .php file, in case of PHP) and using them this way? Isn't that faster?

I'm trying to make this question general (that's why asking on Programmers, not on SO), but since I'm PHP programmer, PHP-based example is the only that comes to my mind. Assume, that I have a file containing:

```<code><?php
    return array
    (
        '1'=>'male',
        '2'=>'female',
        '3'=>'unspecified',
        '4'=>'unknown'
    );
?>
</code>```

Why shouldn't I use it as my "lookup solution", instead of replicating the same dataset in lookup table?

答:
I think you are confusing a few different things here.

1: database normalisation.

The question answer you link to is about normalizing out repeated data into a second table with a FK. The key needent be an int and will be repeated, so if your data is JUST the key you are already normalized.

2: ints as keys (due to space?)

You suggest that using an int is better as a key, but this is contaversial. GUIDs are another option and strings can be used.

3: persisting enum values

So an enum will eval as an int, but if you only store the int -> name relationship in your code and not the db you have potential issues if you ever change the enum.

If you replicate the enum in a lookup table then you double up on this problem and will need some way of syncing code with db.

Its usualy best to persist an enum as a string, as this carries the meaning and an enum is not a 'display string' that will change, be translated etc

So taking these together, where you have a poco object with an enum field. i recommend storing the field as a string in a db table with cols which match the objects properties. Ie

Person

Id -> some guid

Name -> fred

Sex (ENUM) -> male

Where the property is a class with more than one property you should use a FK to another table. Ie.

address (class) -> (addressId col) some guid

If you treat the enum like a class and move it out to a lookup table you can achieve space savings if you have many rows and few enum values Eg.

Sex(enum) male -> (sexId [short] ) 0

Sex

id [short]

Name [varchar(50)]

But the id and FK relationship should be purely at the DB layer. You shoud still return the Name from queries and deserialise that  string back to your enum rather than mapping the short Id to your enum int.

However, this is an optimisation rather than a normalisation and you are only saving space, which as your referenced question says, is cheap. Personally I tend to leave this kind of thing to DBAs

Consider for example you will need an insert sproc, which takes the enum string, checks the lookup table to find the short id, adds the enum to the lookup table if required and then uses the short id for the insert. So there is a downside to the optimisation as well as an upside

Title: Why should I use lookup tables at all?


答:
You are suggesting a client-side join: Fetch some data from the database via a query, and then in code you perform further joins via lookup tables loaded from files.

This is almost certainly going to be slower, and definitely more complex than just doing the join in the database. Think about it - why should you be able to write you own join-logic to be faster than what happens in a database? Unless you have very specific requirements (e.g you want to minimize the amount of data returned from the database) I don't see any advantages to performing the join on the client side.

Title: Why should I use lookup tables at all?

Body:
This question confirmed, what I was already aware of -- instead of directly storing strings in table, I should rather use integers or enums and join them with lookup table, to get, as a result, string, that I actually want.

But, why should I use lookup at all? If I'm getting an integer from base table, what prevents me (or what should prevent me) from loading lookup values from file (for example an associative array stored in text file or directly in .php file, in case of PHP) and using them this way? Isn't that faster?

I'm trying to make this question general (that's why asking on Programmers, not on SO), but since I'm PHP programmer, PHP-based example is the only that comes to my mind. Assume, that I have a file containing:

```<code><?php
    return array
    (
        '1'=>'male',
        '2'=>'female',
        '3'=>'unspecified',
        '4'=>'unknown'
    );
?>
</code>```

Why shouldn't I use it as my "lookup solution", instead of replicating the same dataset in lookup table?


答:
If you are asked for an "amortized constant time" algorithm, your algorithm may sometimes take a long time. For example, if you use std::vector in C++, such a vector may have allocated space for 10 objects, and when you allocate the 11th object, space for 20 objects is allocated, 10 objects are copied, and the 11th added, which takes considerable time. But if you add a million objects, you may have 999,980 fast and 20 slow operations, with the average time being fast.

If you are asked for a "constant time" algorithm, your algorithm must always be fast, for every single operation. That would be important for real-time systems where you might need a guarantee that each single operation is always fast. "Constant time" is very often not needed, but it is definitely not the same as "amortized constant time".


问:
Strategies to analyze collected exceptions
We want to add error feedback to our application. I had a look at existing solutions (e.g. raygun.io), but these work "in the cloud", which is a no-go for us:

most installations of our application are offline, so we will need to export the collected logs to a file and then send it per email.

I don't feel comfortable uploading exception details to a third party server because of privacy concerns. (some of our clients would probably kill us).

Now, just logging these exceptions is not that hard. I have attached handlers to AppDomain.UnhandledException and AppDomain.FirstChanceException and then write them out to a small SQLite DB.

But the question for me is how to best analyze them. Analyzing them by hand would cost too much time, so we need to at least be able to group them into "buckets" and order them by number of occurrences, etc.

I do have some ideas in mind where I compare callstacks and messages, etc, but I feel like someone else MUST have done the same already.

Do you know of good strategies to classify exceptions and group them?

答:
I have no detailed solution for this but my approach would be to make sub classes of
the exceptions you catch and store + analyse and implement some information about the exception type.

```<code>public enum ExceptionDanger
{
    Low,
    Middle,
    SecurityCritical
    // And so on
}
</code>```

Now we add this to the derived exception class:

```<code>public class MonitoredException : Exception
{
    public readonly ExceptionDanger danger;

    public MonitoredException(string message, ExceptionDanger danger)
        : base(message)
    {
        danger = danger;
    }
}
</code>```

And in the AppDomain.FirstChanceException event subscriber we use the information to build a new log info (same for AppDomain.UnhandledException):

```<code>static void FirstChanceHandler(object source, FirstChanceExceptionEventArgs e)
{
    var monitoredException = e.Exception as MonitoredException;
    if(monitoredException != null)
    {
        var exDanger = monitoredException.danger;
        var exType = monitoredException.GetType().Name;
        var exTimestamp = DateTime.Now;

        // Build a package like a struct or so and exDanger, exType and exTimestamp to it
    }
}
</code>```

Now when the server receives the package (that consists out of exDanger and exType) the data can be used for storing how many errors of this type were thrown and if you add a user ID to the package you can specify which users threw the exceptions.
The ExceptionDanger enum is to sort the importance of the exception serverside.

I hope this gave you tips or at least an idea on how to sort and analyse exceptions.

Body:
I have no detailed solution for this but my approach would be to make sub classes of
the exceptions you catch and store + analyse and implement some information about the exception type.

public enum ExceptionDanger
{
    Low,
    Middle,
    SecurityCritical
    // And so on
}

Now we add this to the derived exception class:

public class MonitoredException : Exception
{
    public readonly ExceptionDanger danger;

    public MonitoredException(string message, ExceptionDanger danger)
        : base(message)
    {
        danger = danger;
    }
}

And in the AppDomain.FirstChanceException event subscriber we use the information to build a new log info (same for AppDomain.UnhandledException):

static void FirstChanceHandler(object source, FirstChanceExceptionEventArgs e)
{
    var monitoredException = e.Exception as MonitoredException;
    if(monitoredException != null)
    {
        var exDanger = monitoredException.danger;
        var exType = monitoredException.GetType().Name;
        var exTimestamp = DateTime.Now;

        // Build a package like a struct or so and exDanger, exType and exTimestamp to it
    }
}

Now when the server receives the package (that consists out of exDanger and exType) the data can be used for storing how many errors of this type were thrown and if you add a user ID to the package you can specify which users threw the exceptions.
The ExceptionDanger enum is to sort the importance of the exception serverside.

I hope this gave you tips or at least an idea on how to sort and analyse exceptions.


问:
How can I make an object/class inaccessible to Reflection
I am building an API for minecraft called the Quantum API. We all know that reflection can be used to do some nasty stuff to classes, and even cause undefined behavior if used without care.

Is there a way to make classes and objects immune to reflection? Perhaps with a security manager? Or vice versa, restrict a certain list of classes/objects from using reflection?

My use would be to prevent other mods that are loaded with this API from using reflection to change a RuntimePermission in a SecurityManager, and to prevent modification of minecraft's base classes (and objects) at runtime, as well as the API's own classes (and objects).

答:
I would suggest using obfuscation.  It doesn't prevent reflection, but it'll make it practically impossible (technically, someone could still do it but it'll take them far more effort to figure it all out) for someone to figure out what part of the code does what, as it'll (amongst other things) scramble the names of functions.

You can usually set exclusions, such as functions that need to be publically accessible for an API.

Unfortunately, it'll only work for your own code, and not Minecraft itself, but it's the best practical solution I can think of.

Otherwise, I think there might be a solution that involves making your own custom loader for Minecraft with a SecurityManager that sandboxes everything and prevents reflection, but I'm not entirely sure if that's possible.  You may want to look at this question on StackOverflow which discusses that possibility further.


问:
How to handle short notice (but high priority) maintenance tasks in SCRUM
currently shifting to SCRUM, we wonder what should be done exactly in the specific case :

Our analytics team need some script to be updated on the site we're managing. It occurs on a regular basis (possibly several times a month), but with no exact schedule, and they require  this to be done "ASAP". This somewhat "emergency" wouldn't allow us to use the normal process for devs which would imply to have it in the product backlog in order to put in in the sprint backlog during sprint planning meeting. But this is not an incident neither and from what I understood incidents are the only tasks that should enter the sprint backlog during the sprint (we have a contingency for that). Shortenning the sprints wouldn't be an option neither as they're already only 2 weeks long and for most of the tasks this is very appropriate. What are our options ?

Thanks !

EDIT : I need to mention SCRUM is not an alternative here (or actually is the only one we can use). We're in a big corporation deploying agile methodologies and enforcing SCRUM. DevOps Teams using scrum are just the end of a End-to-End delivery model based on SAFe, with a whole process before an item makes it to the product backlog (which is defacto less AGILE than what it should, but as simple employees we don't get to choose, "empowered" is more a good intention than reality...). In other words, if the answer implies switching methodology, we can't really apply it, especially as SCRUM fits well for most of our tasks, only a few don't quite find their place in this model...

答:
If those maintenance tasks happen without a predictable schedule, why not classify them as incidents? If all you have is a hammer, your task becomes a nail.

Alternatively, enter several tasks into your backlog labeled "examine the scripts and update as required." Pull one for each week of the sprint, close them when you've either changed the script or determined that no change is necessary.

But that's trying to fit square pegs into round holes. Are those script updates so much work that you need them tracked on the board? Each programmer should have some time to spare for things that need doing, without ticket.