问:
What happens if I close an InputStream that is passed as an argument?
I have read that Java is pass-by-value, and I've been reading about it in  this question at StackOverflow, but I'm still a bit confused, regarding the close() or shutdown() methods in various classes.

What I want to know is, suppose that I do this:

```<code>public Constructor(){

    if(isProceeding){
        InputStream iStream = new InputStream();
        processStuff(iStream);
    }
}

public void processStuff(InputStream stream){
    //do stuff
    stream.close();
}
</code>```

Does the iStream variable actually get closed in processStuff() method or a copy of it gets closed and iStream itself is still left open?

答:
Objects that are passed around to other methods can be changed by the method, and the caller will notice the change. If you let someone else use your Stream, they might close it and you'd never notice until you try to write and fail. That's why it's usually a good idea not to pass mutable objects around outside your control.

Confusion often arises because many textbooks categorically say "Java has pass-by-value semantics". That is technically true, but not very helpful for a language learner. Technically, it's not the object that gets passed around but a reference to an object,
and the called method gets a copy of the reference, which of course references the same object.

But in practice, the difference between object and object reference is often not clear in people's minds. Nobody is ever interested in the value of a reference other than to check whether or not it is null. In fact, Java doesn't even have a dereferencing syntax apart from the member selector .. What people care about is the state of the underlying object. So effectively this means that mutable objects are passed by reference in the sense that the caller gets to change them, and you might be affected by that. In this sense, the textbook explanation is correct and useful for primitive types, but correct and misleading for object types.


问:
Can someone help me understand MVC?
I've read a few articles on the MVC pattern and tried to understand what it exactly is. But till now, what I get is a plain diagram showing 3 modules of Model, View and Controller. Some say that it helps increase code reuse (DRY), while I think it does the opposite.

I currently separate my application code into different directories, one for Viewing part (presentation: Html/Css/Js + client side req) and the other one for Core related functions. I haven't found any disadvantage to this approach yet. Maybe because I haven't developed big applications yet, just small hobby ones.

So, apart from this separation, what I find in MVC is some sort of url rewriting, which I think can be achieved if necessary. Is there something I am missing? There must be a reason developers are so inclined towards the MVC pattern.

答:
Model
The model represents the domain you are trying to model, and also encapsulates the business logic of your application. For example, using the good old blog example, think about all the things your make up your blog: Posts, Comments, Tags, Categories, Authors, Commentors, Editors, Feeds, etc.

This is your domain, and depending on which of those you want to work with in your application, you model them as the M in MVC. For example, you would create a Post model to represent a post that a user makes or a Comment model to represent a comment that a user makes. Most frameworks allow models to have have relationships with other models. For example, a model can 'own' one or more other models, or belong to one or more other models, or both at the same time. These relationships are typically expressed as:

One-to-One

The simplest type of relationship, a one-to-one relationship between two models simply says that one model owns the other.

One-to-Many

Since your authors create posts, you could reason that your Author model owns many Post models. This is expressed as a one-to-many relationship where your Author model is the one side of the relationship and your Post model is the many

Many-to-One

The opposite of the above relationship, one or more Post models belong to one Author model. Here, your Post model is the many side of the relationship and the Author model is the one

Many-to-Many

Sometimes, you have the scenario where you want many models to belong to or own many other models. Think about tags on your blog post. You would want to be able to associate many tags with many posts. Therefore, your Post/Tag models have a many-to-many relationship with each other.

Models are where you want your business logic to go. For example, lets say you wanted authors to be able to upload an image along with their posts, but you only wanted images of a certain size/dimension. The business logic for checking the images file size or changing its dimensions would go in the Post model, since that image is a property of the Post model and belongs to it. This leads to the saying that your models should be fat and your controllers skinny. A common mistake that new comers to the MVC pattern make is putting all the business logic in the controller and having empty models that just represent rows in a database (e.g., doing the image re sizing logic in the controller rather than the model).

Normally, you'll interact with databases using an ORM (Object Relational Mapper). If you are using a popular framework like Ruby on Rails, Laravel, Symfony, the ORM typically uses the ActiveRecord pattern. Some would argue that ActiveRecord is a bad pattern because it means that your models are responsible for persisting themselves to the database as well as their own internal business logic. Models don't have to be persisted to the database, but when they are their values are stored a row in a table in a database. They are not the row or even the database as another answer suggests. Typically the model's values will be stored in just one row, but you can (if you really, really want to) store them across multiple rows in different tables/databases. Other frameworks handle this differently. For example in ASP.NET MVC models are not responsible for persisting themselves to the database. Whether one is better than the other is debatable. I use both Rails and ASP.NET MVC and appreciate both approaches where it makes sense (simple applications with simple models ActiveRecord is great). The main problem with the ActiveRecord approach is that your model has to be the same as the table that you are saving it to in your database. If you have a much larger table and you want to extract data from it and map it to a model (think pre-existing/legacy data) becomes tricky.

View
Views are the simplest part to understand, because they are simple by nature. The convention with most MVC frameworks is that your views should be dumb. That is, they should not perform any business logic (that is done by your models, remember?). All they do is receive data from the controller and display in a way that looks nice to the user.

While your view shouldn't be performing business logic, you can have some client side logic in there. For example, if you have a view to display a list of posts or authors, you can use JavaScript to allow users to do things like dynamically change the ordering of the list (without having to make another HTTP request to your application). The point is that they can apply some processing to the data they receive, it should be only for the purposes of displaying the data in a different way, not changing it.

Controller
The controller is the glue that holds your application together. Think of them like the conductor in an orchestra. While they don't actually play any instruments, the orchestra wouldn't be able to function without them. Your controllers are the same. They interpret requests from the user and perform the necessary operations to produce a desired result.

Typically, when your user enters a URL (let us say posts/show/my-first-post) your MVC framework (Rails/Laravel/ASP.NET MVC/whatever) will have a routing engine that will parse the URL and determine the correct controller to invoke. Usually, your URLs will follow some sort of convetion that makes this easy. Let us say you are using a convention where the URL segments relate to {controller}/{action}/{id} where the first segment is the controller to invoke, the second segment is the action on that controller to use, and the third (or however many parameters you wish to pass to the controller) are passed to that controller's action as parameters. So, if you had a post controller with a show action that took one parameter, id the routing engine would pass along the HTTP request to it.

Typically, your controller will invoke a model (which performs some business logic and returns a result) and then passes that result along to the view for your user to see (in the form of a web page).

ContentLicense: CC BY-SA 3.0

Title: Can someone help me understand MVC?


问:
Differences between Direct, Composition, Aggregation, and Temporary Association
I am looking to take my java certification very soon, and I have a question about the different types of associations described in the official oracle guide book.

The book describes the 4 as the following:

Direct = "has-a"

Composition = "composed-of"

Aggregation = "part-of"

Temporary = method parameters or local variables inside a method etc..

I understand the examples they provide, but when shown a piece of code I can never figure out why it is one type over another. To further my frustration these don't seem to be common terms in uml diagrams and composition or aggragate is usually described as a "has-a" relationship depending on where you read.

Here is a link to the book. http://www.amazon.com/Programmer-Study-Guide-1z0-803-Oracle/dp/0071789421

Pages 386-388 describe the different associations. Code examples would be very helpful.

答:
HAS-A Relationship

Has-A means an instance of one class “has a” reference to an instance of another class or another instance of same class.
It is also known as “composition” or “aggregation”.
There is no specific keyword to implement HAS-A relationship but mostly we are depended upon “new” keyword.

Composition :

Without existence of container object, if there is no chance of existence of contained objects then container and contained objects are said to be strongly associated and this strong association is known as composition.
Eg: A “university” has several “departments”. Without existence of “university” there is no chance for the “departments” to exist. Hence “university” and “departments” are strongly associated and this strong association is known as composition.

Aggregation

Without existence of container object, if there is a chance of existence of contained objects then container and contained objects are said to be loosely associated and this strong association is known as aggregation.
Eg: A  “department” has several “professors”. Without existence of “departments” there is good chance for the “professors” to exist. Hence “professors” and “department” are loosely associated and this loose association is known as Aggregation.

Example For "Has-A" and "is-A" Relationship:

```<code>Class Library extends School

   {

          Book b=new Book();

          CD cc=new CD();

   }
</code>```

Let us take one example.

Has-A:

```<code>    Library needs book and cd to run library. If you don't have book and cd then it
</code>```

can't be a Library. So Library "has a" relationship with Book and CD.

IS-A:

```<code>    Assume that Library placed inside a school and prohibited to use Third persons
</code>```

(outside) and only school person can able to use that Library. So Library(class) "is a"

relationship with School(class).

Temporary:

```<code>    1.Temporary variable or Local Variables or automatic variables have its lifetime
</code>```

within blocks ( i.e { and } braces), methods and constructors.

```<code>    2.Access modifiers cannot be used for local variables.

    3. Only final (non-access modifier) maybe used for local variables.
</code>```

Lets finish this with one small example program:

class TestAge {

```<code>int age; // Instance Variable age

public void exampleAge() {
    int age = 7; // Local Variable;
    System.out.println(" Age is : " + age); // prints 7,  Local variable age.
}

public static void main(String args[]) {
    TestAge test = new TestAge();
    test.exampleAge();
    test.age = 10; // accessing Instance Variable
    System.out.print(test.age); // prints 10, Instance Variable age.

}
</code>```

}

output:
 Age is : 7  10

