David A. Wheeler's Blog



Mon, 19 May 2008

YEARFRAC Incompatibilities between Excel 2007 and OOXML (OXML)

In theory, the OOXML (OXML) specification is supposed to define what Excel 2007 reads and writes. In practice, it's not true at all; the latest public drafts of OOXML are unable to represent many actual Excel 2007 files.

For example, at least 26 Excel financial functions depend on a parameter called "Basis", which controls how the calendar is interpreted. The YEARFRAC function is a good example of this; it returns the fraction of years between two dates, given a "basis" for interpreting the calendar. Errors in these functions can have large financial stakes.

I've posted a new document, YEARFRAC Incompatibilities between Excel 2007 and OOXML (OXML), and the Definitions Actually Used by Excel 2007 ([OpenDocument version]), which shows that the definitions of OOXML and Excel 2007 aren't the same at all. "This document identifies incompatibilities between the YEARFRAC function, as implemented by Microsoft Excel 2007, compared to how it is defined in the Office Open Extensible Mark-up Language (OOXML), final draft ISO/IEC 29500-1:2008(E) as of 2008-05-01 (aka OXML). It also identifies the apparent definitions used by Excel 2007 for YEARFRAC, which to the author’s knowledge have never been fully documented anywhere. They are not defined in the OOXML specification, because OOXML’s definitions are incompatible with the apparent definition used by Excel 2007."

"This incompatibility means that, given OOXML’s current definition, OOXML cannot represent any Excel spreadsheet that uses financial functions using “basis” date calculations, such as YEARFRAC, if they use common “basis” values (omitted, 0, 1, or 4). Excel functions that depend upon "basis" date calculations include: ACCRINT, ACCRINTM, AMORDEGRC, AMORLINC, COUPDAYBS, COUPDAYS, COUPDAYSNC, COUPNCD, COUPNUM, COUPPCD, DISC, DURATION, INTRATE, MDURATION, ODDFPRICE, ODDFYIELD, ODDLPRICE, ODDLYIELD, PRICE, PRICEDISC, PRICEMAT, RECEIVED, YEARFRAC, YIELD, YIELDDISC, and YIELDMAT (26 functions)."

I have much more information about YEARFRAC if you want it.

path: /misc | Current Weblog | permanent link to this entry

Fri, 09 May 2008

Bilski: Information is physical!?

The US Court of Appeals for the Federal Circuit in Washington, DC just heard arguments in the Bilski case, where the appellant (Bilski) is arguing that a completely mental process should get a patent. The fact that this was even entertained demonstrates why the patent system has truly descended into new levels of madness. At least the PTO rejected the application; the problem is that the PTO now allows business method patents and software patents. Once they allowed them, there's no rational way to say "stop! That's rediculous!" without being arbitrary.

Mr. David Hanson (Webb Law Firm) argued for the appellant (Bilski), and got peppered with questions. "Is a curve ball patentable?", for example. At the end, he finally asked the court to think of "information as physical"; it is therefore tangible and can be transformed.

That is complete lunacy, and it clearly demonstrates why the patent office is in real trouble.

Information is not physical, it is fundamentally different, and that difference has been understood for centuries. If I give you my car, I no longer have that car. If I give you some information, I still have the information. That is a fundamental difference in information, and always has been. The fact that Bilski's lawyer can't understand this difference shows why our patent office is so messed up.

This fundamental difference between information and physical objects was well-understood by the U.S. founding fathers. Here's what Thomas Jefferson said: "That ideas should freely spread from one to another over the globe, for the moral and mutual instruction of man, and improvement of his condition, seems to have been peculiarly and benevolently designed by nature, when she made them, like fire, expansible over all space, without lessening their density at any point, and like the air in which we breath, move, and have our physical being, incapable of confinement or exclusive appropriation. Inventions then cannot, in nature, be a subject of property." Thomas Jefferson was a founder, and an inventor. No, they didn't have computers then, but computers merely automate the processing of information; the essential difference between information and physical/tangible objects was quite clear then.

Our laws need to distinguish between information and physical objects, because they have fundamentally different characteristics.

Basically, by failing to understand the differences, the PTO let in software patents and business method patents, which have been grossly harmful to the United States.

Even if you thought they were merely "neutral", that's not enough. There's a famous English speech about the trade-offs of copyright law, whose principles also apply here: "It is good that authors should be remunerated; and the least exceptionable way of remunerating them is by a monopoly. Yet monopoly is an evil. For the sake of the good we must submit to the evil; but the evil ought not to last a day longer than is necessary for the purpose of securing the good." - Thomas Babbington Macaulay, speech to the House of Commons, February 5, 1841.

I believe that software patents need to be abolished, pronto. As I've discussed elsewhere, software patents harm software innovation, not help it.

But here in the Bilski case we see why some some people have managed to sneak software patents into the patent process. In short, too many people do not understand the fundamental differences between information and physical objects. People whose thinking is that fuzzy are easily duped. Though clearly many people aren't as confused as Bilski's lawyer, I think too many people in the patent process have become so confused about the difference between physical objects and information that they don't understand why software patents are a serious problem. Patents should only apply to processes that directly change physical objects, and their scope should only cover the specifics of those changes. I add that latter part because yes, changing the number on a display does change something physical, but that is irrelevant. If you have a wholly new process for making displays (say, using a new chemical compound), that could be patentable, but changing a "5" to a "6" should not be patentable because "changing a 5 to a 6" is not fundamentally a change in nature. Taking something unpatentable and adding the phrase "doing it with a computer" should not change an unpatentable invention into a patentable one; the Supreme Court understood that, but the PTO still fails to understand that.

I think pharmaceutical companies are afraid of any patent reform laws, because they're afraid that a change in the patent system might hurt them. But if the patent system isn't fixed - by eliminating business method patents and software patents - the entire patent system might become too overwhelmed to function, and thus eventually scrapped. I don't know if pharma patents are more help than hinderance; I'm not an expert in that area. But I make my living with software, and it's obvious to me (and most other software practitioners) that software patents and business patents are becoming a massive drag on innovation. If we can't fix the patent system, we'll have to abolish the patent system completely. A lot of lawyers will be unhappy if the patent system is eliminated, but there are more non-lawyers than lawyers. If the pharma companies want to have a working patent system, then they'll need to help reign in patents in other areas, or the whole system may collapse.

path: /misc | Current Weblog | permanent link to this entry

Fri, 21 Mar 2008

Microsoft Office XML (OOXML) massively defective

Robert Weir has been analyzing Microsoft's Office XML spec (aka OOXML) to determine how defective it is, with disturbing results.

Most standards today are relatively small, build on other standards, and are developed publicly over time with lots of opportunity for correction. Not OOXML; Emca submitted Office Open XML for "Fast Track" as a massive 6,045 page specification, developed in an absurdly rushed way, behind closed doors, using a process controlled by a single vendor. It's huge primarily because does everything in a non-standard way, instead of referring to other standards where practical as standards are supposed to do (e.g., for mathematical equations they created their own incompatible format instead of using the MathML standard). All by itself, its failure to build on other standards should have disqualified OOXML, but it was accepted for review anyway, and what happened next was predictable.

No one can seriously review such a massive document in a short time, though ISO tried; ISO's process did find 3,522 defects. It's not at all clear that the defects were fixed - there's been no time to really check, because the process for reviewing the standard simply wasn't designed to handle that many defects. But even if they were fixed - a doubtful claim - Robert Weir has asked another question, "did they find nearly all of the defects?". The answer is: Almost all of the original defects remain. By sampling pages, he's found error after error, none of which were found by the ISO process. The statistics from the sample are very clear: practically all serious errors have not been found. It's true that good standards sometimes have a few errors left in them, after review, but this isn't "just a few errors"; these clearly show that the specification is intensely defect-ridden. Less than 2% of the defects have been found, by the data we have so far, which suggests that there are over 172,000 important defects (49x3522) left to find. That's rediculous.

Want more evidence that it's defect-ridden? Look at Inigo Surguy's "Technical review of OOXML", where he examines just the WordProcessingML section's 2300 XML examples. He wrote code to check for well-formedness and validation errors, and found that more than 10% (about 300) were in error even given this trivial test. Conclusion? "While a certain number of errors is understandable in any large specification, the sheer volume of errors indicates that the specification has not been through a rigorous technical review before becoming an Ecma standard, and therefore may not be suitable for the fast-track process to becoming an ISO standard." This did not include the other document sections, and this is a lower bound on accuracy (XML could validate and still be in error). (He also confirmed that Word 2007 does not implement the extensibility requirements of the Ecma specification, so as a result it would be hard to "write an interoperable word processor with Word" using OOXML.)

I think that all by itself, these vast number of errors in OOXML prove that the "Fast Track" process is completely inappropriate for OOXML. The "Fast Track" process was intended to be used when there was already a widely-implemented, industry-accepted standard that had already had its major problems addressed. That's just not the case here.

