Smart Software

Online Courses

I have been regularly sifting through course material (syllabi, presentations) in MIT's publicly accessible OpenCourseWare website since the program was launched years ago.

Earlier this year, I took a further step and started delving deeper by approaching one of the courses as a student. The courses in question are graduate courses, 6.972 Algebraic Techniques and Semidefinite Optimization, and 6.883 Program Analysis in the Electrical Engineering and Computer Science Department.

I purchased some of the suggested texts from Amazon.

• Cox, D. A., John B. Little, and Donal O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. New York, NY: Springer-Verlag, 1997. ISBN: 0387946802.
• Mishra, Bhubaneswar. Algorithmic Algebra (Monographs in Computer Science). New York, NY: Springer-Verlag, 1993. ISBN: 0387940901.
• Sturmfels, Bernd. Solving Systems of Polynomial Equations. Providence, RI: American Mathematical Society, 2002. ISBN: 0821832514.
• Yap, Chee-Keng. Fundamental Problems of Algorithmic Algebra. New York, NY: Oxford University Press, 2000. ISBN: 0195125169.

I have been developing my static analysis tool without taking formal course, although I did review a number of lecture slides and academic papers. The reading list from a syllabus of another program verification course led me to purchase Logic in Computer Science (Modeling and Reasoning about Systems) and Software Abstractions, which after a couple days of reading, allowed me to come to understand the major approaches used in program verification including model checking and temporal logic.

The impetus for my self-study was my frustration with using the Internet as a resource for  learning. While various sites like Google Scholar, CiteSeer, and ACM Digital Library are valuable for reading up on latest research and techniques, and many detailed lecture notes and readings for introducing computer science theories are available in PDF, learning about established approaches at the graduate-level over the Internet is inadequate (look up Grobner Bases, for example). The Internet in such cases is not a good substitute for university courses in which material is selected, organized, and designed for pedagogy.

I uncovered tricks for reading through entire contents of a book though A9, Amazon's book search engine, but admittedly prefer, Google Books Search which offers substantial excerpts and previews of many academic publications such as in modal logic, hard to find even at a university book store.

I discovered later this year the University of Washington professional masters program in computer science has video taped lectures online for all their master's course, a practice that I assume was funded by local employer, Microsoft. The site includes a Conference XP web viewer that conveniently synchronizes slides, video, and agenda for remote listening. I had at one point considered applying for a UW MSCS degree in 1996, when the program was just starting with approximately 40 students, but the course offerings then were limited, and not in areas that I was interested in (ie, Transaction Processing). The program seems to have grown significantly larger over the decade since.

My goals have since evolved so that I might actually try something more ambitious, which is to gain exposure to the whole range of courses lectures in computer science, mathematics and other disciplines that I am interested in.

I don't think that my undergraduate education was as well designed as it could have been, but it might have been through the fault of my own not interacting with my advisers more. The ease of access of university courses is such an advantage for college students coming in today. Had I been a student now, I would have learned material online before taking the course, allowing me to decide whether I want to reinforce the learning and enroll in the course.  I could also listen to multiple courses taught by different lecturers to acquire a different perspective on the material.

Symbolic Ray-Tracing

I thought of an approach to ray-tracing that could result in faster performance using symbolic evaluation. I mention it here to illustrate the benefits of thinking symbolically and also because I don't see myself writing a ray tracer anytime in the next decade.

Images typically contain stretched out areas that correspond to the surfaces of individual objects. While each pixel in an area may have a unique color value, all of the pixels may easily computed by a single, simple function, even for textured surfaces. In theory, the applicable area of a function could be extended to the full dimensions of the image by using conditionals, but such a function would be unwieldy. 

Instead of calculating a color value for each ray we shoot out from each screen pixel, we could produce a partially evaluated function that returns a color. (This could work recursively in the event of reflected surfaces.) The computation for a single pixel would suffer, but the function could be reused to fill out the area occupied by adjacent related pixels, which also share the same function. Search and anti-aliasing costs for these pixels would be eliminated.

One approach to area detection is to produce a second function, which returns a boolean value indicating whether the first function is still valid for a given point, based on the information gathered from intersection tests of the original pixel. The second function basically serves as the boundary test for the flood fill operation. With this approach, we have the choice of making our first function a compiled function constructed from closures, a partially evaluated function represented as data, or a combination of both. Compiled functions might be faster, but data representations, being symbolic, could produce exact results.

