问:
Is this simple XOR encrypted communication absolutely secure?
Say Alice and Peter each have a 4GB USB flash memory stick. They meet and save on both sticks two files named alice_to_peter.key (2GB) and peter_to_alice.key (2GB) which contain randomly generated bits. They never meet again, but communicate electronically. Alice also maintains a variable called alice_pointer and Peter maintains variable called peter_pointer, both of which are initially set to zero.

When Alice needs to send a message to Peter, she does (where n is the nth byte of the message):

```<code>encrypted_message_to_peter[n] = message_to_peter[n] XOR alice_to_peter.key[alice_pointer + n]
encrypted_payload_to_peter = alice_pointer + encrypted_message_to_peter
alice_pointer += length(encrypted_message_to_peter)
</code>```

(and for maximum security, the used part of the key can be erased)

Peter receives encrypted_payload_to_peter, reads alice_pointer stored at the beginning of message and does:

```<code>message_to_peter[n] = encrypted_message_to_peter[n] XOR alice_to_peter.key[alice_pointer + n]
</code>```

And for maximum security, after reading of message also erase the used part of the key.
- EDIT: In fact this step with this simple algorithm (without integrity check and authentication) decreases security, see Paŭlo Ebermann post below.

When Peter needs to send a message to Alice they do the reverse, this time with peter_to_alice.key and peter_pointer.

With this trivial schema they can send each day for the next 50 years 2GB / (50 * 365) = ~115kB of encrypted data in both directions. If they need more data to send, they could use larger keys, for example with today's 2TB HDs (1TB keys) it would be possible to exchange 60MB/day for the next 50 years! That's a lot of data in practice; for example, using compression it's more than hour of high quality voice communication.

It seems to me that there is no way for an attacker to read the encrypted messages without the keys, because even if they have an infinitely fast computer, with brute force they can get every possible message under the limit, but this is an astronomical number of messages and the attacker doesn't know which of them is the actual message.

Am I right? Is this communication scheme really absolutely secure? And if it is secure, does it have its own name? XOR encryption is well-known, but I'm looking for the name of this concrete practical application using large keys on both sides? I am humbly expecting that this application has been invented someone before me. :-)

Note: If it's absolutely secure then it's amazing, because with today's low cost large storage devices, it would be much cheaper to do secure communication than with expensive quantum cryptography, and this has equivalent security!

EDIT:
I think this will be more practical in the future as storage costs decrease. It can solve secure communication forever. Today you have no certainty if someone successfully attacks existing ciphers even a year later and makes its often expensive implementations insecure. In many cases before communication occurs, when both sides meet personally, that's the time to generate the keys. I think it's perfect for military communication, for example between submarines which can have HDs with large keys, and military central can have a HD for each submarine. It could also be practical in everyday life, for example to control your bank account, because when you create your account you meet with the bank etc.

答:
Actually it's not entirely safe. What your protocol leaks is the LENGTH of the communicated message.

For example, if the spy knows you will reply with "yes" or "no" and sees the length =2 he can deduce it's "no".

It actually is amazing how much can be deduced only from known lengths if one can guess the context.


问:
How to convince management of making our project open source?
Xamarin 3 was released last week with a great new addition: Xamarin.Forms . This triggered our attention because we've been using such a system for a couple of years now. We've developed it by ourselves and used it for a bunch of projects.

We've been looking for a way to make this project open source but we didn't manage to convince the management. They believe we should not make it open source because we won't win anything with it and all that will happen is that the competition will be able to build apps quicker with our library. We believe open sourcing our library will make the world a better place and that it will make our library much more stable and complete.

So my question to all you people out there: How can we convince the management to open source our library?

答:
Let's assume you open source this project and your competition starts to use it and they save time creating apps which makes them equally attractive to customers.

If your company isn't marketing, selling or making a counter-proposal to this client, you'll never win the account, but there is a chance your competition wouldn't win it without your open source project. The fact is, someone will and it will NOT be your company in this case.

In the case where your company is directly competing for the same account, why wouldn't you be able to convince the client to hire you since you created the platform the competition is using? Your company should be the known absolute experts. Try to claim you can build a better basecamp.com using Ruby On Rails-pause for laughter.

Will making it open source improve the project? Tell your bosses you'll be getting 'free' testing and bug fixing. The code base will become more solid. With your company as the sponsor, very few will be able to make any grand claims to being a better contributor than your company. It's a marketing strategy.

Save the "make the world a better place" for the convention keynote address.

ContentLicense: CC BY-SA 3.0


问:
Storing editable site content?
We have a Django-based website for which we wanted to make some of the content (text, and business logic such as pricing plans) easily editable in-house, and so we decided to store it outside the codebase. Usually the reason is one of the following:

It's something that non-technical people want to edit. One example is copywriting for a website - the programmers prepare a template with text that defaults to "Lorem ipsum...", and the real content is inserted later to the database.

It's something that we want to be able to change quickly, without the need to deploy new code (which we currently do twice a week). An example would be features currently available to the customers at different tiers of pricing. Instead of hardcoding these, we read them from database.

The described solution is flexible but there are some reasons why I don't like it.

Because the content has to be read from the database, there is a performance overhead.

We mitigate that by using a caching scheme, but this also adds some complexity to the system.

Developers who run the code locally see the system in a significantly different state compared to how it runs on production. Automated tests also exercise the system in a different state. Situations like testing new features on a staging server also get trickier - if the staging server doesn't have a recent copy of the database, it can be unexpectedly different from production.

We could mitigate that by committing the new state to the repository occasionally (e.g. by adding data migrations), but it seems like a wrong approach. Is it?

Any ideas how best to solve these problems? Is there a better approach for handling the content that I'm overlooking?

答:
This is a good task for your DevOps. :)
You can do the following:

Put editable resources in separate artifact/VCS repository (I'll use Git terminology here).

Implement your build and deployment process so that these resources will be simply pulled from that repository to separate location on server (you can establish some convention for different environments so you will not need to configure this location separately for each one).

When user changes something on the web site, the change is simply saved to resource file. Push to remote repository is executed asynchronously on each change.

To deploy any changes, developer disables the editing functionality and merges his changes into remote repository. Then, on production, he pulls the merged files from remote repo. After that, editing functionality can be re-enabled.

It's possible to automate everything except the merge with Chef or any other tool, so this solution can be comfortable both for users, developers and SQA.

Title: Storing editable site content?


问:
Can I, as author and copyright holder, relicense my code under a more liberal license after it has been published under a more restrictive license?
Say, for example I published my code under GPL.

A month after release, I decide evil corporations (*cough*) are allowed to use my code after all, because it's so brilliant and bug-free. Can I just relicense my own code, or have I locked myself out of the right to do so?

答:
Yes, the license says what other people can do to the code not what you (the copyright holder) can.

Of course GPL does not prevent a corporation from using code - or even distributing code, however they may want to license under a different license to prevent their code needing to be GPL


答:
As a copyright holder you can license the code any which way you want, again and again and again.  You could license it as GPL, and then have a client ask for a license for the MS-Pl for one of their projects, and then license it again under BSD...

You, the copyright holder, always have the power to decide to release the work under a different license.  You can't revoke how people got it previously, but you can always release it under a new license.

That 'you can't revoke' does have some implications.  If someone went to your GPL version and forked it form there, with their contributions being GPL licensed, that code would still be GPL licensed.

The license is something you use to instruct other people on how they can use your code - and the license for it sticks with it.  It never limits how you can use it or decide to license and relicense your code.

Title: Can I, as author and copyright holder, relicense my code under a more liberal license after it has been published under a more restrictive license?

Body:
Say, for example I published my code under GPL.

A month after release, I decide evil corporations (*cough*) are allowed to use my code after all, because it's so brilliant and bug-free. Can I just relicense my own code, or have I locked myself out of the right to do so?


问:
Mechanics of reasoning during programming interviews
This is not the usual "I don't want to write code during an interview", in this question the assumption is that

I need to write code during an interview (think about the level of rewriting the quicksort or mergesort from scratch)

I know how the algorithm work or I have a basic idea of how I should start working from there, i.e. I don't remember the algorithm by heart

I noticed that even on a whiteboard, I always end up writing bugged code or code that doesn't compile. If there's a typo, whatever I usually live with that.. but when there's a crash due to some uncaught particular case I end up losing confidence in my skills.

I realize that perhaps interviewers might want to look at how I write code and/or how I solve problems rather than proof-compiling my whiteboard code, but I'd like to ask how should I approach the above problem in mental terms, i.e. what mental steps should I follow when writing code for an interview with the two bullet points above.

There must be a unique and agreed series of steps I should follow to avoid getting stuck/caught into particular exception cases (limit cases) that might end up wasting my time and my energies rather than focusing on the overall algorithm for the general case.

I hope I made my point clear

答:
If I were asked to write code for a problem that I thought was particularly finicky or had edge-case complications, I would definitely write notes on the board first. For a simple example, let's say I was asked to write the method Arrays.toString(int[] array) in Java. I would write, on the board, something like:

If the input is null, return "null"

If the input is an empty array, return "[]"

Otherwise, I must:

Output a "[" for the first element

Output a "]" for the last element

Output a ", " between elements

If there is exactly one element, don't print a ", ".

Then, I would tell the interviewer that normally I would write test cases first to test each of these bullets, and ask them if they want me to do that here. Assuming they say no, as I write the code, I would keep each of these bullets in mind, and check them off as I am fairly certain they work.

Doing this planning step is something you could and should definitely practice yourself with some of the easier problems on Project Euler or from the Elements of Programming Interviews book.


问:
Should angularjs directive directly interact with services or is it considered an anti-pattern?
Which one is considered better:

having a directive that interacts with services directly

or

having a directive that exposes certain hooks to which controller may bind behaviour (involving services)?

答: As per AngularJS framework , we should singleton factories/services for getting any data from server. So that these factories can be reused across application without rewriting the same.Well inside directive we can call these factories to get data fetched from Api/server.</p>


答:
I noticed that even on a whiteboard, I always end up writing bugged code or code that doesn't compile.

I've seen this happen in interviews and it often is followed by a statement of denial. The candidate will struggle to write effective code, and then make statements like "I write better code than this". The problem here is that the candidate just demonstrated that he/she does not.

While you can counter argue that the problem is context. That solving problems in an interview is not the same as in the quiet private space of your own desk. It is the interview context that matters to successfully get the job for that quiet desk.

I realize that perhaps interviewers might want to look at how I write code and/or how I solve problems rather than proof-compiling my whiteboard code

There is no solution to a problem if it does not compile, and interviewers can see how you write code once you've put it on the whiteboard.

Your argument is this: My problem solving abilities with this programming language are not relative to my understanding of the languages syntax and compiling rules.

If you want to demonstrate only your problem solving abilities, then ask to solve the problem in a different programming language. One that you will not make mistakes in.

how should I approach the above problem in mental terms, i.e. what mental steps should I follow when writing code for an interview with the two bullet points above

Practice:

Google popular programming challenges for interviews, and then practice solving them. If the whiteboard presents a challenge then buy a whiteboard and practice on one.

Practice writing source code on paper with a pen. Review your work for compile accuracy and then work on improving it.

Study the rules for the compiler you are using.

There is no easy answer other than to work on improving oneself in the areas they are weakest.

Good luck on your interviews.

Title: Mechanics of reasoning during programming interviews

Body:
This is not the usual "I don't want to write code during an interview", in this question the assumption is that

I need to write code during an interview (think about the level of rewriting the quicksort or mergesort from scratch)

I know how the algorithm work or I have a basic idea of how I should start working from there, i.e. I don't remember the algorithm by heart

I noticed that even on a whiteboard, I always end up writing bugged code or code that doesn't compile. If there's a typo, whatever I usually live with that.. but when there's a crash due to some uncaught particular case I end up losing confidence in my skills.

I realize that perhaps interviewers might want to look at how I write code and/or how I solve problems rather than proof-compiling my whiteboard code, but I'd like to ask how should I approach the above problem in mental terms, i.e. what mental steps should I follow when writing code for an interview with the two bullet points above.

There must be a unique and agreed series of steps I should follow to avoid getting stuck/caught into particular exception cases (limit cases) that might end up wasting my time and my energies rather than focusing on the overall algorithm for the general case.

I hope I made my point clear


问:
REST API at backend and MVC Javascript framework at client side
I am building an online social network. I have finished writing RESTful API service using Django. This will return only JSON response (No HTML will be generated from server side) so that this JSON response can be used to build native smartphone apps. API service being common to all clients.

My question is, since there is no HTML response from server side, can the MV* Javascript Frameworks like Angular / Backbone / Ember take care of complete Front-end, right from generating HTML page with CSS?

答:
Yes, popular MVC framework like AngularJS/Ember works for you.

AngularJS framework gives greatest advantage of TWO WAY binding, it means that any change in MODEL will automatically get changed in VIEW and vice verse.

Mainly AngularJS is for Data binding, it takes complete care of calling web api and binding data with concerned html elements.

And for generating HTML which can be easily done creating angularJS directive, which makes your application clean , neat and maintainable code.

Lastly for CSS you can use bootstrap 3 , which has inbuilt in classes for responsive UI design for all type of devices.

Hope this helps for you.


问:
How can I be certain that my code is flawless?
I have just completed an exercise from my textbook which wanted me to write a program to check if a number is prime or not.

I have tested it and seems to work fine, but how can I be certain that it will work for every prime number?

```<code>public boolean isPrime(int n)
    {
       int divisor = 2;
       int limit = n-1 ;

            if (n == 2)
            {
                return true;
            }
            else
            {
                int mod = 0;
                while (divisor <= limit)
                {
                      mod = n % divisor;
                      if (mod == 0)
                      {
                          return false;
                      }
                    divisor++;
                }

                if (mod > 0)
                {
                    return true;
                }
            }

      return false;
}
</code>```

Note that this question is not a duplicate of Theoretically Bug Free Programs because that question asks about whether one can write bug free programs in the face of the the limitative results such as Turing's proof of the incomputability of halting, Rice's theorem and Godel's incompleteness theorems. This question asks how a program can be shown to be bug free.

答:
You cannot establish correctness via testing. All that tests tell you is that the system responds correctly to the cases you exercised. (Even if there is a finite number of possible inputs, that is not enough, because strictly speaking, the test only tells you that the system responded correctly in this instance - it might be secretly non-deterministic, and you'd never know.)

To establish that your code is indeed correct for all possible inputs, verification is required. It amounts to a mathematical proof that the transformation that your code embodies is indeed the correct one for the specified problem.

Verification is perfectly possible, particularly for mathematical tasks, but usually not worth the added effort. Particularly, making sure that your requirement does indeed state what it seems to state and your code does indeed define what it seems to define is surprisingly difficult and hairy when all details of a real programming language, platform, standard library etc. are properly considered. That is why verification is not encountered  in practice as much as copious amounts of regression tests.


答:
For something like prime numbers, you will never be sure that it will work for all primes, because the set of all prime numbers is infinitely long, and therefore you'd never stop coding your unit test.  That being said, there's many different ways to judge the quality of code, and passing a unit test is only one of them.  For example, if you're building a piece of code to find all the primes in the world, your solution will probably work fine for lower numbers, but as the size of the numbers gets larger, you will exceed the size of int, which means you've got one small limitation in your program.  Also, performance will degrade as the numbers get bigger and your loop takes longer.

One other small point, negative numbers can't be prime, so instead of int, you could use unsigned int, or unsigned long to extend the range of numbers you can verify.

In your case though, what you're doing is focusing on the wrong thing.  No code is ever flawless.  There will always be bugs.  Does it meet the requirements you have set before you?  Does it perform adequately well for your needs?

Then you're good.

Title: How can I be certain that my code is flawless?

Body:
I have just completed an exercise from my textbook which wanted me to write a program to check if a number is prime or not.

I have tested it and seems to work fine, but how can I be certain that it will work for every prime number?

```<code>public boolean isPrime(int n)
    {
       int divisor = 2;
       int limit = n-1 ;

            if (n == 2)
            {
                return true;
            }
            else
            {
                int mod = 0;
                while (divisor <= limit)
                {
                      mod = n % divisor;
                      if (mod == 0)
                      {
                          return false;
                      }
                    divisor++;
                }

                if (mod > 0)
                {
                    return true;
                }
            }

      return false;
}
</code>```

Note that this question is not a duplicate of Theoretically Bug Free Programs because that question asks about whether one can write bug free programs in the face of the the limitative results such as Turing's proof of the incomputability of halting, Rice's theorem and Godel's incompleteness theorems. This question asks how a program can be shown to be bug free.


问:
How to Detect Sprites in a SpriteSheet?
I'm currently writing a Sprite Sheet Unpacker such as Alferds Spritesheet Unpacker. Now, before this is sent to gamedev, this isn't necessarily about games. I would like to know how to detect a sprite within a spriitesheet, or more abstactly, a shape inside of an image.

Given this sprite sheet:

I want to detect and extract all individual sprites. I've followed the algorithm detailed in Alferd's Blog Post which goes like:

Determine predominant color and dub it the BackgroundColor

Iterate over each pixel and check ColorAtXY == BackgroundColor

If false, we've found a sprite. Keep going right until we find a BackgroundColor again, backtrack one, go down and repeat until a BackgroundColor is reached. Create a box from location to ending location.

Repeat this until all sprites are boxed up.

Combined overlapping boxes (or within a very short distance)

The resulting non-overlapping boxes should contain the sprite.

This implementation is fine, especially for small sprite sheets. However, I find the performance too poor for larger sprite sheets and I would like to know what algorithms or techniques can be leveraged to increase the finding of sprites.

A second implementation I considered, but have not tested yet, is to find the first pixel, then use a backtracking algorithm to find every connected pixel. This should find a contiguous sprite (breaks down if the sprite is something like an explosion where particles are no longer part of the main sprite). The cool thing is that I can immediately remove a detected sprite from the sprite sheet.

Any other suggestions?

答:
After a little browsing, I created my own solution a few months back but failed to post it here in the interest of anybody that would like to do the same. Therefore, I will quickly describe the method before showing the code. It's in kotlin, but if you're familiar with Java and/or AS3 you should be able to understand the syntax.

The Method

Scan the entire image and store each color in a table.

Determine which color shows up most often- this is the background color

Start at the top left and scan each line.

If a pixel does not match the background color, then it is a sprite.

Use a backtracking algorithm to "fill out" the entire sprite.

Create a rectangle out of this plot.

Store it and cut the sprite out of the image.

Repeat 4-7 until finished.

The Code

The source is available on github, and here is the code w/o documentation or imports.

```<code> fun unpack(spriteSheet: Path): List<Image> {
    Preconditions.checkArgument(Files.exists(spriteSheet),
                                "The file ${spriteSheet.getFileName()} does not exist")

    logger.debug("Loading sprite sheet.")
    // TODO: Convert to png so we have an alpha layer to work with
    val spriteSheetImage = readImage(spriteSheet).toBufferedImage()

    logger.debug("Determining most probable background color.")
    val backgroundColor  = determineProbableBackgroundColor(spriteSheetImage)
    logger.debug("The most probable background color is $backgroundColor")

    return findSprites(spriteSheetImage, backgroundColor) map(::copySubImage.bindFirst(spriteSheetImage))
}

private fun findSprites(image: BufferedImage,
                        backgroundColor: Color): List<Rectangle> {
    val workingImage = copy(image)

    val spriteRectangles = ArrayList<Rectangle>()
    for (pixel in workingImage) {
        val (point, color) = pixel

        if (color != backgroundColor) {
            logger.debug("Found a sprite starting at (${point.x}, ${point.y})")
            val spritePlot = findContiguous(workingImage, point) { it != backgroundColor }
            val spriteRectangle = Rectangle(spritePlot, image)

            logger.debug("The identified sprite has an area of ${spriteRectangle.width}x${spriteRectangle.height}")

            spriteRectangles.add(spriteRectangle)
            eraseSprite(workingImage, backgroundColor, spritePlot)
        }
    }

    logger.info("Found ${spriteRectangles.size()} sprites.")
    return spriteRectangles
}

private fun findContiguous(image: BufferedImage, point: Point, predicate: (Color) -> Boolean): List<Point> {
    val unvisited = LinkedList<Point>()
    val visited   = HashSet<Point>()

    unvisited.addAll(neighbors(point, image) filter { predicate(Color(image.getRGB(it.x, it.y))) })

    while (unvisited.isNotEmpty()) {
        val currentPoint = unvisited.pop()
        val currentColor = Color(image.getRGB(currentPoint.x, currentPoint.y))

        if (predicate(currentColor)) {
            unvisited.addAll(neighbors(currentPoint, image) filter {
                !visited.contains(it) && !unvisited.contains(it) &&
                predicate(Color(image.getRGB(it.x, it.y)))
            })

            visited.add(currentPoint)
        }
    }

    return visited.toList()
}

private fun neighbors(point: Point, image: Image): List<Point> {
    val points = ArrayList<Point>()

    if (point.x > 0)
        points.add(Point(point.x - 1, point.y))
     if (point.x < image.getWidth(null) - 1)
     points.add(Point(point.x + 1, point.y))

     if (point.y > 0)
     points.add(Point(point.x, point.y - 1))
     if (point.y < image.getHeight(null) - 1)
     points.add(Point(point.x, point.y + 1))

     return points
 }
</code>```

However, the code is not yet complete- packing and creating the metafile is missing- and has been languishing in my Github since March, but I'll hopefully complete it one day.

ContentLicense: CC BY-SA 4.0

Title: How to Detect Sprites in a SpriteSheet?

Body:
After a little browsing, I created my own solution a few months back but failed to post it here in the interest of anybody that would like to do the same. Therefore, I will quickly describe the method before showing the code. It's in kotlin, but if you're familiar with Java and/or AS3 you should be able to understand the syntax.

The Method

Scan the entire image and store each color in a table.

Determine which color shows up most often- this is the background color

Start at the top left and scan each line.

If a pixel does not match the background color, then it is a sprite.

Use a backtracking algorithm to "fill out" the entire sprite.

Create a rectangle out of this plot.

Store it and cut the sprite out of the image.

Repeat 4-7 until finished.

The Code

The source is available on github, and here is the code w/o documentation or imports.

 fun unpack(spriteSheet: Path): List<Image> {
    Preconditions.checkArgument(Files.exists(spriteSheet),
                                "The file ${spriteSheet.getFileName()} does not exist")

    logger.debug("Loading sprite sheet.")
    // TODO: Convert to png so we have an alpha layer to work with
    val spriteSheetImage = readImage(spriteSheet).toBufferedImage()

    logger.debug("Determining most probable background color.")
    val backgroundColor  = determineProbableBackgroundColor(spriteSheetImage)
    logger.debug("The most probable background color is $backgroundColor")

    return findSprites(spriteSheetImage, backgroundColor) map(::copySubImage.bindFirst(spriteSheetImage))
}

private fun findSprites(image: BufferedImage,
                        backgroundColor: Color): List<Rectangle> {
    val workingImage = copy(image)

    val spriteRectangles = ArrayList<Rectangle>()
    for (pixel in workingImage) {
        val (point, color) = pixel

        if (color != backgroundColor) {
            logger.debug("Found a sprite starting at (${point.x}, ${point.y})")
            val spritePlot = findContiguous(workingImage, point) { it != backgroundColor }
            val spriteRectangle = Rectangle(spritePlot, image)

            logger.debug("The identified sprite has an area of ${spriteRectangle.width}x${spriteRectangle.height}")

            spriteRectangles.add(spriteRectangle)
            eraseSprite(workingImage, backgroundColor, spritePlot)
        }
    }

    logger.info("Found ${spriteRectangles.size()} sprites.")
    return spriteRectangles
}

private fun findContiguous(image: BufferedImage, point: Point, predicate: (Color) -> Boolean): List<Point> {
    val unvisited = LinkedList<Point>()
    val visited   = HashSet<Point>()

    unvisited.addAll(neighbors(point, image) filter { predicate(Color(image.getRGB(it.x, it.y))) })

    while (unvisited.isNotEmpty()) {
        val currentPoint = unvisited.pop()
        val currentColor = Color(image.getRGB(currentPoint.x, currentPoint.y))

        if (predicate(currentColor)) {
            unvisited.addAll(neighbors(currentPoint, image) filter {
                !visited.contains(it) && !unvisited.contains(it) &&
                predicate(Color(image.getRGB(it.x, it.y)))
            })

            visited.add(currentPoint)
        }
    }

    return visited.toList()
}

private fun neighbors(point: Point, image: Image): List<Point> {
    val points = ArrayList<Point>()

    if (point.x > 0)
        points.add(Point(point.x - 1, point.y))
     if (point.x < image.getWidth(null) - 1)
     points.add(Point(point.x + 1, point.y))

     if (point.y > 0)
     points.add(Point(point.x, point.y - 1))
     if (point.y < image.getHeight(null) - 1)
     points.add(Point(point.x, point.y + 1))

     return points
 }

However, the code is not yet complete- packing and creating the metafile is missing- and has been languishing in my Github since March, but I'll hopefully complete it one day.


问:
Where should I start reading AngularJS's source code?
After reading this article I realized that I really didn't read any "serious" source code during my 3-years as a professional developer.

Recently I started a new web-project which makes heavy use of AngularJS, so I decided to start my reading - or, better, decoding [as the blogger wrote] - activity from something that is both challenging and professionally useful.

Now I just need to be pointed in the right direction. Should I just start from the start of the source code or is there a better starting point?

答:
For AngularJS :
Prerequisites ::
1) Firstly you need have good hands over on JAVASCRIPT patterns like revealing pattern, prototype pattern, model pattern and prototype revealing pattern.
2) Go through MVC framework concepts how does this works. Taking server side MVC frameworks like MVC3/MVC4.