These huge error rates were predictable, too. The committee for creating OOXML wasn't even created until OpenDocument was complete, so they had to do a massive rush job to produce anything. ( Doug Mahugh admitted that "Microsoft... had to rush this standard through.") They didn't reuse existing mature standards, so they ended up creating much more work for themselves. Most developers (who could have helped find and fix the defects) stayed away from the Ecma process in the first place; its rules gave one vendor complete control over what was allowed, and there was already a vendor-independent standard in place, which gave most experts no reason to participate. The Ecma process was also almost entirely closed-door (OpenDocument's mailing lists are public, in contrast), which predictably increased the error rate too.

The GNOME Foundation has been involved in OOXML's development, and here's what they say in the GNOME Foundation Annual Report 2007: "The GNOME Foundation’s involvement in ECMA TC45-M (OOXML) was the main discussion point during the last meeting.... [the] Foundation does not support this file format as the main format or as a standard..." I don't think this is as widely touted as it should be. Here's an organization directly involved in OOXML development, and it thinks OOXML should not be a standard at all.

India has already voted "no" to OOXML. I hope others do the same. Countries with the appropriate rights have until March 29 to decide. It's quite plausiable that the final vote will be "no", and indeed, based on what's published, it should be "no". Open Malaysia reported on the March 2008 BRM meeting, for example. It reports that everybody "did their darnest to improve the spec... The final day was absolute mayhem. We had to submit decisions on over 500 items which we hadn't [had] the time to review. All the important issues which have been worked on repeatedly happened to appear on this final day. So it was non-stop important matters... It was a failure of the Fast Track process, and Ecma for choosing it. It should have been obvious to the administrators that submitting a 6000+ page document which failed the contradiction period, the 5 month ballot vote and poor resolution dispositions, should be pulled from the process. It should have been blatantly obvious that if you force National Bodies to contribute in the BRM and end up not deliberating on over 80% of their concerns, you will make a lot of people very unhappy... judging from the reactions from the National Bodies who truly tried to contribute on a positive manner, without having their concerns heard let alone resolved, they leave the BRM with only one decision in their mind come March 29th. The Fast Tracking process is NOT suitable for ISO/IEC DIS 29500. It will fail yet again. And this time it will be final."

In my opinion, the OOXML specification should not become an international standard, period. I think it clearly doesn't meet the criteria for "fast track" - but more importantly, it doesn't meet the needs for being a standard at all. It completely contradicts the goal of "One standard, one test - Accepted everywhere", and it simply is not an open standard. I've blogged before that having multiple standards for office documents is a terrible idea. There's nothing wrong with a vendor publishing their internal format; in fact, ISO's "type 2 technical report" or "ISO agreement" are pre-existing mechanisms for documenting the format of a single vendor and product line specification. But when important data is going to be exchanged between parties, it should be exchanged using an open standard. We already have an open standard for office documents that was developed by consensus and implemented by multiple vendors: OpenDocument (ISO/IEC 26300). For more clarification about what an open standard is, or why OpenDocument is an open standard, see my essay "Is OpenDocument an Open Standard? Yes!" OpenDocument works very well; I use it often. In contrast, it seems clear that OOXML will never be a specification that everyone can fully implement. Its technical problems alone are serious, but even more importantly, the Software Freedom Law Center's "Microsoft's Open Specification Promise: No Assurance for GPL" makes it clear that OOXML cannot be legally implemented by anyone using any license. And this matters greatly.

Andy Updegrove calls for recognition of "Civil ICT Standards", which I think helps puts this technical stuff into a broader and more meaningful context. He notes that in our new "interconnected world, virtually every civic, commercial, and expressive human activity will be fully or partially exercisable only via the Internet, the Web and the applications that are resident on, or interface with, them. And in the third world, the ability to accelerate one’s progress to true equality of opportunity will be mightily dependent on whether one has the financial and other means to lay hold of this great equalizer... [and thus] public policy relating to information and communications technology (ICT) will become as important, if not more, than existing policies that relate to freedom of travel (often now being replaced by virtual experiences), freedom of speech (increasingly expressed on line), freedom of access (affordable broadband or otherwise), and freedom to create (open versus closed systems, the ability to create mashups under Creative Commons licenses, and so on)... This is where standards enter the picture, because standards are where policy and technology touch at the most intimate level. Much as a constitution establishes and balances the basic rights of an individual in civil society, standards codify the points where proprietary technologies touch each other, and where the passage of information is negotiated... what will life be like in the future if Civil ICT Rights are not recognized and protected, as paper and other fixed media disappear, as information becomes available exclusively on line, and as history itself becomes hostage to technology? I would submit that a vote to adopt OOXML would be a step away from, rather than a way to advance towards, a future in which Civil ICT Rights are guaranteed".

Ms. Geraldine Fraser-Moleketi, Minister of Public Service and Administration, South Africa, gave an interesting presentation at the Idlelo African Conference on FOSS and the Digital Commons. She said, "The adoption of open standards by governments is a critical factor in building interoperable information systems which are open, accessible, fair and which reinforce democratic culture and good governance practices. In South Africa we have a guiding document produced by my department called the Minimum Interoperability Standards for Information Systems in Government (MIOS). The MIOS prescribes the use of open standards for all areas of information interoperability, including, notably, the use of the Open Document Format (ODF) for exchange of office documents... It is unfortunate that the leading vendor of office software, which enjoys considerable dominance in the market, chose not to participate and support ODF in its products, but rather to develop its own competing document standard which is now also awaiting judgement in the ISO process. If it is successful, it is difficult to see how consumers will benefit from these two overlapping ISO standards... The proliferation of multiple standards in this space is confusing and costly." She also said, "One cannot be in Dakar without being painfully aware of the tragic history of the slave trade... As we find ourselves today in this new era of the globalised Knowledge Economy there are lessons we can and must draw from that earlier era. That a crime against humanity of such monstrous proportions was justified by the need to uphold the property rights of slave owners and traders should certainly make us more than a little cautious about what should and should not be considered suitable for protection as property."

You can get more detail from the Groklaw ODF-MSOOXML main page, but I think the point is clear. The world doesn't need the confusion of a specification controlled by a single vendor being labelled as an international standard. NoOOXML has a list of reasons to reject OOXML.

path: /misc | Current Weblog | permanent link to this entry

Thu, 06 Dec 2007

Readable s-expressions (sweet-expressions) draft 0.2 for Lisp-like languages

Back in 2006 I posted my basic ideas about "sweet-expressions". Lisp-based programming languages normally represent programs as s-expressions, and though they are regular, most people find them hard to read. I hope to create an alternative to s-expressions that have their advantages, and not their disadvantages. You can see more at my readable Lisp page. I've gotten lots of feedback, based on both my prototype of the idea, as well as on the mailing list discussing it.

I've just posted a a draft of version 0.2 of sweet-expressions. This takes that feedback into account, in particular, it's now much more backwards-compatible. There's still a big question about whether or not infix should be a default; see the page for more details.

Here are the improvements over version 0.1:

  1. This version is much more compatible with existing Lisp code. The big change is that an unprefixed "(" immediately calls the underlying s-expression reader. This way, people can quietly replace their readers with a sweet-reader, without harming most existing code. In fact, many implementations could quietly switch to a sweet-reader and users might not notice until they use the new features. Instead of using (...), this uses {..} and [...] for grouping expressions without disabling sweet-expressions.
  2. It can work more cleanly with macros that provide infix precedence (for those who want precedence rules).
  3. It extends version 0.1's "name-prefixing" into "term-prefixing". This is not only more general, it also makes certain kinds of functional programming much more pleasant.
  4. It adds syntax for the common case of accessing maps (such as indexed or associative arrays) - now a[j] is translated into (bracketaccess a j).
  5. Infix default supports arbitrarily-spelled infix operators, and it automatically accepts "and" and "or".

Here's an example of (ugly) s-expressions: 

 (defun factorial (n)
   (if (<= n 1)
       1
       (* n (factorial (- n 1)))))

Here's sweet-expressions version 0.1: 

 defun factorial (n)
   if (n <= 1)
       1
       n * factorial(n - 1)

Here is sweet-expressions version 0.2 (draft), with infix default (it figures out when you have an infix operation from the spelling of the operation): 

 defun factorial (n)
   if {n <= 1}
       1
       n * factorial(n - 1)

Here is sweet-expressions version 0.2 (draft), with infix non-default (you must surround every infix operator with {...}): 

 defun factorial (n)
   if {n <= 1}
       1
       {n * factorial{n - 1}}

I'm still taking comments. If you're interested, take a look at http://www.dwheeler.com/readable. And if you're really interested, please join the readable-discuss mailing list.

path: /misc | Current Weblog | permanent link to this entry

Sun, 04 Nov 2007

Added "MapReduce" to the "Software Innovations" list

Ken Krugler's recent blog said that my article of The Most Important Software Innovations was "very good", but he was surprised that I hadn't included MapReduce as an important software innovation. Basically, MapReduce makes writing certain kinds of programs that process huge amounts of data, on vast distributed clusters, remarkably easy and efficient. (Wikipedia explains MapReduce, including links to alternative implementations like the open source Hadoop.)

It's not because I didn't know about MapReduce; I read about it almost immediately after it got published. I thought it was very promising, and even forwarded the original paper to some co-workers. I think MapReduce is especially promising because, now that we have cheap commodity computers, having a way to easily exploit their capabilities is really valuable. But even with something this promising, I didn't want to add it to my list of innovations right away - after all, maybe after a little while it turns out to be not so helpful.

Currently, there's aren't many who have Google-sized clusters of computers available. But it's clear that this approach is useful in many other circumstances as well. It's new, but I think it's stood the test of time enough that it's a worthy addition... so I've just added it.

One interesting issue is that the MapReduce framework is itself built primarily on the "map" and "reduce" functions, which are far, far older. So, is MapReduce really a new idea, or is it just a high-quality implementation of an old idea? I'll accept that it's a new idea, but that can be difficult to judge. This judgment doesn't really matter unless you think software patents are a good idea (since every software patents in theory prevents progress for 20 years). But I think it's quite clear that software patents are a foolish idea, and it's clear that others have come to the same conclusion. Eric S. Maskin, an economist who has long criticised the patenting of software, recently received the 2007 Nobel Prize for Economics. Here's a nice quote: "... when patent protection was extended to software in the 1980s, [...] standard arguments would predict that R&D intensity and productivity should have increased among patenting firms. Consistent with our model, however, these increases did not occur." Someone who correctly predicted that software patents were harmful to innovation just received a Nobel prize. I hope to someday see people receive other prizes because they ended software patenting in the United States.

path: /misc | Current Weblog | permanent link to this entry

Mon, 22 Oct 2007

Donald Macleay

Don Macleay was my mentor and friend, and he just passed away (Oct. 15, 2007). So, this is a small blog entry in his honor.

Donald (Don) Macleay Here's what I said at his funeral: "In 1980, Don was the manager of a computer store. I was only 15, but he took a chance on employing me, and I'm grateful. He taught me much, in particular, showing by example that you could be in business (even as a salesman!) and be an honest person. He later moved to other companies, and I moved twice with him, because I found that good bosses were hard to find. Don was honest, reliable, a good friend, and an inspiration to me. I will miss him, and I look forward to seeing him again in heaven." I should add that he spoke at my Eagle scout ceremony. Later on, when he moved out to the country, it was always a pleasure to visit him and his family.

Here's a part of his biography, as printed in the funeral bulletin: "Born in Washington, D.C., on October 27, 1934, Donald Macleay was raised in Falls Church. He attained the rank of Eagle Scout and graduated at the top of the first class of St. Stephen's School in 1952. In 1956, he graduated with a Bachelor of Arts in English from the Virginia Military Institute (VMI).

After serving as a Marine Corps officer, Donald Macleay spent many years in the business world before becoming a Parole Officer for the Department of Juvenile Justice in Stafford County. As well, in 1992, he was a candidate for the U.S. Congress as an Independent."

The biography goes on to note that he "valued being a Christian, a husband, a father and grandfather, and a friend." Much of his last years were spent helping troubled youth in his area (Fredericksburg, VA), and from all accounts he was extraordinarily successful at helping them and their families.

path: /misc | Current Weblog | permanent link to this entry

Thu, 11 Oct 2007

Readable s-expressions (sweet-expressions) for Lisp-like languages

Back in 2006 I posted my basic ideas about "sweet-expressions". Here's a basic recap, before I discuss what's new. Lisp-based programming languages normally represent programs as s-expressions, where an operation and its parameters are surrounded by parentheses. The operation to be performed is identified first, and each parameter afterwards is separated by whitespace. So the traditional “2+3” is written as “(+ 2 3)” instead. This is regular, but most people find this hard to read. Here's a longer example of an s-expression - notice the many parentheses and the lack of infix operations: 

 (defun factorial (n)
   (if (<= n 1)
       1
       (* n (factorial (- n 1)))))

Lisp-based systems are very good at symbol manipulation tasks, including program analysis. But many software developers avoid Lisp-based languages, even in cases where they would be a good tool to use, because most software developers find s-expressions really hard to read. I think I've found a better solution, which I call "sweet-expressions". Here's that same program be written using sweet-expressions: 

 defun factorial (n)         ; Parameters can be indented, but need not be
   if (n <= 1)               ; Supports infix, prefix, & function <=(n 1)
       1                     ; This has no parameters, so it's an atom.
       n * factorial(n - 1)  ; Function(...) notation supported

Sweet-expressions add the following abilities:

  1. Indentation. Indentation may be used instead of parentheses to start and end expressions: any indented line is a parameter of its parent, later terms on a line are parameters of the first term, lists of lists are marked with GROUP, and a function call with 0 parameters is surrounded or followed by a pair of parentheses [e.g., (pi) and pi()]. A “(” disables indentation until its matching “)”. Blank lines at the beginning of a new expression are ignored. A term that begins at the left edge and is immediately followed by newline is immediately executed, to make interactive use pleasant.
  2. Name-ending. Terms of the form ‘NAME(x y...)’, with no whitespace before ‘(’, are interpreted as ‘(NAME x y...)’;. Parameters are space-separated inside. If its content is an infix expression, it's considered one parameter instead (so f(2 + 3) computes 2 + 3 and passes its result, 5, to f).
  3. Infix. Optionally, expressions are automatically interpreted as infix if their second parameter is an infix operator (by matching an “infix operator” pattern of symbols), the first parameter is not an infix operator, and it has at least three parameters. Otherwise, expressions are interpreted as normal “function first” prefix notation. To disable infix interpretation, surround the second parameter with as(...). Infix expressions must have an odd number of parameters with the even ones being the same binary infix operator. You must separate each infix operator with whitespace on both sides. Precedence is not supported; just use parens (a lot more about that in a moment). Use the "name-ending" form for unary operations, e.g., -(x) for "negate x". Thus "2 + (y * -(x))" is a valid expression, equivalent to (+ 2 (* y (- x))). "(2 + 3 + 4)" is fine too. Infix operators must match this pattern (and in Scheme cannot be =>): 
        [+-\*/<>=&\|\p{Sm}]{1-4}|\:

For more information on sweet-expressions or on making s-expressions more readable in general, see my website page at http://www.dwheeler.com/readable. For example, I provide a demo sweet-expression reader in Scheme (under the MIT license), as well as an indenting pretty-printer in Common Lisp. In particular, you can see my lengthy paper about why sweet-expressions do what they do, and some plausible alternatives. You can also download some other implementation code. I've also set up a SourceForge project named "readable" to discuss options in making s-expressions more readable, and to distribute open source software to implement them (unimplemented ideas don't go far!).

Okay, but all of that was true in 2006 - what's new? What's new is a change of heart about precedence. I've been occasionally trying to figure out how to "flesh out" sweet-expressions with operator precedence, and I just kept hitting one annoying complication after another. Precedence is nearly universal among programming languages; they're very useful, and only a few infix-supporting languages (such as Smalltalk) lack them. "Everyone" knows that 2+3*4 is 14, not 20, because of years of training in math classes that you multiply before you add. They're also pretty easy to code (it's an old solved problem). But I've discovered that in the typical use cases of a Lisp-like language's expression reader, supporting precedence (in the general case) has some significant downsides that are irrelevant in other situations. Which is interesting, given how widespread they are elsewhere, so let's see why that is.

First, let's talk about a big advantage to not supporting precedence in sweet-expressions: It makes the creation of every new list obvious in the text. That's very valuable in a list processing language; the key advantage of list processing languages is that you can process programs like data, and data like programs, in a very fluid way, so having clear markers of new lists using parentheses and indentation is very valuable.

Now let me note the downsides to supporting precedence in the specific cases of a Lisp-like language, which leads me to believe that it's a bad idea for this particular use. Basically, adding precedence rules to a general-purpose list expression processor creates a slippery slope of complexity. There are two basic approaches to defining precedence: dynamic and static.

It's easier to add precedence later, if that turns out to be important after more experimentation. But after the experimentation I've done so far, it appears that precedence simply isn't worth it in this case. Precedence creates complexity in this case, and it hides where the lists begin/end. It's not hard to work without it; you can even argue that (2 + (5 * 6)) is actually clearer than (2 + 5 * 6). Precedence is great in many circumstances - I'd hate to lose it in other languages - but in this particular set of use cases, it seems to be more of a hurt than a help.

Of course, you can write code in some Lisp dialect to implement a language that includes precedence. Many programs written in Lisp, including PVS and Maxima, do just that. But when you're implementing another language, you know what the operators are, and you're probably implementing other syntactic sugar too, so adding precedence is a non-problem. Also, if you're really happy with s-expressions as they are, and just want precedence in a few places in your code, a simple macro to implement them (such as infpre) works very well. But sweet-expressions are intended to be a universal representation in Lisp-like languages, just like S-expressions are, so their role is different. In that different role, precedence causes problems that don't show up in most other uses. It think not supporting precedence turns out to be much better for this different role.

Here are some more examples, this time in Scheme (another Lisp dialect):
Sweet-expression (Ugly) S-expression 
define factorial(n)
   if (n <= 1)
       1
       n * factorial(n - 1)
substring("Hello" (1 + 1) string-length("Hello"))
define move-n-turn(angle)
   tortoise-move(100)
   tortoise-turn(angle)
if (0 <= 5 <= 10)
   display("True\n")
   display("Uh oh\n")
define int-products(x y)
  if (x = y)
    x
    x * int-products((x + 1) y)
int-products(3 5)
(2 + 3 + (4 * 5) + 7.1)
(2 + 3 + (4 / (5 * 6)))
*(2 3 4 5)

(define (factorial n)
   (if (<= n 1)
       1
       (* n (factorial (- n 1)))))
(substring "Hello" (+ 1 1) (string-length "Hello"))
(define (move-n-turn angle)
   (tortoise-move 100)
   (tortoise-turn angle))
(if (<= 0 5 10)
   (display "True\n")
   (display "Uh oh\n"))
(define (int-products x y)
  (if (= x y)
      x
      (* x (int-products (+ x 1) y))))
(int-products 3 5)
(+ 2 3 (* 4 5) 7.1)
(+ 2 3 (/ 4 (* 5 6)))
(* 2 3 4 5)

So I've modified my demo program so that it supports infix operator chaining, such as (2 + 3 + 4). Since I no longer need to implement precedence, the addition of chaining means that I now have a working model of the whole idea, ready for experimentation. My demo isn't ready for "serious use" in development yet; it has several known bugs and weaknesses. But it's good enough for experimentation, to see if the basic idea is sensible - and I think it is. You can actually sit down and play with it, and see if it has merit. There are still some whitespace rules I'd like to fiddle with, to make both long files and interactive use as comfortable as possible, but these are at the edges of the definitions... not at its core.

I'm suggesting the use of && for "logical and", and || for "logical or". These are common symbols in other languages, and using the same symbols aids readability. Now, in Common Lisp and some Scheme implementations, || is "the symbol with 0-length name". Oddly enough, this doesn't seem to be a problem; Lisps can generally bind to the symbol with the 0-length name, and print it the same way, so it works perfectly well! In Scheme this is trivially done by running this: 

define(&& and)
define(|| or)
Then you can do this: 
(#t && #t)
if ((a > b) || ((a * 2) < (c + d + e))) ...
Instead of the hideous s-expressions: 
(and #t #t)
(if (or (> a b) (< (* a 2) (+ c d e))) ...)

Here are some quotable quotes, by the way, showing that I'm not the only one who thinks there's room for improvement:

Lisp-based languages are all over the place. There are vast number of implementations of Common Lisp and Scheme. GNU guile is a Scheme implementation embedding into many other programs, for example. GNU emacs is a widely-used text editor, built on its own dialect of Lisp. AutoCAD has its own variant under the covers, too. Programs like PVS are implemented in Lisp, and interacting with it currently requires using s-expressions. It'd be great if all of these supported an alternative, simpler syntax. With sweet-expressions, typical s-expressions are legal too. So I think this is a widely-useful idea.

So if you're interested, take a look at http://www.dwheeler.com/readable.

path: /misc | Current Weblog | permanent link to this entry

Sat, 23 Jun 2007

ISPs Inserting Ads Into Your Pages: Unlawful Modifications (Copyright Violation)

Here's a nasty trick. Apparantly some shady Internet Service Providers (ISPs) are inserting advertizements into other people's web pages without their permission.

I believe these are usually illegal modifications. Whoever creates a work automatically has a copyright on that work. (If you're doing work for someone else, or if you sell the copyright, they have the copyright.) Anyone who releases a public web page obviously grants others the right to copy that work to view it, but unless otherwise stated, you don't have the right to modify the work. U.S. law also has "fair use" provisions that let you quote another work without being sued, and so on, but those can't possibly be stretched into letting someone insert ads. The copyright owner can release works permitting such actions (that's how Free-libre / open source software works), but they have to give that permission... you can't just unilaterally modify it. What really angers me is that they might insert stuff I am morally opposed to, and sullying my reputation.

If you run a website, here's a sample letter that you can send to inform these ISPs that what they're doing is wrong. 

Dear (name here),

I am concerned that you appear to be violating copyright laws,
by unlawfully modifying and then redistributing copyrighted works
of mine and many others.

In particular, your "terms of service" say... (quote them, if you can).

My website, (www.dwheeler.com), distributes many copyrighted works
at no charge, but I do _NOT_ give the right to modify many of
those works.  Many other websites do the same.  (Some can add:
In addition, I have ads on my site; by adding your own ads, you are
diluting the value of MY ads and in essence stealing from me.)

Please stop modifying my web pages immediately.  It is my hope that
this was just a misunderstanding, and that we can settle this amicably.

Thank you very much.

path: /misc | Current Weblog | permanent link to this entry

Mon, 11 Jun 2007

Reviews of Books, Movies, etc.

I read voraciously, and occasionally I've even been known to see a movie. So I've started to write down Reviews of Books, Movies and Other Stuff. There you can see what I think of various books, movies, etc. It's not huge yet, but I intend to make it grow.

In many cases you can click on it to get your own copy via Amazon.com. If you buy something that way, I even get a small cut. I won't get rich that way, but if you choose to buy something by doing that, thanks very much!

path: /misc | Current Weblog | permanent link to this entry

Tue, 05 Jun 2007

Comparing OpenDocument (ODF) with MS-XML (OOXML/EOOXML) - and why Multiple Competing Standards are a Bad Idea

Microsoft continues to give its bizarre argument that multiple competing (conflicting) standards for the same purpose is a good thing. They are dreadfully confused. Having multiple competing products is a good thing, but having multiple competing standards is terrible.

Multiple competing standards risk massive property loss, many lives, and even the loss of your country, according to history. My presentation Open Standards and Security notes two of the many historical examples, the 1904 Baltimore fire and the U.S. Civil war:

  1. In 1904, a huge (80-block) area of Baltimore burned to the ground. Fire fighters from other cities came but couldn't effectively connect their fire hoses to the fire hydrants, because every city had their own incompatible standard. That resulted in 2,500 burned buildings over a 30 hour period.
  2. Perhaps even more strikingly, one of the important reasons the U.S. South (the Confederacy) lost the U.S. Civil War was because the southern states had incompatible rail gauges. The U.S. North had a single rail gauge standard (for the most part), and could move troops and materiel to battles far more quickly than the U.S. South, even though the U.S. North had far greater distance to travel. Ned Harrison's paper “'States Rights' doomed Confederate nation" (Nov. 12, 2005) cites the problems with railroads, including the rail gauge incompatibility, as an important factor in the U.S. South's loss (it certainly was not the only reason, but it was an important factor). Indeed, when the North conquered an area, one of the first things it did was move the rails to the Northern standard... so it could continue to exploit that advantage as it advanced.

But what about document converters, don't they make it easy to have multiple competing standards? Well, it's true that there are converters like ODF Converter. But while converters are very useful for one-time transitions, they are lousy long-term solutions... they make it clear that there has been a failure, not a success, in standards-making. Look at the problems multiple standards cause in other areas. We can easily convert between metric and English units, but NASA lost a $125 million Mars orbiter because a Lockheed Martin engineering team used English units of measurement while the agency's team used the more conventional metric system. Another example is the Gimli Glider, a Boeing 767 that ran out of fuel in Canada in 1983 due, in large part, to confusion about English/metric conversion. Why do we want this problem in office documents too? Also, as of June 5, 2007, there are 6 pages of problems converting MS XML to ODF, but only 2 pages of problems converting ODF to MS XML. In general, ODF appears to be a much more capable format; just from that list it appears that it'll be easier to improve ODF than to try to use MS XML for all documents. Which is unsurprising; the ODF work included membership from a variety of office suite implementors, while MS XML is the work of just one. That's even more true when you consider that OpenDocument uses existing standards, instead of creating a trade barrier through nonsense one-off specifications. Microsoft claims that OOXML is necessary to "fully" capture old binary documents, but I have not seen much evidence this is actually true. A quick look at the CONVERT function in OOXML revealed many absolutely incorrect unit measures, for example. More generally, I have no reason to believe that the OOXML spec actually includes what is needed to capture the older binary formats like .doc - no mapping has been presented to prove this claim, and it'd be easy for the OOXML spec to omit lots of important information.

Regardless of the facts, Microsoft continues to press for ISO standardization of its format, aka "Microsoft XML" (MS-XML), OOXML, or EOOXML. There are now several papers about problems with OOXML. Groklaw's EOOXML objections has lots of good information. Edward Macnaghten's Technical Distinctions of ODF and OOXML: A Consultation Document (ODFA UKAG) is interesting because it shows what actual documents look like using the different specs - and it exposes a lot of problems in MS XML that have not been widely discussed before. Sam Hiser has an interesting ODF / OOXML comparison as well. Rob Weir has interesting comments as well.

Perhaps a more elegant demonstration the OOXML is absurd is this picture of their 6000-page spec, printed. This is a single spec; no wonder there's been so little review compared to OpenDocument. Yet even with this hideously large size, MS XML (OOXML) still fails to give the important details that a spec really needs. The reason it's so hideously long, while still failing to give the important details a spec needs, is simply because they ignored a vast number of standards - so they end up re-inventing lots of already-existing standards. Thus, they end up conflicting with a large number of different standards. They even ignored MathML, a widely-used standard that even they supported, and redid things from scratch.

Even on the ground this pressure for OOXML makes little sense. Magazines like Science and Nature reject Office 2007 documents. Macintoshes still can't read the .docx (etc) format, nor can Pocket PCs.

I guess one good result is that Microsoft has encouraged voting for OpenDocument, because that's the only logical thing it can do if it really believes that having "many conflicting formats are a good thing". In contrast, there's no reason that someone who wants a truly open single format needs to vote for OOXML. It's perfectly reasonable to reject OOXML on the grounds that it conflicts with an already-existing ISO standard (OpenDocument). If there's something that OOXML does that OpenDocument doesn't, it would be much easier to add that tweak to OpenDocument, because OpenDocument builds on existing standards while OOXML fails to do so.

Microsoft is not a "universal evil", and I praise them when they do good things. But encouraging multiple conflicting standards for the same area is not a good thing. In some sense, I don't care if MS XML or ODF become "the" format for office documents, as long as the final specification is truly open. But the materials noted above lead me to believe that MS XML is not really open; it appears to be effectively controlled by one vendor, both in its current and future forms, as one obvious example. So MS XML isn't really an option, and we already have a nice working solution.

What I want is a single document format that is fully open. What's that mean? See Is OpenDocument an Open Standard? Yes! to see what the phrase "open standard" really means. And let's look at it in practice. Currently I can edit text documents using the program "vim", and I don't even bother to ask if the other person uses emacs, or Notepad... just by saying "simple text format" we can exchange our files. Similarly, I can edit a GIF or PNG file without wondering what originally created the file - or who will edit it next. That's generally true with other standards like HTML, HTTP, and TCP/IP. That's the beauty of open standards - real open standards enable a thriving industry of competing products, allowing users to choose and re-choose between them. I want to see that beautiful sunlight in office suites as well.

path: /misc | Current Weblog | permanent link to this entry

Wed, 18 Apr 2007

George Mason University (GMU) Thesis/Dissertation Sample Document in OpenDocument Format

I've released a "sample document" that implements all the requirements of George Mason University (GMU)'s Thesis/Dissertation format in the OpenDocument format. You can get it in OpenDocument or PDF formats.

If you're a student at GMU who needs it, you really need this.. but even if you're not, there's lots that can be shown from this template.

First, if you're a student at GMU who needs it, let me explain why you really need it. Most universities have their own formats that have many detailed requirements, so by using a pre-created format, you immediately comply with lots of the details that are meaningless, yet you can't graduate without meeting them. GMU requires page numbers to be on the top right, except at chapter headings (where they are centered on the bottom)... except that appendix chapter headings aren't considered chapter headings. Got all that? GMU requires that there be a horizontal line between any footnotes and the main text, and it must be exactly 2" long. Oh, and there are lots of margin requirements, which you must get exactly right. Every university has its own oddnesses; this format, for example, is explicitly single-sided, uses U.S. customary measurement units everywhere, and has its own odd placement rules (e.g., appendixes must be placed after, not before, the bibliography). Headings are 2" from the top.. except that level 1 appendix headings aren't considered headings. It took me a long time of back-and-forth discussions with the GMU dissertation and thesis coordinator to get all the details right. (The problem wasn't that OpenDocument couldn't do it; the problem was understanding what the GMU requirements actually were.) You can spend many, many hours to redo these details... or just grab this sample document and have the problems solved for you.

But whether you're a GMU student or not, there's lots that can be shown from this template. It certainly shows that OpenDocument is fully capable of representing fairly complicated (and odd!) formats, for large documents, completely automatically. That shouldn't be surprising; one of the OpenDocument developers was Boeing, who develop so many large documents to build an airplane that the documents (when printed) outweigh the plane.

In particular, this document shows that an OpenDocument document can automate all sorts of things, easing development:

  1. Just create a "Heading 1" (control-1 in OpenOffice.org) and the page format automatically switches to first chapter format (with page numbering in a different place).
  2. The spacing and text flow all happen automatically, without weird artifacts like undesired "extra" vertical space on the top of a page. In fact, nearly everything is very automatic - you can concentrate on writing a paper, instead of fixing formats. The entire document is based on "paragraph styles" - just make sure each paragraph has the right style (which is nearly always correct), and the document will look right.
  3. Tables of Contents, of tables, and figures can all be automatically regenerated.
  4. Even the bibliography can be regenerated automatically, so that only documents actually cited in the paper are listed. You can even determine what order is appropriate (e.g., alphabetically or in citation order).

What's particularly amusing is to compare the OpenDocument template to the GMU Word templates, because their Word templates are horrible to use. GMU's Word templates are a bunch of individual files, completely inappropriate for actual use by a writer. Even the first page of a chapter and the rest of a chapter are in separate documents, and the table of contents has to be regenerated by hand. But even merging these files together won't completely solve the problem; Word sometimes fails to correctly generate tables of contents (it's happened to me!), which is one reason why so many people hand-create tables of contents. And Word certainly doesn't match other OpenDocument capabilities, such as automated bibliography management. What's worse, even though Word does have paragraph styles, Word seems to work especially hard to subvert and make their use difficult. Word seems to love redefining all your carefully-crafted styles, making Word painful to use as the document gets long. In contrast, OpenDocument is a breeze to use (at least in OpenOffice.org, and probably other OpenDocument-based systems as well) - setting paragraph styles is trivial (and for the most part completely automatic), once set they stay set, and they can make all the other formatting decisions automatic. Creating useful sample documents in Word is also painful; I started and completed one in OpenDocument quite easily, while GMU is still struggling to create a Word template.

You don't have to use OpenOffice.org to use OpenDocument, which is great - choice and competition are good things. But OpenOffice.org is a reasonable choice. Bruce Byfield's articles Replacing FrameMaker with OOo Writer and OpenOffice.org Writer vs. Microsoft Word showed that OpenOffice.org is remarkably capable, especially in its word processor. Byfield's comparison of OpenOffice.org with the widely-lionized FrameMaker is especially enlightening: "I began comparing FrameMaker and Writer when a regular on the OpenOffice.org User's list asked what it would take to give Writer the power of FrameMaker. When I started, I mentally pictured a scale with Microsoft Word on one end and FrameMaker on another, with Writer in the middle, but closer to Microsoft Word. As I proceeded, I found Writer was a much stronger contender than I had expected. At the end of the comparison, I had to conclude that the two products compare quite closely, depending on what features are more important to a given user... [OpenOffice.org users] can be in little doubt that they are using software that competes with FrameMaker on its own terms, and wins as often it loses. Even ignoring the cost and philosophical differences, OpenOffice.org is clearly an acceptable alternative to FrameMaker."

In short, if you're creating a thesis at GMU, use OpenDocument. I've used Word, Word Perfect, OpenOffice.org, and FrameMaker to write large documents. FrameMaker is nice but hideously overpriced, and because it's overpriced, non-standard, and poorly supported, it's mostly disappearing from the marketplace. Word works well for 1-2 page documents, but its weaknesses become apparant as your documents get larger, and it's based on proprietary formats that lock you into a single product. It's painful to use for larger documents; GMU has yet to create a Word template that is even slightly non-painful. In contrast, in short order I created an OpenDocument format that did everything they wanted, with lots of automation. OpenDocument is an ISO standard, with nice products to support it, and specifically designed for large documents. If you need to make large documents, use the right tool for the job.

path: /misc | Current Weblog | permanent link to this entry

Fri, 01 Sep 2006

Planet definition problems, and Pluto too

Well, at the last minute International Astronomical Union (IAU) changed their proposed definition of the term "planet", and voted on it. Pluto is no longer a planet!

Well, maybe.

Usually definitions like this go through a lot of analysis; I think this one was rushed through at the last minute. I see three problems: It was an irregular vote, it's vague as written, and it doesn't handle faraway planets well. Let's look at each issue in turn.

This was a pretty irregular vote, I think. As I noted, at the last minute the proposal changed, with no time for deeply examining it. There were 2,700 attendees, but only 424 astronomers (about 10%) voted on the proposal that "demoted" Pluto. And only a few days after the vote, 300 astronomers have signed a petition saying they do not accept this IAU definition - almost as many as voted in the first place. That doesn't sound like consensus to me.

More importantly, it's too vague. That's not just my opinion; Space.com notes that there's a lot of uncertainty about it. Now a planet has to control its zone... but Earth doesn't, there are lots of objects that cross Earth's orbit. Does this mean that Earth is not a planet? I haven't seen any published commentary on it, but I think there's even a more obvious problem - Neptune is clearly not a planet, because it hasn't cleared out Pluto and Charon. A definition which is that vague is not an improvement.

But in my mind, the worst problem with this definition is a practical one: it doesn't handle other planets around other stars well. We are too far away to observe small objects around other stars, and I think we will always be able to detect larger objects but not smaller ones in many faraway orbits. So when we detect an object in another galaxy with the mass of Jupiter, and it's orbiting a star, is it a planet? Well, under this current definition we don't know if it's a planet or not. Why? Because we may not be able to know what else is there in orbit. And that is a real problem. I think it's clear that we will always be able to observe some larger objects without being able to detect the presence of smaller ones. If we can't use the obvious word, then the definition is useless - so we need a better definition instead.

I thought the previous proposal (orbits a star, enough mass to become round) was a good one, as I noted earlier in What's a planet? Why I'm glad there's an argument. I think they should return to that previous definition, or find some other definition that is (1) much more precise and (2) lets us use the term "planet" in a sensible way to discuss large non-stars that are orbiting faraway stars. Whether Pluto is in, or not. Of course, none of this affects reality; this is merely a definition war. But clear terminology is important in any science.

I still think that what's great about this debate is that it has caused many people to discuss and think about what's happening in the larger universe, instead of focusing on the transient. That is probably the most positive result of all.

path: /misc | Current Weblog | permanent link to this entry

Mon, 21 Aug 2006

What's a planet? Why I'm glad there's an argument

The International Astronomical Union (IAU) has a proposed definition of the term "planet" that is currently being vigorously debated. I like the definition, and I'm even more delighted that there's a vigorous discussion about the proposed definition.

We've used the term "planet" for thousands of years, without trouble. But now that we're learning more about the heavens, we now know about many objects orbiting other stars, and about many more objects orbiting our own Sun. As a result, our simple intuitions aren't enough. Obviously objects will orbit other objects no matter what we call them, but since we want humans to be able to communicate with each other, it's very important that we have definitions that help rather than hinder communication.

The latest proposed definition is actually very sensible. Basically (and I'm paraphrasing here), it defines a planet as an object that (1) orbits a star, and (2) has enough mass that its gravity can make itself "round". The real definition has some clever nuances that make this workable. For example, Saturn rotates so fast that it bulges, but since it has enough mass to make it round, it's clearly a planet by this definition. Also, if objects orbit each other and their center of gravity isn't inside any of them, then they're all planets - so both Pluto and Charon become planets under this definition. The object "2003 UB313" (unofficially called Xena) would be recognized as a planet as well, as would Ceres.

I think this definition is very sensible, because it's based on observable basic physical properties, which are at least somewhat less arbitrary. One previous proposal was "orbits a star and is at least as big as Mercury" - which makes the "Pluto isn't a planet" group happy, but is incredibly arbitrary. Another approach, which I happened to prefer before this proposal surfaced, is "orbits a star and is at least as big as Pluto" - which makes the "Pluto is a planet" group (like me) happy, and causes fewer changes to textbooks, but it's still really arbitrary. All such definitions are a little arbitrary, but this new proposed definition is at least somewhat less arbitrary - this definition emphasizes a fundamental physical characteristic of the object. Namely, it has enough gravity to force a change in its own shape.

Some astronomers have complained that this proposed definition doesn't account for "how the planets were formed"; I think this is nonsense. Humans weren't around to watch the planets form; our current theories about planet formation may be grossly mistaken. In fact, I think it's almost certain we're wrong, because we can't observe much about planets of other stars to verify or debunk our current theories. And what's worse, since we can't really observe much about objects orbiting other stars, we can't really know if they're planets based on some "formation" definition - because we can't get enough data to figure out their ancient history. And here's a funny thought experiment - someday we may be able to create planets ourselves. Yes, that's not exactly likely to be soon, but it's a great thought experiment. If we create a planet, is it a planet? It should be. Any definition like "planet" should be based on its obvious observable properties, not on best guesses (likely wrong!) about formation events of long ago. A definition that uses only unimpeachable data is far more useful, and when observing farway objects we get very little information.

No one wants to claim that every pebble orbiting a star is a planet -- our intuition says that there's something fundamentally "big" about a planet that makes it a planet. I asked an 11-year-old what made a planet, a planet. Her first answer, before hearing about this argument, was "it's round" (!). While that's not a scientific survey, it does suggest that the creators of this definition really are on to something - kids can intuitively understand (and even guess at!) this definition.

Are there weird things about this definition? Sure! Charon becomes a planet too, as I noted above. Since our own moon is slowly moving away, in a few billion years our moon might become a planet (assuming the Earth and Moon don't get destroyed by the Sun first). I guess you could "fix" the definition for those two cases by saying that the "most massive" object of a group was the planet, but I don't see the need for this "fix". In fact, you get an interesting insight if your definition forces you to note that their centroid isn't inside any of them. The object Ceres, now considered an unusually large asteriod, becomes a planet. That's okay, Ceres was originally considered a planet when it was discovered - it even has a planetary symbol. It'll make people rewrite the textbooks, but we've learned so much recently that they need rewriting anyway. It'll make it easy to see which books are obsolete - they're the ones which say we have only 9 planets.

What's really great about this debate is that it's making people think about the heavens. Any definition of "planet" is in some ways arbitrary, frankly. I think this essential arbitrariness makes such definitions the hardest things to agree on in science, because there's no way that more observations can prove or disprove a theory. This definition is much less arbitrary than others people have come up with, because it focuses on an important "change in state" of the object. And that's a pretty good reason to endorse this definition.

In any case, this debate has caused many people to discuss and think about what's happening in the larger universe, instead of focusing on the transient. And that is probably the most positive result of all.

path: /misc | Current Weblog | permanent link to this entry

Sat, 17 Jun 2006

Learning from the Masters

If you want to learn something, study what the masters do. To me that seems obvious, and yet many don't do it. Perhaps we simply forget. So let me inspire you with a few examples...

I just got an advance copy of David Shenk's "The Immortal Game: A history of chess" - and I'm referenced in it! Which is an odd thing; I don't normally think of myself as a chess commentator. But I do like the game of chess, and one of my key approaches to getting better is simple: Study the games of good players. I've even posted a few of the games with my comments on my web site, including The Game of the Century (PGN/Text), The Immortal Game (PGN/Text), The Evergreen Game (PGN/Text), and Deep Blue - Kasparov, 1996, Game 1 (PGN/Text). It's my Byrne/Fischer writeup that was referenced in Shenk's book. But I didn't create that stuff for a book, originally. I can't play like these great players can, but I get better by studying what they do. In short, I've found that I must study the work of the masters.

There are many children's educational philosophies that have, at least in part, the notion of studying good examples as part of education. Ruth Beechick's "natural method" for teaching writing emphasizes starting by copying and studying examples of great writing. She even notes Jack London and Benjamin Franklin started by studying works they admired. Learning begins by studying the work of the masters.

I often write about free-libre/open source software (FLOSS). In part, I do because it's one amazingly interesting development. But there are other reasons, too. Some developers of FLOSS programs are the best in the business - you can learn a lot by seeing what they do. In short, one important advantage of FLOSS is that it is now possible for software developers to study the work of the masters.

I recently wrote the article High Assurance (for Security or Safety) and Free-Libre / Open Source Software (FLOSS)... with Lots on Formal Methods (aka high confidence or high integrity) (I gave it the long title to help people find it). Here, I note the many tools to create high assurance software - but there are precious few FLOSS examples of high assurance software. True, there are very few examples of high assurance software, period, but where are the high assurance software components that people can study and modify without legal encumberances? (If you know of more, contact me.) That worries me; how are we supposed to educate people how to create high assurance software, if students never see it? People do not wake up one morning and discover that they are an expert. They must learn, and books about a topic are not enough. They must study the work of the masters.

path: /misc | Current Weblog | permanent link to this entry

Readable s-expressions and sweet-expressions: Getting the infix fix and fewer parentheses in Lisp-like languages

Lisp-based programming languages normally represent programs as s-expressions, where an operation and its parameters are surrounded by parentheses. The operation to be performed is identified first, and each parameter afterwards is separated by whitespace. So the traditional “2+3” is written as “(+ 2 3)” instead. This is regular, but most people find this hard to read. Here's a longer example of an s-expression - notice the many parentheses and the lack of infix operations: 

 (defun factorial (n)
   (if (<= n 1)
       1
       (* n (factorial (- n 1)))))

I think there's a small resurging interest in Lisp-based systems, because Lisp is still very good at "programs that manipulate programs". The major branches of Lisp (Common Lisp, Scheme, and Emacs Lisp) have not disappeared, after all. And I recently encountered a very cool and very new language in development, BitC. This language was created to write low-level programs (e.g., operating system kernels and real-time programs) that are easy to mathematically prove correct. I learned about this very cool idea while writing my paper High Assurance (for Security or Safety) and Free-Libre / Open Source Software (FLOSS)... with Lots on Formal Methods. BitC combines ideas from Scheme, ML, and C, but it's represented using s-expressions because it's easy to manipulate program fragments that way. I don't know how well it'll succeed, but it has a good chance; if nothing else, I don't know of anyone who's tried this particular approach. The program-prover ACL2 uses Common Lisp as a basis, for the same reason: program-manipulating programs are easy. The FSF backs guile (a Scheme dialect) as their recommended tool for scripting; guile gives lots of power in a small package.

But many software developers avoid Lisp-based languages, even in cases where they would be a good tool to use, because most software developers find s-expressions really hard to read. S-expressions are very regular... but so is a Turing machine. They don't call it ‘Lots of Irritating Superfluous Parentheses’ for nothing. Even if you can read it, most developers have to work with others. Some people like s-expressions as they are - and if so, fine! But many others are not satisfied with the status quo. Lots of people have tried to create easier-to-read versions, but they generally tend to lose the advantages of s-expressions (such as powerful macro and quoting capabilities). Can something be done to make it easy to create easier-to-read code for Lisp-like languages - without spoiling their advantages?

I think something can be done, and I hope to spur a discussion about various options. To get that started, I've developed my own approach, "sweet-expressions", which I think is actually a plausible solution.

A sweet-expression reader will accept the traditional s-expressions (except for some pathological cases), but it also supports various extensions that make it easier to read. Sweet-expressions are automatically translated into s-expressions, so they lose no power. Here's how that same program above could be written using sweet-expressions: 

 defun factorial (n)         ; Parameters can be indented, but need not be
   if (n <= 1)               ; Supports infix, prefix, & function
<=(n 1)
       1                     ; This has no parameters, so it's an atom.
       n * factorial(n - 1)  ; Function(...) notation supported

Sweet-expressions add the following abilities:

  1. Indentation. Indentation may be used instead of parentheses to start and end expressions: any indented line is a parameter of its parent, later terms on a line are parameters of the first term, lists of lists are marked with GROUP, and a function call with 0 parameters is surrounded or followed by a pair of parentheses [e.g., (pi) and pi()]. A “(” disables indentation until its matching “)”. Blank lines at the beginning of a new expression are ignored. A term that begins at the left edge and is immediately followed by newline is immediately executed, to make interactive use pleasant.
  2. Name-ending. Terms of the form ‘NAME(x y...)’, with no whitespace before ‘(’, are interpreted as ‘(NAME x y...)’;. Parameters are space-separated inside. If its content is an infix expression, it's considered one parameter instead (so f(2 + 3) passes the its parameter, 5, to f).
  3. Infix. Optionally, expressions are automatically interpreted as infix if their second parameter is an infix operator (by matching an “infix operator” pattern of symbols), the first parameter is not an infix operator, and it has at least three parameters. Otherwise, expressions are interpreted as normal “function first” prefix notation. To disable infix interpretation, surround the second parameter with as(...). Infix expressions must have an odd number of parameters with the even ones being binary infix operators. You must separate each infix operator with whitespace on both sides; precedence is supported. Use the "name-ending" form for unary operations, e.g., -(x) for "negate x". Thus "2 + y * -(x)" is a valid expression, equivalent to (+ 2 (* y (- x))). Infix operators must match this pattern (and in Scheme cannot be =>): 
        [+-\*/<>=&\|\p{Sm}]{1-4}|\:

I call this combination “sweet-expressions”, because by adding syntactic sugar (which are essentially abbreviations), I hope to create a sweeter result.

For more information on sweet-expressions or on making s-expressions more readable in general, see my website page at http://www.dwheeler.com/readable. For example, I provide a sweet-expression reader in Scheme (under the MIT license), as well as an indenting pretty-printer in Common Lisp. In particular, you can see my lengthy paper about why sweet-expressions do what they do, and some plausible alternatives. You can also download some other implementation code.

I've set up a SourceForge project named "readable" to discuss options in making s-expressions more readable, and to distribute open source software to implement them (unimplemented ideas don't go far!). I will probably need to work on other things for a while, but since I had this idea, I thought it'd be a good idea to write the idea and a quick sample demo of it, so that others could build on top of it. There hasn't a single place for people to discuss how to make s-expressions more readable.. so now there is one. There are a lot of smart people out there; giving like-minded parties a place to discuss them is likely to produce something good. If you're interested in this topic, please visit/join!

path: /misc | Current Weblog | permanent link to this entry

Tue, 13 Jun 2006

How to read the mysterious Winmail.dat / Part 1.2 files (TNEF)

All too often nowadays people report that they "can't open the attachment" of an email, because they only received a file named (typically) "Part 1.2" or "Winmail.dat".

The basic problem is that in certain cases Microsoft Outlook uses a nonstandard extra packaging mechanism called "ms-tnef" or "tnef" when it sends email - typically when it sends attachments. What Outlook is supposed to do is simply use the industry standards (such as MIME and HTML) directly for attachments, but Outlook fails to do so and adds this other nonsense instead. The full name of the format is "Transport Neutral Encapsulation Format", but that is a misleading name... it may be neutral on transport, but it obstructs reception.

Almost no other email reader can read this nonstandard format. Email clients that can't (currently) read this format include Lotus Notes, Thunderbird / Netscape Mail, and Eudora. In fact, I've been told that even Microsoft's own Outlook Express can't read this format!

So take a look at my new article, Microsoft Outlook MS-TNEF handling (aka Winmail.dat or "Part 1.2" problem of unopenable email attachments). It gives you a brief explanation of the problem, and what to do about it, both from the sender view (how can I stop sending unopenable email?) and the receiver view (how can I read them anyway?).

path: /misc | Current Weblog | permanent link to this entry

Mon, 05 Jun 2006

Sony Playstation 3: Train wreck in process

I try to keep up with the general gaming business. Many of the best new computer hardware technologies first show up in the gaming world, for one thing. And for another, I once in the business; in the mid-1980s I was lead software developer/maintainer for the first commercial multiplayer role-playing game in the U.S., Scepter of Goth. (Full disclosure: I didn't write the original, I maintained it after it had been initially developed. Scepter may have been the first commercial multiplayer RPG in the world, but I have never gotten good-enough data to show conclusively if MUD or Scepter were first. Bartle's MUD was clearly first in the UK, and Scepter was clearly the first in the US, and neither knew of the other for a long time.) I also wrote some videogames for the Apple ][, which I sold. (I still play occasionally, but my hand/eye coordination is awful; my brother had to playtest them, since I couldn't get far in my own games.) I generally hope for good competition, since that is what keeps the the innovation flowing and the prices down. My hopes are getting dashed, because Sony seems to have had a full lobotomy recently.

If Sony is trying to go (mostly) out of business, it's got a great process going. Recently about half of Sony's income has depended on the Playstation 2, so you'd think that they would avoid bone-headed decisions that would doom them in the market as they release their next-generation console.

But the Sony Playstation 3 will come with an outrageous pricetag: starting at $599 (or $499 for a stripped-down version). Home video-game consoles have sold for $199 to $299 traditionally, and the X-Box 360 (its primary competitor) costs much less than this announced price too.

Why so much? One significant reason is because Sony is including a Blu-ray reader, a proprietary video format that they hope will replace DVDs; this is both raising the price substantially and appears to be delaying shipment. Didn't Sony learn its lesson from Betamax, their earlier costly blunder in the videotape format war? No, it appears that Sony must go out of business to learn. Betamax was supposed to be better technically (and it was in some ways), but it cost much more. In part, the higher cost was due to the lack of competing suppliers; the competing VHS market was full of competing suppliers who quickly marched past the proprietary format. Sony has even lost big money on other proprietary formats, too. Blu-Ray has all the same earmarks of a failure, in exactly the same way. The Playstation 3 will have a hopelessly high price tag because of Blu-ray, and it looks like the Playstation 3 will go down with it. Since both Blu-Ray and its competitor HD-DVD have really more egregious digital restrictions management (DRM) mechanisms built in, I hope both fail - their improvements frankly don't justify abandoning DVDs in my eyes.

Ah, but the higher price tag implies better performance, right? Wrong. The Inquirer reports that there are some serious technical flaws in the Playstation 3, The Playstation 3 will have half the triangle setup capability compared to Xbox 360. What's worse, its local cell memory read speed is about 1/1000th of the speed it should be getting. In fact, one slide describing the Playstation 3 performance had to say "no that isn't a typo", because the performance figures on this fundamental subsystem are so horrifically bad. So people will have the option of spending a lot more money for a less capable machine that is saddled with yet another failed proprietary format. And in addition, Sony is already really late with its next-gen console; if you're not first, you need to be better or cheaper, not obviously worse and more expensive. Yes, it'll run Linux, but I can run Linux very well on a general-purpose computer system, for less money and without the hampering I expect from Sony.

Has greed disabled Sony's ability to think clearly? The Sony-BMG DRM music CD scandal, where Sony subverted a massive number of computers through a rootkit on its music CDs, just led to a big settlement. Granted, it could have been worse for Sony; under the laws of most countries, many Sony executives should probably be in jail. In the Sony-BMG case, Sony tried to force a digital restrictions management (DRM) system on users by breaking into their customers' operating systems. The point of DRM systems is to prevent you from using copyrighted products in ways the company doesn't approve of -- even if they are legal (!). Hrmpf. The All Party Parliamentary Internet Group (APIG) in the UK recommended the publication of "guidance to make it clear that companies distributing Technical Protection Measures systems in the UK would, if they have features such as those in Sony-BMG’s MediaMax and XCP systems, run a significant risk of being prosecuted for criminal actions." It's fine to want money, but it's wise to make money by making a good product -- one that is cheaper or better in some way. "Get rich quick" schemes, like rootkitting your customers to keep them from doing stuff you don't like, or trying to establish proprietary format locks so everyone has to go to you, often backfire.

What's weird is that this was all unnecessary; it would have been relatively easy for Sony to create a platform with modern electronics that had much better performance, worth paying for, without all this. It would have been much less risk to Sony if they'd taken a simpler route. What's more, their market share is so large that it was theirs to keep; they just had to be smart about making a good follow-on product.

Maybe Sony will pull things through in spite of its problems. I hope they don't just collapse, because competition is a critical force in keeping innovation going and prices low. Their product's ability to play Playstation 2 games, for example, is an advantage... but I doubt that will be enough, because the old games won't exploit any of the advantages of a next-generation platform. If Sony can get a massive number of amazingly-good platform-unique games -- ones so good that people will choose the Playstation 3 specifically for them -- then maybe they can survive. But I doubt they can get that strong a corner on good games; many independents will not want to risk their companies by making single-platform games, especially one as risky as this one, and Sony is unlikely to have the finances to buy them all up or back them enough to eliminate the risks. What is more likely to happen is that there will be a few platform-unique games for Playstation 3, a few platform-unique games for its competitors (particularly XBox 360), and a few multiple-platform games... which means no lock for Sony. In short, things do not look very good right now for Sony; Sony seems to have hoisted themselves on their own petard. I don't even see what they can do now to recover.

I think Jonathan V. Last of the Philadelphia Inquirer has it right: "Obsessed with owning proprietary formats, Sony keeps picking fights. [And] It keeps losing. And yet it keeps coming back for more, convinced that all it needs to do is push a bigger stack of chips to the center of the table. If Blu-ray fails, it will be the biggest home-electronics failure since Betamax. If it drags PlayStation 3 down with it, it will be one of the biggest corporate blunders of our time."

path: /misc | Current Weblog | permanent link to this entry

Sun, 12 Mar 2006

In memorium: William Alson ("Al") Wheeler

Picture of William Alson (Al) Wheeler William Alson ("Al") Wheeler (2 March 1916 – 28 February 2006) was my grandfather and a wonderful, godly man. He recently went to be with the Lord, and I will miss him very much until my time comes. Many of my own traits (love of music, math, science fiction, science, and learning in general) are easily traced back to him. He loved jokes and humor; he laughed often, and his eyes often twinkled.

He demonstrated his extraordinary character throughout his life; a few anecdotes will have to suffice. His love of learning was extraordinary; in his 80s he started learning koine Greek, and near the time of his death he was reading the 984-page "Chaos and Fractals: New Frontiers of Science" (a book full of mathematical concepts). He dedicated his life to serving others; he was a music minister for over 45 years. He prayed, and prayed often, for his family and friends. When he last moved to Pennsylvania, he donated his mechanic's tools to the Smithsonian, which had been hunting for the kind of tools he had. And even in death he served others; rather than having his body be buried, he donated his body for medical research. I am honored that I can count myself as one of his grandchildren. He did not leave riches behind; he left behind something much greater.

Below is a short biography of his life, as printed at his memorial service on March 4, 2006. May we all strive to have such a positive biography. "Children's children are a crown to the aged, and parents are the pride of their children." (Proverbs 17:6, (NIV)) (New International Version)

Al was born in the small town of Pottsville, PA. He grew up in Oxford, PA and graduated in 1933 from Oxford High School. He worked a couple years with the Wheeler and Sautelle and then the Wheeler and Almond Circuses. In 1935 he moved to Reading, PA, and entered the Wyomissing Polytechnic Institute to become a machinist. He met his future wife, Mary Clouse, in 1938 at a YWCA sponsored dance. It was during this time that Al taught himself to play tennis and the clarinet. He came from a musical family and had begun singing with the Choral Society in Reading. He began working at the Textile Machineworks in Wyomissing, but found a job in early 1940 with the Federal Government at the Naval Gun Factory in Washington, DC. He married Mary in June 1940. While living in southeast Washington, they had three children: Bill, Ray and Joyce. In 1946, after a few interim jobs, he began working for the Bureau of Standards followed by the Naval Research Laboratory. He moved to the Bureau of Naval Weapons in 1957. He moved his family to Maryland in 1958. In 1962 he made his last career move to the Naval Air Systems Command and retired from there in 1974. Throughout this time he should have received a chauffeur’s license since he performed that duty extensively. Mary went home to be with the Lord in 1996. In 1999 he moved to Perkiomenville, PA to live with his daughter, son-in-law Phil, and grandson Bryan.

After moving to Washington the war initially kept him out of church activities. Mary had started attending Fountain Memorial Baptist Church. After the war, Al started attending also. They professed Christ as Lord and Savior and were baptized together. In 1950, Al started directing the Junior Choir, grades 4 thru 6. In 1953 he became the Music Director at Fountain Memorial and spent the next 45 years directing music in 6 different churches. He loved his music and his collection of choir music, mini orchestral scores, records, reel-to-reel tapes, cassette tapes, and CDs attest to it. His primary instrument was the clarinet, but he had obtained and played saxophone, flute, and trombone and, at one point, two synthesizers.

Although work and family responsibilities cut down on his tennis activities, he never gave them up completely. After retirement he taught tennis part time for the Maryland Department of Recreation and was regularly playing with his friends until moving back to PA in 1999.

He loved science fiction and one of his favorite pastimes was solving the “Word Power” article in the Reader’s Digest. He rarely missed those words.

Al had a wonderful life and was adored by all his family. He is survived by three children, five grandchildren, and 7 great-grandchildren.

path: /misc | Current Weblog | permanent link to this entry

Wed, 30 Nov 2005

How to revive an old laptop

A relative gave me an old laptop with Windows 98, Which led me to the question: can you take a castoff laptop and, with zero or very little money, improve it so it's more useful and can run more "modern" software? The answer is: yes! In fact, this turned into a little game/project for me, and I learned a few things along the way. So I wrote down what I decided to do, in the hopes that you may find these ideas useful for reviving an old laptop yourself:

How to revive an old laptop

I think it's a shame that older machines sometimes rot in closets instead of helping people, and I hope that this document will help change that. With a little elbow grease (and adjusted expectations), you can still get mileage out of an older laptop.

I talk about getting new hardware (keep it cheap!), buying a wireless card, making backups and moving windows to a new disk, installing GNU/Linux, updating a Windows 98 System, and making a boot floppy for windows.

path: /misc | Current Weblog | permanent link to this entry

Fri, 25 Nov 2005

OpenDocument Accessibility

There has been a lot of virtual ink spent on OpenDocument accessibility. I've written up a short essay on OpenDocument accessibility, where I point to some other resources that talk about OpenDocument accessibility, and point out that there are lots of ways to get it. For a vast number of cases, products that natively support OpenDocument do just fine today. For some cases, just use Microsoft Office with an OpenDocument plug-in; you already have to use a third party plug-in to add accessibility in those cases, so saying that you can't add a third-party plug-in for OpenDocument as well is simply hypocritical.

I also post a lengthy letter from Wesley Parish, who is disabled and yet is a strong supporter of OpenDocument. The article has more, but here are a few quotes: "It is necessary for the disabled to have access to all government information relevant to them, in a file format that is readily available for as many different applications from as wish it, one that does not insist that one jump through licensing hoops in order to implement it, one that can be readily extended in the future according to need - and one that can not be used as an excuse by lazy bureaucrats to deny me my rights! The question currently buzzing in Massachussetts is , "Does Open Document Format limit accessibility?" For myself, I find it does not. [In Computer Science] I found one of the most persistent concepts was a strict separation between data and executable code. ODF provides that strict separation, defining data separately from the code. ... An open specification that allows ANYONE to implement accessibility solutions is the way to solve the problems of access by the the blind and other disabled. Otherwise, government data will be tied to specific programs and NOT accessible to all, and in time, NOT accessible at all."

So go take a peek at my short essay on OpenDocument accessibility.

path: /misc | Current Weblog | permanent link to this entry