Hope you understood. Thank You :)

Body:
HAS-A Relationship

Has-A means an instance of one class “has a” reference to an instance of another class or another instance of same class.
It is also known as “composition” or “aggregation”.
There is no specific keyword to implement HAS-A relationship but mostly we are depended upon “new” keyword.

Composition :

Without existence of container object, if there is no chance of existence of contained objects then container and contained objects are said to be strongly associated and this strong association is known as composition.
Eg: A “university” has several “departments”. Without existence of “university” there is no chance for the “departments” to exist. Hence “university” and “departments” are strongly associated and this strong association is known as composition.

Aggregation

Without existence of container object, if there is a chance of existence of contained objects then container and contained objects are said to be loosely associated and this strong association is known as aggregation.
Eg: A  “department” has several “professors”. Without existence of “departments” there is good chance for the “professors” to exist. Hence “professors” and “department” are loosely associated and this loose association is known as Aggregation.

Example For "Has-A" and "is-A" Relationship:

Class Library extends School

   {

          Book b=new Book();

          CD cc=new CD();

   }

Let us take one example.

Has-A:

    Library needs book and cd to run library. If you don't have book and cd then it

can't be a Library. So Library "has a" relationship with Book and CD.

IS-A:

    Assume that Library placed inside a school and prohibited to use Third persons

(outside) and only school person can able to use that Library. So Library(class) "is a"

relationship with School(class).

Temporary:

    1.Temporary variable or Local Variables or automatic variables have its lifetime

within blocks ( i.e { and } braces), methods and constructors.

    2.Access modifiers cannot be used for local variables.

    3. Only final (non-access modifier) maybe used for local variables.

Lets finish this with one small example program:

class TestAge {

int age; // Instance Variable age

public void exampleAge() {
    int age = 7; // Local Variable;
    System.out.println(" Age is : " + age); // prints 7,  Local variable age.
}

public static void main(String args[]) {
    TestAge test = new TestAge();
    test.exampleAge();
    test.age = 10; // accessing Instance Variable
    System.out.print(test.age); // prints 10, Instance Variable age.

}

}

output:
 Age is : 7  10

Hope you understood. Thank You :)


问:
Should special (simpler) cases have separate code paths?
I have a rather complex method which can get called in two possible "scenarios". One is a special case of the other in which all the nested foreach loops are only executed once and several if statements are false such that essentially only two lines of code nested deeply inside the method are actually executed.

Now the question is: Should I provide a separate (simpler) code path for the special case even though the complex code handles that case just as well?

I suppose the code would be more readable/understandable that way but I don't want to give the impression that the two cases are handled differently.

Performance is not an issue here so the fact that a simpler code path might also execute faster is negligible.

Example code:

```<code>foreach(...)
{
    foreach(...)
    {
    ...
        if(...)
        {
            ...
        }

        Something();
    }
}
</code>```

as compared to

```<code>if(SpecialCase)
{
    Something();
}
else
{
    foreach(...)
    {
        foreach(...)
        {
        ...
            if(...)
            {
                ...
            }

            Something();
        }
    }
}
</code>```

答: To me it would be a balance of costs.  Would the extra development & maintenance cost be justified by the saved run-time cost?  You say "performance is not an issue," so you would be increasing expenditure with no payback.  Don't do it.</p>


问:
Refactoring previous intern's noodle code with future interns in mind
Background

I've run across this problem as I am currently an intern at a large company's local software division. I have been given the task of extending a project that several previous interns have worked on (not collectively but sequentially). The project is written in C# and is a relatively simple tool (codebase of about 10,000 lines)

The problem

The first intern started writing the tool using pretty much only lists and ignoring the fact that setting up data structures (such as objects) makes the tool much more extensible and readable. The interns that came afterward did not bother to change this and instead built upon the tool in the same manner. This led to a couple of massive methods ( +700 lines), lots of global variables (most variables were global), and just very bad organization.

My Approach

I spent countless hours in the debugger understanding the logic of the code and have (for the most part) a very good outlook on it. I have written the required data structures and am organizing as well as rewriting "black box" portions of the code in order to make it possible to add a new feature without spending +2 weeks trying to figure out what is going on. I am doing this not just for my own sanity but for the intern that will come after me. I am constantly trying to focus on readability and simplicity while avoiding solutions that are short, effective, but slightly esoteric to another intern. I am following general OOP design and trying to avoid pitfalls that come from blindly believing a certain method is the best method without researching it and understanding why and how its applied. I am leaning heavily to a top-down approach in terms of design and how the execution flow will be laid out as this seems to be easier for others to quickly understand and internalize, but am open to suggestions for alternative approaches or methodologies.

The Question

How would I go about balancing my wish to write good code and writing code is understandable to a relatively untrained intern (the assumption is that they are pursuing a computer science degree but are still in school) while having a good outlook for the future in terms of extendability?

Any help is greatly appreciated

答: The point of an internship is to learn. I would refactor the code to be better and ignore the assumed limitations of people you don't know. For all you know, the company will move that project to an internal team rather than interns soon.</p>


答:
The idea is simply to create a clear separation between business logic and the UI.

The Model is the data and the business logic of the application. The View is UI logic, and creates a visual representation of the Model. The Controller is mediating between the two to keep them loosely coupled.

Here's an example to help you understand. This relates more to desktop MVC, not web MVC, but the general idea is the same:

Imagine a text processing application. The user has just selected some text and pressed the 'Bold' button.

The View knows that a button was pressed, but doesn't (and shouldn't) know how to handle this event. So it notifies the Controller (e.g. controller.boldPressed()).

The Controller 'knows' what this means for the Model. Sometimes it would mean simply doing model.makeTextBold(), and sometimes it would mean something more complex, such as first fetching the selected text from the view, and then making several method calls on the model.

The Model then receives the method calls from the Controller, and performs the desired actions, i.e. making a piece of text bold. Note that the text is kept inside the Model - this is where the data is kept. The View is merely a visual representation of this data, i.e. a visual representation of the Model.

At the last step, the View has to be notified that the state of the Model has changed, so it can update itself (it's a visual representation of the Model). This is often done via the Observer pattern (learn it if your'e not familiar with it). Or, it can be done by the Controller.

The View is notified that the Model has changed and updates itself. And we got some bold text.

This is the idea. As you can see, the View knows nothing about how the Model operates, and more importantly, the Model knows nothing about the View. This loose-coupling makes things easier to maintain, because you don't have business logic in your UI event handlers, and no intimate knowledge of the UI in your business logic. And it can even mean that you can replace different Views or Models with minimal changes to the other parts of the system.

One last thing: note that sometimes the Controller may feel unnecessary, like all it does is pass method calls to the Model. In small applications, this will often be the case. But it's still good to have this separation layer, in case the application gets bigger.

Hope this helps.

Title: Can someone help me understand MVC?

Body:
I've read a few articles on the MVC pattern and tried to understand what it exactly is. But till now, what I get is a plain diagram showing 3 modules of Model, View and Controller. Some say that it helps increase code reuse (DRY), while I think it does the opposite.

I currently separate my application code into different directories, one for Viewing part (presentation: Html/Css/Js + client side req) and the other one for Core related functions. I haven't found any disadvantage to this approach yet. Maybe because I haven't developed big applications yet, just small hobby ones.

So, apart from this separation, what I find in MVC is some sort of url rewriting, which I think can be achieved if necessary. Is there something I am missing? There must be a reason developers are so inclined towards the MVC pattern.


问:
Spring Controllers and Services
we are at the middle of a project. It's a REST Service. Now we have controllers to handle the Requestmappings and the forwarding to the Services.
A concrete example we have a UserController, GroupController, UserService and a GroupService.

The user controller has as injection the UserService and the GroupController has as injection the GroupService. (one to one dependency)

When I create/update/delete a user then the scenario is simple: userControllers tells the userService and it do this.

Now the system has a lot of other controller/services that are going to be added.
But what I don't know is: what is the best way when I have to to mix user/group action?
For example: I have to add a user in a group. But I must check that the user exists, that the group exists and after save the information in the user (Entity/DTO) that the user is now port of this group.

1) schould I manage all from the userController:
-userService.checkUser()
-groupService.checkGroup()
-userService.updateUser()

2) or schould I manage al from the userService:
-userService.addUser()
(in the userService then:
  -checkUser()
  -checkGroup()
  -updateUser()
)

In the solution 1 what I don't like is the injection of some other Services that not belongs to users
In the solution 2 I have the idea that I'm going to replicate concepts that exists on the groupServices...

The exapmle above is only a litle part of the great picture. But that what i would understand is how can I design this part to don't have a lot dependency and a lot of code replication?

答:
It depends on how you want to structure your layers (controller, service, persistence).

Ideally controllers shouldn't mess with all the business logic, that's what services are for. The exception is for surface checks (validation, nullity, types).

Try to keep the Single responsibility principle in mind to help you structure correctly your code.

That's why I recommend what you describe as the solution 2.

Title: Spring Controllers and Services


答:
There are two things of note here: you seem to know quite a bit about good practices and the project is meant to disappear "soon" (though not right after you leave).

As Telastyn mentions, make the most out of this experience to learn what works and what doesn't and how to apply best practices in a real-world environment. Think about yourself first.

That said, best practices include keeping the code easy to understand for your colleagues, so as part of the learning experience, you should still strive to write good readable code. Using OOP to structure things properly is also a part of this and should naturally help make things easier to understand and maintain in the long run.