Since this approach reduces work for typical images, I suspect that high quality images could one day be produced in the same amount of time that lowest quality images currently take without special hardware. 

LISP

Randal Munroe posted some "XKCD" comics on LISP, which I thought were  especially relevant to my situation.

This one below drawn a while back is called ""LISP" and captures my fascination with functional programming and its remarkable ability to express simply and elegantly everything about the world.

This more recent one called "LISP Cycles" conveys my attempt to use the light side of the "force," functional programming, to overcome the dark side, imperative programming (and --shhh!-- singlehandedly defeat the evil empire in the process.)

Old School Programming

Scott Hanselman recently wrote about teaching children and kids to program the old school way by using the Commodore 64 emulator. It seems just recently that Zenzo, his 18–month old child, jumped off the cradle.

I wonder if old-school programming with direct access to the computer and the operating system is preferable to learning with scripting languages of today. What follows is my case for old-school programming, but scripting languages do provide a much better, functional programming language to learn from..

I first got into programming with the Commodore PET, followed by the Commodore 64. Like Scott, I would spend hours typing up long BASIC and machine language programs (written in hex) from various computer magazines such as Compute! and Run. It was then that I began programming full-time. I still remember 53280/1 as the addresses for changing the screen colors, SYS 64738 for rebooting the operating system. I still have most of the 6510 codes burned in my head. LDA was A9 (169), LDX A2 (162), JSR 20 (32), RTS 60 (96), and of course BRK was zero.

I wrote my own assembler and disassembler and used both to write primarily in assembly language for the next few years (near address location 40960 which was an unused section of memory), which was all before high school. I used my disassembler to decode and rewrite the entire 8K of BASIC ROM and parts of the 8K kernel back to source with meaningful symbols. I remember becoming mesmerized with how the 256 byte stack was used for parsing expressions. Even though processors were slow, linear search was used everywhere even during frequent operations such as changes in control flow and variable access. I eventually added my own extensions to the BASIC language to support structured programming and better graphics.

I also played around as if I was the operating system, disabling interrupts to create my own interrupt routines, which I used to implement a partial multitasker, an animation engine, as well as a rasterizer that bypassed hardware limits for 8 sprites. In the default screen mode, every character occupied one byte of memory for a total of 1000 characters in a 25x40 grid; the number of characters were limited to 255. I also replaced the default mode to bitmapped mode, which consume eight times as many bytes: This enabled me to support character styles (bold, italics and underline), independent background/foreground colors for each character, larger character sets, and integrated graphics. I also experimented with proportional fonts (based on automatic detection of character boundaries and bit shifting) and screen widths larger than 40 characters.

I wrote rather than purchased my own software, as, being a child, I had no money. I built a range of programs including a wordprocessor to figure out how things works; some of these programs were better than commercial versions, but I just did not know how to sell them. I did seriously think about whether I could one day develop and sell my own software independently. In college, I purchased a couple books on developing and marketing shareware.

Programming at an early age helped with my education. I often found myself exposed to college material as a result of my activities. At a self-pace program in my elementary school, I began taking some high school courses while in sixth grade. Because I was already comfortable with memory addresses and stack, I never had the slightest difficulty with pointers and recursion, when I encountered them in C and Pascal; they both seemed natural to me. (Back eight years earlier, when I encountered PEEKs and POKEs, streams of hexadecimals numbers inside DATA statements, and mysterious SYS statements in computer magazines, I did find myself confused.)

 

Fabricated Complexity

There is a quote in computer science, “the solution to a hard problem, when solved, is simple.” I don’t know who to attribute it to, but I have repeatedly found myself arriving at very simple and elegant solutions to hard problems—problems in natural language, in AI, and in application development.

Anna Liu mentioned a talk by Willty Zwaenepoel on research and fabricated complexity.

He spoke of "Fabricated Complexity" - and basically about his observation that researchers often over complicate issues to make them seem 'interesting and novel' and to be accepted by the academic peer review process, while real practical/applicable ideas that lead to useful innovations often are actually based on 'simple ideas'.

