January 30, 2012

Continued Confusion

People have trouble understanding continuations, and this is no surprise when you realize that the term "continuation" is overloaded in all three senses: as a word, as a concept, and as a programming construct.

The confusion comes from two fields where continuations are used as a concept: compiler intermediate representations (where Continuation-Passing Style (CPS) is one possible form of intermediate representation), and First-Class Continuations (FCC), which is a metaprogramming technique for manipulating the stack of a program.

In terms of being a programming construct, continuations only exist in FCC. When it comes to CPS, a continuation is a concept only. In CPS, this concept is easy to understand: a continuation is the next step in a computation - the next instruction in the instruction stream.

For FCC, the concept consists of two parts: saving the current computation, and resuming a saved computation.

The main cause of confusion around FCC is that the First-Class Continuation programming construct is traditionally represented as a function (this has to do with the fact that FCC as an idea was derived from work in CPS). But a First-Class Continuation is not in any way a function. As Christian Queinnec points out in Lisp in Small Pieces, a First-Class Continuation is more like catch/throw:

Saving the current computation is like setting up a catch block, and resuming that computation is like throwing a value to that tag - anything that happened between that catch and throw is forgotten. The thing that makes a First-Class Continuation special is that you can throw to it anytime from anywhere, and you end up in the corresponding catch, with whatever you were doing previously forgotten.

Marc Feeley has proposed an alternative interface for First-Class Continuations that makes invoking First-Class Continuations explicit, which is implemented in Gambit Scheme.

So finally we get to continuation as a word. As a word, "continuation" is used in three contexts:

  1. In Continuation-Passing Style as a conventional way of calling the next step in a computation.

  2. In First-Class Continuations as a name for saved computations.

  3. To indicate the next step in a computation when looking at a particular point in any given piece of code.

Christopher Wadsworth coined the term "continuation" for a way to formally reason about jumps/gotos, but the term can also be used informally when talking about a particular point in a piece of code. If you mentally use a different word in each of the three contexts, I think a lot of the confusion surrounding continuations can be cleared up. Something like the following might work:
  1. "next"

  2. "saved stack"

  3. "continuation"

January 24, 2012

WebRTC and the File API

Two interesting developments in HTML5 I've recently been made aware of are WebRTC (thanks to Manuel Simoni) and File API (thanks to Rich Jones). The RTC part of WebRTC stands for Real-Time Communications, but it's basically a way to provide TCP/IP sockets for a web browser while pretending you're not providing TCP/IP. The top-layer part consists of various video and audio codecs, but the basic gist is a way of providing a bidirectional channel for web browsers to communicate with each other. This is accomplished with NAT traversal in mind (the functionality for traversing NATs and proxies in the reference implementation is provided by the very handy looking libjingle library that seems to do most of the common NAT traversal tricks).

One obvious use of WebRTC is providing audio and video chat in webpages without Flash (WebRTC specifies audio/video input, real-time codecs, and jitter buffers). Another obvious use is to develop a BitTorrent-like distribution protocol for videos; something like this should really cut down on YouTube's bandwidth bills.

The File API provides the potential to use WebRTC for any kind of P2P file sharing. This is I think the most exciting potential of WebRTC.

To step back in terms of commentary, the web browser has now come full circle to being a very weird virtualized operating system, whose APIs rival Windows in size, idiosyncrasies and complexity. The need for application hosting declines - both the application and "putting your data in the cloud" can now be handled by a Freenode or Tahoe-LAFS-like WebRTC library. What's interesting is that friction surrounding development and deployment should push new web applications away from a centralized server and towards the P2P approach. Unlike fully hosted apps, there is no extra effort involved in making an offline version. Server rent/lease and administration costs are reduced considerably by offloading as much data storage and computation as possible onto the browser. This latter possibility in particular should enable many startups to avoid the capital requirements needed for scaling up services that depend on the network effect, such as most "social" things. I don't like to use buzzwords, but this looks to be disruptive.

January 18, 2012

Upcoming presentation about Parenscript

I'm going to be giving a talk about Parenscript to the Montreal Scheme/Lisp Users Group on Thursday, January 19 (meeting details here).

The slides I'm going to be using are here, and a list of links referenced in the talk is below. The last time I gave a presentation on Parenscript was to LispNYC in 2007. Parenscript has received a huge number of changes and improvements since then, and continues to be the best language/compiler to JavaScript and one of the best tools available for web application development. What's also new since 2007 are libraries and tools that extend Parenscript: Red Daly has added CLOS and the Common Lisp condition system to JavaScript as a Parenscript library, and there are now several options for interactive development with SLIME in your browser.