In my opinion, OO code should be easier to read because it's well structured, so I'm not sure why you need to make a choice between good code and intern-readable code. If interns do not know OOP well enough, this is an occasion to learn. I'd rather give good OOP code to new programmers so they immediately learn with good bases.

If you really feel the need to make things even more understandable, I'd consider adding comments to any part that, to you, is already looking complicated, such as when you struggle to get code you wrote days or a few weeks ago. If you struggle, imagine the effect on someone who never even wrote the code.

You may also go through your "old" code and suddenly realize a better structure based on later insights and you might spot duplicate code that can be turned into a function with parameters. That's when you may want to refactor what you have, if you feel confident the time spent doing it will truly help in the long run (still struggling with such estimates myself).

Adding unit tests or other form of test suites could also help you and anyone next as it can be run to ensure you haven't broken features of the existing code. I think it can be a great tool for newcomers as it's often hard to grasp the impact of modifying bits of code you don't know (even code you do know, really).

You might write some documentation on what your application should accomplish and giving insight into its most complicated aspects. Knowing what is expected behavior helps clarify whether you found a bug or a lack of feature (often a mixed up notion to final users).

Why not ask your colleagues? If they show knowledge of OOP and good practices and yet do not easily "get" your code, you could ask what they're struggling with and what's missing to help them understand.

Title: Refactoring previous intern's noodle code with future interns in mind

Body:
Background

I've run across this problem as I am currently an intern at a large company's local software division. I have been given the task of extending a project that several previous interns have worked on (not collectively but sequentially). The project is written in C# and is a relatively simple tool (codebase of about 10,000 lines)

The problem

The first intern started writing the tool using pretty much only lists and ignoring the fact that setting up data structures (such as objects) makes the tool much more extensible and readable. The interns that came afterward did not bother to change this and instead built upon the tool in the same manner. This led to a couple of massive methods ( +700 lines), lots of global variables (most variables were global), and just very bad organization.

My Approach

I spent countless hours in the debugger understanding the logic of the code and have (for the most part) a very good outlook on it. I have written the required data structures and am organizing as well as rewriting "black box" portions of the code in order to make it possible to add a new feature without spending +2 weeks trying to figure out what is going on. I am doing this not just for my own sanity but for the intern that will come after me. I am constantly trying to focus on readability and simplicity while avoiding solutions that are short, effective, but slightly esoteric to another intern. I am following general OOP design and trying to avoid pitfalls that come from blindly believing a certain method is the best method without researching it and understanding why and how its applied. I am leaning heavily to a top-down approach in terms of design and how the execution flow will be laid out as this seems to be easier for others to quickly understand and internalize, but am open to suggestions for alternative approaches or methodologies.

The Question

How would I go about balancing my wish to write good code and writing code is understandable to a relatively untrained intern (the assumption is that they are pursuing a computer science degree but are still in school) while having a good outlook for the future in terms of extendability?

Any help is greatly appreciated


问:
Why shouldn't an object reference have access to a static member in C#
Context of my question:

I am reading C#.

Trying to understand Static keyword.

I understand that when Static is applied to a member of a class, it can only be modified by the class and not the class object references.

I will take an example here.

```<code>public class BluePrint
{
   public static string BluePrintCreatorName;
}
</code>```

If I need to know the BluePrintCreator's Name, I can call

```<code>BluePrint.BluePrintCreatorName;
</code>```

But if a house that is created from the blueprint wants to know the BluePrintCreator's Name, it does not have access.

```<code>BluePrint NewHouse = new BluePrint();
NewHouse.BluePrintCreatorName; //This is not accessible
</code>```

Compiler error says:

Member 'AccessModifier.BluePrint.BluePrintCreatorName' cannot be accessed
with an instance reference; qualify it with a type name instead
```

I understand this is the way it works. But I want to know the basic concept to why Static keyword was required at all?

What will go wrong if a class object reference would have access to the static member?

答:
Consider the following (legal) Java code:

```<code>Thread workerThread = new MyWorkerThread();
workerThread.start();
workerThread.sleep(5000);
</code>```

At first glance, it looks like the last line is requesting that workerThread sleep for five seconds.  However, the Thread.sleep method is actually static, and makes the current thread sleep.

In C#, requiring static functions to be called through the class instead of an instance helps prevent writing misleading code like this.

Body:
Consider the following (legal) Java code:

Thread workerThread = new MyWorkerThread();
workerThread.start();
workerThread.sleep(5000);

At first glance, it looks like the last line is requesting that workerThread sleep for five seconds.  However, the Thread.sleep method is actually static, and makes the current thread sleep.

In C#, requiring static functions to be called through the class instead of an instance helps prevent writing misleading code like this.


答:
I learnt about this once but not from a book.. but hopefully this is not  inaccurate.

MVC stands for Model, View, Controller.

The View is the GUI

The model is most of your program, and the controller is part of your program that interfaces between your model and your GUI/view.

The benefit to that is that e.g. if there is a sudden change in requirements, and a new GUI is required, then when you have separated your program into those components, you only have to change one component. The Model part of the program won't have to be rewritten or amended. (perhaps the controller will need a little amendment but not much). And you just focus on writing the view portion. So your program is built to have different views.

Furthermore if you had to structure your program differently, in terms of how you store data, then you wouldn't have to rewrite code that describes the GUI.

Title: Can someone help me understand MVC?


问:
Do immutable objects that constantly change impact memory/performance?
I'm writing a program that goes into a loop and keeps changing the state of some models (similar to a game). Naturally, many things are mutable. However, I'm also writing some classes that are immutable because they're inherently treated like values (for example: vectors, matrices, etc.)

However, these values change on every loop (maybe 50-100 times a second). Does this mean that on every change, the program would need to allocate a new chunk of memory? If I'm using managed code, does this mean that the memory usage will build up very quickly? How does this impact determinism, performance, and garbage collection in languages such as C# and Java, especially when many garbage collectors have to pause the entire program in order to clear the memory?

答:
All structs are allocated on stack or is part of memory of containing class. Even if you allocate millions of structures, it is not going to impact memory. On the other hand, passing big struct around by value (not by reference) might impact performance, because it is copied every time.

On the other hand, allocating new class might impact memory consumption, because new class instance = new allocated memory. Also, it might impact performance, because GC needs to keep track of it and dispose it. There are some optimizations like Generational GC, but if you really need performance, it is best to manage the memory yourself.


问:
What's the shortest generating one-way hash algorithm?
I have a 24 character long id which is guaranteed to be unique. I would like to shorten that to 7-10 (or even shorter) characters long. If I generate an short id randomly then I would have to check every time if that shortid is available. Is there an one-way hash algorithm that could return back 7-10 character hash from passing in the 24 character id.

Are there any other ways to guarantee that the generated short id is unique without checking?

答:
You cannot guarantee that a shortened ID is unique, because there are much fewer 10-character strings than 24-character strings. Sooner or later, values will be reused.

Depending on how your IDs are generated, there are different things you could do in practice. If you get consecutive numbers, taking their last 10 characters will work for a while, but then wrap around after X^10 values. If the ID is itself totally random, you can take any 10 of its digits to get another value that is probably unique, but sooner or later will lead to collisions unpredictably. But the problem as posed is not solvable.


问:
Calling same method on different object - Recursion?
I have an object that contains a reference to another object of the same type.  Example in PHP:

```<code>class A {
    protected $child;
    public function __construct(A $child = null) {
        $this->child = $child;
    }

    public function go() {
        if($this->child) {
            $this->child->go();
        }
    }
}

$a = new A(new A());
$a->go();
</code>```

Is the go method considered a recursive method?  I can see it both ways myself, and I'm not sure if there is a 'correct' answer or not, but I assume that there is.

答:
It is recursive, since the call stack needs to grow. A new call frame has to be pushed (to the same function).

If the go method called another foo method (even on an unrelated class) which itself calls again go on the same class, you would have a mutual recursion ...

Another way to look at that is noticing that method invocation is just a dispatch phase (computing which function should really be called depending upon the receiver), followed by a function call (whose first argument is the reciever).

However, read about tail calls (or tail recursion). It enables to replace the current call frame with the newly called one (without growing the call stack).

So good compilers implement a tail call as a "jump with arguments"; read also about continuation passing style


问:
Print the next smallest from 2^i * 5^j where i,j >= 0
I was asked this question during a technical phone screening recently and didn't do well. The question is included verbatim below.

Generate {2^i * 5^j | i,j >= 0} sorted collection. Continuously print the next
  smallest value.

Example: { 1, 2, 4, 5, 8, 10...}

"Next smallest" makes me think a min-heap is involved, but I didn't really know where to go from there and no assistance was provided by the interviewer.

Does anyone have advice on how to solve such a problem?

答:
This is a common enough interview question that it's useful to know the answer. Here's the relevant entry in my personal crib sheet:

to generate the numbers of the form 3a5b7c in order, start
  with 1, stuff all three possible successors (3, 5, 7) into an
  auxiliary structure, then add the smallest number from it to your list.

In other words, you need a two-step approach with an additional sorted buffer to solve this efficiently. (A good longer description is in Cracking the Coding Interview by Gayle McDowell.


问:
Confusion about instance in an interface
I'm trying to learn OGSi framework (Equinox distribution).

I have registered my service, but I'm confused about a piece of code that I've copied:

```<code>IAgendaService service = new AgendaService();
</code>```

What does this line of code mean?

I think that in the service object, there are the IAgendaService methods that I've implemented in AgendaService, but I' m not sure about this.

Could it be a sort of upcating? (I know that it can't be because there is no inheritance, but I try to find something similar to compare)

答:
AgendaService is a class that implements the IAgendaService interface.  That line is the equivalent to the following:

```<code>IAgendaService service;
AgendaService agendaService = new AgendaService();
service = agendaService;
</code>```

The service variable can reference any object that implements IAgendaService.  In the example above, service is referencing an instance of the AgendaService class.

AgendaSevice implements IAgendaService, so it must contain all the methods in the IAgendaService interface.  You can call any method in the IAgendaService interface using the service object.  If you attempt to call an AgendaService method, then it will result in a compilation error.

To help clarify here is an example.  The processing in the main class will result in the same output.

```<code>public interface IAgendaService {
    public void method1();
    public void method2();
}

