CISL 2010 Buenos Aires
Andrés Osinski
The upcoming CISL (Conferencia Internacional de Software Libre) is coming this September 7, in the Biblioteca Nacional de Buenos Aires. It will be including great panelists from all over the world and discussing an array of topics ranging from FOSS development to FOSS technologies, to Free Culture. Don't miss it.
Frameworks and Platforms Presentation Slides
Andrés Osinski
Just as I promised to the attendants of the last TechBaries conference, here are the slides on my presentation on choosing languages and frameworks for developing software.
English version is here.
Original version in Spanish is here.
This presentation is meant as just a series of notes on the subject, so don't expect the juiciest parts to appear here. Nontheless, they provide an adequate overview of the subjects that were touched on.
0 comments View moreSome Thoughts on Silverlight
Andrés Osinski
Some time I ago I began a project for a customer in an all-Microsoft shop. Given that the project had highly restrictive time requirements and a RIA design, a decision was taken to develop the project with Silverlight.
I have always expressed openly my preference for Free Software solutions above proprietary ones, and this preference still stands, however, throughout this article I'll judge the platform on technical merits alone, given that there's already many enlightened voices out there to warn us about the perils of working on proprietary platforms.
My initial impression came when installing the necessary development environment. Previous to this project I'd worked on several projects using Visual Studio 2008, by all means a very nice and capable IDE that ran well enough on a current, midrange machine.
But Visual Studio 2010 changed, and for the worse. I can't speak for the addition of new features, but there's one, single factor that makes it stand out from previous versions: it is slow. And I mean slow like a Java-IDE-from-5-years-ago slow. Half a minute to load up, 15 seconds to connect to a Team Foundation Server (don't ask, it's what the customer has). Start piling up a few open Silverlight windows and we're talking a couple of seconds between switching windows, and at least a 10-second build time for a medium-sized application. I understand that things are a lot better when working with WinForms apps, but for a new platform that's supposed to be highly productive for getting things up and running, this is unacceptably slow. The astoundingly good autocompletion features do not make up for this.
Let's go back to that last comment for a bit. If there's something which I think Visual Studio has above any other environment is the combination of the incredible autocompletion coupled with a very good language like C#. It competes very well in its niche as an application development language against similar alternatives. The problem, however, lies for the most part in the underlying applications framework used for the project; Silverlight itself. Yes, Siverlight is in many ways just a subset of the standard .NET library, which is not bad at all. The issues here have mostly to do with the presentation layer.
XAML, Or A Failure In Declarative Programming
Many will probably disagree with me on this, but XAML is a piece of garbage. It is touted as a declarative DSL with support for some level of logic, where it's theoretically possible to write CRUD interfaces without touching a line of code. This, in practice, is about as feasable as writing a GUI in SQL.
- There are no good mechanisms for separating content from style. Yes, there's the Style attribute, but it's a poor excuse for a well-executed styling system. Even CSS, warts and all, is better for this.
- It is complex. Very complex, to the point where there's a strict dependency on the IDE to get anything done. The number of elements and attributes, the slight irregularity on the naming schemes of different attributes, the verbosity of each element, all pile up to make even the slightest of edits require opening up the IDE.
- You can't depend completely on either the GUI designer nor text editing. Due to the above factors it become prohibitively difficult to write an interface without the designer (we're talking literally thousands of lines of XAML code for rather simple stuff), yet it's very limited when it comes to describing fluid layouts properly. And it's slow. So slow.
- The C# compiler is a marvelously effective and productive tool. Not so the one for XAML. Parsing XAML is sluggish, autocompletion is mediocre to downright bad, a surprisingly large number of errors are caught at runtime (difference with HTML being that in order to debug a Silverlight application you need at least 20 seconds to start up a debugging instance, and no runtime changes are allowed), and interaction with your C# namespaces is painfully difficult and bureaucratic.
- In classic Microsoft tradition, the GUI toolkit contains items that just have no purpose being described on the interface. Specifically, Data Sources, a sort of dynamic connector to a database query that magically handles saving and updating data. I have a whole section dedicated to that, but let's just say it's not a good practice.
The worst offender of these is Microsoft selling XAML as an easy, expressive method for defining a UI without writing "real code". The reality is that not only does writing a new screen require copious amounts of C#, but that the standard controls are inadequate, to the point where they're the greatest factor in contributing to delays in my project.
The issue falls squarely in the fact that behavior for many actions is ill-defined and buggy. How does a SelectionChanged even know when it's being triggered by the user instead of by the loading of data? Why don't click events work properly on custom controls? Why do I have to explicitly unload and reload certain resources to register when they should work properly just by changing them once? Such distractions have cost me days, and apparently few people have straight answers for many of these problems (the standard response for the majority of these shortcomings is writing custom controls and intermediary Converter classes for things that would take two lines in jQuery).
The DataSource and DataGrid: Convention Over Configuration, Failed
A big culprit of delayed projects is when things that are at first glance very simple are actually overly complicated. By and large, this is the main issue with using these very standardized components.
Most CRUD applications can be written as a grid with data feeding off a set of entities, a few rows and columns, and a couple of buttons to manipulate things. For this workflow, you use a DataGrid that takes its data from a DataSource, binding it to a query, filtering by whatever criterion you want, and the control automatically handles the rest for you.
This should actually be a great boost to productivity, since you can take the hassle off saving and retrieving data and presenting it. And for the most part, it actually works very well: define your entities, create a providing Web Service, and you're good to go. For 70% of the use cases this works marvelously well. Unfortunately, it's disastrous for the remaining 30%.
So what problems does this entail?
- The Grid interface is slow. Clicks don't register properly when doing asynchronous operations in the background (and everything in Silverlight is asynchronous, to the point where forcing synced operations to enforce certain dependencies on interaction is very difficult), animations stutter, loading and reloading data is awkward when compared to equally featured HTML or (gasp) VB6 applications. The result is diminished user interaction.
- Working within the Grid is annoying and difficult. There is no easy way to reference elements and controls within a grid (it's possible, but it'll take you 5 times longer than necessary and will be fraught with bugs). Binding of controls within the grid is buggy and your standard events don't cover the range of interactions you need. Many times things just don't work as expected and you need to spend hours coming up with a workaround, which can end up in adopting a different UI solution because your original idea is simply infeasable (something that's never happened to me before).
- The API is inflexible. It is difficult to customize a grid to override default behavior. Anything that's slightly complex requires yet more boilerplate code, and we're not talking about the sort of API that fits in your head, so expect to be looking over Stack Overflow and the Silverlight Forums very frequently for answers to simple questions (and not finding the answers to what you need way too often).
- Silverlight's UI theming has nothing to do with the clients OS, unable to look like true desktop clients, yet harder to style than web applications.
All of this comes down to the fact that getting the DataGrid and Datasource to do what you want it do is nowhere as simple as it should be.
Not a Polyglot
Part of the promise of .NET 4.0 was that the ecosystem would be getting more and more open to dynamic languages and newcomers like F#. This seems evident in the new documentation for the framework. The unfortunate reality is that, like I've said before, since languages are community and culture, it's very difficult to get a team up and running with a Silverlight project (which is already alien to most .NET developers) with IronPython or IronRuby. Almost no documentation is available, and nothing to speak of as far as code samples. Coupled with the fact that there is not much effort from the Microsoft evangelist to actually convert people away from C#, and we have an idea that's failed from the start.
This is truly a pity since Silverlight would be an excellent match for dynamic languages, given the tremendous amount of casting and anonymous functions that are necessary for manipulating so many data structures, and which currently presents my only objection to using C# in this context. The dynamism of the framework means that many errors will still not be caught by the compiler, and verbose blocks of code are needed where a simple Python one-liner would suffice.
Opinions Bottom-up
It's interesting to note that despite my comments and what I consider to be some pretty egregious faults in Silverlight, you'll find people practically lining up to praise this framework. And to be honest, it's not the worst thing as far a RIA apps go by a long shot (I'm pretty certain it's much better than Eclipse RIA, and possibly comparable to Flex).
While it fares favorably against many technologies, it just doesn't hold its own against modern web technologies like Django, Rails, and similarly inspired web frameworks. There's more boilerplate, less flexibility, and many of the advantages of a RIA platform are lost against the sort of dynamic web applications that jQuery with extensiones can help you create. It's better than ASP.NET, probably, but I don't believe it's good enough when we lose so many things in the process, such as
- Depending on a proprietary platform running on a single operating system. Silverlight for Mac OS and Mono just don't count. Trust me on that. It's very easy to write platform-dependent code on Silverlight.
- Spending thousands of dollars on your development platform, which will be outdated in a couple of years and requires a substantial investment in a vertically-integrated set of solutions that don't work well with anything else.
- Limiting the amount of community support. For a platform that counts with commercial support, the amount of extensions, tutorials, and tips just pales in comparison to the level of documentation and support you can get with jQuery, Django, or other FOSS solutions. IRC is still the best support line available for developers.
In conclusion, on purely technical grounds, it is a decent platform, albeit flawed in pretty important ways. If you work with .NET most things will not seem to alien. For everyone else, stay away. And when you factor in the matters of using a privative platform for in the days of the Open Web, everyone should probably disregard this platform, instead favoring web clients when possible and native clients when necessary.
2 comments View more
If Adobe wants to fight, it should leverage FOSS
Andrés Osinski
As we have seen in the blogosphere, devs are up in arms about Apple's attempt to close down their mobile ecosystem even further. Suffice to say people are not glad about the fact that their choices for programming in one of their favorite platforms have been reduced substantially.
This does not come as a surprise for myself or anyone with a little bit of common sense on the Free Software camp: you live by the sword coding for a proprietary (or, as Spanish-speaking FOSS supporters like to say, privative) platform, you die by the sword. In the choice of submitting to a master, you must accept that the rules are arbitrary and "enlightened self-interest" is merely a way to say most of the times you'll come out fine, and accept the lack of control a another risk to take into account (or not, considering how many people were not capable of seeing a lockdown of this magnitude).
But let's get away from the rhetoric for a minute and concentrate on the emerging warfare between Adobe and Apple. Evidently the Adobe folks were taken off-guard by these events as well. Now, Adobe-Apple animosity has existed for as long as Photoshop's been running on Apple computers; Adobe has consistently been late to adopt platform guidelines, has suffered blowback from a subpar Flash implementation, and receives constant criticism for its CS flagship applications crashing during the middle of work sessions.
Despite that, the interested parties have all much to lose from altering the status quo: Adobe moves a massive amount of Photoshop licenses on Mac, Apple gets a substantial market share of designers and application developers from having Adobe products as first-class citizens, everyone in the Mac camp from consumers to pros to developers is happy (except for the occasional Flash crash). If the Adobe experience were to worsen on Macs, several things might happen:
- Large design and graphic houses whose lifeblood depends on Adobe CS products would migrate to Windows, living with whatever gripes and lack of expertise they might have on the platform in favor of staying on the move.
- Independent Mac devs (and possibly Apple itself) would fill up the niche and take opportunity of Adobe's weakness to develop first-class alternatives. A barely "good enough" product would not move the large players away from their software dependencies, but it could shake up freelancers and independents, having a sufficient market share to eventually face Adobe head-on. Anyone who can stay on the market for 2-3 years to live a software upgrade cycle can afford to compete.
Adobe, however, as a software vendor with a cross-platform product, need not actually have to back down from the Mac platform to cause substantial damage to Apple; it need only port its existing solution to an operating system that has clear advantages of its own and provide legitimate competition. That OS, right now, is Linux.
Let's take the facts at hand:
- There's been a gradual push in the last two years for Linux vendors to create ties with proprietary software devs to improve the user experience, doing things such as giving a uniform UI experience and stable, predictable API release cycles. Yes, an important number of FOSS advocates want nothing to do with this, but as Linux market share increases and it becomes a more mainstream product (surprisingly so, when looking at the market share in many countries, corporations and governments), a substantial number of users want the software they need to work. And as long as these improvements don't worsen current FOSS options, no one's in a position to complain.
- Linux already sees much use in large FX houses, both in the back end and the front end. Most 3D rendering packages already have Linux ports of very high quality, and a number of companies and users are not afraid of embracing a new product if it offers clear, visible advantages as far as cost and vendor lock-in go. Since most places already have specific Windows and OSX machines just for Photoshop work, moving over this part of the workflow to where the rest of things happen would not be a difficult choice, and would help to homogenize software configurations.
- Platform mindshare for Linux is already there. The knowledge for porting large projects from UNIX to Linux and from Windows to Linux exists, and commercial Linux vendors such as Red Hat, Canonical and Novell would be more than happy to provide assistance if it means exponential growth and a new market opportunity in light of most UNIX installs having already converted to Linux where necessary.
- Believe me: Apple is scared to death of Linux. It is the antithesis of their revenue model and lock-in strategies, and while they have very good ways to make the public aware of Linux's liabilities, they have nothing to counter the obvious weaknesses of a closed, proprietary model in both mobile and desktop offerings (Mark Pilgrim has a very good writeup on the reasons for switching to a Free platform). Apple's marketing is oriented towards shooting down Microsoft's software, but the fact that Linux is not even mentioned on their keynotes, even on graphs where it is highly relevant, shows they have no intention of making the average consumer aware of a third alternative.
Would this be ideal? Not really. I'd be the first to say Adobe would have a huge task at hand that might not even work out correctly:
- Adobe already has a massive number of employees working to maintain two ports of their software; adding a third would imply more than a 50% increase in workload (a port from scratch would need a lot of research ) to make the Linux experience an equal with current offerings. The codebase is old and very likely littered with little things that might not have even contemplated anything not Win32 or Carbon (see the troubles Adobe has with the Cocoa API).
- Nobody can say for sure whether Adobe is actually affected enough to warrant and effort of this level.
- A port would likely take years, during which Apple would obviously realize what's coming and find ways of its own to remediate the situation, and I trust they would have an adequate alternative with such motivation.
- Free Software developers love creating alternatives to proprietary solutions; you can be sure GIMP development would double in speed, and a dozen projects would spring to life trying to offer new choices. Most would fail, but a couple of success stories would be sufficient to hinder the initiative.
How to Rant your Way Into the Front Page
Andrés Osinski
- Get an amazingly idiotic, extreme, or unthought opinion on a hot topic. Make sure it's something that will merit a knee-jerk reaction from at least 50% of your readers. Better if by some weird twist of interpretation your opinion can be bent into something that might look somewhat reasonable if you squint really hard.
- Inflame your readers by insulting people, movements, companies, and anything popular yet slightly flawed. Cussing, putdowns, and destructive criticism that tears down ideas but provides no alternatives is the preferred method here.
- Put a headline that continues the flamefest, such as "You Suck at X", "Why X will never be like Y", "Why I'm never going back to Z", "Should you even consider A?" (implying that only a mouthbreathing retard would ever consider A).
- Replace all <p> tags in your article for <li> (list items). People like lists. If they have 10 items, better. Don't bother adding more content; they won't be reading it anyway.
- Don't research information. Factually correct articles are boring and a waste of time when you could be ranting and racking up more page views.
- Don't spell-check. Clarity makes it easier for people to see just how shallow your rants are; it's better to leave the benefit of a doubt for as long as it takes for the reader to upvote your link on a social network.
- Steal content. Got a reply for a page? Save yourself the hard work of thinking up stuff and just paste that fucker in the middle of your article and reply to large, well-researched paragraphs with one-liners. Quote sections twice for emphasis (people can't get enough emphasis, so use caps and bold text liberally). Just keep the informative, boring parts to a minimum to allow more room for ranting.
- Dichotomize in absolutes. Everything falls into two, at most three, distinct categories. No shades of grey, no alternatives. If X is good, non-X is bad. People always fall into 3 types. If you have to make compromises in logic to awkwardly fit something into your categories, do so, just don't allow room for alternatives; fixing logical inconsistencies just makes you look like a flip-flopper, and probably a Communist too.
On a similar note, nothing you write should be boring or debatable, it's either Things That Are Awesome or Things That Sucks And Should Burn in Hell. - Pictures are awesome and you need more of those. If you're writing an article on PHP ORMs and have no idea of what to put in, just add an image of something Cool and Hip, like sushi, Pedobear, the Starbucks logo, or concept cars. Apparently Pedobear's more glamorous than being a coder.
On a more serious note, these last three weeks many an Internet reader has lost countless hours of his time reading opinion pieces on NoSQL and a few other tech fads. Thankfully we still have a few bastions of great writing (or at least a judicious choice of links), but the signal-to-noise ratio has hit a low point these last few weeks, and will probably bottom out with the release of the iPad.
0 comments View moreOn Proving Stuff, Part 1
Andrés Osinski
(Huge thanks to Walter Vulej and Iván Raskovsky)
The topic of program verification and software proofs is tangentially related to program optimization: if you can prove assumptions on your code and discard certain special cases, you can significantly speed up your program by eliminating type checks, intermediate steps and dead code. In order to do this, compilers have a range of very complex, very interesting code analysis techniques that attempt to prove facts about code. Today I want to look at a largely theoretical, but mindblowingly awesome verification method: structural induction.
Induction
Induction is a general technique for devising mathematical proofs, which consists of these steps:
How does this work then?
We know that there's a "first" element in the set (because it's well ordered) and that P applies for it.
Now, if we can show that if P is valid for an element then it's valid for the next element, we can apply this property to show that P is valid for the second element. Since we know it's valid for the second, we then know it also works for the 2nd +1th element, the 3rd + 1th, and so on and so forth.
Structural Induction
This is fine and dandy for natural numbers, but what does this, exactly, have to do with code and variables and such things? And how do can we extend this knowledge to complex data structures?
Long before the concept of object-oriented programming was devised, the theoretical construct of Abstract Data Types (ADTs) already existed. Abstract data types are basically a set of generators and applicable operations, and a simple logical language strong enough to evaluate truth statements, conditionals, and recursion. A generator is an entity that represents a minimal unit that makes an ADT (you could somewhat think of them as constructors). Generators can be recursively applied, taking other generators as parameters, to produce arbitrary data structures(sounds familiar?).
Using ADTs we have a system sufficiently descriptive to create a notion of natural numbers. Here's an example:
| ADT Nat | ||
| Generators | ||
| 0 | : | ⇒ Nat |
| suc | :Nat | ⇒ Nat |
| Observers | ||
| * =0? | :Nat | ⇒ bool |
| prev | :Nat | ⇒ Nat |
| Observational Equality | ||
| ∀ n,m: Nat | n ≡obs m iff ((n=0? =obs m=0?) ^ ((n != 0) ⇒ prev(n) =obs prev(m))) | |
| Operations | ||
| * + * | : Nat x Nat | ⇒ Nat |
| * - * | : Nat x Nat | ⇒ Nat |
| Axioms (∀ n,m: Nat) | ||
| 0 =0? | = | true |
| suc(n) =0? | = | false |
| prev(suc(n)) | = | n |
| n + m | = | if m ≡ 0 then n else suc( n + prev(m)) fi |
| n - m | = | if m ≡ 0 then n else prev(n) - prev(m) fi |
Let's go piece by piece:
- We define an Abstract Data Type called Nat
- We define two "generators". All other Nats will be defined through these. The first one is zero, our first number. The second generator is the "successor to a number", and takes a Nat as a parameter. That is, 1 is the successor to 0, 2 is suc(suc(0)), 3 is suc(suc(suc(0))), and so on. As you can see, we don't use numerals to represent these values, and we don't need to, beyond using them as a convenience. We recursively build up on these two generators to make any possible natural number.
- We define observers. Observers are a mechanism to "look" at our constructed ADT. The idea is that we don't want to look directly at the constructors, since we may have structures where a different set of generators or a different order of application might not be of our interest. Observers let us analyze ADTs without regard for their internals, just concentrating on what makes one instance of an ADT different from another (formally, observers are the minimal set of operations we need to be able to distinguish among them. Think of a set as an example: it doesn't matter in which order you add elements to a set, yet you can make different permutations of constructors and they should still be externally identical).
- We define something called "Observational Equality": the conditions under which we can say that two instances of an ADT are equal. The particular statement above says that n is observationally equal to m when (n ≡ 0) ≡ (m ≡ 0) (that is, they're both either zero or nonzero) and if n is not zero then the previous number to n is observationally equal to the previous number to m, creating a nice, recursive definiton.
- We define two operations for Nats: addition and substraction, both of which take two Nats and return and Nat.
We also declare a set of axioms that must hold valid for any instance of Nat:
- If n is made up by the generator 0, it is observationally 0. If it's anything else, it's not zero. This might seem fairly evident at first glance, but like I said, a data type with potentially different generators might be equal observationally.
- The previous number to a successor of n is n. Again, looks like common sense, but we need this operation to backtrack and "consume" the generators of an ADT. Note that we don't have a definition for prev when our number is zero.
- Adding n and m is returning n if m is 0, otherwise it's the successor to recursively adding m and prev(m).
- Subtracting m from n is returning n if m is 0, otherwise it's subtracting prev(m) from prev(n)
Through these axioms we have a consistent, logically coherent definition of data which behaves much like the Integers we use day to day.
Now we'll look at a more interesting ADT, a real data structure: binary trees
| ADT Tree | ||
| Generators | ||
| nil | : | ⇒ bt(a) |
| bt | :bt(a) x a x bt(a) | ⇒ bt(a) |
| Basic Observers | ||
| nil? | :bt(a) | ⇒ bool |
| root | :bt(a) | ⇒ a |
| left | :bt(a) | ⇒ bt(a) |
| right | :bt(a) | ⇒ bt(a) |
| Other operations | ||
| height | :bt(a) | ⇒ Nat |
| size | :bt(a) | ⇒ Nat |
| complete | :bt(a) | ⇒ bool |
| Axioms | ||
| nil?(nil) | = | true |
| nil?(bin(l x a x r)) | = | false |
| root(bin(l x a x r)) | = | a |
| left(bin(l x a x r)) | = | l |
| right(bin(l x a x r)) | = | r |
| size(a) | = | if nil?(a) then 0 |
| else max(height(left(a)),height(right(a))) | ||
| complete(a) | = | if nil?(a) then true |
| elseif nil?(left(a)) ^ !nil(right(a)) then false | ||
| elseif !nil?(left(a)) ^ nil(right(a)) then false | ||
| else (size(left(a)) ≡ size(right(a))) ^ | ||
| complete(left(a)) ^ complete(right(a)) | ||
| height(a) | = | if nil?(a) then 0 |
| else 1 + max(height(left(a)),height(right(a))) | ||
Observational equality omitted; rest assured it's sufficiently clear when two trees are the same.
We'll clarify the above once more:
- A tree is either nil, or it's a node containing a value of a generic type (a) and two trees.
- We define observers through which the other operations will have access to the tree's content.
- The size of a tree is the number of nodes it contains: 0 if it's nil, 1 + the size of the contained trees if not.
- A tree is complete if it's nil, a leaf, or both subtrees are the same size and complete. This is the same as saying that all leaves are found at the same height.
- The height of a non-nil tree is 1 + the maximum height of the contained nodes, 0 otherwise.
Let's use what he have learned to try and prove a pretty basic property on complete trees:
P: (∀ t:bt) complete(t) ⇒ (size(t) ≡ 2height(t) - 1)
"For all trees, if a tree is complete, then its size is 2 to the 'height(tree)'th power minus 1". This makes sense, intuitively: a leaf is size 1, a complete 2-level tree's size 3, a 3-level tree is size 7, etc. Proving it formally is a different matter. Let's start with the base case: the nil tree.
P(nil) ⇔ complete(nil) ⇒ size(nil) ≡ 2height(t) - 1
Given that a nil tree has a height 0 and size 0, and 20 is 1, P holds for nil.
Now, what about the inductive step? It's easy to construct an inductive step when you only have to deal with natural numbers. With generators that can be composed in multiples ways, it gets tricky, but possible. What is the natural progression to a nil binary tree? The bt generator, which takes two more generators and a generic element as arguments. Thus we would need to take all the possible combinations of these generators, which are:
bt(nil x a x nil)
bt(bt x a x nil)
bt(nil x a x bt)
bt(bt x a x bt)
Thankfully, only in the last case can we have a complete tree, so we only test that. Formally, for the first three cases, complete() is false, so the statement evaluates to true.
We now compose our inductive step, saying: "if the fact that P holds for a tree t implies that it holds for a tree that contains subtrees like t for which P also applies, then P applies for all trees":
(complete(t) ⇒ size(t) ≡ 2height(t) - 1) ⇒ (complete (bt(t x a x t)) ⇒ size(bt(t x a x t)) ≡ 2height(bt(t x a x t)) - 1)
The above would be similar to P(n) ⇒ P(n+1). For the sake of simplicity, we'll omit the inductive hypothesis from each step.
First, if complete() is not true, then P is valid; no need to elaborate further.
Let's assume complete() is true. We then need to establish the validity of
size(bt(l x a x r)) ≡ 2height(bt(l x a x r)) - 1
We label the left and right trees l and r, so that we can distinguish them as different, even if we assume P applies to both. We also expand the size() and height() axioms based on what we wrote when declaring the ADT (and we cheat by not using observers to get the left and right members to make it easier to understand).
1 + size(l) + size(r) ≡ 2(1 + max(height(l),height(r))) - 1
Lookee here, we have a lonely 1 acting as exponent on the right, which we can turn into a 2 multiplying the rest of the statement (check the math: 2(n+1) ≡ 2 * 2n):
1 + size(l) + size(r) ≡ 2 * 2( max(height(l),height(r))) - 1
Remember that we assume P to be true for this step? This means we can convert the size(l) and size(r) statements into (2^height(l)-1) and (2^height(r)-1), respectively:
1 + 2height(l) - 1 + 2height(r) -1 ≡ 2 * 2max(height(l),height(r))) - 1
We take add those loose 1s on the left:
2height(l) + 2height(r) -1 ≡ 2 * 2(max(height(l),height(r))) - 1
Since we know that size(l) ≡ size(r) (because of the complete() axiom) and both subtrees are complete, we know through our inductive hypothesis that both have equal height. Thus we replace height(r) for height(l), and evaluate max() to height(l):
2height(l) + 2height(l) -1 ≡ 2 * 2height(l) - 1
2 * 2height(l) - 1 ≡ 2 * 2height(l) -1
We've now established the statements on the left and right to be equal, thus showing that P is valid for all trees!
Ideas for using structural induction for program verification have been published at least as far back as the 60s, and we keep seeing a variety of papers on how to apply this concept to prove the validity of certain compilers. While it hasn't seen widespread use as an applied tool for general-purpose compilers, it has applications in automated theorem proving. Above all, it's a simple, effective way to reason about the validity of programs; it's personally helped me develop a "feel" of when I've made an erroneous, implicit assumption about data structures.
Will you be using this every day, fighting against ORMs, exceptions, and HTTP requests? I doubt it. Will understanding this concept help you when working with sensitive sections of code, coding data structures, and working with complicated algorithms? Absolutely. Understanding this proof mechanism helps us think about the underlying properties of code. More importantly, it shows us that code doesn't need to be thought of exclusively as a set of binary data that runs on silicon, but as its very own little, logical universe, with its own working rules, theorems, properties, and mechanisms that work even when taken out of the context of electronic machines.
Let that think sink in for a minute.
Stay tuned for Part 2.
6 comments View moreProgramming Languages DO Have Speed
Andrés Osinski
(A reply to this post)
Your favorite language has a lot of differentiating characteristics that separate it from its different alternatives. We might say, naively, that if you consider a language to be just:
- Syntax
- Grammar
- Evaluation rules
- A standard library
Syntax and grammar limit or expand your level of abstraction
How does your language copy and array? Does your language say:
- "perform this array copy operation using SSE3 XMM registers on memory-aligned data",
- "for each element: copy into destination", or
- "copy raw data as fast as possible on this machine"?
Alas, if your language supports objects as memory references and the elements in question are such, that's not working right, because you're just doing a shallow copy, not actually moving all that data on memory. Do you have the semantics to support this detail? Should you actually need to support it?
Extremely high-level languages have the advantage that they can leave optimization to the compiler/interpreter/JIT of choice to find an optimal optimization strategy, but the overhead of this process and the lack of visualization of lower-level, potentially more optimal choices, means that you're missing out on what may be really, really important shortcuts, and you'll be consuming more RAM and time trying to find what works best.
And that is really not a trivial thing to say, yet most languages do not have support for annotating data in ways that may aid compilers, and for some extremely dynamic languages some static inferences of data are simply not possible. At the same time, some optimizations can only be performed during runtime, and it's unlikely that hand-coded lower-level code can be as optimal (witness some edge cases in JVM benchmarks, or the performance increase that Fortran arrays have over C arrays by avoiding pure pointer arithmetic). This leads to a second point...
Languages can specify implementation details
When a language sets in stone some of its capabilities, it's inherently describing some level of implementation details that all legal interpreters/VMs/compilers have to abide to. Capabilities that can have important effects on performance. If a language considers classes as objects, its internals will differ much from languages that use arrays of function pointers. If a language expects every function name to be available at runtime, there will be information that you must have somewhere in memory. If a language defines a calling convention, you must abide by it. A language that supports monkey patching needs a set of internals that's prepared to do so, even when it can be statically compiled. A lot of features simply incur a minimum level of overhead, whether they're used or not. Note the painstaking planning C++ required to make sure every interesting feature could be discarded and not consume resources (and how that makes it significantly less developer-friendly than many alternatives). On the other hand, look at how interpreted languages such as Python simplify the use of external symbols with the simple 'import' statement.
OK, so let's say we want to disregard everything and start over, not caring about the language's interop and minimizing the overhead of run-time capabilities so that they're irrelevant for all intents and purposes. But that takes us to the last point...
Languages Are Communities
Javascript, among others, could probably be turned into a fine systems programming language, yet you don't see people making efforts to bring V8 to do fast bit twiddling and instead turn their attention to the most common Web use cases. C++ could be made into a fine scripting language with sufficient macro magic, but most would scoff at the idea. That's because a language is more than what you get in the "Learning X Programming Language" book. It's an ecosystem of libraries, interop systems, VMs, compilers, coding styles and community. It's a way of doing things.
Who would write Python without considering the Zen of Python? Where would Javascript be without jQuery and mooTools? Why is it that Ruby first had Rails and RSpec and not some other language?
And some of these tools work as well as they do because they're not all fast at all. In fact, they work as well because usability and extensibility took precedence over performance and that design decision ends up paying off so well that the project lives on another day and gets sufficient critical mass to get people thinking about improving it in many ways. But if speed is not a concern, why worry, when it's just one of the many angles to the utility of our tools.
As much as we fantasize about having our favorite language be molded to fit into different performance and use envelopes, each community chooses where to take its language because they use them to get certain things done, while other tasks get different tools. And that's fine, actually, because trying to wedge language concepts and idioms where they don't fit ends up getting tiring, and sooner or later it's going to show and it will require dexterous hackery and many a sleepless night trying to understand just why something works the way it does.
This is another reason why alternative implementations of languages are hardly ever as popular as the standard implementation. The mainline Ruby VM is the most used VM despite it not being the most performant because it's the gold standard, and if code doesn't work adequately with it then it probably has little utility for the community. Mono includes an AOT compiler for C#, yet that just doesn't get used as much as the JIT, even when it might come in handy, because you lose the possibility of linking with other .NET libraries and using a lot of the goodness that comes from a managed environment.
Ultimately, a programming language has a set of rules, tools, communities and legacy that indeed gives it a "speed". Yes, a lot of them can be adapted for more performant tasks with C/C++ interop, and a lot of them can be made to be more useful for certain tasks with macros and some really hard thought put into them. But at the end of the day what matters is the speed you can get out of your tool's actual use, not the theory that a few microbenchmarks might say.
1 comments View more12 Reasons To Be Learning Graph Theory
Andrés Osinski
Courtesy of Matt Britt
Throughout our schooling we always encounter some topics that we feel very strongly about, either because of how fascinating they are or how tediously boring or difficult they may be. Graph Theory is one of those controversial topics CS students will always be opinionated in; you either love it and are fascinated by its utility and applications, or you're appalled by the uselessness of the topic in your career. And let's be honest: when was the last time you actually, honestly had to work with graphs in a serious manner?
Even if you're lucky enough to never need to apply Graph Theory for what you do (which is actually the case with the majority of CS graduates), it's in the interest of everyone who wants to spend 4-6 years of their life dedicated to the study of computing and come out of the experience as a well-rounded professional. Now, you ask, what's so specially important that I should mind spending the next six months trying to wrap my head around these concepts and complete some of the most difficult coursework available? Here's just a few of the topics where this knowledge applies:
- PageRank: the algorithm behind Google. Indexes pages and content as graphs, with edges representing cross-references. There's probably several properties each node and edge has, but that's the basics.
- Pathfinding: Finding a path from one place to the other. Nodes represent forks in a road. Edges represent roads. Each edge is weighted with its distances or approximate traveling time. If a road is unidirectional, the edge is directed. After this, a sort of shortest-path algorithm or heuristic is applied ( Dijkstra's,Bellman-Ford, Floyd, etc). This is used everywhere, from industrial control systems, GPS units, optimization, etc.
- Optimal traffic distribution in a network: A bunch of data on a network (be it a computer network or anything that can be represented analogously) is given a source node and a destination node. Each node in the network represents a network device. Each edge represents a connection. Each edge has a weight, which determines the maximum amount of content it can carry (capacity). From there, you can apply the a series of flow algorithms to determine the optimal distribution of data you're sending between all the possible nodes it can traverse. Used for routing algorithms.
It should be noted that that's the naive version of the problem. In real life this gets tremendously complicated, as you have to deal with several flows, each vying for the same capacity. - Compiler optimization: A CPU has a limited number of registers where it can store its data, which is the quickest way to access it. Given a certain number of variables used in a program, you need to find a way to allocate variables in registers so as to maximize the use of the registers and minimize access to memory. This is solved through graph coloring, assigning each node/variable a "color", such that two adjacent nodes (variables used at the same time in a program) do not have the same color. This is an NP-complete problem, so you need to know that no optimal solution can be found in a reasonable time for large problems.
- Finding locations of distribution centers: say you need to supply a city with some service. You need to select certain places so that you can cover the whole city with an adequate supply of goods without using more centers than necessary by a certain margin. This relates to the Maximum Weight Independent Set problem, the Maximum Clique problem, vertex covering, and Maximum Independent Set problem.
- Chemical interactions: Atoms and their bindings in molecules are clearly modeled as graphs. For more complex models it's insufficient to represent a molecule as a graph, but it is a significant part of the modeling component.
- Scheduling: You have a conference center with a certain number of rooms, and different courses/presentations are assigned. Allocate all the presentations so that the schedules do not overlap, maximizing the usage of the conference rooms, and minimizing the duration of each conference by packing related courses as near as possible without overlap. This is actually an extremely difficult problem.
- Optimum distributions paths: You need to distribute the mail to every house in a town, minimizing the number of trucks you use and making sure the trucks take the necessary routes and no more. This is a classing problem with Eulerian and Hamiltonian cycles; Traveling Salesman or Chinese Postman problem.
- Project Management: A PERT graph is a type of directed graph used for project management. It's a fairly universal tool for determining the dependencies and times for the completion of a project. The Critical path algoritm is applied to determine the shortest possible time a project can be completed in while meeting all its dependencies.
- Program analysis: Several program analysis techniques used for determining the types of variables, compiler warning and errors, null-dereferencing bugs and variable optimization techniques can be utilized by describing a program as a series of graphs. One examples is the control flow graph. Although from computability theory you should know that the Halting Problem means that you can't determine if every program can terminate, in practice using the Invariant Theorem you can see if most sorts of problems terminate. How do you reference the life cycle of variables, control structures, and data dependencies? You guessed it!
A simple call graph - Package management and dependency management: In any serious operating system, packages have dependencies on each other, such as Firefox depending on GTK, glibc, etc. Nodes: packages: Edges: dependencies.
- Circuit board layout: The layout of circuits can be described as a graph where components are nodes and electrical lines are edges. Now, you can't draw arbitrary lines through a circuit board, and not all layouts are optimal. Ideally, you want a planar layout where you can draw the lines without them criss-crossing. This is the Graph Planarity problem. Metarecursively speaking, you also need to apply the planarity problem to draw graphs in in a sheet of paper in a way that can easily understoof by a human reader; a graphical representation of a graph is completely arbitrary and unrelated to the graph's actual structure.
And this is just the tip of the iceberg. Any mildly interesting computer problem can be described with graphs. Combine graph theory with linear programming and numerical methods and you've got Operations Research, one of the most interesting (and lucrative) branches of applied mathematics. Knowledge in graph theory is generally a deal-breaker when getting a job in software research or any sort of intersting position that involves solving difficult problems. It's essential for working in research postions at Google, IBM, and other technology companies. Knowledge in Operations Research and Combinatorial Opimization is essential for industrial processes of any kind, and it's helped to create and destroy entire companies (shipping and logistics companies, for example, depend on it completely to lower costs and operate efficiently). A lot of hard research in social interaction is modeled with graphs, etc.
This could go on and on, but suffice to say that these examples should convince you of just how relavant, current and important Graph Theory is for our professions, whether we work directly with it creating new technologies, or silently working for us in the background, day after day.
4 comments View more