He also came to the conclusion that 'design by contract/stable interfaces' are the key to successful (maintainable) innovation, despite he and his team spent many years of building some of the most 'sophisticated/complex' algorithms in distributed systems technologies, it was down to these simple software engineering concepts that would lead any innovation to wide adoption.

One paper that comes to mind is from the Spec# at Microsoft, Abstract Interpretation with Alien Expressions and Heap Structures. It took me a few readings to digest this paper. I gathered that “polyhedra domains” refers to the feasible region in the simplex algorithm, but much of the other content made more sense after going through related literature and course material.

What is more surprising is that I came up with a simpler, more elegant and more general solution than those mentioned in this paper. Perhaps, fabricated complexity leads to complex solutions. If simple, familiar ideas were used, would our mind be able to discover more associations with other related ideas? There may also be a greater tendency to preserve the beauty of a system when the components themselves are beautiful; when not, anything goes.

In economics, unions effectively drive up wages while limiting employment. Professional organizations maintain high levels of income of their highly-paid members by creating legal barriers of entry to new (usually younger) entrants. They lobby the government to impose stricter requirements for licensing, while, at the same time, urging grandfather clauses for existing practitioners. New interns must undergo many years of schooling, learn a new vocabulary, and work hours with low pay for a number of years. The same holds especially true for researchers of academia. 

I am not making a value judgment here; such practices might attract only the most dedicated people and also improve quality. We don’t want to reward those who only see the monetary incentive, but are not willing to put in effort. For the most part, the tendency for professionals to sharply divide the world between “knows” and “knows-not” is unconscious but convenient.

Just as professionals introduce a more complicated vocabulary, software companies often come up with complicated names in their products and libraries when simple ones would do. Since computer programming is so broadly applicable and valuable, an arcane vocabulary in this industry does not serve us well. While it’s not as basic a skill as reading and elementary mathematics, it ranks with business vocabulary, which is more accessible than the vocabulary of other professions.

Apple has always used friendly names in developer APIs. In contrast, Microsoft often unnecessarily complicated its API, especially COM, with cryptic names and hungarian notation, unintentionally driving users to the Java space and other platforms. Perhaps, this is partly because the architect of COM/OLE used to be a high-energy physicist from Oxford. His influence can be seen through the use of physical terms like source and sink in some COM interfaces. I once spoke to an OLE dev lead, who remarked that OLE development was incompatible with a short development time. It became clear to me that Microsoft APIs were unconsciously designed for other large software companies, most of which have since been vanquished by you know who.

The .NET Framework, especially with the help of the FX tool, enforces that the name of every type and method can be found a certain dictionary. Because it was designed for multiple languages, it had to serve the lowest common denominator; it had to be easy to use by the VB developer. This I think is one of the many reasons for its success.

One problem with functional languages comes from its heritage in academia. Hence, newcomers are often intimidated by the unfamiliar terminology, which actually refers to simple ideas. Functional programming languages look hard or too mathematical, when in fact they should actually be conceptually easier. The LINQ team has made many functional constructs dramatically more accessible by giving them names that sound more like conversational English. Operators like Map, filter, reduce, fold were changed to the names of their SQL counterparts such as select, where, sum, aggregate and so on. Terms like lambda expressions or closures might also become more accessible if described as anonymous functions or blocks. (Don’t try to figure out why closures are called “closures.” The origin of the name, which I have forgotten, is now meaningless today, but there use to be an “open” counterpart to the concept.)

Patents

Google just launched a search engine for finding patents. I typed in my name and discovered that I had been awarded a patent (assigned to Microsoft) for some obscure PivotTable feature in Excel.

In my MBA program, I attended some classes and seminars in a variety of laws including intellectual property law. I also used to regularly attend monthly sessions given by Washington Software Association to keep up to date on latest changes to law regarding software.

I have ambivalent feelings about whether I should seek patents. Software patents limit technological progress, and I would like to see the day when computers take over the world before I die.

There are a number of genuine inventions in my product that I think are patent-worthy. My needs are primarily defensive, though. I am not incline to sue anymore, especially the open-source community and small companies, and have even thought about opening up technology after I made a independently livable amount of wealth.