Links:

January 17, 2012

Compiling by simplifying

When you read the original Lambda Papers carefully, one thing you notice is that Steele didn't view Scheme as just a programming language, but also (and I would argue, primarily) as a philosophy of constructing compilers.

This philosophy made clear and transparent the issues of translating a high-level language into Von Neumann-style register machine code, and provided mechanisms to radically simplify the transformation. Continuation-passing style reified issues of control transfer, temporary stack values, and register use. Function arguments become registers, function calls - jumps. Difficult issues like nested scopes, first-class functions, closures, and exceptions become easy.

The other great, simplifying thing about Steele's philosophy is the self-similarity of the code as it undergoes transformation. The input of each stage of the compiler is a Scheme program, and (until machine code generation), the output is a simpler Scheme program.

Many compilers miss out on the self-similarity aspect of Scheme in two major ways. Those compilers that do follow continuation-passing style usually implement the CPS portion of compilation using completely different data structures than the other portions. This adds needless boilerplate code and makes the CPS portion look more complicated than it is. This needless complexity shows up in some ML compilers - in particular, Andrew Appel's otherwise excellent and highly recommended Compiling with Continuations, and causes people to remark that implementing SSA is not all that much harder than doing CPS (Olin Shivers disagrees).

The subtler, but even more serious omission is ignoring Steele's advice to implement the parts of the language above the intermediate layers as macros. This spreads the complexity for implementing features like classes and objects throughout the different portions of the compiler, starting with the parser.

Following Steele's techniques, building a Scheme compiler that is several times faster (and many times smaller) than the compilers/virtual machines of popular dynamic languages like Python and Ruby is easy. Scheme 48 was originally written in 48 hours. If you don't have that much time, Marc Feeley can show you how to build a Scheme compiler in 90 minutes. And if you're really strapped for time and don't want to sit through CPS theory, Abdulaziz Ghuloum shows you how to dive right into generating x86 machine code in 10 pages.

January 11, 2012

The personal computer you've never heard of

I was watching Dan Ingalls' Seven (give or take) Smalltalk Implementations talk given at Stanford in 2005 on YouTube, and around the 43 minute mark Ingalls talked about something I consider shocking:

In 1978*, a year after the introduction of the Apple II, Xerox PARC built a portable computer with a 7 inch, 640 by 480 resolution bit-mapped, touch-screen display based around a commonly available 1 MHz, 16-bit microprocessor with 128 KiB** of memory running Smalltalk-76. The computer was called the NoteTaker.



The NoteTaker ran Smalltalk as fast as the Alto (the Smalltalk-76 VM (6 KiB) actually executed bytecode twice as fast on the 8086 as on the Alto, but the memory bus was much slower, making interactive performance feel similar).

I always thought the 8086 was extremely underpowered and good only for DOS and terminals. In hindsight, it's mind-boggling how long it took x86 PCs to catch up with the Macintoshes and Amigas of the 1980s.

* Note that Wikipedia and other sources give the NoteTaker's date as 1976, but this is likely the date when design started, as the 8086 design also just started in 1976 and the processor did not ship until 1978. The NoteTaker manual is also dated December, 1978.

** The NoteTaker manual specs the machine at 256 KiB of memory.

*** The current Wikipedia article about NoteTaker claims this computer would have cost more than $50,000 if sold commercially (presumably in 1978 dollars). Assume that the CRT, floppy disk, power supply, keyboard and mouse cost $2,000 (a whole Apple II system with 4 KiB memory retailed for $1,298.00 in 1977). The 8086 originally wholesaled for $360. According to the NoteTaker manual, the NoteTaker had a second 8086 which acted as an I/O processor but was "also available for general purpose computing tasks." It would have been entirely possible to replace the I/O processor with a much cheaper CPU. Looking again at Apple's price list, a 48 KiB Apple II board retailed for $1,938, while a bare-bones 4 KiB one sold for $598, which gives $31 per KiB. So 128 KiB would retail for $3,900 and 256 KiB would retail for $7,800. It certainly would have been possible to produce and maybe even sell the NoteTaker with 256 KiB of memory for less than $15,000. Note that a few years later, Kim McCall and Larry Tessler made a subset of Smalltalk-76 that ran in 64 KiB of memory, but with the full system image only about 8 KiB of memory was available for user programs.

