Taking the grunt work out of web development

A Web page today is the result of a number of interacting components -- like cascading style sheets, XML code, ad hoc database queries, and JavaScript functions. For all but the most rudimentary sites, keeping track of how these different elements interact, refer to each other, and pass data back and forth can be a time-consuming chore.

In a paper being presented at the Association for Computing Machinery's Symposium on Principles of Programming Languages, Adam Chlipala, the Douglas Ross Career Development Professor of Software Technology, describes a new programming language, called Ur/Web, that lets developers write Web applications as self-contained programs. The language's compiler -- the program that turns high-level instructions into machine-executable code -- then automatically generates the corresponding XML code and style-sheet specifications and embeds the JavaScript and database code in the right places.

In addition to making Web applications easier to write, Ur/Web also makes them more secure. "Let's say you want to have a calendar widget on your Web page, and you're going to use a library that provides the calendar widget, and on the same page there's also an advertisement box that's based on code that's provided by the ad network," Chlipala says. "What you don't want is for the ad network to be able to change how the calendar works or the author of the calendar code to be able to interfere with delivering the ads." Ur/Web automatically prohibits that kind of unauthorized access between page elements.

Typing, scoping

Ur/Web's ability to both provide security protection and coordinate disparate Web technologies stems from two properties it shares with most full-blown programming languages, like C++ or Java. One is that it is "strongly typed." That means that any new variable that a programmer defines in Ur/Web is constrained to a particular data type. Similarly, any specification of a new function has to include the type of data the function acts on and the type of data it returns.

In computing the value to return, the function may need to create new variables. (A function that returned an average of values in a database, for instance, would first need to calculate their sum.) But those variables are inaccessible to the rest of the program. This is the second property, known as "variable scoping," because it limits the scope -- the breadth of accessibility -- of variables defined within functions.

"You might want to write a library that has inside of it as private state the database table that records usernames and passwords," Chlipala says. "You don't want any other part of your application to be able to just read and overwrite passwords. Most Web frameworks don't support that style. They assume that every part of your program has complete access to the database."

Typing helps with security, too. Many Web development frameworks generate database queries in such a way that someone ostensibly logging into a website can type code into the username field that in fact overwrites data in the database. With Ur/Web, usernames would constitute their own data type, which would be handled much differently than database queries.

Meeting expectations

Typing is also what enables coordination across Web technologies. Suppose that a bit of JavaScript code is supposed to act on data fetched from a database and that the result is supposed to be displayed on a Web page at a location determined by some XML code. If an Ur/Web programmer wrote a database query that extracted data of a type the JavaScript wasn't expecting, or if the JavaScript generated an output of a type that the XML page wasn't expecting, the compiler would register the discrepancy and flag the code as containing an error.

Often, code that isn't explicitly typed still has implicit consistency rules. For instance, if you write a query in the SQL database language that asks for the average numerical value of a bunch of text fields, the database server will tell you that it can't process your request. To enable Ur/Web to coordinate the flow of data between Web technologies, Chlipala had to create libraries of new data types for SQL, XML, and cascading style sheets (CSS) that embody these rules.

While the Ur/Web compiler does generate XML, JavaScript, and SQL code in its current version, it doesn't produce style sheets automatically. But, Chlipala says, "One thing the compiler can do is analyze your full program and say, 'Here is an exhaustive list of all the CSS classes that might be mentioned, and here is a description of the context in which each class might be used, which tells you what properties might be worth setting.' So, for instance, some particular class might never be used in a position where table properties would have any meaning, so you don't have to bother setting those."

Selengkapnya »»  

More-flexible digital communication

Communication protocols for digital devices are very efficient but also very brittle: They require information to be specified in a precise order with a precise number of bits. If sender and receiver -- say, a computer and a printer -- are off by even a single bit relative to each other, communication between them breaks down entirely.

Humans are much more flexible. Two strangers may come to a conversation with wildly differing vocabularies and frames of reference, but they will quickly assess the extent of their mutual understanding and tailor their speech accordingly.

Madhu Sudan, an adjunct professor of electrical engineering and computer science at MIT and a principal researcher at Microsoft Research New England, wants to bring that type of flexibility to computer communication. In a series of recent papers, he and his colleagues have begun to describe theoretical limits on the degree of imprecision that communicating computers can tolerate, with very real implications for the design of communication protocols.