I could used this as a bargaining chip if I ever sold my technology. However, if that happen, I could get into the awful position of not being able to use what I invented. There’s a staggering amount of reuse between different areas of my product, and this is principally due to the inherently compositional nature of functional-style programming.

Incidentally, I have been contacted by the chief scientist of a leading source code analysis company, flowing with PhDs. He called my product “unique and interesting” and inquired about how my product works; he also mentioned potential business cooperation opportunities. Maybe, I hit some gold.

I can’t afford to actually buy a lawyer, but, since I am a do-it-yourselfer, I purchased last year Patent It Yourself by Nolo Press and other manuals. The law is constantly changing, so you need the latest copy. 

If I do go ahead, I may also buy Nolo’s software package, PatentEase. First, I would do a provisional patent application, which allows me to label my product as “patent-pending” and gives me a one-year window to actually file an application (I believe, but ask a real lawyer). Since I have been through the process before, have taken a number of basic courses, I think that I am prepared even though I am sure I will make some mistakes.

My motivation isn’t mostly money. I will probably never buy a large house or a car that costs over 40K. I inherited my father’s value system, which regards excessive, ostentatious wealth as vulgar. My motivation is to avoid meaningless work at a large corporation, to eliminate stress and to maintain a high level of freedom. I like the idea of staying a small company. My motivation is also intellectual—to explore the unrealized possibilities of computer, to find that intersection of human and computer intelligence.

Lego Programming

Joel reviewed a book Beyond Java, and, in his review, he enthusiastically recommended an essay by Fred Brooks called "No Silver Bullet: Essence and Accidents of Software Engineering." He recently mentioned it again in his post Lego Programming. Brooks wrote the Mythical Man Month, which was really the first software engineering text. It was remarkable in identifying surprising asymmetries in software development. For example, Brooks identified the network costs in adding more developers to a project and dramatic disparities  in individual developer productivity (eg, "adding manpower to a late softer project makes it later"), but he also made a number of forgotten poor predictions in the same book, some of which he confesses to in "The Mythical Man Month After 20 Years"  such as "I am convinced that interactive systems will never displace batch systems for many applications."

I have written about Silver Bullets in the past and emphatically feel the widely regarded author to be irresponsible and premature in his assessment of there being no silvery bullets, which is leading many developers, not the least of which is Joel, to be unimaginative and pessimistic of advances in software development.

For example, Brooks asserts in the start of his essay this bit of false wisdom:

There is no single development, in either technology or in management technique, that by itself promises even one order-of-magnitude improvement in productivity, in reliability, in simplicity.

That assertion turns out to be pure nonsense, amply disproven by numerous advances in IDEs, languages, frameworks, componentization over the past few decades. Our expectations of software and our ability have risen. A year of work takes a month or a month of work takes a day. An order of magnitude improvement usually results in major qualitative changes, often resulting in an existing lengthy project becoming a short task item or a new project suddenly becoming feasible, such as when end users start writing applications (using scripting and RAD tools) that were once exclusively the domain of IT.

The net effect is that we often don't consciously recognize tenfold improvements in productivity. We forget how hard it was to program decades ago. Consider developing a game for the simple Atari 2600 gaming system back in the early 1980s.

I see the driving force towards tenfold productivity as the move to more declarative and compositional approaches, be it through functional, object-oriented, and component-based programming. Kinda like Lego.

Technical Assistant

I just read about the next technical assistant of Bill Gates, Joshua Goodman, from the Natural Language Blog. He was another classmate of mine at Harvard University majoring in computer science. We knew each other especially because the computer science department was so small, ~25 students out of 1600 per class.

I joined Microsoft as a Researcher in MSR in 1998. During that time, I’ve worked on speech recognition, stopping spam, and email among other topics. I helped start the MSN Safety Team that still builds spam filters for Microsoft’s email products, and I spent two years on loan to that team, getting some product experience. Early in my career, I worked as a developer at Dragon Systems, a long gone speech recognition company: some of my code has survived 12 years, two acquisitions and a bankruptcy. I interned at Microsoft in 1989 as a PM on the Excel team, and in 1991 as a developer on the iFax project (an intelligent fax machine – this would have been huge if it were not for the internet.) Until I joined Microsoft, I spent most of my life in the Boston area, including time at Harvard earning a Bachelors, Masters and Ph.D., all in computer science. I’m married with three young boys who enjoy playgrounds, lakes and pools.