**** The NoteTaker also came with an Ethernet interface.

PS - While researching this article, I also stumbled on another PC you've probably never heard of. The Kenbak-1, similar in operation and capabilities to the MITS Altair 8800 (both came with lights, toggle switches, and 256 bytes of memory), was sold via advertisements in Scientific American for $750 in 1971, four years before the Altair.

What is ClearSky going to look like as an application?

ClearSky is going to have to be as simple as possible to use. Facebook-level simplicity. The only unavoidable extra requirement is that the node software is going to have to run as a binary on your own computer. The installation process needs to consist of just downloading a single binary. Once you have it, no more extra installation steps.

The first time the binary is run, it opens a web browser pointing to a page that asks you to choose a nickname and password (the binary will have a web server to present the local interface). In the background, it's going to generate a private/public key pair and set up the filesystem directory where you store data for that account. After that, it will let you look up friends online. I'm undecided about how this step will work. There are a lot of alternatives for federated, centrally located directories: just build a web one, XMPP (integration with chat seems like a good idea), IRC, etc. I don't know a lot about how the distributed options work, but they are out there and seem to work ok (Freenet, GNUnet, etc.). It seems like a good idea to make this part modular, but present it behind a consistent and easy to use interface.

The binary will provide an HTTPS port to the outside world to let your friends log in remotely (see previous discussion). If you're behind a NAT gateway, it's going to take some extra work - both the NAT-PMP and IGD protocols will need to be supported.

In general, UDP hole punching needs to be present to let two ClearSky nodes talk to each other, although it alone is not enough to provide remote logins from the outside. UDP hole punching needs an accessible third party to be present - using either a friend's computer that has an unrestricted connection, or a central server if no such friends are available. Using unknown third parties is problematic because it relies on either volunteers (every ClearSky client can be a volunteer, but this opens up possibilities for surveillance) or your mirror provider.

All traffic between you and your friends goes over SSH. Messages and files are cryptographically signed to ensure authenticity, but encryption during transport is provided by SSH. The ClearSky client should encrypt data before writing it to disk to ensure privacy even if the hosting computer gets lost or stolen.

Apps are going to be started in a separate process (via fork(), or by running the same executable with different options) for extra security, stability, and to let the OS handle resource control. Games, content libraries, chat, voice, calendars etc. are all possible apps. One example app that could be built but that's not possible with Facebook is a Tahoe-LAFS that would let you trade harddrive space with your friends to securely and redundantly back up your private data.

Apps will communicate with the ClearSky process via sockets and the file system. Security is going to be provided by language-level virtualization. The app runtime will prompt the user when the app wants to access filesystem folders or other resources. Things like video and audio will ideally be handled by HTML5, if not then by Flash. It's undesireable to have the app display native UI or use the OS multimedia or other capabilities directly - this shouldn't be included in the platform unless there's a good concrete demonstration that it's needed. OTOH, having an app be able to manage its own sockets may be a good idea.

Common Lisp is a good language/runtime to base the ClearSky platform on. A Common Lisp binary can run all the basic ClearSky functions (web server, crypto, discovery, networking, SSH) in the same process, provides excellent support for language-level virtualization (and of course already comes with a compiler), and has very good support for hosting and virtualizing other programming languages - of the popular scripting ones, CLPython and CL-JavaScript are currently available, and new ones are easy to implement: CL-JavaScript was written by 3 people (Alan Pavičić, Marijn Haverbeke, and Iva Jurišić), CL-Python by just one person (Willem Broekema).

January 9, 2012

Payment for hosting and mirroring

Having a purely p2p private messaging and file sharing network works up to a tradeoff between the number of nodes, the aggregate average availability and bandwidth of all nodes, and the file sizes being shared. The larger a p2p network becomes, the less trusted and private it's going to be. But for example a torrent with a small number of seeders with low upload speeds doesn't work very well for huge files.

It would be nice to share a large number of large files securely with your friends over a high-bandwidth link. As well, having a reliable server on a high-bandwidth link would make replication and backup of your data more convenient.

A large number of companies offer storage services that can do that. Dropbox is the most popular, but it doesn't provide convenient sharing features because it focuses on replicating and syncing your private files. Ubuntu One is similar. These services are also insecure - Dropbox and Ubuntu One can read your files.