"Our goal is not to understand how human communication works," Sudan says. "Most of the work is really in trying to abstract, 'What is the kind of problem that human communication tends to solve nicely, [and] designed communication doesn't?' -- and let's now see if we can come up with designed communication schemes that do the same thing."

One thing that humans do well is gauging the minimum amount of information they need to convey in order to get a point across. Depending on the circumstances, for instance, one co-worker might ask another, "Who was that guy?"; "Who was that guy in your office?"; "Who was that guy in your office this morning?"; or "Who was that guy in your office this morning with the red tie and glasses?"

Similarly, the first topic Sudan and his colleagues began investigating is compression, or the minimum number of bits that one device would need to send another in order to convey all the information in a data file.

Uneven odds

In a paper presented in 2011, at the ACM Symposium on Innovations in Computer Science (now known as Innovations in Theoretical Computer Science, or ITCS), Sudan and colleagues at Harvard University, Microsoft, and the University of Pennsylvania considered a hypothetical case in which the devices shared an almost infinite codebook that assigned a random string of symbols -- a kind of serial number -- to every possible message that either might send.

Of course, such a codebook is entirely implausible, but it allowed the researchers to get a statistical handle on the problem of compression. Indeed, it's an extension of one of the concepts that longtime MIT professor Claude Shannon used to determine the maximum capacity of a communication channel in the seminal 1948 paper that created the field of information theory.

In Sudan and his colleagues' codebook, a vast number of messages might have associated strings that begin with the same symbol. But fewer messages will have strings that share their first two symbols, fewer still strings that share their first three symbols, and so on. In any given instance of communication, the question is how many symbols of the string one device needs to send the other in order to pick out a single associated message.

The answer to that question depends on the probability that any given interpretation of a string of symbols makes sense in context. By way of analogy, if your co-worker has had only one visitor all day, asking her, "Who was that guy in your office?" probably suffices. If she's had a string of visitors, you may need to specify time of day and tie color.

Existing compression schemes do, in fact, exploit statistical regularities in data. But Sudan and his colleagues considered the case in which sender and receiver assign different probabilities to different interpretations. They were able to show that, so long as protocol designers can make reasonable assumptions about the ranges within which the probabilities might fall, good compression is still possible.

For instance, Sudan says, consider a telescope in deep-space orbit. The telescope's designers might assume that 90 percent of what it sees will be blackness, and they can use that assumption to compress the image data it sends back to Earth. With existing protocols, anyone attempting to interpret the telescope's transmissions would need to know the precise figure -- 90 percent -- that the compression scheme uses. But Sudan and his colleagues showed that the protocol could be designed to accommodate a range of assumptions -- from, say, 85 percent to 95 percent -- that might be just as reasonable as 90 percent.

Buggy codebook

In a paper being presented at the next ITCS, in January, Sudan and colleagues at Columbia University, Carnegie Mellon University, and Microsoft add even more uncertainty to their compression model. In the new paper, not only do sender and receiver have somewhat different probability estimates, but they also have slightly different codebooks. Again, the researchers were able to devise a protocol that would still provide good compression.

They also generalized their model to new contexts. For instance, Sudan says, in the era of cloud computing, data is constantly being duplicated on servers scattered across the Internet, and data-management systems need to ensure that the copies are kept up to date. One way to do that efficiently is by performing "checksums," or adding up a bunch of bits at corresponding locations in the original and the copy and making sure the results match.

That method, however, works only if the servers know in advance which bits to add up -- and if they store the files in such a way that data locations correspond perfectly. Sudan and his colleagues' protocol could provide a way for servers using different file-management schemes to generate consistency checks on the fly.

"I shouldn't tell you if the number of 1's that I see in this subset is odd or even," Sudan says. "I should send you some coarse information saying 90 percent of the bits in this set are 1's. And you say, 'Well, I see 89 percent,' but that's close to 90 percent -- that's actually a good protocol. We prove this."

"This sequence of works puts forward a general theory of goal-oriented communication, where the focus is not on the raw data being communicated but rather on its meaning," says Oded Goldreich, a professor of computer science at the Weizmann Institute of Science in Israel. "I consider this sequence a work of fundamental nature."

"Following a dominant approach in 20th-century philosophy, the work associates the meaning of communication with the goal achieved by it and provides a mathematical framework for discussing all these natural notions," he adds. "This framework is based on a general definition of the notion of a goal and leads to a problem that is complementary to the problem of reliable communication considered by Shannon, which established information theory."

Selengkapnya »»