Going through above steps first will be added advantage while understanding angularjs :: Directives, structure **and work flow.**
 Greatest source for learning AngularJS concepts is  https://docs.angularjs.org/guide/concepts

Lastly  http://plnkr.co/ this is greatest online tool for editing and running angularjs application.


问:
asp.net mvc vs angular.js model binding
So I've noticed a trend lately of .net web developers using angular.js on the client side of applications and I've become more curious as I play around with angular and compare it to how I would do things in asp.net mvc.

I'll give a quick example of what really got me thinking.

I recently came across a situation at work (I work in a .net environment) where I needed to create a table bound to a collection of objects that had the ability to add and remove rows/items from the collection. I had an add button that created a new object and appended a row to the end of the table, and a remove button in each row to remove a particular object/row. Using asp.net mvc, I first found myself making an ajax call to the server for each operation, updating the server side model, and refreshing part of the page to show the result in the table. This worked but I didn't really like the idea of calling the server to update the model each time, so I tried to come up with a solution to do this on the client side. It turned out to be quite a task, as I had to generate the html on add with validation and all and the correct indexing for the model binding to work. It got worse on remove, as I ended up with a crazy string replace function to recreate the indexes on each item to satisfy the binding requirements (if an item other than the last is removed, the indexes are no longer correct). Now out of curiosity, I tried to recreate this at home in angular (which I had no experience with) and it took me all of about 10 minutes with simple functions to add and remove items from the client side model.

This is just one example, but it seems to me that I'm able to achieve the same results with far fewer calls to the server in angular because of the fact that it binds to a client side model.

So my question is, is this a distinct advantage of using a javascript mvc framework or am I somehow under utilizing the power of asp.net mvc and am I right in thinking that these operations should be done on the client and have no business requiring calls to the server?

答:
Greatest benefit of using AngularJS framework (MVC) at client side is TWO WAY BINDING.
Basically Asp net MVC is at server side.And you can use angularjs at client side for binding data.

Title: asp.net mvc vs angular.js model binding


问:
How can I handle this string concatenation in C in a reusable way
I've been writing a small C application that operates on files, and I've found that I have been copy+pasting this code around my functions:

```<code>char fullpath[PATH_MAX];
fullpath[0] = '\0';
strcat(fullpath, BASE_PATH);
strcat(fullpath, subdir);
strcat(fullpath, "/");
strcat(fullpath, filename);

// do something with fullpath...
</code>```

Is there a better way? The first thought that comes to mind is to create a macro but I'm sure this is a common problem in C, and I'm wondering how others have solve it.

答:
Reusable for a function like the one you describe means several things:

Doesn't assume the input is valid.

Uses sane defaults.

Prevents buffer overruns.

Returns some indication of success or failure.

In your case:

```<code>#define BASE_PATH "/path/to/wherever"
bool build_path(char *dest, size_t size, char *subdir, char *filename)
{
    // Don't assume the input is valid
    if ( (dest == NULL) || (size < 1) || (filename == NULL) ) {
        return false;
    }

    // Make no subdir work  (sane default behavior)
    if ( subdir == NULL ) {
        subdir = "";
    }

    // Prevent buffer overruns by using a safe formatting function
    size_t stored = snprintf(dest, size, BASE_PATH "/%s/%s", subdir, filename);

    // Returns success (true) if the path fit the buffer
    return ((stored+1) <= size);
}

char fullpath[PATH_MAX];
if ( ! build_path(fullpath, sizeof(fullpath), "foo/bar", "baz") ) {
   // Handle error
}
</code>```

Body:
Reusable for a function like the one you describe means several things:

Doesn't assume the input is valid.

Uses sane defaults.

Prevents buffer overruns.

Returns some indication of success or failure.

In your case:

#define BASE_PATH "/path/to/wherever"
bool build_path(char *dest, size_t size, char *subdir, char *filename)
{
    // Don't assume the input is valid
    if ( (dest == NULL) || (size < 1) || (filename == NULL) ) {
        return false;
    }

    // Make no subdir work  (sane default behavior)
    if ( subdir == NULL ) {
        subdir = "";
    }

    // Prevent buffer overruns by using a safe formatting function
    size_t stored = snprintf(dest, size, BASE_PATH "/%s/%s", subdir, filename);

    // Returns success (true) if the path fit the buffer
    return ((stored+1) <= size);
}

char fullpath[PATH_MAX];
if ( ! build_path(fullpath, sizeof(fullpath), "foo/bar", "baz") ) {
   // Handle error
}


问:
Should a Parent with Children have a DefaultChild, or should a Child have a Default property?
Which of the following two models makes more sense? I'm leaning towards the first one because there can only be one default child.

The examples are in C# but I think it can apply to other languages too.

Here DefaultChild holds one of the items in Children.

```<code>class Parent
{
    int ID { get; set; }

    Child DefaultChild { get; set; }

    IEnumerable<Child> Children { get; set; }
}

class Child
{
    int ID { get; set; }
}
</code>```

Here one of the items in Children has Default set to true while the others have it set to false.

```<code>class Parent
{
    int ID { get; set; }

    IEnumerable<Child> Children { get; set; }
}

class Child
{
    int ID { get; set; }

    bool Default { get; set; }
}
</code>```

A concrete situation: a User in our system has one or more Customers attached. When logging in, if said User has a default Customer, they are immediately working under this Customer. If they don't, they have to select a Customer to work under. While logged in, they can switch between Customers.

答:
In your specific scenario, a Parent should have a DefaultChild. The problem with giving a child an IsDefault property is that it A) allows for Parents with multiple default children and B) disallows Parents of the same child to have different settings for their child. The fact that neither of these scenarios can actually happen is irrelevant; both scenarios logically make sense, despite not at all matching your intentions.

From a high level perspective, it makes more sense to talk about the Default child of a parent than to say a particular child is inherently a default.


答:
You are confusing contract details with implementation details. A contract is the API that objects expose to be manipulated.

What you need to decide upon is what interface you need for those objects. How those objects are implemented is just an exercise in code efficiency.

Let's assume the following interfaces make sense.

```<code>public interface iNode
{
     int getID();
     bool isDefault();
}

public interface iParent : iNode
{
     iNode getDefault();
     IEnumerable<iNode> getChildren();
}
</code>```

What methods your interface has can limit or expand your implementation details. You need to decide if you need isDefault knowledge of an iNode in your code elsewhere.

Here is one approach.

```<code>public class Node : iNode
{
    public int getID() { return _id; }
    public bool isDefault() { return _default; }
}

public class Parent : Node
{
    public iNode getDefault() { return getChildren().FirstOrDefault(child=>child.isDefault()); }
    public IEnumerable<iNode> getChildren() { return _children; }
}
</code>```

Alternatively, if you do not require that iNode expose that it is a default.

```<code>public class Node : iNode
{
    public int getID() { return _id; }
}

public class Parent : Node
{
    public iNode getDefault() { return _default; }
    public IEnumerable<iNode> getChildren() { return _children; }
}
</code>```

It's important to focus on how your objects will be used, and not get overly distracted by how they will be implemented. Do you expect to have references to iNode objects and no longer have a reference to it's parent? If so, maybe it should have a flag that it's the default.

Still, you could just add getParent to the iNode interface.

I think you need to flush out your object contracts first.

Title: Should a Parent with Children have a DefaultChild, or should a Child have a Default property?

Body:
Which of the following two models makes more sense? I'm leaning towards the first one because there can only be one default child.

The examples are in C# but I think it can apply to other languages too.

Here DefaultChild holds one of the items in Children.

```<code>class Parent
{
    int ID { get; set; }

    Child DefaultChild { get; set; }

    IEnumerable<Child> Children { get; set; }
}

class Child
{
    int ID { get; set; }
}
</code>```

Here one of the items in Children has Default set to true while the others have it set to false.

```<code>class Parent
{
    int ID { get; set; }

    IEnumerable<Child> Children { get; set; }
}

class Child
{
    int ID { get; set; }

    bool Default { get; set; }
}
</code>```

A concrete situation: a User in our system has one or more Customers attached. When logging in, if said User has a default Customer, they are immediately working under this Customer. If they don't, they have to select a Customer to work under. While logged in, they can switch between Customers.

Body:
You are confusing contract details with implementation details. A contract is the API that objects expose to be manipulated.

What you need to decide upon is what interface you need for those objects. How those objects are implemented is just an exercise in code efficiency.

Let's assume the following interfaces make sense.

public interface iNode
{
     int getID();
     bool isDefault();
}

public interface iParent : iNode
{
     iNode getDefault();
     IEnumerable<iNode> getChildren();
}

What methods your interface has can limit or expand your implementation details. You need to decide if you need isDefault knowledge of an iNode in your code elsewhere.

Here is one approach.

public class Node : iNode
{
    public int getID() { return _id; }
    public bool isDefault() { return _default; }
}

public class Parent : Node
{
    public iNode getDefault() { return getChildren().FirstOrDefault(child=>child.isDefault()); }
    public IEnumerable<iNode> getChildren() { return _children; }
}

Alternatively, if you do not require that iNode expose that it is a default.

public class Node : iNode
{
    public int getID() { return _id; }
}

public class Parent : Node
{
    public iNode getDefault() { return _default; }
    public IEnumerable<iNode> getChildren() { return _children; }
}

It's important to focus on how your objects will be used, and not get overly distracted by how they will be implemented. Do you expect to have references to iNode objects and no longer have a reference to it's parent? If so, maybe it should have a flag that it's the default.

Still, you could just add getParent to the iNode interface.

I think you need to flush out your object contracts first.


问:
Dalvik + Java licensing question
This is a licensing question about the Dalvik and J2SE core libraries. In particular the license governing java.util.concurrent.SynchronousQueue.

The license header of the class in the JDK source states that it is GPLv2 only (see grepcode).
However, the same file in the Dalvik core libraries seems to be governed by the Apache 2 license only (see android source).

How is this possible? I didn't think you could take GPLv2 source and re-license it as Apache 2.