The service that's most convenient for private and easy to share storage on remote hosted servers was Allmydata. Allmydata may be gone, but the people behind and software behind it (Tahoe-LAFS) are still there. Tahoe-LAFS is Free Software and the techniques and algorithms well documented.

But storage and bandwidth aren't free. How would the economic model behind a secure, private mirroring service work?

Very few people want to pay cash for mirroring. Can't have the mirror show you ads - that would defeat the privacy aspect (besides, how would these ads be served and where would they be viewed?).

But your computer is going to be on a lot of the time to participate in the p2p network. Why not have it mine bitcoins? Then you can pay for mirroring storage/bandwidth with the bitcoins gained from contributing work to a mining pool.

Metcalfe's law hypothesizes that each node brings value to the network when it joins. A logical conclusion is that not only the network, but the node itself should be able to realize that value in monetary terms. Cryptographic currency mining enables this.

Another long sought-after idea that may be enabled by the mining approach is micropayments, but that's a problematic and unrelated area.

January 7, 2012

Who else is working on this stuff?

None of the ideas in the ClearSky concept are original to me. This is sort of the zeitgeist of the times. Here's a list of people and projects that have thought about or are working on the same problem:

The basic idea stems back to the home media convergence attempts of the late 90s (and indeed Tonido is still following this marketing strategy).