public class AgendaService implements IAgendaService {
    private String instanceName;

    public AgendaService(String instanceName) {
        this.instanceName = instanceName;
    }

    public void method1() {
        System.out.println(instanceName + " - method1");
    }

    public void method2() {
        System.out.println(instanceName + " - method2");
    }

    public void method3() {
        System.out.println(instanceName + " - method3");
    }
}

public class Main {
    public static void main(String[] args) {
       AgendaService agendaService = new AgendaService("1");
       agendaService.method1(); // prints 1 - method1
       agendaService.method2(); // prints 1 - method2
       agendaService.method3(); // prints 1 - method3

       IAgendaService iAgendaService = agendaService;
       iAgendaService.method1(); // prints 1 - method1
       iAgendaService.method2(); // prints 1 - method2
       iAgendaService.method3(); // compile error because IAgendaService doesn't have a method3
    }
}
</code>```

Body:
AgendaService is a class that implements the IAgendaService interface.  That line is the equivalent to the following:

IAgendaService service;
AgendaService agendaService = new AgendaService();
service = agendaService;

The service variable can reference any object that implements IAgendaService.  In the example above, service is referencing an instance of the AgendaService class.

AgendaSevice implements IAgendaService, so it must contain all the methods in the IAgendaService interface.  You can call any method in the IAgendaService interface using the service object.  If you attempt to call an AgendaService method, then it will result in a compilation error.

To help clarify here is an example.  The processing in the main class will result in the same output.

public interface IAgendaService {
    public void method1();
    public void method2();
}

public class AgendaService implements IAgendaService {
    private String instanceName;

    public AgendaService(String instanceName) {
        this.instanceName = instanceName;
    }

    public void method1() {
        System.out.println(instanceName + " - method1");
    }

    public void method2() {
        System.out.println(instanceName + " - method2");
    }

    public void method3() {
        System.out.println(instanceName + " - method3");
    }
}

public class Main {
    public static void main(String[] args) {
       AgendaService agendaService = new AgendaService("1");
       agendaService.method1(); // prints 1 - method1
       agendaService.method2(); // prints 1 - method2
       agendaService.method3(); // prints 1 - method3

       IAgendaService iAgendaService = agendaService;
       iAgendaService.method1(); // prints 1 - method1
       iAgendaService.method2(); // prints 1 - method2
       iAgendaService.method3(); // compile error because IAgendaService doesn't have a method3
    }
}


答:
Let's reword the problem:
Output every number from 1 to infinity such that the number has no factors except 2 and 5.

Below is a simple C# snippet:

```<code>for (int i = 1;;++i)
{
    int num = i;
    while(num%2 == 0) num/=2;
    while(num%5 == 0) num/=5;
    if(num == 1) Console.WriteLine(i);
}
</code>```

Kilian's/QuestionC's approach is much more performant.  C# snippet with this approach:

```<code>var itms = new SortedSet<int>();
itms.Add(1);
while(true)
{
    int cur = itms.Min;
    itms.Remove(itms.Min);
    itms.Add(cur*2);
    itms.Add(cur*5);
    Console.WriteLine(cur);
}
</code>```

SortedSet prevents duplicate insertions.

Basically, it works by ensuring that the next number in the sequence is in itms.

Proof that this approach is valid:

The algorithm described ensures that after for any number output in the form 2^i*5^j, the set now contains 2^(i+1)*5^j and 2^i*5^(j+1).  Suppose the next number in the sequence is 2^p*5^q.  There must exist a previously output number of the form 2^(p-1)*5^(q) or 2^p*5^(q-1) (or both, if neither p nor q are equal to 0).  If not, then 2^p*5^q is not the next number, since 2^(p-1)*5^(q) and 2^p*5^(q-1) are both smaller.

The second snippet uses O(n) memory (where n is the number of numbers that have been output), since O(i+j) =  O(n) (because i and j are both less than n), and will find n numbers in O(n log n) time.  The first snippet finds numbers in exponential time.

Title: Print the next smallest from 2^i * 5^j where i,j >= 0

Body:
I was asked this question during a technical phone screening recently and didn't do well. The question is included verbatim below.

Generate {2^i * 5^j | i,j >= 0} sorted collection. Continuously print the next
  smallest value.

Example: { 1, 2, 4, 5, 8, 10...}

"Next smallest" makes me think a min-heap is involved, but I didn't really know where to go from there and no assistance was provided by the interviewer.

Does anyone have advice on how to solve such a problem?

Body:
Let's reword the problem:
Output every number from 1 to infinity such that the number has no factors except 2 and 5.

Below is a simple C# snippet:

for (int i = 1;;++i)
{
    int num = i;
    while(num%2 == 0) num/=2;
    while(num%5 == 0) num/=5;
    if(num == 1) Console.WriteLine(i);
}

Kilian's/QuestionC's approach is much more performant.  C# snippet with this approach:

var itms = new SortedSet<int>();
itms.Add(1);
while(true)
{
    int cur = itms.Min;
    itms.Remove(itms.Min);
    itms.Add(cur*2);
    itms.Add(cur*5);
    Console.WriteLine(cur);
}

SortedSet prevents duplicate insertions.

Basically, it works by ensuring that the next number in the sequence is in itms.

Proof that this approach is valid:

The algorithm described ensures that after for any number output in the form 2^i*5^j, the set now contains 2^(i+1)*5^j and 2^i*5^(j+1).  Suppose the next number in the sequence is 2^p*5^q.  There must exist a previously output number of the form 2^(p-1)*5^(q) or 2^p*5^(q-1) (or both, if neither p nor q are equal to 0).  If not, then 2^p*5^q is not the next number, since 2^(p-1)*5^(q) and 2^p*5^(q-1) are both smaller.

The second snippet uses O(n) memory (where n is the number of numbers that have been output), since O(i+j) =  O(n) (because i and j are both less than n), and will find n numbers in O(n log n) time.  The first snippet finds numbers in exponential time.


问:
Is SourceSafe really safe?
Having spent all morning trying to check something in - I now realise I've lost a couple of days worth of work.

Its happened before - and is apparently common occurrence with SourceSafe.  Can SourceSafe be used successfully, without problems, and if so, how?

答: Back in the day I was saddled with SCCS under XENIX. VSS, in Visual Studio 6, for all it's failures and problems had distinct advantages. I still use it for small projects and I no longer use SCCS in any version.</p>

Title: Is SourceSafe really safe?

ContentLicense: CC BY-SA 2.5


答:
I suggest you the "book" I am writing about MVC. It's far from complete, but it may give you an idea.

MVC on the web is a strange beast, however. If you check most resources, they will present MVC for a GUI, but on the web you have a different structure: the View is isolated from the Model and the Controller, can only push requests, and the communication is slow. For this reason, the entry point is on the controller, which acts more like a mediator. The View does not talk to the Model directly, like in traditional MVC.

Title: Can someone help me understand MVC?


答:
The instance on which the method is invoked (the receiver of the message, in Smalltalk terms) is typically treated as an implicit, zeroth parameter to the method.

So a method like

public function go()

that takes no arguments can be thought of as actually taking one argument, named $this, of type A:

public function go(A $this)

And a call to that method, dispatched on some particular instance of A, could then be thought of, not as being written

$this->child->go()

but rather written like this:

go($this->child)

When looked at in these terms, it clearly becomes a recursive call. (The Cfront C++ compiler, in the very early days of C++, translated C++ into C code like this, which was then compiled with a C compiler.)

Title: Calling same method on different object - Recursion?

Body:
I have an object that contains a reference to another object of the same type.  Example in PHP:

```<code>class A {
    protected $child;
    public function __construct(A $child = null) {
        $this->child = $child;
    }

    public function go() {
        if($this->child) {
            $this->child->go();
        }
    }
}

$a = new A(new A());
$a->go();
</code>```

Is the go method considered a recursive method?  I can see it both ways myself, and I'm not sure if there is a 'correct' answer or not, but I assume that there is.


问:
Nested maps vs. combined keys
in the project I am currently working on we had three different types of prices depending on the age of the user (adult, child, etc...). So we had on the DB a table looking like this:

PRICES
type     Amount
A         20
B         15
C         ..
D         ..
```
</blockquote>

<p>At first we only had 4 different types of prices, so in the code, we had something like this:</p>

<pre class="lang-none prettyprint-override"><code>Map<String, BigDecimal> prices = new HashMap<String, BigDecimal>();
</code>```

Where the keys were the price type.

Recently, they added a new business rule that adds 3 subtypes to every price type, so now we have something like this:

PRICES
type   subtype  Amount
A          1      20
A          2      15
A          3      ..
B          1      ..
B          2      ..
...        ..     ..
```
</blockquote>