(It's obvious they did: a comment above the Java Doc even says "removed link to collections framework docs"!)

I'm asking because I have a GPLv3 project and would like to include a derivative work of some source from the core libraries (either Dalvik or J2SE) but publish it under GPLv3. I thought I could do this with Apache 2, but not GPLv2.

I know that the J2SE class source is itself derivative work from public domain source, but the changes from the original are substantial. (The original is available at gee.cs.oswego.edu if you are interested.) Therefore the android source really is just a copy of the J2SE source, but published under Apache 2 instead of GPLv2. Is Google really allowed to do this?

答:
I understand the complexities of the situation, and I doubt you will get a good answer without paying for it. Which I would not recommend.

As I tell people repeatedly, if you make no money out of it and harm no-one then just do your best, acknowledge the work of others and don't worry too much. If you make money out of your product or services and/or if you may cause damage to someone, you must take competent legal advice. That won't protect you, but it will warn you about the risks and possibly help to mitigate them.

Title: Dalvik + Java licensing question


问:
Synthetic database records
Assume we are getting some statistics from a customer which we analyse and we send our comments to the customer.  Now, the customer tells us that the statistic they computed between January and March are based on a wrong methodology and sends us corrected series.  We want perform analysis with the wrong and with the correct set of data, which are huge and only differ from January to March, so that we want to avoid data duplication.

Therefore, we need something like synthetic database records implementing the following logic:

```<code>synthetic[1] = wrong_data
synthetic[2] = correct_data between Januar and March, wrong_data otherwise
</code>```

With this, we can easily perform our analyses on synthetic records.

Should such synthetic records be implemented in the application logic or on the side of the database?  What are common pitfalls of such an implementation?

答:
Since synthetic records are actually data, I would ... um, put them in the database.

The logic for retrieving them is relatively straightforward.  You do an outer join on the synthetic table, and substitute the synthetic value if the outer join returns something other than a null.  The simplest way is just to replace the entire record.

If you want to "version" the data, you can provide a sequence number field, at the cost of a little more complexity in the SQL to retrieve the most current version of the synthetic data.  Since you probably only want the most recent revision in most cases, the most sensible approach is to put the current record data in a "history" table, and modify the original record in place.

Further Reading

How to version control a record in a database

SQL Strategies for Versioned Data

Title: Synthetic database records


问:
how can we have a person to allot and track tasks in agile development
I understand that Agile team should be self organized and self driven,

but is there a provision that I can have someone who will allot tasks to developers and ensure that all user stories will be completed on time??

For example if there are two persons in an agile team who are not self motivated to take up tasks and they will work only when task is assigned to them with a deadline, how can we deal this in Agile?

The problem I face is that no one is fixing the deadlines for the tasks and the team is under delivering for the last two sprints.
It will be better if we can have someone who can fix deadlines. IS there a provision for this in Agile

答:
To answer your question directly, you can with a scrum master or senior developer dictating this, but shouldn't.

It sounds like you are at the start of an agile journey. It is the Scrum Master's job to enforce the rules of Scrum, which is exactly what you need at this stage.  Over time the team will get better at discussing and distributing tasks, but will need some encouragement to start with.

As a scrum master in this situation I would:

Ensure stories are split into tasks that are smaller than half a days work for one person, and estimated in hours at sprint planning.  This means everyone can see progression (or none) quickly and clearly on a daily basis.

Ensure that at the stand up every team member commits to deliver an appropriate amount of work.  If they don't, ask them why they won't commit to more, and don't let them avoid it unless there is a valid reason.  This is the crux of the issue.  With a team I worked with in the past we even marked our daily committed tasks with a dot, so we could see if we under delivered the next day.

At the stand-up the next day if people haven't met their commitment, get them to update the estimate to how long they think is remaining.  Ask why they didn't get it completed and offer help from others, but make sure to do this with concern, not anger.  Do not pass their tasks off to other people, but offer them all the assistance they need from other developers that could help.

Use the burn-down chart as a discussion point at the stand-up and ask the team how we (not they) can get the top priority story (or the sprint goal) done, but do not allocate work to them yourself.  You shouldn't really get hugely behind if the estimates are ok and you are following the steps above, but if you do it is a talking point for the retrospective.  Is it distractions? Was it too much work in the sprint? Was it risky work you didn't think about enough? Absence?  Learn from it.

I don't think you should allocate tasks any more formally than this, but at the early stages it is important to track them.  Whether you link this to people (names on tasks) is up to you, but I prefer not to as it encourages team input into a task and a less individual mindset, and also reduces the feeling of being monitored as a developer.


答:
There are a number of frameworks for proving that code is correct.  You can read about some of them in books such as

A practical theory of programming, Hehner, 1993-2014.

The science of programming, Gries, 1981.

A method of programming, Dijkstra and Feijn, 1988.

Programming from specifications, Morgan, 1990, 1994, 1998.

For your program, I'll assume that you don't care about negative n and that you can handle the n==0, n==1, and n==2 cases without any help; I'll only look at the case where n>2.

The key is to note that (in cases where n > 2) every time the loop's guard expression divisor <= limit is evaluated, the following 5 facts are true of the program's state:

```<code>n % i != 0, for all i from 2 up to, but not including divisor
limit == n-1
2 <= divisor && divisor <= n
mod != 0 || divisor == 2
n is the same as the argument  // i.e. n hasn't been changed
</code>```

These 5 facts are called the loop's invariant. To trust that the loop's invariant holds where I said it does, you can check

that it holds the first time the guard is evaluated and

that, if the invariant is true and the guard is true, then one execution of the loop's body will leave the program in a state where the invariant is true again.

Therefore, when and if the loop terminates normally*, all the above are true and so is divisor > limit.  This tells you that divisor == n and so you have

```<code>n % i != 0, for all i from 2 up to, but not including n
mod != 0
n is the same as the argument // i.e. n hasn't been changed
</code>```

Therefor, if the loop terminate normally, the return true after the loop will be executed and the argument is prime.

The only cases left to worry about are those where the loop does not terminate normally. There are two reasons a loop might not terminate normally: it is infinite or there is a jump out of it, such as a break, return, or exception. In your code, the loop can be shown not to be infinite and the only jump out is when n % divisor == 0. Since, at that point, we also have

```<code>2 <= divisor       // from the invariant
divisor <= limit   // from the guard
limit == n-1       // from the invariant
</code>```

we have 2<=divisor && divisor < n. So if the return false in the loop is executed, it is only when n % divisor == 0 and divisor is greater than 1 and less than n, and so the n (and hence the argument) is not prime.

In summary

for nonprimes (greater than 2), the loop can not terminate normally and so the return false must be executed, and

for primes (greater than 2) the loop must terminate normally and in a state where mod != 0 and so the return true will be executed.

The proof suggests a few ways you could make the code simpler. The books I mentioned provide ways to make the analysis more formal, although I think only Hehner's provides a way to deal with early exits from loops.

[*] By "terminates normally", I mean that it terminates because its guard evaluates to false.

Does this analysis give you absolute certainty that you code is flawless?  I hope not. But it should give you reassurance. One can use tools such as  ESC/Java2 or  Spec# so that a computer can check that one hasn't made any mistakes.  That would raise the level of trust that the code is right to a very high level.  Of course there could be bugs in the program one uses to check the verification or in the hardware it runs on. For practical purposes code such as yours can be verified and the verification can be checked by carefully written and trustworthy tools.

Body:
There are a number of frameworks for proving that code is correct.  You can read about some of them in books such as

A practical theory of programming, Hehner, 1993-2014.

The science of programming, Gries, 1981.

A method of programming, Dijkstra and Feijn, 1988.

Programming from specifications, Morgan, 1990, 1994, 1998.

For your program, I'll assume that you don't care about negative n and that you can handle the n==0, n==1, and n==2 cases without any help; I'll only look at the case where n>2.

The key is to note that (in cases where n > 2) every time the loop's guard expression divisor <= limit is evaluated, the following 5 facts are true of the program's state:

n % i != 0, for all i from 2 up to, but not including divisor
limit == n-1
2 <= divisor && divisor <= n
mod != 0 || divisor == 2
n is the same as the argument  // i.e. n hasn't been changed

These 5 facts are called the loop's invariant. To trust that the loop's invariant holds where I said it does, you can check

that it holds the first time the guard is evaluated and

that, if the invariant is true and the guard is true, then one execution of the loop's body will leave the program in a state where the invariant is true again.

Therefore, when and if the loop terminates normally*, all the above are true and so is divisor > limit.  This tells you that divisor == n and so you have

n % i != 0, for all i from 2 up to, but not including n
mod != 0
n is the same as the argument // i.e. n hasn't been changed

Therefor, if the loop terminate normally, the return true after the loop will be executed and the argument is prime.

The only cases left to worry about are those where the loop does not terminate normally. There are two reasons a loop might not terminate normally: it is infinite or there is a jump out of it, such as a break, return, or exception. In your code, the loop can be shown not to be infinite and the only jump out is when n % divisor == 0. Since, at that point, we also have

2 <= divisor       // from the invariant
divisor <= limit   // from the guard
limit == n-1       // from the invariant

we have 2<=divisor && divisor < n. So if the return false in the loop is executed, it is only when n % divisor == 0 and divisor is greater than 1 and less than n, and so the n (and hence the argument) is not prime.

In summary

for nonprimes (greater than 2), the loop can not terminate normally and so the return false must be executed, and

for primes (greater than 2) the loop must terminate normally and in a state where mod != 0 and so the return true will be executed.

The proof suggests a few ways you could make the code simpler. The books I mentioned provide ways to make the analysis more formal, although I think only Hehner's provides a way to deal with early exits from loops.

[*] By "terminates normally", I mean that it terminates because its guard evaluates to false.

Does this analysis give you absolute certainty that you code is flawless?  I hope not. But it should give you reassurance. One can use tools such as  ESC/Java2 or  Spec# so that a computer can check that one hasn't made any mistakes.  That would raise the level of trust that the code is right to a very high level.  Of course there could be bugs in the program one uses to check the verification or in the hardware it runs on. For practical purposes code such as yours can be verified and the verification can be checked by carefully written and trustworthy tools.


问:
Theoretically bug-free programs
I have read lot of articles which state that code can't be bug-free, and they are talking about these theorems:

Halting problem

Gödel's incompleteness theorem

Rice's theorem

Actually Rice's theorem looks like an implication of the halting problem
and the halting problem is in close relationship with Gödel's incompleteness theorem.

Does this imply that every program will have at least one unintended behavior?
Or does it mean that it's not possible to write code to verify it?
What about recursive checking? Let's assume that I have two programs. Both of them have bugs, but they don't share the same bug. What will happen if I run them concurrently?

And of course most of discussions talked about Turing machines. What about linear-bounded automation (real computers)?

答:
Does this imply that every program will have at least one unintended behavior?

No.

The halting problem says that it's impossible to write a program that tests whether every program halts in a finite amount of time. This does not mean that its impossible to write a program that can categorize some programs as halting, some others as non-halting. What it means is that there are always will exist some programs that a halting analyzer cannot categorize one way or the other.

Gödel's incompleteness theorems have a similar gray area to them. Given a mathematical system of sufficient complexity, there will exist some statements made in the context of that system whose veracity cannot be assessed. This does not mean mathematicians have to give up on the idea of proof. Proof remains the cornerstone of mathematics.

Some programs can be proven to be correct. It's not easy, but it can be done. That is the goal of formal theorem proving (a part of formal methods). Gödel's incompleteness theorems do strike here: Not all programs can be proven to be correct. That does not mean it is utterly futile to use formal methods because some programs can indeed be formally proven to be correct.

Note: Formal methods preclude the possibility of a cosmic ray striking the processor and executing launch_missiles() instead of a+b. They analyze programs in the context of an abstract machine rather than real machines that are subject to single event upsets such as Robert Harvey's cosmic ray.

Title: Theoretically bug-free programs


问:
Why do XML namespace URIs use the http scheme?
A XML namespace should be a URI, but it can use any URI scheme, including those that are not URLs.

Then why do all widely used XML namespaces use the http scheme (e.g. http://www.w3.org/XML/1998/namespace), considering that trying to use the URI as an URL by retrieving that document using the HTTP protocol is not guaranteed to do anything useful (and often doesn't)?

I understand the usefulness of DNS domains in namespace names to help guarantee uniqueness. But that doesn't require the http scheme, there could be a separate scheme for that (something like namespace:w3.org/XML/1998/namespace). This would avoid the confusion between URIs and URLs, while maintaining domain-based uniqueness.

答:
W3C explains their reasoning for using http URIs in the article URNs, Namespaces and Registries. It specifically discusses XML namespaces and a proposed scheme very similar to namespace mentioned in the question.

According to the article, the big advantage of using http is that retrieving the document pointed to by the URI can work and it can provide useful information to both humans and machines.


问:
Is a finite state machine an appropriate solution for this situation?
I was writing some test code as an example where I had a washing machine class. It has a door state that should be open or closed, and also a running state, either on or off. I want to prevent the running state from changing from 'off' to 'on' when the door is 'open', and also prevent the door from being set to 'open' while the machine is 'on'.

I have this functionality rigged up with a bunch of if statements. It feels inelegant and it could quickly turn into spaghetti code if I want to add another state that puts additional conditions on the changes of other states. I wonder, is a finite state machine a solution for this situation? Would it simplify adding states and defining valid transitions?

答:
A finite state machine implementation would be very adequate for the problem you describe. It is a good method for all problems with states that are allowed or not. This method helps you to check if your analysis is correct and complete.

I'm not sure if you are experienced in the field of finite state machines (and eventually digital circuit design). I like the following  youtube tutorial: Methodology for Finite State Machine design

Good luck with your development. If you need libraries: I like using Foma (free C library) and FSM (Java code).


问:
What is the "Free Monad + Interpreter" pattern?
I've seen people talking about Free Monad with Interpreter, particularly in the context of data-access. What is this pattern? When might I want to use it? How does it work, and how would I implement it?

I understand (from posts such as this) that it's about separating model from data-access. How does it differ from the well-known Repository pattern? They appear to have the same motivation.

答:
A free monad is basically a monad that builds a data structure in the same "shape" as the computation rather than doing anything more complicated. (There are examples to be found online.) This data structure is then passed to a piece of code which consumes it and carries out the operations.* I am not entirely familiar with the repository pattern, but from what I've read it appears to be a higher level architecture, and a free monad + interpreter could be used to implement it. On the other hand, the free monad + interpreter could also be used to implement entirely different things, such as parsers.

*It is worth noting that this pattern is not exclusive to monads, and in fact can produce more efficient code with free applicatives, or free arrows. (Parsers are another example of this.)

OwnerDisplayName: Benjamin Hodgson


答:
The actual pattern is actually significantly more general than just data access. It's a lightweight way of creating a domain-specific language that gives you an AST, and then having one or more interpreters to "execute" the AST however you like.

The free monad part is just a handy way to get an AST that you can assemble using Haskell's standard monad facilities (like do-notation) without having to write lots of custom code. This also ensures that your DSL is composable: you can define it in parts and then put the parts together in a structured way, letting you take advantage of Haskell's normal abstractions like functions.

Using a free monad gives you the structure of a composable DSL; all you have to do is specify the pieces. You just write a data type that encompasses all of the actions in your DSL. These actions could be doing anything, not just data access. However, if you specified all your data accesses as actions, you would get an AST that specifies all the queries and commands to the data store. You could then interpret this however you like: run it against a live database, run it against a mock, just log the commands for debugging or even try optimizing the queries.

Lets look at a very simple example for, say, a key value store. For now, we'll just treat both keys and values as strings, but you could add types with a bit of effort.

```<code>data DSL next = Get String (String -> next)
              | Set String String next
              | End
</code>```

The next parameter lets us combine actions. We can use this to write a program that gets "foo" and sets "bar" with that value:

```<code>p1 = Get "foo" $ \ foo -> Set "bar" foo End
</code>```

Unfortunately, this is not enough for a meaningful DSL. Since we used next for composition, the type of p1 is the same length as our program (ie 3 commands):

```<code>p1 :: DSL (DSL (DSL next))
</code>```

In this particular example, using next like this seems a little odd, but it's important if we want our actions to have different type variables. We might want a typed get and set, for example.

Note how the next field is different for each action. This hints that we can use it to make DSL a functor:

```<code>instance Functor DSL where
  fmap f (Get name k)          = Get name (f . k)
  fmap f (Set name value next) = Set name value (f next)
  fmap f End                   = End
</code>```

In fact, this is the only valid way to make it a Functor, so we can use deriving to create the instance automatically by enabling the DeriveFunctor extension.

The next step is the Free type itself. That's what we use to represent our AST structure, build on top of the DSL type. You can think of it like a list at the type level, where "cons" is just nesting a functor like DSL:

```<code>-- compare the two types:
data Free f a = Free (f (Free f a)) | Return a
data List a   = Cons a (List a)     | Nil
</code>```

So we can use Free DSL next to give programs of different sizes the same types:

```<code>p2 = Free (Get "foo" $ \ foo -> Free (Set "bar" foo (Free End)))
</code>```

Which has the much nicer type:

```<code>p2 :: Free DSL a
</code>```

However, the actual expression with all of its constructors is still very awkward to use! This is where the monad part comes in. As the name "free monad" implies, Free is a monad—as long as f (in this case DSL) is a functor:

```<code>instance Functor f => Monad (Free f) where
  return         = Return
  Free a >>= f   = Free (fmap (>>= f) a)
  Return a >>= f = f a
</code>```

Now we're getting somewhere: we can use do notation to make our DSL expressions nicer. The only question is what to put in for next? Well, the idea is to use the Free structure for composition, so we will just put Return for each next field and let the do-notation do all the plumbing:

```<code>p3 = do foo <- Free (Get "foo" Return)
        Free (Set "bar" foo (Return ()))
        Free End
</code>```

This is better, but it's still a bit awkward. We have Free and Return all over the place. Happily, there's a pattern we can exploit: the way we "lift" a DSL action into Free is always the same—we wrap it in Free and apply Return for next:

```<code>liftFree :: Functor f => f a -> Free f a
liftFree action = Free (fmap Return action)
</code>```

Now, using this, we can write nice versions of each of our commands and have a full DSL:

```<code>get key       = liftFree (Get key id)
set key value = liftFree (Set key value ())
end           = liftFree End
</code>```

Using this, here's how we can write our program:

```<code>p4 :: Free DSL a
p4 = do foo <- get "foo"
        set "bar" foo
        end
</code>```

The neat trick is that while p4 looks just like a little imperative program, it's actually an expression that has the value

```<code>Free (Get "foo" $ \ foo -> Free (Set "bar" foo (Free End)))
</code>```

So, the free monad part of the pattern has gotten us a DSL that produces syntax trees with nice syntax. We can also write composable sub-trees by not using End; for example, we could have follow which takes a key, gets its value and then uses that as a key itself:

```<code>follow :: String -> Free DSL String
follow key = do key' <- get key
                get key'
</code>```

Now follow can be used in our programs just like get or set:

```<code>p5 = do foo <- follow "foo"
        set "bar" foo
        end
</code>```

So we get some nice composition and abstraction for our DSL as well.

Now that we have a tree, we get to the second half of the pattern: the interpreter. We can interpret the tree however we like just by pattern-matching on it. This would let us write code against a real data store in IO, as well as other things. Here's an example against a hypothetical data store:

```<code>runIO :: Free DSL a -> IO ()
runIO (Free (Get key k)) =
  do res <- getKey key
     runIO $ k res
runIO (Free (Set key value next)) =
  do setKey key value
     runIO next
runIO (Free End) = close
runIO (Return _) = return ()
</code>```

This will happily evaluate any DSL fragment, even one that isn't ended with end. Happily, we can make a "safe" version of the function that only accepts programs closed with end by setting the input type signature to (forall a. Free DSL a) -> IO (). While the old signature accepts a Free DSL a for any a (like Free DSL String, Free DSL Int and so on), this version only accepts a Free DSL a that works for every possible a—which we can only create with end. This guarantees we won't forget to close the connection when we're done.

```<code>safeRunIO :: (forall a. Free DSL a) -> IO ()
safeRunIO = runIO
</code>```

(We can't just start by giving runIO this type because it won't work properly for our recursive call. However, we could move the definition of runIO into a where block in safeRunIO and get the same effect without exposing both versions of the function.)

Running our code in IO is not the only thing we could do. For testing, we might want to run it against a pure State Map instead. Writing out that code is a good exercise.

So this is the free monad + interpreter pattern. We make a DSL, taking advantage of the free monad structure to do all the plumbing. We can use do-notation and the standard monad functions with our DSL. Then, to actually use it, we have to interpret it somehow; since the tree is ultimately just a data structure, we can interpret it however we like for different purposes.

When we use this to manage accesses to an external data store, it is indeed similar to the Repository pattern. It intermediates between our data store and our code, separating the two out. In some ways, though, it's more specific: the "repository" is always a DSL with an explicit AST which we can then use however we like.

However, the pattern itself is more general than that. It can be used for lots of things which do not necessarily involve external databases or storage. It makes sense wherever you want fine control of effects or multiple targets for a DSL.

Title: What is the "Free Monad + Interpreter" pattern?

Body:
I've seen people talking about Free Monad with Interpreter, particularly in the context of data-access. What is this pattern? When might I want to use it? How does it work, and how would I implement it?

I understand (from posts such as this) that it's about separating model from data-access. How does it differ from the well-known Repository pattern? They appear to have the same motivation.

Body:
The actual pattern is actually significantly more general than just data access. It's a lightweight way of creating a domain-specific language that gives you an AST, and then having one or more interpreters to "execute" the AST however you like.

The free monad part is just a handy way to get an AST that you can assemble using Haskell's standard monad facilities (like do-notation) without having to write lots of custom code. This also ensures that your DSL is composable: you can define it in parts and then put the parts together in a structured way, letting you take advantage of Haskell's normal abstractions like functions.

Using a free monad gives you the structure of a composable DSL; all you have to do is specify the pieces. You just write a data type that encompasses all of the actions in your DSL. These actions could be doing anything, not just data access. However, if you specified all your data accesses as actions, you would get an AST that specifies all the queries and commands to the data store. You could then interpret this however you like: run it against a live database, run it against a mock, just log the commands for debugging or even try optimizing the queries.

Lets look at a very simple example for, say, a key value store. For now, we'll just treat both keys and values as strings, but you could add types with a bit of effort.

data DSL next = Get String (String -> next)
              | Set String String next
              | End

The next parameter lets us combine actions. We can use this to write a program that gets "foo" and sets "bar" with that value:

p1 = Get "foo" $ \ foo -> Set "bar" foo End

Unfortunately, this is not enough for a meaningful DSL. Since we used next for composition, the type of p1 is the same length as our program (ie 3 commands):

p1 :: DSL (DSL (DSL next))

In this particular example, using next like this seems a little odd, but it's important if we want our actions to have different type variables. We might want a typed get and set, for example.

Note how the next field is different for each action. This hints that we can use it to make DSL a functor:

instance Functor DSL where
  fmap f (Get name k)          = Get name (f . k)
  fmap f (Set name value next) = Set name value (f next)
  fmap f End                   = End

In fact, this is the only valid way to make it a Functor, so we can use deriving to create the instance automatically by enabling the DeriveFunctor extension.

The next step is the Free type itself. That's what we use to represent our AST structure, build on top of the DSL type. You can think of it like a list at the type level, where "cons" is just nesting a functor like DSL:

-- compare the two types:
data Free f a = Free (f (Free f a)) | Return a
data List a   = Cons a (List a)     | Nil

So we can use Free DSL next to give programs of different sizes the same types:

p2 = Free (Get "foo" $ \ foo -> Free (Set "bar" foo (Free End)))

Which has the much nicer type:

p2 :: Free DSL a

However, the actual expression with all of its constructors is still very awkward to use! This is where the monad part comes in. As the name "free monad" implies, Free is a monad—as long as f (in this case DSL) is a functor:

instance Functor f => Monad (Free f) where
  return         = Return
  Free a >>= f   = Free (fmap (>>= f) a)
  Return a >>= f = f a

Now we're getting somewhere: we can use do notation to make our DSL expressions nicer. The only question is what to put in for next? Well, the idea is to use the Free structure for composition, so we will just put Return for each next field and let the do-notation do all the plumbing:

p3 = do foo <- Free (Get "foo" Return)
        Free (Set "bar" foo (Return ()))
        Free End

This is better, but it's still a bit awkward. We have Free and Return all over the place. Happily, there's a pattern we can exploit: the way we "lift" a DSL action into Free is always the same—we wrap it in Free and apply Return for next:

liftFree :: Functor f => f a -> Free f a
liftFree action = Free (fmap Return action)

Now, using this, we can write nice versions of each of our commands and have a full DSL:

get key       = liftFree (Get key id)
set key value = liftFree (Set key value ())
end           = liftFree End

Using this, here's how we can write our program:

p4 :: Free DSL a
p4 = do foo <- get "foo"
        set "bar" foo
        end

The neat trick is that while p4 looks just like a little imperative program, it's actually an expression that has the value

Free (Get "foo" $ \ foo -> Free (Set "bar" foo (Free End)))

So, the free monad part of the pattern has gotten us a DSL that produces syntax trees with nice syntax. We can also write composable sub-trees by not using End; for example, we could have follow which takes a key, gets its value and then uses that as a key itself:

follow :: String -> Free DSL String
follow key = do key' <- get key
                get key'

Now follow can be used in our programs just like get or set:

p5 = do foo <- follow "foo"
        set "bar" foo
        end

So we get some nice composition and abstraction for our DSL as well.

Now that we have a tree, we get to the second half of the pattern: the interpreter. We can interpret the tree however we like just by pattern-matching on it. This would let us write code against a real data store in IO, as well as other things. Here's an example against a hypothetical data store:

runIO :: Free DSL a -> IO ()
runIO (Free (Get key k)) =
  do res <- getKey key
     runIO $ k res
runIO (Free (Set key value next)) =
  do setKey key value
     runIO next
runIO (Free End) = close
runIO (Return _) = return ()

This will happily evaluate any DSL fragment, even one that isn't ended with end. Happily, we can make a "safe" version of the function that only accepts programs closed with end by setting the input type signature to (forall a. Free DSL a) -> IO (). While the old signature accepts a Free DSL a for any a (like Free DSL String, Free DSL Int and so on), this version only accepts a Free DSL a that works for every possible a—which we can only create with end. This guarantees we won't forget to close the connection when we're done.

safeRunIO :: (forall a. Free DSL a) -> IO ()
safeRunIO = runIO

(We can't just start by giving runIO this type because it won't work properly for our recursive call. However, we could move the definition of runIO into a where block in safeRunIO and get the same effect without exposing both versions of the function.)

Running our code in IO is not the only thing we could do. For testing, we might want to run it against a pure State Map instead. Writing out that code is a good exercise.

So this is the free monad + interpreter pattern. We make a DSL, taking advantage of the free monad structure to do all the plumbing. We can use do-notation and the standard monad functions with our DSL. Then, to actually use it, we have to interpret it somehow; since the tree is ultimately just a data structure, we can interpret it however we like for different purposes.

When we use this to manage accesses to an external data store, it is indeed similar to the Repository pattern. It intermediates between our data store and our code, separating the two out. In some ways, though, it's more specific: the "repository" is always a DSL with an explicit AST which we can then use however we like.

However, the pattern itself is more general than that. It can be used for lots of things which do not necessarily involve external databases or storage. It makes sense wherever you want fine control of effects or multiple targets for a DSL.


问:
URIs and Resource vs Resource representation
URL is an URI which identifies a resource by location.

Resource representation is a view of resource's state. This view is encoded in one or more transferable formats, such as XHTML, Atom, XML, MP3 ...

URIs associate resource representations with their resources

a) So I assume URI identifies a resource and not resource representation?

b) I've read that relationship between an URI and resource representation is one to many. Assuming we're talking about URL, how can a single URL address more than one resource representation?