Why no one has been successful so far is that the solutions offered are too hard to use (if it's any harder than Facebook, very few people will use it), don't address the issue of replication (Tonido and Opera Unite, for example), and don't have sustainable revenue models. I think that with the right design, engineering and business approach, these problems are not insurmountable.

You might notice I left out one project: Diaspora. A look at Diaspora's source code should convince you that while the project claims the same goals, the approach they're taking does not address any of the three aspects mentioned above.

The future of the App Store is source-only distribution

Following up on the ClearSky idea, let's look at what the applications that run on your and your friends' computers will be like.

Obviously, the Apple app store model of cryptographic signing is useless as a measure of trust of what an application does in a decentralized scenario (note that this is different than using signing to establish authenticity during application distribution). The Apple app store model of cryptographic signing is actually useless for Apple app store apps as well - I know of at least two apps that have made it into the Apple app store that will keep an open, non-password protected telnet port on your iPhone. So centralized quality control does not work.

Will virtualization be able to solve the safety problem? What virtualization is really about is names and meta-machines. In the case of running a VMware virtual machine on your real PC, your real PC is the meta-machine from the point of view of the VMware one, and memory addresses are the names. As long as the software in the VMware box has no access to the memory addresses belonging to your real PC, it cannot escape to do things that the VMware virtual machine cannot already do (you can think of virtualization like being the plot of The Matrix).

Even if the virtualization is unbreakable and the virtual machine does everything you need without posing a danger to your data (and how would it do that if it needs to modify your data to be useful?), you cannot tell whether the app that the virtual machine will run doesn't have secret back-doors or information leaking channels (both can be accomplished using steganography to hide things in the data the app consumes and produces as part of its regular operation). Checking compiled binaries for these is simply not feasible.

The only alternative that is left is the one advocated by Richard Stallman - you can't trust a program unless you can read its source code. While it is still possible to hide back-doors in source code, it requires a very large and extremely messy code base to hide them effectively. And very large and extremely messy code bases tend to lead to shit applications that no one really wants to use (unless corporate IT makes you). Applications with clean code bases that are easy to audit are nice; use them.

Note that this model of software distribution (source-only) is not new - in fact, it has been the most popular method of software distribution for the last 10 years. This is how JavaScript works. And JavaScript has also shown that language-level virtualization (ie "sandboxing") is extremely effective as a security mechanism - there have been very few exploits where an attacker was able to escalate privileges outside of the JavaScript virtual machine.

There are two ways to get around the "easily auditable source" ideal with JavaScript. The most popular way is to use code obfuscation tools. The other way (which in the past year has gained more and more recognition) is to use JavaScript itself to implement another virtual machine (kind of like Russian nesting dolls).

While there is no way to prevent these two techniques (and in fact it is undesirable to do so; but it doesn't stop Apple from trying), you certainly should be able to have the freedom to use applications written and audited by people you trust. The centralized, signed app store approach used by Apple destroys this continuum of trust by putting all applications on an equal level - "approved by Apple" doesn't mean much when the approval process is secretive, arbitrary, and does not guarantee quality or security.

Are there any other benefits to source-only distribution besides security? Plenty: complete portability, high performance (compile to native code), tiny download sizes, easy dependency management, etc.

One way to encourage the ideal of "easily auditable source" is via licensing. This is where the innovation of Henry Poole comes in handy - the Affero GPL is the most business-friendly of all Free Software licenses (more on that in a later post) and when used effectively will enable disruptive new business models. The "platform" part of the hypothetical ClearSky virtual machine will benefit tremendously from being licensed under the AGPL.

January 5, 2012

Friends with [login] benefits

To follow up on the last post, think about what it would mean to have a web application running on your friends' computers. How would you log in from a random computer on the Internet?

The account name and password combination is convenient to remember and seems to work well in practice for logging in to computer systems.

It's easy enough keeping your password secret when you log into your own machine, and you can use public-key cryptography to have trusted communications with your friends. You can remember your account name and password, but you're not going to be carrying around your private key (if such a system is to work for most people, you're probably not even going to be aware you have a private key).

You can trust your friends, but you don't want to tempt them by transmitting the cleartext passwords to their machine (ever have an obsessive ex as a friend on Facebook?). Having a unique password for each of your friends' machines won't work because you can't remember them all.

On the other hand, you can assume that your friends probably won't want to crack your password hash to get your password, and if their machine ever gets stolen, they'll tell you so you can change your password (ok, maybe that last point is not true).

If you take your password, assign each of your friends a unique salt, and give them the salt and the PBKDF2 (or whatever) digest of the salt and password, you can do the password checking in any browser with JavaScript by having their machine send the salt to the browser, the browser computing the PBKDF2 digest and sending it back to their machine, and their machine verifying the digest.

Your friends don't have your private key, but they can sign your messages with the private keys on their machines on your behalf. If you see strange messages signed on your behalf, you can assume that either your password has been compromised, or your friend's machine is acting maliciously (because it has been stolen, compromised, or your friend is doing the equivalent of the "let's post "I'm pregnant" status update" joke when you forgot to log out of Facebook).

You still have your private key on your machine, from where you can change your password, repudiate the fake messages, and publish a revised list of friends that you trust to sign messages on your behalf.

I'm sure this scheme has been thought of before, and I'm sure it has problems I didn't see. Any thoughts or comments? Where should I post this to get the opinions of people knowledgeable on cryptography?

January 4, 2012

I don't want Clouds, I want clear skies

The Cloud is one of the most idiotic things to happen to computing.

The only thing fuzzy about The Cloud is the definition of the word. It's basically a way for large companies to bamboozle you into giving up your privacy.

There's also a lot of wishful thinking reality distortion involved here. Large companies would love it if the only way people could do anything was in The Cloud, because today that word really means "hundreds of thousands of servers," and only large companies have enough capital to afford that, keeping competition out. Hosting companies like Amazon (there, I've said it) love it even more, because they get better utilization of their hundreds of thousands of servers, and therefore of their capital.

This situation should remind you of something: the 70s. This isn't really any different than the mainframe era. Can't afford a mainframe tons of servers? Call Tymshare Amazon!

So why are all these hundreds of thousands of servers needed? In the case of Google or YouTube, it seems pretty straightforward - it takes a lot of space to index most of the Internet and host millions of cat videos. But what about Facebook? What's really on there besides a few hundred (or maybe thousand) photos, links to YouTube cat videos shared by your friends, and your whiny status updates? It's hard to purchase a USB memory stick that would be small enough not to fit all that three times over.

It turns out there are a lot of other things on Facebook. Things like your click stream (ie - things you don't care about), which is needed for analytics (ie - using statistics to invade your privacy) to better serve you advertisements (ie - make you buy things you don't want).

The only reason Facebook needs to be "web scale!!!" is so they can sell ads. The only reason they're selling ads is because millions of people signed up for Facebook. The only reason millions of people signed up for Facebook is because it's the easiest way to share photos, links to cat videos, and important news about where they had lunch with their friends (oh yeah, and play Farmville or whatever).

Putting it this way, it's obvious why Facebook needs to sell ads - their service isn't valuable enough to you to get you to pay for it. So it's certainly not worth your time to set up your own web server with a bunch of pub/sub protocols and get all your friends to do the same so you can log into your MyFace social network to post inane status updates and grow virtual beets from other random computers connected to the Internet. That's hard, and who wants to pay for hosting?

Except you and your friends already have one or more computers connected to the Internet. What if it was easy?