<p><strong>Which of the following two options do you think is better and why?</strong></p>

<h1>Nested Maps</h1>

<pre class="lang-java prettyprint-override"><code>Map<String, Map<String, BigDecimal>> prices;
</code>```

where the keys are the price type and subtype:

prices.get(type).get(subtype);
```

<h1>Combined Keys</h1>

<p>The same map than originally:</p>

<pre class="lang-java prettyprint-override"><code>Map<String, BigDecimal> prices;
</code>```

And concatenate the keys to index the different prices:

prices.get(type+"_"+subtype);
```

答:
Avoid nested Maps. They're harder to scale and lead to code that is very verbose and hard to read with all the nested generics declarations going on.

More importantly, Maps in Java tend to consume a lot of memory. Populating a Map with even more Maps will only aggravate the memory consumption issue.

Lastly, a Map that uses composite keys is easier to reason about.

Using composite keys will make your life easier in the most typical cases, yet some things will be harder. Getting all prices for a specific key component for instance, but you're more likely to query that result straight from the database rather than distilling it from the Map.

Title: Nested maps vs. combined keys


问:
Hash function for progressive changes
I am looking for a hashing algorithm that works like this. I start with a text file, and compute its hash. Now I know that I will remove one character at, say, position 67 and this character is a "m", and I would like to compute the new hash without reapplying the hash function to the full text, but instead using the hash of the full text and the knowledge that I removed 'm' from position 67. If I readd the "m" in the same place, I will again recompute with the same methodology and get the same initial hash.

What is the technical name for such hash functions, so that I can search some pointers around? a CRC is not what I need I guess, because (afaik) a CRC works on a stream addition, not on arbitrary changes throughout the initial data.

答: A "Divide and Conquer" strategy would work well here.  Instead of hashing the entire file, hash portions of the file, maintaining an array of hashes to detect changes. The most straightforward way to do it would be to maintain a hash for each line of text.</p>

Title: Hash function for progressive changes


问:
Why does C dominate in the embedded software market?
Almost everyone will now say the blessing:

performance!

Okay, C does allow to write athletic code. But there are other languages that can do so, after all! And the optimising power of modern compilers is awesome. Does C have some advantages that no other language has? Or there's simply no need for more flexible instruments in the domain?

答:
Embedded software is very different.

On a desktop app, abstractions and libraries save you a lot of development time.  You have the luxury of throwing another couple megabytes or gigabytes of RAM or some 2+GHz 64-bit CPU cores at a problem, and someone else (users) is paying for that hardware.  You may not know what systems the app will run on.

In an embedded project, resources are often very limited.  In one project I worked on (PIC 17X-series processors) the hardware had 2Kwords of program memory, 8 levels of (in-hardware) stack and 192 bytes (< 0.2kB) of RAM.  Different I/O pins had different capabilities and you configured the hardware as needed by writing to hardware registers. Debugging involves an oscilloscope and logic-analyzer.

In embedded, abstractions often get in the way and would manage (and cost) resources you don't have.  E.g. most embedded systems have no file system.  Microwave ovens are embedded systems.  Car engine controllers.  Some electric toothbrushes.  Some noise-cancelling headphones.

One very important factor for me in developing embedded systems is knowing and controlling what the code translates to in terms of instructions, resources, memory and execution time.  Often the exact sequence of instructions controls e.g. timing for hardware interface waveforms.

Abstractions and behind-the-scenes 'magic' (e.g. a garbage-collector) is great for desktop apps.  Garbage-collectors save you a LOT of time chasing down memory leaks, when memory is / can be dynamically allocated.

However in the real-time embedded world we need to know and control how long things take, sometimes down to nanoseconds, and can't throw another couple meg of RAM or a faster CPU at a problem.  One simple example:  when doing software dimming of LEDs by controlling duty cycle (the CPU had only on/off control of the LEDs), it is NOT OK for the processor to go off and do e.g. garbage collection for 100ms because the display would visibly flash bright or go out.

A more-hypothetical example is an engine controller that directly fires spark-plugs.  If that CPU does off and does garbage-collection for 50ms, the engine would cut out for a moment or fire at the wrong crankshaft position, potentially stalling the engine (while passing?) or damaging it mechanically.  You could get someone killed.


问:
What's your favourite quote about programming?
What's your favourite quote about programming?

One quote per answer, and please check for duplicates before posting!

答:
Knowledge is proud that it knows so
  much; wisdom is humble that it knows
  no more.

--William Cowper

LastEditorDisplayName: Roger Pate


答:
Here's an answer that runs with constant memory, at the expense of CPU. This is not a good answer in the context of the original question (i.e. answer during an interview). But if the interview is 24 hours long, then it's not so bad. ;)

The idea is that if I have n which is a valid answer, then the next in the sequence is going to be n times some power of two, divided by some power of 5. Or else n times a power of 5, divided by a power of two. Provided it divides evenly. (...or the divisor can be 1 ;) in which case you're just multiplying by 2 or 5)

For example, to go from 625 to 640, multiply by 5 ** 4 / 2 ** 7. Or, more generally, multiply by some value of 2 ** m * 5 ** n for some m, n where one is positive and one is negative or zero, and the multiplier divides the number evenly.

Now, the tricky part is find the multiplier. But we know a) the divisor must divide the number evenly, b) the multiplier must be greater than one (the numbers keep increasing), and c) if we pick the lowest multiplier greater than 1 (i.e. 1 < f < all other f's), then that's guaranteed to be our next step. The step after that will be it's lowest step.

The nasty part is finding the value of m, n. There are only log(n) possibilities, because there are only so many 2's or 5's to give up, but I had to add a factor of -1 to +1 as a sloppy way to deal with roundoff. So we only have to iterate through O(log(n)) each step. So it's O(n log(n)) overall.

The good news is, because it takes a value and finds the next value, you can start anywhere in the sequence. So if you want the next one after 1 billion, it can just find it by iterating through the 2 / 5's or 5 / 2's and picking the smallest multiplier greater than 1.

(python)

```<code>MAX = 30
F = - math.log(2) / math.log(5)

def val(i, j):
    return 2 ** i * 5 ** j

def best(i, j):
    f = 100
    m = 0
    n = 0
    max_i = (int)(math.log(val(i, j)) / math.log(2) + 1) if i + j else 1
    #print((val(i, j), max_i, x))
    for mm in range(-i, max_i + 1):
        for rr in {-1, 0, 1}:
            nn = (int)(mm * F + rr)
            if nn < -j: continue
            ff = val(mm, nn)
            #print('  ' + str((ff, mm, nn, rr)))
            if ff > 1 and ff < f:
                f = ff
                m = mm
                n = nn
    return m, n

def detSeq():

    i = 0
    j = 0
    got = [val(i, j)]

    while len(got) < MAX:
        m, n = best(i, j)

        i += m
        j += n
        got.append(val(i, j))

        #print('* ' + str((val(i, j), m, n)))
        #print('- ' + str((v, i, j)))

    return got
</code>```

I validated the first 10,000 numbers this generates against the first 10,000 generated by the sorted list solution, and it works at least that far.

BTW the next one after a trillion seems to be 1,024,000,000,000.

...

Hm. I can get O(n) performance -- O(1) per value (!) -- and O(log n) memory usage by treating best() as a lookup table that I extend incrementally. Right now it saves memory by iterating each time, but it's doing a lot of redundant calculations. By holding those intermediate values -- and a list of min values -- I can avoid the duplicate work & speed it up a lot. However, the list of intermediate values will grow with n, hence the O(log n) memory.

Body:
Here's an answer that runs with constant memory, at the expense of CPU. This is not a good answer in the context of the original question (i.e. answer during an interview). But if the interview is 24 hours long, then it's not so bad. ;)

The idea is that if I have n which is a valid answer, then the next in the sequence is going to be n times some power of two, divided by some power of 5. Or else n times a power of 5, divided by a power of two. Provided it divides evenly. (...or the divisor can be 1 ;) in which case you're just multiplying by 2 or 5)

For example, to go from 625 to 640, multiply by 5 ** 4 / 2 ** 7. Or, more generally, multiply by some value of 2 ** m * 5 ** n for some m, n where one is positive and one is negative or zero, and the multiplier divides the number evenly.