thank you

答:
With content negotiation. http://en.wikipedia.org/wiki/Content_negotiation

When you dereference your URI using HTTP, you pass an "Accepts" header with the different mime types you're willing to take. For example, you might be able to read JSON, XML or plain text: "application/json application/xml text/plain". Whatever resource you're reading (or writing) might come back as a representation in any of those formats.

In practice, most applications deal with one representation. Usually it's just HTML, JSON, or XML. Sometimes a framework can render data resource with either JSON or XML, based on the Accepts header. But since we usually write code for one representation, or else the parsing is hidden by our framework, it kind of feels like the resource just has one representation. But that's just a perception.


问:
Is it good practice to analyse who introduced each bug?
I used to analyse performance of programmers in my team by looking at the issues they have closed. Many of the issues are of course bugs. And here another important performance aspect comes - who introduced the bugs. I am wondering, if creating a custom field in the issue tracking system "Blamed" for reporting the person who generated the problem, is a good practice.

One one hand it seems ok to me to promote personal responsibility for quality and this could reduce the additional work we have due to careless programming. On the other hand this is negative, things are sometimes vague and sometimes there is a reason such us "this thing had to be done very quickly due to a client's...".

What to you think?

答:
No, no, 1024 times no

What's important is to figure out how to prevent similar future bugs. Everyone makes mistakes, there is nothing to be gained from finger-pointing. Blaming people does not improve the process, nor does it help the team