The job of technical assistant was created basically to assist Bill Gates in responding to the large volume of requests for technical feedback and guidance that he receives from across the company. Pretty cool to have someone who knows about natural language work in that role!

Funny. It seems that all three of us, Joshua Goodman, Alex Gounares (the previous technical assistant, whom I was also on a first-name basis), and myself have all had some involvement in natural language.

Powers Of Ten

The New York Times recently included an interesting graphic,“Separated at Birth,” which compares the image of the universe to that of a mouse’s neurons. The graphic strangely suggests that the universe may wrap around itself as we delve more into the infinite or the infinitesimal.

This notion is captured nicely in this Simpson’s Power of Ten video. The Simpson’s video is actually a parody of the original Power of Tens video produced by two IBM scientists; the scientists also have a www.Powersof10.com website that depicts 10X transitions across both space and time. This video has resulted in numerous copycats: “Secret Worlds: The Universe Within,” and “CellsAlive! How Big.”

In the early nineties, I read a book by Andy Grove, former CEO of Intel, called Only the Paranoid Survive, which describes how 10X forces create strategic inflection points, which can topple established companies. Intel faced such a disruptive transition as it moved from being primarily a memory chip company to a CPU company in the last eighties. It left such an impression on me, that it’s the only thing I recall from the book.

Being a quantitative person, I tend to evaluate features in product in terms of quantifiable attributes. Mark Miller, of DevExpress, also uses quantifiable metrics to evaluate the usability of a feature. For example, he measures the amount of mouse distance and keyboard costs required by each new feature. When viewing feature sets quantitatively, I often look at is what the introduction of an order of magnitude change in productivity would mean for the design of a product. I often tell people that the goal of one of my future products is to improve the writing process by a factor of ten.

 

Research Pipeline

On the last day of the Lang.NET Symposium, I sat through an interesting lecture on F# with Don Syme. Don Syme is a researcher at Microsoft Research’s Cambridge office. He and Andrew Kennedy previously researched and designed generics years before its eventual incorporation into the Whidbey version (2.0) of the .NET Framework. The research project was called Gyro. Don’s work was instantly credible because it was implemented on top of the CLR infrastructure.

Research Pipeline at Intel

I congratulated him on being able to navigate the research and development divide, and asked him how he was able to do it. Don said that he previously interned at Intel, which had an established notion of a research pipeline unlike Microsoft and trained researchers on the proper steps to facilitate research into development.

At Intel, researchers were more closely involved in development. They were required to make proposals and identify the stage of their research — prototype, design, development, so on... As each stage proceeded, more development resources would be allocated to it, roughly double the amount before. The researcher had to be associated with a group, and must be able name a number of development contacts. A critical success factor is the researcher ability to convince a development group to invest money and resources into the idea—to bring in important stakeholders.

The culture of integrating research and development at Intel is probably due to the founders, Robert Noyce, Gordon Moore and Andy Grove, all having doctoral degrees and conducting significant research. Robert Noyce coinvented the integrated circuit and, had he lived long enough, would have shared the 2000 Nobel Prize given to coinventor Kilby; compare that to Bill Gates’s intellectual accomplishments.

Because of his prior involvement in Intel, Don Syme successfully spearheaded generics into the CLR, and made sure the implementation of generics was of high-quality and completely orthogonal. As a result, generics introduced hardly any seams into the CLR. Underneath the execution engine, though, a single IL instruction may translate into substantial code as some features like generic virtual methods, generic interfaces, and generic static fields may use dictionary lookups rather than simple vtable dispatch.

Don also paved the way for additional research projects to migrate into development tools like LINQ, which was incubated in research as Comega. Future research projects, Spec# and Polyphonic C#, will probably migrate into the fourth iteration of .NET.

Google

This happens to be why I feel optimistic about Google’s chances, given both top management and the founders of the company are researchers themselves. Google also institutes the now famous 20% time and embeds a researcher into each product team. The executives recognize the bottom-up nature of innovation as well as the limits that bounded rationality places on top-down management.

 Update: Don Syme has a presentation on Tech Transfer at Microsoft.