Now, the tricky part is find the multiplier. But we know a) the divisor must divide the number evenly, b) the multiplier must be greater than one (the numbers keep increasing), and c) if we pick the lowest multiplier greater than 1 (i.e. 1 < f < all other f's), then that's guaranteed to be our next step. The step after that will be it's lowest step.

The nasty part is finding the value of m, n. There are only log(n) possibilities, because there are only so many 2's or 5's to give up, but I had to add a factor of -1 to +1 as a sloppy way to deal with roundoff. So we only have to iterate through O(log(n)) each step. So it's O(n log(n)) overall.

The good news is, because it takes a value and finds the next value, you can start anywhere in the sequence. So if you want the next one after 1 billion, it can just find it by iterating through the 2 / 5's or 5 / 2's and picking the smallest multiplier greater than 1.

(python)

MAX = 30
F = - math.log(2) / math.log(5)

def val(i, j):
    return 2 ** i * 5 ** j

def best(i, j):
    f = 100
    m = 0
    n = 0
    max_i = (int)(math.log(val(i, j)) / math.log(2) + 1) if i + j else 1
    #print((val(i, j), max_i, x))
    for mm in range(-i, max_i + 1):
        for rr in {-1, 0, 1}:
            nn = (int)(mm * F + rr)
            if nn < -j: continue
            ff = val(mm, nn)
            #print('  ' + str((ff, mm, nn, rr)))
            if ff > 1 and ff < f:
                f = ff
                m = mm
                n = nn
    return m, n

def detSeq():

    i = 0
    j = 0
    got = [val(i, j)]

    while len(got) < MAX:
        m, n = best(i, j)

        i += m
        j += n
        got.append(val(i, j))

        #print('* ' + str((val(i, j), m, n)))
        #print('- ' + str((v, i, j)))

    return got

I validated the first 10,000 numbers this generates against the first 10,000 generated by the sorted list solution, and it works at least that far.

BTW the next one after a trillion seems to be 1,024,000,000,000.

...

Hm. I can get O(n) performance -- O(1) per value (!) -- and O(log n) memory usage by treating best() as a lookup table that I extend incrementally. Right now it saves memory by iterating each time, but it's doing a lot of redundant calculations. By holding those intermediate values -- and a list of min values -- I can avoid the duplicate work & speed it up a lot. However, the list of intermediate values will grow with n, hence the O(log n) memory.


答:
If other conditions are favorable, assign your short ids serially.  First string
that needs an Id gets 1, second get 2 etc.  Guaranteed to be unique and no checking
is needed.</p>

Title: What's the shortest generating one-way hash algorithm?

Body:
I have a 24 character long id which is guaranteed to be unique. I would like to shorten that to 7-10 (or even shorter) characters long. If I generate an short id randomly then I would have to check every time if that shortid is available. Is there an one-way hash algorithm that could return back 7-10 character hash from passing in the 24 character id.

Are there any other ways to guarantee that the generated short id is unique without checking?


问:
Do modern languages still use parser generators?
I was researching about the gcc compiler suite on wikipedia here, when this came up:

GCC started out using LALR parsers generated with Bison, but gradually switched to hand-written recursive-descent parsers; for C++ in 2004, and for C and Objective-C in 2006. Currently all front ends use hand-written recursive-descent parsers

So by that last sentence, (and for as much as I trust wikipedia) I can definitely say that
"C (gcc), C++ (g++), Objective-C, Objective-C++, Fortran (gfortran), Java (gcj), Ada (GNAT), Go (gccgo), Pascal (gpc),... Mercury, Modula-2, Modula-3, PL/I, D (gdc), and VHDL (ghdl)" are all front-ends that no longer use a parser generator. That is, they all use hand-written parsers.

My question then is, is this practice ubiquitous? Specifically, I'm looking for exact answers to "does the standard/official implementation of x have a hand-written parser" for x in [Python, Swift, Ruby, Java, Scala, ML, Haskell]? (Actually, information on any other languages is also welcome here.) I'm sure I can find this on my own after a lot of digging. But I'm also sure this is easily answerable by the community. Thanks!

答:
Parser generators and parser engines are quite general. The advantage of the generality is that building an accurate parser quickly and getting it functional is easy, in the overall scheme of things.

The parser engine itself suffers on the performance front because of its generality. Any hand-written code will always be significantly faster than the table-driven parser engines.

The second area where parser generators/engines have difficulty is that all real programming languages are context sensitive, often in quite subtle ways. LR languages are context-free, meaning that there are many subtleties about positioning and environment that are impossible to properly convey in the syntax. Attributed grammers attempt to address basic language rules like "declare before use", etc. Wiring this context-sensitivity into hand-written code is straight forward.

OwnerDisplayName: phileaton


问:
General recursion to tail-recursion
Is it theoretically possible to transform every kind of general-recursion into tail-recursion? Are they equivalent for example from a lambda-calculus point of view? That's a debate between me and an acquaintance.

My view is that it's not possible everytime. For example if you have a function which calls itself recursively twice or three times, then you can't make all the recursive calls into tail-calls, right? Or is there always a way to reduce the number of recursive calls to one single recursive call?

答:
You can do that transformation using Continuation Passing Style.

Read for instance A.Appel Compiling with Continuations book

Intuitively, you replace -after CPS transformation- (nearly) each call frame of the call stack with a heap-allocated continuation frame (or "closure" when viewing continuations as functions). (so you might not win much: the avoided stack frames are replaced by garbage collected continuation frames).

See also Appel's old paper: garbage collection can be faster than stack allocation

(which might be less true today, perhaps because of cache issues)

Title: General recursion to tail-recursion


答:
You should be able to do it using continuation passing style.

In CPS, each function takes an explicit continuation function which represents the rest of the computation. Instead of returning a value directly, a function in CPS passes the result to the continuation instead.

For example if you had the following Tree data type:

```<code>type Tree = Empty | Node of Tree * int * Tree
</code>```

and you wanted to sum the values, you could write function to sum the left and right subtrees in turn:

```<code>let rec sum_cps t f =
    match t with
        | Empty -> f 0
        | Node(l, v, r) -> sum_cps l (fun lv ->
            sum_cps r (fun rv -> f (lv + v + rv)))

let sumT t = sum_cps t (fun i -> i)
</code>```

Title: General recursion to tail-recursion

Body:
Is it theoretically possible to transform every kind of general-recursion into tail-recursion? Are they equivalent for example from a lambda-calculus point of view? That's a debate between me and an acquaintance.

My view is that it's not possible everytime. For example if you have a function which calls itself recursively twice or three times, then you can't make all the recursive calls into tail-calls, right? Or is there always a way to reduce the number of recursive calls to one single recursive call?

Body:
You should be able to do it using continuation passing style.

In CPS, each function takes an explicit continuation function which represents the rest of the computation. Instead of returning a value directly, a function in CPS passes the result to the continuation instead.

For example if you had the following Tree data type:

type Tree = Empty | Node of Tree * int * Tree

and you wanted to sum the values, you could write function to sum the left and right subtrees in turn:

let rec sum_cps t f =
    match t with
        | Empty -> f 0
        | Node(l, v, r) -> sum_cps l (fun lv ->
            sum_cps r (fun rv -> f (lv + v + rv)))

let sumT t = sum_cps t (fun i -> i)


问:
Does the usage of LINQ and Lambda Expressions lead to less readable code?
I'm having a discussion with a co-worker on Linq, I'll copy here:

Co-Worker: Lets be honest here. Linq
syntax sucks. It's confusing and
non-intuitive.

Me: oh come on, more
confusing than T-SQL?

Co-Worker: uh,
yes.

Me: it has the same basic
parts, select, where, and from

Co-Worker: Linq, to me, is a
bastardization of relational + OO.
Co-Worker: Don't get me wrong - it's
incredibly powerful, but they
repurposed SQL to use agains object
collections.

I'm of the opinion that using Linq + Lamda's is very powerful (he agrees), and also makes code easier to read (he disagrees on that point):

pickFiles = from f in pickFolder.GetFiles("*.txt")
where ValidAuditFileName.IsMatch(f.Name)
select f;
```
<p>or</p>
<pre class="lang-cs prettyprint-override"><code>var existing = from s in ActiveRecordLinq.AsQueryable<ScannedEntity>()
where s.FileName == f.FullName && s.DocumentType != "Unknown"
select s;
</code>```

or (VB code here)

   Dim notVerified = From image In images.AsParallel
     Group Join verifyFile In verifyFolder.GetFiles("*.vfy").AsParallel.Where(
      Function(v) v.Length > 0
      ).AsParallel
   On image.Name.Replace(image.Extension, ".vfy") Equals verifyFile.Name
     Into verifyList = Group
    From verify In verifyList.DefaultIfEmpty
    Where verify Is Nothing
    Select verify
```

To me this is clean and easy (at least easier than the alternatives) to read, what are your opinions on it?

答: I agree with you that Linq syntax is not significantly different from T-SQL. I think your coworker might really be objecting to relational stuff getting mixed in which his nice and shiny OO code. On the other hand, functional programming takes a bit of getting used to, and a willingness to get used to it. </p>


答:
AFAIK, GCC use hand-written parsers in particular to improve syntactic error diagnostics (i.e. giving human meaningful messages on syntax errors).

Parsing theory (and the parsing generators descending from it) is mostly about recognizing and parsing a correct input phrase. But we expect from compilers that they give a meaningful error message (and that they are able to parse meaningfully the rest of the input after the syntactic error), for some incorrect input.

Also, old legacy languages -like C11 or C++11- (which are conceptually old, even if their latest revision is only three years old) are not at all context-free. Dealing with that context sensitiveness in grammars for parser generators (i.e. bison or even menhir) is boringly difficult.

Title: Do modern languages still use parser generators?

Body:
I was researching about the gcc compiler suite on wikipedia here, when this came up:

GCC started out using LALR parsers generated with Bison, but gradually switched to hand-written recursive-descent parsers; for C++ in 2004, and for C and Objective-C in 2006. Currently all front ends use hand-written recursive-descent parsers

So by that last sentence, (and for as much as I trust wikipedia) I can definitely say that
"C (gcc), C++ (g++), Objective-C, Objective-C++, Fortran (gfortran), Java (gcj), Ada (GNAT), Go (gccgo), Pascal (gpc),... Mercury, Modula-2, Modula-3, PL/I, D (gdc), and VHDL (ghdl)" are all front-ends that no longer use a parser generator. That is, they all use hand-written parsers.

My question then is, is this practice ubiquitous? Specifically, I'm looking for exact answers to "does the standard/official implementation of x have a hand-written parser" for x in [Python, Swift, Ruby, Java, Scala, ML, Haskell]? (Actually, information on any other languages is also welcome here.) I'm sure I can find this on my own after a lot of digging. But I'm also sure this is easily answerable by the community. Thanks!


问:
Loading dynamic CSS based on user
I want to provide different UI theme based on user who logged in. For that I have came up with following 2 options:

Create separate files for all themes duplicating all the common CSS. This way I can easily do some login in scripting and get the required CSS file. But I end up having same CSS classes code in many different theme files. This is real pain when you have to change something common to all files.

Make a common file and separate theme files containing only theme specific CSS. This way everytime I need to load 2 CSS files, one - common file by default and then load theme specific file to override default CSS classes.

If there is other simple and easy way to do it then please do let me know.

答:
Definitely go with option 2, it will be much easier to maintain. You could structure your CSS something like this:

```<code>css/
 |---default.css
 |---users/
       |----user1.css
       |----user2.css
       |----user3.css
</code>```

I have a similar functionality implemented on my web site. Instead of giving each user a stylesheet, I have several predefined stylesheets that the user can switch between. I use JavaScript to change between stylesheets and a cookie to save their preferences across the site.

Another thing I did is in my equivalent of default.css, I have only the code that is the same across styles, and have an additional stylesheet that is applied by default (e.g. defaultuser.css).

Title: Loading dynamic CSS based on user

Body:
Definitely go with option 2, it will be much easier to maintain. You could structure your CSS something like this:

css/
 |---default.css
 |---users/
       |----user1.css
       |----user2.css
       |----user3.css

I have a similar functionality implemented on my web site. Instead of giving each user a stylesheet, I have several predefined stylesheets that the user can switch between. I use JavaScript to change between stylesheets and a cookie to save their preferences across the site.

Another thing I did is in my equivalent of default.css, I have only the code that is the same across styles, and have an additional stylesheet that is applied by default (e.g. defaultuser.css).


问:
Are there any public statistics on the implementation time of software tasks?
I'd like to get better at estimating how long it will take me to complete tasks. When estimating things I know little about, I think it's best to start with base rate information and adjust it based on things I do know, rather than to go on 'gut feeling' which is what I normally do, and is generally optimistic. What I lack is that base rate information.

Are there any statistics available which give typical ideal man-hour costs (or some other metric) based on some property/properties of the task in question?

For some context, I work as a programmer in the video games industry, and I'm talking about chunks of work that typically take somewhere between 2-16 hours, though occasionally drag on far longer than that... ;)

I realise this is a big ask, but I have to start somewhere!

Things I've already tried:

google - my search terms appear to be too general - lots of irrelevant results.

This question - asks for overall estimate, in a different domain. Unsatisfactory answers.

答:
I don't know of any useful statistics on how long a task takes and I doubt that they would help you.

The best way to get better at estimating is to do it a lot and to evaluate why the actual time deviated from the estimate.

This all depends on knowing the estimate you gave, what you considered to be included in the task when estimating, the actual time it took to complete the work and what the task actually entailed.

With that information, you can find consistent deviations in your estimations and/or sub-tasks that you consistently forget in your estimate.

For example, I found after a number of estimations that I consistently underestimate the amount of work by a factor of 8 and that the number that pop into my head is typically only for the coding itself, without testing and documentation. What I do nowadays is, if I initially think a task will take 2 hours, then I give 2 days as my estimation to the team. So, I simply multiply my gut feeling with the factor that I know to usually be off by.

Another way to get better estimations is to base your numbers on the actual time it took to complete similar tasks.


答:
Both nested and combined keys have their places. bowmore gives a pro argument for composite keys, and a con argument for nested maps. Let me provide the loyal opposition:

Composite map keys work great when you're looking up a specific known item.

Nested maps work well when you need to rapidly find all the variations, kinds, and subtypes of type A. For example, choosing A (vs. B, C,  ...) might be the first step in a decision tree. Once the user or algorithm or whatever picks A, then you need to know only about A's subtypes, and B..Z or B..ZZZZZ no longer matter.

Now you're dealing with a very tight and efficient lookup structure for the subsearch. If you try to do that with composite keys, you end up doing a full table scan a la [ (key, value) for (key, value) in prices.items() if key.startswith('A') ]. That's not an efficient operation, and will be slow if the map is at all large.

Nested maps also work well when the number of nesting levels may grow. The problem structure already extended from type to (type, subtype). Is there any chance the next rev will need (type, subtype, variation) or (type, subtype, version)? If so, a nested mapping approach can be cleanly extended. This, however, is a stylistic, second-order advantage, especially compared to the "easy subsearch" advantage above.

Title: Nested maps vs. combined keys

Body:
in the project I am currently working on we had three different types of prices depending on the age of the user (adult, child, etc...). So we had on the DB a table looking like this:

PRICES
type     Amount
A         20
B         15
C         ..
D         ..
```
</blockquote>

<p>At first we only had 4 different types of prices, so in the code, we had something like this:</p>

<pre class="lang-none prettyprint-override"><code>Map<String, BigDecimal> prices = new HashMap<String, BigDecimal>();
</code>```

Where the keys were the price type.

Recently, they added a new business rule that adds 3 subtypes to every price type, so now we have something like this:

PRICES
type   subtype  Amount
A          1      20
A          2      15
A          3      ..
B          1      ..
B          2      ..
...        ..     ..
```
</blockquote>

<p><strong>Which of the following two options do you think is better and why?</strong></p>

<h1>Nested Maps</h1>

<pre class="lang-java prettyprint-override"><code>Map<String, Map<String, BigDecimal>> prices;
</code>```

where the keys are the price type and subtype:

prices.get(type).get(subtype);
```

<h1>Combined Keys</h1>

<p>The same map than originally:</p>

<pre class="lang-java prettyprint-override"><code>Map<String, BigDecimal> prices;
</code>```

And concatenate the keys to index the different prices:

prices.get(type+"_"+subtype);
```


问:
What payoffs have you seen from taking care of technical debt?
This article on technical debt has some good points, including:

Working on the "technical matters" works best when it is driven by stories. The code base is probably in need of work everywhere, but the payoff will be received only where the code is going to be worked on for user-facing reasons. If no stories are going to pass through some crufty area, working on it is largely wasted.

Therefore, I prefer the approach of taking stories as usual (but probably fewer of them), and following the "boy scout rule" of leaving the campground better than you found it. In other words, wherever the stories lead us, let's write more tests, let's refactor more aggressively.

This approach has at least these advantages:

maintains "best sensible" flow of stories;

provides help from all team talent;

provides for whole team to learn how to keep code clean;

focuses improvement exactly where it is needed;

does not waste improvement that "may" be needed;

I've seen code quality have a very big effect on long-term productivity, so I am a believer that technical debt should be taken care of.  I think the post above makes sense, but I'm not so sure about the last two points.  I'm interested in finding out real experiences of benefits from cleaning technical debt, even if it was not related to user stories.

What positive benefits have you seen from cleaning up your code base and ridding yourself of technical debt? What methods did you use to get the work done?

答: It's been my experience that the benefits of code cleanup are most noticeable when I have to maintain code where the cleanup hasn't been done. Where the cleanup's been done, my changes consist of reading through the code, spotting the one or two places that need to be changed, and going from there. If the cleanup hasn't been done, add an initial step of reading the code a couple of times and trying to figure out what the author (sometimes me) was thinking when he wrote it.</p>


问:
How do you deal with being behind on a task?
I have a question for you guys. Say, you're given a task as an item in a product backlog. Say, you have a deliverable that's due the following day. If you're behind on the task compared to when you made your estimates, what do you do about it? Does it make you anxious knowing your behind schedule? How do you deal with this? Do you tell the scrum master or the product owner?</p>

答:
Yes, it makes me anxious. But I am usually both behind and anxious anyway.

That's what daily standups are for -- so the team doesn't discover a week later that you're a week behind.


问:
What approach to use to query multiple XML files?
I'll be receiving tens of thousands of XML files, which will continue to grow with new files over time. I need to be able to query these files as a whole (like SQL querying all the records in a database). What technologies and/or approaches should I be looking at for this problem?

I feel like I should be looking into XQuery. I'm not that familiar with it, though.

UPDATE 1:

Example queries I might run:

Return all the product code, product name, product description from all XML files in /folder 1/ where the supplier id = x and store id = y

Return all the product code and product price from all XML files in /folder 2/ where the supplier id = x and store id = y

Maybe join the results of the two queries above, joining on product code

As there may be multiple results per product code for the two queries above, only get the most recent values based on some tag / attribute in the XML

UPDATE 2:

It seems like this article suggests that XQuery can be used: http://www.ibm.com/developerworks/xml/library/x-xquerymaven/index.html?ca=. As I am implementing a LAMP solution, I think there might be XQuery libraries available to PHP. Does this mean that I don't need an XML database to query loads of XML files?

答: I have used eXist-db for storing and querying many XML files in different collections using xquery (http://exist-db.org). There are many ways to interface with it and it has proven to be reliable for my applications.</p>


答: I would usually relay that information to the scrum master during the daily scrum meeting. As soon as you know you're behind you should inform the scrum master so he can either get someone to help you (maybe someone else is ahead of schedule and has bandwidth to help), determine whether overtime is needed, or if it's an impediment outside of your team's control then the backlog item needs to be deferred he can provide rationale to stakeholders.</p>

Title: How do you deal with being behind on a task?

Body: I have a question for you guys. Say, you're given a task as an item in a product backlog. Say, you have a deliverable that's due the following day. If you're behind on the task compared to when you made your estimates, what do you do about it? Does it make you anxious knowing your behind schedule? How do you deal with this? Do you tell the scrum master or the product owner?</p>


问:
Should we avoid using design patterns in constantly changing projects?
A friend of mine is working for a small company on a project every developer would hate: he's pressured to release as quickly as possible, he's the only one who seem to care about technical debt, the customer has no technical background, etc.

He told me a story which made me think about the appropriateness of design patterns in projects like this one. Here's the story.

We had to display products at different places on the website. For example, content managers could view the products, but also the end users or the partners through the API.

Sometimes, information was missing from the products: for example, a bunch of them didn't have any price when the product was just created, but the price wasn't specified yet. Some didn't have a description (the description being a complex object with modification histories, localized content, etc.). Some were lacking shipment information.

Inspired by my recent readings about design patterns, I thought this was an excellent opportunity to use the magical Null Object pattern. So I did it, and everything was smooth and clean. One just had to call product.Price.ToString("c") to display the price, or product.Description.Current to show the description; no conditional stuff required. Until, one day, the stakeholder asked to display it differently in the API, by having a null in JSON. And also differently for content managers by showing "Price unspecified [Change]". And I had to murder my beloved Null Object pattern, because there was no need for it any longer.

In the same way, I had to remove a few abstract factories and a few builders, I ended up replacing my beautiful Facade pattern by direct and ugly calls, because the underlying interfaces changed twice per day for three months, and even the Singleton left me when the requirements told that the concerned object had to be different depending on the context.

More than three weeks of work consisted of adding design patterns, then tearing them apart one month later, and my code finally became spaghetti enough to be impossible to maintain by anyone, including myself. Wouldn't it be better to never use those patterns in the first place?

Indeed, I had to work myself on those types of projects where the requirements are changing constantly, and are dictated by persons who don't really have in mind the cohesion or the coherence of the product. In this context, it doesn't matter how agile you are, you'll come with an elegant solution to a problem, and when you finally implement it, you learn that the requirements changed so drastically, that your elegant solution doesn't fit any longer.

What would be the solution in this case?

Not using any design patterns, stop thinking, and write code directly?

It would be interesting to do an experience where a team is writing code directly, while another one is thinking twice before typing, taking the risk of having to throw away the original design a few days later: who knows, maybe both teams would have the same technical debt. In the absence of such data, I would only assert that it doesn't feel right to type code without prior thinking when working on a 20 man-month project.

Keep the design pattern which doesn't make sense any longer, and try to add more patterns for the newly created situation?

This doesn't seem right neither. Patterns are used to simplify the understanding of the code; put too much patterns, and the code will become a mess.

Start thinking of a new design which encompasses the new requirements, then slowly refactor the old design into the new one?

As a theoretician and the one who favors Agile, I'm totally into it. In practice, when you know that you'll have to get back to the whiteboard every week and redo the large part of the previous design and that the customer just doesn't have enough funds to pay you for that, nor enough time to wait, this probably won't work.

So, any suggestions?

答:
My humble opinion is that you shouldn't avoid or not-avoid using design patterns.

Design patterns are simply well known and trusted solutions to general problems, that were given names. They aren't different in a technical manner than any other solution or design you can think of.

I think the root of the problem might be that your friend thinks in terms of "applying or not applying a design pattern", instead of thinking in terms of "what is the best solution I can think of, including but not limited to the patterns I know".

Maybe this approach leads him to use patterns in partly artificial or forced ways, in places where they don't belong. And this is what results in a mess.


答:
In your example of using the Null Object pattern, I believe it eventually failed because it met the programmer's needs and not the customer's needs. The customer needed to display the price in a form appropriate to the context. The programmer needed to simplify some of the display code.

So, when a design pattern doesn't meet the requirements, do we say that all design patterns are a waste of time or do we say that we need a different design pattern?

Title: Should we avoid using design patterns in constantly changing projects?

Body:
A friend of mine is working for a small company on a project every developer would hate: he's pressured to release as quickly as possible, he's the only one who seem to care about technical debt, the customer has no technical background, etc.

He told me a story which made me think about the appropriateness of design patterns in projects like this one. Here's the story.

We had to display products at different places on the website. For example, content managers could view the products, but also the end users or the partners through the API.

Sometimes, information was missing from the products: for example, a bunch of them didn't have any price when the product was just created, but the price wasn't specified yet. Some didn't have a description (the description being a complex object with modification histories, localized content, etc.). Some were lacking shipment information.

Inspired by my recent readings about design patterns, I thought this was an excellent opportunity to use the magical Null Object pattern. So I did it, and everything was smooth and clean. One just had to call product.Price.ToString("c") to display the price, or product.Description.Current to show the description; no conditional stuff required. Until, one day, the stakeholder asked to display it differently in the API, by having a null in JSON. And also differently for content managers by showing "Price unspecified [Change]". And I had to murder my beloved Null Object pattern, because there was no need for it any longer.

In the same way, I had to remove a few abstract factories and a few builders, I ended up replacing my beautiful Facade pattern by direct and ugly calls, because the underlying interfaces changed twice per day for three months, and even the Singleton left me when the requirements told that the concerned object had to be different depending on the context.

More than three weeks of work consisted of adding design patterns, then tearing them apart one month later, and my code finally became spaghetti enough to be impossible to maintain by anyone, including myself. Wouldn't it be better to never use those patterns in the first place?

Indeed, I had to work myself on those types of projects where the requirements are changing constantly, and are dictated by persons who don't really have in mind the cohesion or the coherence of the product. In this context, it doesn't matter how agile you are, you'll come with an elegant solution to a problem, and when you finally implement it, you learn that the requirements changed so drastically, that your elegant solution doesn't fit any longer.

What would be the solution in this case?

Not using any design patterns, stop thinking, and write code directly?

It would be interesting to do an experience where a team is writing code directly, while another one is thinking twice before typing, taking the risk of having to throw away the original design a few days later: who knows, maybe both teams would have the same technical debt. In the absence of such data, I would only assert that it doesn't feel right to type code without prior thinking when working on a 20 man-month project.

Keep the design pattern which doesn't make sense any longer, and try to add more patterns for the newly created situation?

This doesn't seem right neither. Patterns are used to simplify the understanding of the code; put too much patterns, and the code will become a mess.

Start thinking of a new design which encompasses the new requirements, then slowly refactor the old design into the new one?

As a theoretician and the one who favors Agile, I'm totally into it. In practice, when you know that you'll have to get back to the whiteboard every week and redo the large part of the previous design and that the customer just doesn't have enough funds to pay you for that, nor enough time to wait, this probably won't work.

So, any suggestions?


答:
I see some wrong assumptions in this question:

code with design patterns, though applied correctly, needs more time to be implemented than code without those patterns.

Design patterns are no end in itself, they should serve you, not vice versa. If a design pattern does not make the code easier to implement, or at least better evolvable (that means: easier to be adapted to changing requirements), then the pattern misses its purpose. Don't apply patterns when they don't make "life" easier for the team. If the new Null object pattern was serving your friend for the time he used it, then everything was fine. If it was to be eliminated later, then this could be also ok. If the Null object pattern slowed the (correct) implementation down, then its usage was wrong.  Note, from this part of the story one cannot conclude any cause of "spaghetti code" so far.

the customer is to blame because he has no technical background and does not care about cohesion or the coherence of the product

That is neither his job nor his fault! Your job is to care about cohesion and coherence. When the requirements change twice a day, your solution should not be to sacrifice the code quality. Just tell the customer how long it takes, and if you think you need more time for getting the design "right", then add a big enough safety margin to any estimation. Especially when you have a customer trying to pressure you, use the "Scotty Principle". And when arguing with a non-technical customer about the effort, avoid terms like "refactoring", "unit-tests", "design patterns" or "code documentation" - that are things he does not understand and probably regards to be "unnecessary nonsense" because he sees no value in it. Always talk about things which are visible or at least understandable to the customer (features, sub-features, behaviour changes, user docs, error fixes, performance optimization, and so on).

the solution for rapid changing requirements is to rapidly change the code

Honestly, if "underlying interfaces change twice per day for three months", then the solution should not be to react by changing the code twice a day. The real solution is to ask why the requirements change so often and if it is possible to make a change at that part of the process. Maybe some more upfront-analysis will help. Maybe the interface is too broad because the boundary between components is chosen wrong. Sometimes it helps to ask for more information regarding which part of the requirements are stable, and which are still under discussion (and actually postpone the implementation for things under discussion). And sometimes some people just have to be "kicked in their asses" for not changing their minds twice a day.


答:
Using SourceSafe in a commercial operation is like heating the building by burning dollar bills.

In 2000, my eight-developer company probably lost 5-10% of its productivity because of the twice-daily-on-average corruptions of VSS databases. It was only that low because we'd gone to hourly backups.

Since moving away from VSS to Perforce, svn, and git, I've never had an SCM database become corrupted.

Title: Is SourceSafe really safe?

Body:
Having spent all morning trying to check something in - I now realise I've lost a couple of days worth of work.

Its happened before - and is apparently common occurrence with SourceSafe.  Can SourceSafe be used successfully, without problems, and if so, how?