答:
A Finite State Machine, implemented with the State design pattern, is a great solution to what you're trying to do - for two reasons:

The transitions between states are coded inside the states themselves. (They can also be coded in the washing machine class itself, but that makes it harder to add new states and transitions, and may result in long and ugly conditionals). So it's easy to keep track of the possible transitions to and from a state. For example if e.g. you want to prevent a transition from the 'off' state to the 'on' state when the door is 'open', all you have to do is inside the 'off' state, have the transition logic to the 'on' state wrapped with a conditional that checks if the door is open. No ugly long if statements to do this.

Adding new states is easy and doesn't result in growing if statements. All you have to do is add transition logic to the new state from the states that you want to be able to transition to this state. Much cleaner than a central place that manages all the transitions with long spaghetti code.

Good luck

Title: Is a finite state machine an appropriate solution for this situation?

Body:
I was writing some test code as an example where I had a washing machine class. It has a door state that should be open or closed, and also a running state, either on or off. I want to prevent the running state from changing from 'off' to 'on' when the door is 'open', and also prevent the door from being set to 'open' while the machine is 'on'.

I have this functionality rigged up with a bunch of if statements. It feels inelegant and it could quickly turn into spaghetti code if I want to add another state that puts additional conditions on the changes of other states. I wonder, is a finite state machine a solution for this situation? Would it simplify adding states and defining valid transitions?


问:
How to make a non-english clone of CoffeeScript?
I want to make a non-english programming language that is identical to what CoffeeScript is to JavaScript. What I mean is that I don't want to build my own design or syntax. Just want to have a non-english programming language that compiles to JavaScript. I want to follow everything CoffeeScript fellows so I don't really want to make any design decisions.

For example:

This is coffeescript:

```<code>number   = 42
opposite = true

number = -42 if opposite
</code>```

I want my language to be something like:

```<code>رقم = 42
عكس = صحيح

رقم = -42 إذا عكس
</code>```

that get compiled to:

```<code>var number, opposite;

number = 42;

opposite = true;

if (opposite) {
  number = -42;
}
</code>```

答:
Perform a simple, direct transliteration from the Arabic symbols to the English ones in CoffeeScript, and then run the result through the CoffeeScript compiler.  Leave the remaining symbols unchanged.

That's by far the simplest and most reliable way to accomplish what you want, and probably the only way that doesn't require extended semantic analysis.


问:
Learning a new concept - write from scratch or use frameworks?
I have recently been trying to learn about MVVM and all of the associated concepts such as repositories, mediators, data access.  I made a decision that I would not use any frameworks for this so that I could gain a better understanding of how everything worked.  I’m beginning to wonder if that was the best idea because I have hit some problems which I am not able to solve, even with the help of Stack Overflow!

Writing from scratch

I still feel that you have a much better understanding of something when you have been in the guts of it than if you were at a higher level.  The other side of that coin is that you are in the guts of something that you don't fully understand which will lead to bad design decisions.  This then makes it hard to get help because you will create unusual scenarios which are less likely to occur when you working within the confines of a framework.

I have found that there are plenty of tutorials on the basics of a concept but very few that take you all the way from novice to expert.  Maybe I should be looking at a book for this?

Using frameworks

The biggest motivation for me to use frameworks is that they are much more likely to be used in the workplace than a custom rolled solution.  This can be quite a benefit when starting a new job if it's one less thing you have to learn.

I feel that there is much better support for a framework than a custom solution which makes sense; many more people are using the framework than the solution that you created.  The level of help is much wider as well, from basic questions to really specific, detailed questions.

I would be interested to hear other people's views on this.  When you are learning something new, should you/do you use frameworks or not?  Why?  If it's a combination of both, when do you stop one and move on to the other?

答:
Learn it from scratch. Frameworks are there to SPEED UP development by removing the overhead of re-creating common tasks ranging from views to database interactions, whatever things are common to the platform you are going to learn. Additional benefits are things like maintainability, extendability and so on.

After learning the platform, then you can move to a framework, for the above reasons.

You wont have learned a language by learning a framework on it. You will have learned the framework. And some frameworks really abstractify the language they are built to great extent.

AND, most importantly: If you end up working with that language for a long time with a sizable or important application, there WILL come a time at which a framework will be limiting you for a VERY quirky thing the company/firm/workplace/client needs. You will end up having to do wizardry to make it happen. Even the thing you do may appear totally idiotic and irrational to an outsider.

The requirements of the trenches what happen in them can be quite different from what is taught in education institutions.


问:
If the model is validating the data, shouldn't it throw exceptions on bad input?
Reading this SO question it seems that throwing exceptions for validating user input is frowned upon.

But who should validate this data? In my applications, all validations are done in the business layer, because only the class itself really knows which values are valid for each one of its properties. If I were to copy the rules for validating a property to the controller, it is possible that the validation rules change and now there are two places where the modification should be made.

Is my premise that validation should be done on the business layer wrong?

What I do

So my code usually ends up like this:

```<code><?php
class Person
{
  private $name;
  private $age;

  public function setName($n) {
    $n = trim($n);
    if (mb_strlen($n) == 0) {
      throw new ValidationException("Name cannot be empty");
    }
    $this->name = $n;
  }

  public function setAge($a) {
    if (!is_int($a)) {
      if (!ctype_digit(trim($a))) {
        throw new ValidationException("Age $a is not valid");
      }
      $a = (int)$a;
    }
    if ($a < 0 || $a > 150) {
      throw new ValidationException("Age $a is out of bounds");
    }
    $this->age = $a;
  }

  // other getters, setters and methods
}
</code>```

In the controller, I just pass the input data to the model, and catch thrown exceptions to show the error(s) to the user:

```<code><?php
$person = new Person();
$errors = array();

// global try for all exceptions other than ValidationException
try {

  // validation and process (if everything ok)
  try {
    $person->setAge($_POST['age']);
  } catch (ValidationException $e) {
    $errors['age'] = $e->getMessage();
  }

  try {
    $person->setName($_POST['name']);
  } catch (ValidationException $e) {
    $errors['name'] = $e->getMessage();
  }

  ...
} catch (Exception $e) {
  // log the error, send 500 internal server error to the client
  // and finish the request
}

if (count($errors) == 0) {
  // process
} else {
  showErrorsToUser($errors);
}
</code>```

Is this a bad methodology?

Alternate method

Should maybe I create methods for isValidAge($a) that return true/false and then call them from the controller?

```<code><?php
class Person
{
  private $name;
  private $age;

  public function setName($n) {
    $n = trim($n);
    if ($this->isValidName($n)) {
      $this->name = $n;
    } else {
      throw new Exception("Invalid name");
    }
  }

  public function setAge($a) {
    if ($this->isValidAge($a)) {
      $this->age = $a;
    } else {
      throw new Exception("Invalid age");
    }
  }

  public function isValidName($n) {
    $n = trim($n);
    if (mb_strlen($n) == 0) {
      return false;
    }
    return true;
  }

  public function isValidAge($a) {
    if (!is_int($a)) {
      if (!ctype_digit(trim($a))) {
        return false;
      }
      $a = (int)$a;
    }
    if ($a < 0 || $a > 150) {
      return false;
    }
    return true;
  }

  // other getters, setters and methods
}
</code>```

And the controller will be basically the same, just instead of try/catch there are now if/else:

```<code><?php
$person = new Person();
$errors = array();
if ($person->isValidAge($age)) {
  $person->setAge($age);
} catch (Exception $e) {
  $errors['age'] = "Invalid age";
}

if ($person->isValidName($name)) {
  $person->setName($name);
} catch (Exception $e) {
  $errors['name'] = "Invalid name";
}

...

if (count($errors) == 0) {
  // process
} else {
  showErrorsToUser($errors);
}
</code>```

So, what should I do?

I'm pretty happy with my original method, and my colleagues to whom I have showed it in general have liked it. Despite this, should I change to the alternate method? Or am I doing this terribly wrong and I should look for another way?

答:
With my Haskell hat on, both approaches are wrong.

What happens conceptually is that you first have a bunch of bytes, and after parsing and validating, you can then construct a Person.

The Person has certain invariants, such as the precense of a name and an age.

Being able to represent a Person that only has a name, but no age is something you want to avoid at all costs, because that is what creates compleity.  Strict invariants means you do not need to check for the presence of an age later on for example.

So in my world, Person is created atomically by using a single constructor or function.  That constructor or function can again check the validity of the parameters, but no half-Person should be constructed.

Unfortunately, Java, PHP and other OO languages make the correct option pretty verbose.  In proper Java APIs, builder objects are often used.  In such an API, creating a person would look something like this:

```<code>Person p = new Person.Builder().setName(name).setAge(age).build();
</code>```

or the more verbose:

```<code>Person.Builder builder = new Person.Builder();
builder.setName(name);
builder.setAge(age);
Person p = builder.build();
// Person object must have name and age here
</code>```

In these cases, no matter where exceptions are thrown or where validation happens, it is impossible to receive a Person instance that is invalid.

Body:
With my Haskell hat on, both approaches are wrong.

What happens conceptually is that you first have a bunch of bytes, and after parsing and validating, you can then construct a Person.

The Person has certain invariants, such as the precense of a name and an age.

Being able to represent a Person that only has a name, but no age is something you want to avoid at all costs, because that is what creates compleity.  Strict invariants means you do not need to check for the presence of an age later on for example.

So in my world, Person is created atomically by using a single constructor or function.  That constructor or function can again check the validity of the parameters, but no half-Person should be constructed.

Unfortunately, Java, PHP and other OO languages make the correct option pretty verbose.  In proper Java APIs, builder objects are often used.  In such an API, creating a person would look something like this:

Person p = new Person.Builder().setName(name).setAge(age).build();

or the more verbose:

Person.Builder builder = new Person.Builder();
builder.setName(name);
builder.setAge(age);
Person p = builder.build();
// Person object must have name and age here

In these cases, no matter where exceptions are thrown or where validation happens, it is impossible to receive a Person instance that is invalid.


问:
Writing a spell checker similar to "did you mean"
I'm hoping to write a spellchecker for search queries in a web application - not unlike Google's "Did you mean?" The algorithm will be loosely based on this: http://catalog.ldc.upenn.edu/LDC2006T13

In short, it generates correction candidates and scores them on how often they appear (along with adjacent words in the search query) in an enormous dataset of known n-grams - Google Web 1T - which contains well over 1 billion 5-grams.

I'm not using the Web 1T dataset, but building my n-gram sets from my own documents - about 200k docs, and I'm estimating tens or hundreds of millions of n-grams will be generated.

This kind of process is pushing the limits of my understanding of basic computing performance - can I simply load my n-grams into memory in a hashtable or dictionary when the app starts? Is the only limiting factor the amount of memory on the machine?

Or am I barking up the wrong tree? Perhaps putting all my n-grams in a graph database with some sort of tree query optimisation? Could that ever be fast enough?

答:
I'd first implement it in memory, because it is simplest and it may just work.  However, I expect it won't.  I'd then move to some offline system you are familiar with (database?) and see how slow it is.  It may be fast enough that it stays simple.  I suspect it will be too slow.

Now we come to the fun part.  The first word I thought of when I read this is "cache".  With any luck, you will have enough memory to build a big enough cache that it solves the speed problems with the database, because you won't access it that often.

If that doesn't work, then the next thing I would try would be to pack my information as tight as possible to try to get it more in memory.  This will take more work, as you get to learn how your chosen language stores information.  You may end up switching to a language in which you have more control over the amount of space it takes to store an n-gram, or you get to compress and uncompress them when you need them.  This should make you a better programmer, but it will take longer.

As always, find your own path, do the easiest stuff first, and don't be afraid to experiment and fail.  Good luck.